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 F254EBBB7 for ; Tue, 25 Jul 2006 14:01:04 +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 k6PC14OH021971 for ; Tue, 25 Jul 2006 14:01:04 +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 OAA14729 for ; Tue, 25 Jul 2006 14:01:04 +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 k6PC131R001388; Tue, 25 Jul 2006 14:01:03 +0200 Received: from localhost (unknown [127.0.0.1]) by mail-outfwd.lms.be (Postfix) with ESMTP id D190E7F43D; Tue, 25 Jul 2006 14:20:46 +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 25986-08; Tue, 25 Jul 2006 14:20:46 +0200 (CEST) Received: from kaiserslautern1.lmsintl.com (unknown [10.2.0.100]) by mail-kl.lmsintl.com (Postfix) with ESMTP id B385FB6EC6; Tue, 25 Jul 2006 14:20:46 +0200 (CEST) Received: by kaiserslautern1.lmsintl.com with Internet Mail Service (5.5.2653.19) id <32PZS681>; Tue, 25 Jul 2006 14:00:48 +0200 Message-ID: <26EB47FDD566A7469FC862DAF373792F017112A1@kaiserslautern1.lmsintl.com> From: Christoph Bauer To: Damien Doligez , caml-list Subject: Re: [Caml-list] generic Hashtbl.to_array Date: Tue, 25 Jul 2006 14:00:47 +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 concorde with ID 44C60800.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 44C607FF.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 hashtbl:01 iter:01 iter:01 ocamlopt:01 unix:01 cmxa:01 cmx:01 16%:98 16%:98 17%:98 17%:98 19%:98 statistic:98 sourceforge: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 autolearn=disabled version=3.0.3 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"] 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 ()