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 D799EBBB7 for ; Tue, 25 Jul 2006 17:34:49 +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 k6PFYmCO032378 for ; Tue, 25 Jul 2006 17:34:48 +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 RAA18367 for ; Tue, 25 Jul 2006 17:34:48 +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 k6PFYlXZ032375 for ; Tue, 25 Jul 2006 17:34:47 +0200 Received: from localhost (unknown [127.0.0.1]) by mail-outfwd.lms.be (Postfix) with ESMTP id 109DB7F441; Tue, 25 Jul 2006 17:54:48 +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 32502-05; Tue, 25 Jul 2006 17:54:47 +0200 (CEST) Received: from kaiserslautern1.lmsintl.com (unknown [10.2.0.100]) by mail-kl.lmsintl.com (Postfix) with ESMTP id E08D2B6EC8; Tue, 25 Jul 2006 17:54:47 +0200 (CEST) Received: by kaiserslautern1.lmsintl.com with Internet Mail Service (5.5.2653.19) id <32PZS8AM>; Tue, 25 Jul 2006 17:34:46 +0200 Message-ID: <26EB47FDD566A7469FC862DAF373792F017112F3@kaiserslautern1.lmsintl.com> From: Christoph Bauer To: Tom , caml-list Subject: AW: [Caml-list] generic Hashtbl.to_array Date: Tue, 25 Jul 2006 17:34:36 +0200 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C6AFFF.D59D0CC0" X-Virus-Scanned: by IT Services X-j-chkmail-Score: MSGID : 44C63A18.000 on concorde : j-chkmail score : XX : 5/20 0 X-j-chkmail-Score: MSGID : 44C63A17.000 on concorde : j-chkmail score : XX : 5/20 0 X-Miltered: at concorde with ID 44C63A18.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 44C63A17.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 hashtbl:01 ocamlopt:01 unix:01 cmxa:01 cmx:01 iter:01 ocamlopt:01 unix:01 cmxa:01 cmx:01 iter:01 auftrag:98 gesendet:98 dienstag: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,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_01C6AFFF.D59D0CC0 Content-Type: text/plain _____ Von: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] Im Auftrag von Tom Gesendet: Dienstag, 25. Juli 2006 17:21 An: caml-list Betreff: Re: [Caml-list] generic Hashtbl.to_array The dirtiest solution: let to_array t = let a = Array.make (Hashtbl.length t) (Obj.magic 0) in ignore (Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0) ; a This is to_array_5 in the table. Dirty and not the fastest. Don't know why. Maybe a in to_array_1 is keept in a register. Rate to_array_4 to_array_3 to_array_5 to_array_1b to_array_2 to_array_1 to_array_4 418+-0/s -- -16% -16% -16% -17% -18% to_array_3 497+-3/s 19% -- [-0%] [-0%] -1% -3% to_array_5 499+-2/s 19% [0%] -- [-0%] -1% -2% to_array_1b 499+-2/s 19% [0%] [0%] -- -1% -2% to_array_2 504+-2/s 21% 1% 1% 1% -- -1% to_array_1 511+-2/s 22% 3% 2% 2% 1% -- Christoph Bauer (* 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 to_array_5 t = let a = Array.make (Hashtbl.length t) (Obj.magic 0) 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_5", to_array_5, h); ("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 () ------_=_NextPart_001_01C6AFFF.D59D0CC0 Content-Type: text/html
 

Von: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] Im Auftrag von Tom
Gesendet: Dienstag, 25. Juli 2006 17:21
An: caml-list
Betreff: Re: [Caml-list] generic Hashtbl.to_array

The dirtiest solution:

let to_array t =
 let a =  Array.make (Hashtbl.length t) (Obj.magic 0)  in
   ignore
     (Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0) ;
     a  
 
 
 
This is to_array_5 in the table. Dirty and not the fastest. Don't know why.
Maybe a in to_array_1 is keept in a register.
 
 
 
          Rate    to_array_4 to_array_3 to_array_5 to_array_1b to_array_2 to_array_1
 to_array_4 418+-0/s         --       -16%       -16%        -16%       -17%       -18%
 to_array_3 497+-3/s        19%         --      [-0%]       [-0%]        -1%        -3%
 to_array_5 499+-2/s        19%       [0%]         --       [-0%]        -1%        -2%
to_array_1b 499+-2/s        19%       [0%]       [0%]          --        -1%        -2%
 to_array_2 504+-2/s        21%         1%         1%          1%         --        -1%
 to_array_1 511+-2/s        22%         3%         2%          2%         1%         --
 
Christoph Bauer
 
(* 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 to_array_5 t =
 let a =  Array.make (Hashtbl.length t) (Obj.magic 0)  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_5", to_array_5, h);
          ("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 ()

 
------_=_NextPart_001_01C6AFFF.D59D0CC0--