Re: [Caml-list] Specialized dictionaries

["Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>]

Mon, 5 Nov 2001 11:19:56 +0100, Xavier Leroy <xavier.leroy@inria.fr> pisze:

> No, no need to copy anything, just unleash the power of functors!
> 
> module IntHashtbl = Hashtbl.make(struct type t = int
>                                         let equal = (==)
>                                         let hash x = x land 0x3FFFFFFF
>                                  end)

Ok, I tried:

 Implementation                  | Test1 | Test2
---------------------------------+-------+-------
 Hashtbl.t                       | 7.40s | 6.45s
 Hashtbl.Make(...)               | 3.62s | 5.35s
 hashtbl.ml specialized for ints | 2.37s | 5.00s

Test1 is a small program which does nothing but dictionary lookups.
Test2 is a real program where I use dictionaries.

It happenens that

    let equal = (==)

    let equal (x : int) (y : int) = x = y

are fast, where

    let equal x y = x = y
      (* module constrained by Hashtbl.HashedType with type t = int *)

    let equal : int -> int -> bool = (=)

are slow. The compiler doesn't insert the specialized equality version
if it's not immediately applied, or if its type is constrained only
by module signature.

I'm going to use the functorial version: 7% loss of performance
wrt. the specialized version is acceptable.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr