Version française
Home     About     Download     Resources     Contact us    
Browse thread
AW: [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: Christoph Bauer <christoph.bauer@l...>
Subject: AW: [Caml-list] generic Hashtbl.to_array
> 
> 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 ()