AW: [Caml-list] generic Hashtbl.to_array

[Christoph Bauer <christoph.bauer@lms-gmbh.de>]

[-- Attachment #1: Type: text/plain, Size: 4182 bytes --]

 


  _____  

Von: Tom [mailto:tom.primozic@gmail.com] 
Gesendet: Mittwoch, 26. Juli 2006 15:53
An: Christoph Bauer
Betreff: Re: [Caml-list] generic Hashtbl.to_array


Once again...

I'm sorry to say that, but I believe that you results are flawed...


Upon inspecting your code with Toploop, I found out some flaws... 


let h n =
 let m = n * 100000 in
 let h = Hashtbl.create m in

   for i = 0 to m - 1 do       (* <<< not Hashtbl.length h, as it returns 0
for ampty hashtable *)
     Hashtbl.replace h (Random.int <http://random.int/>  max_int) (
Random.int <http://random.int/>  max_int);
   done;
   h


 
 

 
thanks, sorry for this stupid bug.  to_array_5 is now the clear winner.
 
Christoph Bauer
 
 n=8
             Rate      to_array_2 to_array_3 to_array_1c to_array_1
to_array_4 to_array_1b to_array_5
 to_array_2 34.6+-0.4/s         --       -50%        -71%       -72%
-74%        -74%       -79%
 to_array_3 68.8+-0.6/s        99%         --        -42%       -45%
-49%        -49%       -58%
to_array_1c  118+-  2/s       241%        71%          --        -6%
-12%        -13%       -27%
 to_array_1  126+-  0/s       264%        83%          7%         --
-6%         -7%       -22%
 to_array_4  134+-  2/s       287%        95%         14%         6%
--       [-1%]       -17%
to_array_1b  135+-  1/s       290%        96%         15%         7%
[1%]          --       -17%
 to_array_5  162+- 10/s       369%       136%         37%        29%
21%         20%         --
 
 
 (* 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);
               1)
            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 m = n * 1000 in
  let h = Hashtbl.create m in
    for i = 0 to m - 1 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 () 


[-- Attachment #2: Type: text/html, Size: 12793 bytes --]