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 36E8CBBB7 for ; Tue, 25 Jul 2006 12:20:01 +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 k6PAK0rM019136 for ; Tue, 25 Jul 2006 12:20:00 +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 MAA13245 for ; Tue, 25 Jul 2006 12:20:00 +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 k6PAJxRh003764 for ; Tue, 25 Jul 2006 12:19:59 +0200 Received: from localhost (unknown [127.0.0.1]) by mail-outfwd.lms.be (Postfix) with ESMTP id 91AEC7F43D; Tue, 25 Jul 2006 12:39:56 +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 26585-04; Tue, 25 Jul 2006 12:39:56 +0200 (CEST) Received: from kaiserslautern1.lmsintl.com (unknown [10.2.0.100]) by mail-kl.lmsintl.com (Postfix) with ESMTP id 805F3B6EC7; Tue, 25 Jul 2006 12:39:56 +0200 (CEST) Received: by kaiserslautern1.lmsintl.com with Internet Mail Service (5.5.2653.19) id <32PZS6N5>; Tue, 25 Jul 2006 12:19:59 +0200 Message-ID: <26EB47FDD566A7469FC862DAF373792F0171128D@kaiserslautern1.lmsintl.com> From: Christoph Bauer To: Erick Tryzelaar , Christoph Bauer Cc: caml-list Subject: AW: [Caml-list] generic Hashtbl.to_array Date: Tue, 25 Jul 2006 12:19:52 +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 44C5F050.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 44C5F04F.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 inverting:01 hashtbl:01 iterator:01 usr:01 usr:01 caml-list:01 int:01 int:01 closure:01 closure:01 benchmark:02 benchmark:02 sys:03 sys:03 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, > > You could also try inverting the Hashtbl fold into an > iterator+closure and pass the closure into the Array.init > function, but I'm not sure how complicated/efficient that would be. Something like: 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 > > I suppose it just depends on how efficient you need it to be. > If it's just some simple stuff, I'd just use the intermediary list. benchmarking shows, that all three approaches are similar with respect to efficiency. Regards, Christoph Bauer Benchmark: Throughputs for to_array_1, to_array_2, to_array_3, each running 5 times for at least 1 CPU seconds: to_array_1: 1 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560) 1 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560) 2 WALL ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 491.23/s (n=560) 1 WALL ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 486.96/s (n=560) 1 WALL ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 486.96/s (n=560) to_array_2: 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 2 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) to_array_3: 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 1 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) 2 WALL ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 482.24/s (n=516) Rate to_array_2 to_array_3 to_array_1 to_array_2 482/s -- [-0%] -1% to_array_3 482+-0/s [0%] -- -1% to_array_1 490+-2/s 2% 2% -- 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 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_2", to_array_2, h); ("to_array_3", to_array_3, h); ] in tabulate res let () = main ()