[Caml-list] generic Hashtbl.to_array
Christoph Bauer
what is the best way to write Hashtbl.to_array?
Hashtbl.to_array : ('a, 'b) Hashtbl.t -> ('a * 'b) array
The simples idea has the problem, that you don't have
a initial value to make the result array:
let to_array t =
let a = Array.init make (Hashtbl.length t) ?init? in
ignore
(Hashtbl.fold
(fun k v i ->
a.(i) <- (k, v); i + 1)
t 0);
a
The best solution I found is
let to_array t =
let dummy = Array.init 0 (fun _ -> raise Not_found) in
fst
(Hashtbl.fold
(fun k v (a, i) ->
if i = 0 then
let a = Array.make (Hashtbl.length t) (k, v) in
(a, 0)
else (a.(i) <- (k, v); (a, i + 1)))
t (dummy, 0))
Is there a better one?
Thanks,
Christoph Bauer
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Erick Tryzelaar
> Hi,
>
> what is the best way to write Hashtbl.to_array?
>
> Hashtbl.to_array : ('a, 'b) Hashtbl.t -> ('a * 'b) array
>
> The simples idea has the problem, that you don't have
> a initial value to make the result array:
The easiest is to use a temporary list:
# let x = Hashtbl.create 2;;
val x : ('_a, '_b) Hashtbl.t = <abstr>
# Hashtbl.add x 5 3;;
- : unit = ()
# Hashtbl.add x 7 2;;
- : unit = ()
# Array.of_list (Hashtbl.fold (fun a b c -> (a, b) :: c) x []);;
- : (int * int) array = [|(7, 2); (5, 3)|]
You could also try inverting the Hashtbl fold into an iterator+closure
and pass the closure into the Array.init function, but I'm not sure how
complicated/efficient that would be.
I suppose it just depends on how efficient you need it to be. If it's
just some simple stuff, I'd just use the intermediary list.
-e
Christoph Bauer
>
> You could also try inverting the Hashtbl fold into an
> iterator+closure and pass the closure into the Array.init
> function, but I'm not sure how complicated/efficient that would be.
Something like:
let to_array_2 t =
let init _ = fun () -> raise Not_found in
let a = Array.init (Hashtbl.length t) init in
ignore
(Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
Array.map (fun f -> f ()) a
>
> I suppose it just depends on how efficient you need it to be.
> If it's just some simple stuff, I'd just use the intermediary list.
benchmarking shows, that all three approaches are similar
with respect to efficiency.
Regards,
Christoph Bauer
Benchmark:
Throughputs for to_array_1, to_array_2, to_array_3, each running 5 times for
at least 1 CPU seconds:
to_array_1: 1 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560)
1 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560)
2 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560)
1 WALL ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 486.96/s (n=560)
1 WALL ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 486.96/s (n=560)
to_array_2: 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
2 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
to_array_3: 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
2 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516)
Rate to_array_2 to_array_3 to_array_1
to_array_2 482/s -- [-0%] -1%
to_array_3 482+-0/s [0%] -- -1%
to_array_1 490+-2/s 2% 2% --
open Benchmark
let to_array_1 t =
let dummy = Array.init 0 (fun _ -> raise Not_found) in
fst
(Hashtbl.fold
(fun k v (a, i) ->
if i = 0 then
let a = Array.make (Hashtbl.length t) (k, v) in
(a, 0)
else (a.(i) <- (k, v); (a, i + 1)))
t (dummy, 0))
let to_array_2 t =
let init _ = fun () -> raise Not_found in
let a = Array.init (Hashtbl.length t) init in
ignore
(Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
Array.map (fun f -> f ()) a
let to_array_3 t =
Array.of_list (Hashtbl.fold (fun a b c -> (a, b) :: c) t [])
let h () =
let h = Hashtbl.create 100000 in
for i = 0 to (Hashtbl.length h) do
Hashtbl.add h (Random.int max_int) (Random.int max_int);
done;
h
let main () =
let h = h () in
let res = throughputN ~repeat:5 1
[("to_array_1", to_array_1, h);
("to_array_2", to_array_2, h);
("to_array_3", to_array_3, h); ] in
tabulate res
let () = main ()
skaller
> Hi,
>
> >
> > You could also try inverting the Hashtbl fold into an
> > iterator+closure and pass the closure into the Array.init
> > function, but I'm not sure how complicated/efficient that would be.
>
> Something like:
>
> let to_array_2 t =
> let init _ = fun () -> raise Not_found in
> let a = Array.init (Hashtbl.length t) init in
> ignore
> (Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
> Array.map (fun f -> f ()) a
ugg .. really need a variable length array here. However the most
efficient solution is:
(1) Use Hashtbl.iter to capture just one value out of the
Hashtble:
let get1 h =
Hashtbl.iter (fun k v -> raise XSome (k,v)) h;
raise XNone
in
(2) Initialise the array with it:
let a = try get1 h with
| XSome x -> Array.init (Hashtbl.length h) x
| XNone -> raise Not_found (* zero length array? *)
in
(3) Now use Hashtbl.fold or iter to initialise the array.
This 'costs' a write barrier but there is no additional
data structure required, and the whole thing is quite safe.
This leaves open the problem of making a zero length array
of the correct type.. not a problem if you're writing
the code inside the Hashtbl module, but trickier if you're
doing it outside.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
Damien Doligez
On 2006-07-25, at 10:29, Christoph Bauer wrote:
> The simples idea has the problem, that you don't have
> a initial value to make the result array:
You can get it from the hash table itself:
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
;;
-- Damien
Christoph Bauer
> 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"]
Rate to_array_4 to_array_3 to_array_1b to_array_2
to_array_1
to_array_4 407+-0/s -- -16% -16% -17%
-17%
to_array_3 486+-2/s 19% -- [-0%] [-1%]
-1%
to_array_1b 487+-0/s 20% [0%] -- [-0%]
-1%
to_array_2 489+-2/s 20% [1%] [0%] --
-1%
to_array_1 491+-0/s 21% 1% 1% 1%
--
from http://ocaml-benchmark.sourceforge.net/doc/Benchmark.html
Benchmark.tablulate results prints a comparison table for a list of results
obtained by Benchmark.latencyN or Benchmark.throughputN with each function
compared to all the others. The table is of the type
Rate name1 name2 ... OR s/iter name1 name2 ...
name1 #/s -- r12 name1 # -- r12
name2 #/s r21 -- name2 # r21 --
... ...
where name1, name2,... are the labels of the tests sorted from slowest to
fastest and rij says how much namei is faster (or slower if < 0) than namej
(technically it is equal to (ri - rj) expressed in percents of rj where ri
and rj are the rates of namei and namej respectively).
If several results are associated to a given name, they are used to compute
a Student's statistic to check whether the rates are significantly
different. If ri and rj are not believed to be different, rij will be
printed between brackets.
(* compile with
ocamlopt -o to_array -I benchmark-0.7 unix.cmxa benchmark-0.7/benchmark.cmx
to_array.ml
*)
open Benchmark
let to_array_1 t =
let dummy = Array.init 0 (fun _ -> raise Not_found) in
fst
(Hashtbl.fold
(fun k v (a, i) ->
if i = 0 then
let a = Array.make (Hashtbl.length t) (k, v) in
(a, 0)
else (a.(i) <- (k, v); (a, i + 1)))
t (dummy, 0))
let to_array_2 t =
let init _ = fun () -> raise Not_found in
let a = Array.init (Hashtbl.length t) init in
ignore
(Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
Array.map (fun f -> f ()) a
let to_array_3 t =
Array.of_list (Hashtbl.fold (fun a b c -> (a, b) :: c) t [])
let to_array_1b t =
let a = ref (Array.init 0 (fun _ -> raise Not_found)) in
ignore
(Hashtbl.fold
(fun k v i ->
if i = 0 then
(a := Array.make (Hashtbl.length t) (k, v);
i)
else
((!a).(i) <- (k, v); i + 1))
t 0);
!a
let to_array_4 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
let h () =
let h = Hashtbl.create 100000 in
for i = 0 to (Hashtbl.length h) do
Hashtbl.add h (Random.int max_int) (Random.int max_int);
done;
h
let main () =
let h = h () in
let res = throughputN ~repeat:5 1
[("to_array_1", to_array_1, h);
("to_array_1b", to_array_1b, h);
("to_array_2", to_array_2, h);
("to_array_3", to_array_3, h);
("to_array_4", to_array_4, h); ] in
tabulate res
let () = main ()
Christoph Bauer
> let to_array_4 t =
> let init = ref None in
> begin try Hashtbl.iter (fun k v -> init := Some (k,v);
> raise Exit) t
My guess: hashtbl has to loop over the first empty buckets.
And this eats the cpu cycles.
> 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
Regards,
Christoph Bauer
skaller
> 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
_______________________________________________
ol...@pobox.com
I wonder about the following solution. At least it traverses the
hashtable exactly once (and it does not ignore the result of the
fold).
let to_array9 t =
let Some (a,_) =
Hashtbl.fold (fun k v seed ->
match seed with
Some (a,i) -> a.(i) <- (k,v); Some (a,i+1)
| None -> let a = Array.make (Hashtbl.length t) (k,v) in
Some (a,1))
t None
in a
;;
Christoph Bauer
> let to_array9 t =
> let Some (a,_) =
> Hashtbl.fold (fun k v seed ->
> match seed with
> Some (a,i) -> a.(i) <- (k,v); Some (a,i+1)
> | None -> let a = Array.make (Hashtbl.length t) (k,v) in
> Some (a,1))
> t None
> in a
> ;;
I called this to_array_1c. The hashtable is initialized with n * 100,000
elements, where n is n = 1, 2, 4, 8. Here the results. n = 8 is a good
summary.
n = 1
Rate to_array_4 to_array_1c to_array_3 to_array_2
to_array_1b to_array_5 to_array_1
to_array_4 413+-1/s -- -17% -17% -18%
-18% -19% -19%
to_array_1c 498+-2/s 21% -- [-0%] -1%
-1% -2% -3%
to_array_3 500+-3/s 21% [0%] -- [-0%]
[-0%] -2% -2%
to_array_2 502+-2/s 21% 1% [0%] --
[-0%] -1% -2%
to_array_1b 502+-2/s 21% 1% [0%] [0%]
-- -1% -2%
to_array_5 509+-2/s 23% 2% 2% 1%
1% -- [-1%]
to_array_1 512+-2/s 24% 3% 2% 2%
2% [1%] --
n = 2
Rate to_array_4 to_array_2 to_array_3 to_array_1c to_array_1b
to_array_1 to_array_5
to_array_4 203+-1/s -- -7% -7% -8%
-8% -8% -8%
to_array_2 218+-1/s 8% -- [-0%] [-0%]
[-0%] [-1%] -1%
to_array_3 218+-1/s 8% [0%] -- [-0%]
[-0%] [-1%] -1%
to_array_1c 219+-1/s 8% [0%] [0%] --
[-0%] [-0%] [-1%]
to_array_1b 219+-1/s 8% [0%] [0%] [0%]
-- [-0%] -1%
to_array_1 220+-1/s 8% [1%] [1%] [0%]
[0%] -- [-1%]
to_array_5 221+-1/s 9% 1% 1% [1%]
1% [1%] --
n = 4
Rate to_array_4 to_array_2 to_array_1c to_array_1b
to_array_1 to_array_3 to_array_5
to_array_4 64.7+-0.3/s -- -34% -34% -35%
-35% -35% -35%
to_array_2 98.4+-0.6/s 52% -- [-0%] [-1%]
[-1%] -1% -1%
to_array_1c 98.7+-0.4/s 52% [0%] -- [-0%]
[-1%] -1% -1%
to_array_1b 99.0+-0.0/s 53% [1%] [0%] --
[-0%] -1% -1%
to_array_1 99.4+-0.7/s 54% [1%] [1%] [0%]
-- [-0%] [-0%]
to_array_3 99.6+-0.4/s 54% 1% 1% 1%
[0%] -- [-0%]
to_array_5 99.8+-0.4/s 54% 1% 1% 1%
[0%] [0%] --
n = 8
Rate to_array_4 to_array_5 to_array_3 to_array_2
to_array_1 to_array_1b to_array_1c
to_array_4 38.8+-0.2/s -- -20% -20% -21%
-21% -21% -21%
to_array_5 48.7+-0.3/s 26% -- [-0%] [-0%]
[-0%] [-0%] [-0%]
to_array_3 48.7+-0.2/s 26% [0%] -- [-0%]
[-0%] [-0%] [-0%]
to_array_2 48.8+-0.2/s 26% [0%] [0%] --
[-0%] [-0%] [-0%]
to_array_1 48.8+-0.2/s 26% [0%] [0%] [0%]
-- [-0%] [-0%]
to_array_1b 48.9+-0.2/s 26% [0%] [0%] [0%]
[0%] -- [-0%]
to_array_1c 48.9+-0.2/s 26% [0%] [0%] [0%]
[0%] [0%] --
(* compile with
ocamlopt -o to_array -I benchmark-0.7 unix.cmxa benchmark-0.7/benchmark.cmx
to_array.ml
*)
open Benchmark
let to_array_1 t =
let dummy = Array.init 0 (fun _ -> raise Not_found) in
fst
(Hashtbl.fold
(fun k v (a, i) ->
if i = 0 then
let a = Array.make (Hashtbl.length t) (k, v) in
(a, 1)
else (a.(i) <- (k, v); (a, i + 1)))
t (dummy, 0))
let to_array_2 t =
let init _ = fun () -> raise Not_found in
let a = Array.init (Hashtbl.length t) init in
ignore
(Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
Array.map (fun f -> f ()) a
let to_array_3 t =
Array.of_list (Hashtbl.fold (fun a b c -> (a, b) :: c) t [])
let to_array_1b t =
let a = ref (Array.init 0 (fun _ -> raise Not_found)) in
ignore
(Hashtbl.fold
(fun k v i ->
if i = 0 then
(a := Array.make (Hashtbl.length t) (k, v);
i)
else
((!a).(i) <- (k, v); i + 1))
t 0);
!a
let to_array_4 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
let to_array_5 =
let init = Obj.magic 0 in
fun t ->
let a = Array.make (Hashtbl.length t) init in
ignore
(Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0) ;
a
let to_array_1c t =
let r =
Hashtbl.fold (fun k v seed ->
match seed with
Some (a,i) -> a.(i) <- (k,v); Some (a,i+1)
| None -> let a = Array.make (Hashtbl.length t) (k,v)
in
Some (a,1))
t None
in
match r with
None -> Array.init 0 (fun _ -> raise Not_found)
| Some (a, _) -> a
let h n =
let h = Hashtbl.create (n*100000) in
for i = 0 to (Hashtbl.length h) do
Hashtbl.replace h (Random.int max_int) (Random.int max_int);
done;
h
let main () =
let n = try int_of_string Sys.argv.(1) with _ -> 1 in
let h = h n in
let res = throughputN ~repeat:5 1
[("to_array_1", to_array_1, h);
("to_array_1b", to_array_1b, h);
("to_array_1c", to_array_1c, h);
("to_array_2", to_array_2, h);
("to_array_3", to_array_3, h);
("to_array_4", to_array_4, h);
("to_array_5", to_array_5, h);
] in
tabulate res
let () = main ()
_______________________________________________
Damien Doligez
On 2006-07-25, at 14:44, Christoph Bauer wrote:
>>
>> let to_array_4 t =
>> let init = ref None in
>> begin try Hashtbl.iter (fun k v -> init := Some (k,v);
>> raise Exit) t
>
> My guess: hashtbl has to loop over the first empty buckets.
> And this eats the cpu cycles.
I guess that's correct, since you're doing your tests with a
100000-sized hash table that contains only one entry. I wouldn't
call that a typical case.
-- Damien
Damien Doligez
On 2006-07-26, at 04:16, ol...@pobox.com wrote:
> let to_array9 t =
> let Some (a,_) =
> Hashtbl.fold (fun k v seed ->
> match seed with
> Some (a,i) -> a.(i) <- (k,v); Some (a,i+1)
> | None -> let a = Array.make (Hashtbl.length t) (k,v) in
> Some (a,1))
> t None
> in a
> ;;
It fails whenever the hash table is empty, and the compiler
warns you about it. Replace your "let Some (a,_) = ..."
with a pattern-matching and you have a nice solution.
-- Damien
Stéphane Glondu
Tom a écrit :
> The dirtiest solution:
>
> let to_array t =
> let a = Array.make (Hashtbl.length t) (Obj.magic 0) in
> ignore
> (Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0) ;
> a
What about:
let to_array h =
let res = ref [||] in
let rec assign = ref (fun i x ->
res := Array.make (Hashtbl.length h) x;
!res.(i) <- x;
assign := Array.set !res) in
ignore (Hashtbl.fold (fun k v i -> !assign i (k, v); i+1) h 0);
!res;;
Sorry if it has already been proposed (but I have not seen it).
--
Stéphane Glondu
Stéphane Glondu
Tom a écrit :
> I also corrected my implementation:
>
> let mgc = Obj.magic 0 <<< So that the function is executed only once.
Does this provide any benefit? It seems to me that Obj.magic is the
(inlined) identity (so basically Obj.magic 0 is compiled directly into
the integer 0).
--
Stéphane