From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 02CA4BBB7 for ; Wed, 26 Jul 2006 16:41:52 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k6QEfoc4018317 for ; Wed, 26 Jul 2006 16:41:51 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA02007 for ; Wed, 26 Jul 2006 16:41:50 +0200 (MET DST) Received: from mail-outfwd.lms.be (Kaiserslautern1.lms-gmbh.de [213.68.136.230]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k6QEfnkV032218 for ; Wed, 26 Jul 2006 16:41:49 +0200 Received: from localhost (unknown [127.0.0.1]) by mail-outfwd.lms.be (Postfix) with ESMTP id C18087F418 for ; Wed, 26 Jul 2006 17:01:52 +0200 (CEST) Received: from mail-kl.lmsintl.com ([127.0.0.1]) by localhost (kl-ftp [127.0.0.1]) (amavisd-new, port 20024) with ESMTP id 24065-08 for ; Wed, 26 Jul 2006 17:01:52 +0200 (CEST) Received: from kaiserslautern1.lmsintl.com (unknown [10.2.0.100]) by mail-kl.lmsintl.com (Postfix) with ESMTP id 9CB35B6EC5 for ; Wed, 26 Jul 2006 17:01:52 +0200 (CEST) Received: by kaiserslautern1.lmsintl.com with Internet Mail Service (5.5.2653.19) id <32PZTDBP>; Wed, 26 Jul 2006 16:41:34 +0200 Message-ID: <26EB47FDD566A7469FC862DAF373792F017113B7@kaiserslautern1.lmsintl.com> From: Christoph Bauer To: caml-list@inria.fr Subject: AW: [Caml-list] generic Hashtbl.to_array Date: Wed, 26 Jul 2006 16:41:33 +0200 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C6B0C1.9722F728" X-Virus-Scanned: by IT Services X-j-chkmail-Score: MSGID : 44C77F2F.000 on concorde : j-chkmail score : XX : 5/20 0 X-j-chkmail-Score: MSGID : 44C77F2D.001 on nez-perce : j-chkmail score : XX : 5/20 0 X-Miltered: at concorde with ID 44C77F2F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 44C77F2D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 hashtbl:01 toploop:01 hashtable:01 bug:01 ocamlopt:01 unix:01 cmxa:01 cmx:01 iter:01 argv:01 toploop:01 hashtable:01 bug:01 ocamlopt:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO,HTML_MESSAGE autolearn=disabled version=3.0.3 This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. ------_=_NextPart_001_01C6B0C1.9722F728 Content-Type: text/plain _____ 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 max_int) ( 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 () ------_=_NextPart_001_01C6B0C1.9722F728 Content-Type: text/html
 

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 max_int) ( 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 ()
------_=_NextPart_001_01C6B0C1.9722F728--