Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: [Caml-list] generic Hashtbl.to_array
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] generic Hashtbl.to_array
On Tue, 2006-07-25 at 14:00 +0200, Christoph Bauer wrote:
> Hi,
> 
> > let to_array t =
> >    let init = ref None in
> >    begin try Hashtbl.iter (fun k v -> init := Some (k,v); 
> > raise Exit) t
> >    with Exit -> ()
> >    end;
> >    match !init with
> >    | None -> [| |]
> >    | Some i ->
> >      let a = Array.make (Hashtbl.length t) i in
> >      ignore (Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0);
> >      a
> > ;;
> 
> it's curious, but this solution is slower than the others!
> 
> [skaller's solution seems to be the same, so I
> include only this one in the "benchmark"]

This is not entirely surprising, since Ocaml wastes time 
first initialising the array.. and then assigning the same 
cells new values, recycling the same store through the 
cache twice. However there is no need for a secondary
data structure, which may delay hitting limits of the
next level of caching (for example VM paging disk).

I see in your tests the number of elements is 100,000.
It would be interesting to increase this in a series
of tests to see if the performance tradeoffs change:
cache effects would predict a 'kink' when you hit
cache boundaries?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net