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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id AD3B4BBB7 for ; Wed, 26 Jul 2006 11:29:53 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k6Q9Trht015742 for ; Wed, 26 Jul 2006 11:29:53 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA31155 for ; Wed, 26 Jul 2006 11:29:52 +0200 (MET DST) Received: from mail-outfwd.lms.be (Kaiserslautern1.lms-gmbh.de [213.68.136.230]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k6Q9TnCn022592 for ; Wed, 26 Jul 2006 11:29:52 +0200 Received: from localhost (unknown [127.0.0.1]) by mail-outfwd.lms.be (Postfix) with ESMTP id E1DFE7F444 for ; Wed, 26 Jul 2006 11:49:44 +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 19283-07 for ; Wed, 26 Jul 2006 11:49:44 +0200 (CEST) Received: from kaiserslautern1.lmsintl.com (unknown [10.2.0.100]) by mail-kl.lmsintl.com (Postfix) with ESMTP id C34FEB6ECA for ; Wed, 26 Jul 2006 11:49:44 +0200 (CEST) Received: by kaiserslautern1.lmsintl.com with Internet Mail Service (5.5.2653.19) id <32PZTBH9>; Wed, 26 Jul 2006 11:29:30 +0200 Message-ID: <26EB47FDD566A7469FC862DAF373792F01711355@kaiserslautern1.lmsintl.com> From: Christoph Bauer To: caml-list@inria.fr Subject: AW: [Caml-list] generic Hashtbl.to_array Date: Wed, 26 Jul 2006 11:29:30 +0200 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain X-Virus-Scanned: by IT Services X-Miltered: at nez-perce with ID 44C73611.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 44C7360D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 hashtbl:01 hashtable:01 initialized:01 ocamlopt:01 unix:01 cmxa:01 cmx:01 iter:01 argv:01 100,000:98 17%:98 17%:98 18%:98 18%:98 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 autolearn=disabled version=3.0.3 > > 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 ()