Re: [Caml-list] Hashtbl performance

[Xavier Leroy <Xavier.Leroy@inria.fr>]

Fabrice Le Fessant <Fabrice.Le_fessant@inria.fr>:

> Thus, you should consider using your own hash function, probably only
> considering the ints in the list and its length. Then, use the functor
> in the Hashtbl module.

On 07/28/2011 02:25 PM, barnier@recherche.enac.fr wrote:

> You could also use the hash_param : int -> int -> 'a -> int
> function in the functor which allows to specify the number
> of nodes traversed to compute the key :

Both Fabrice's and Nicolas's suggestions are excellent.

Let me just add that this problem with lists as hashtable keys is one
of the known issues with OCaml's current generic hash function: the
other is that the mixing functions used are simplistic and exhibit
some statistical bias, even for strings.

The SVN trunk for OCaml contains a complete reimplementation of the
generic hash function that addresses both issues: lists and other
complex keys are traversed breadth-first in a more cautious manner
than before, and the mixing functions are based on MurmurHash 3, which
exhibits very good statistical properties.  All this should go in the
next major release 3.13.  So, everyone with an interest in efficient
hash tables is welcome to try the trunk sources and let me know of any
problems encountered.

- Xavier Leroy