Jon Harrop wrote:
> The Map implementation in the OCaml stdlib is also quite inefficient. I did a 
> little benchmark once and discovered that Maps actually waste more space than 
> Hashtbls.

I find it unfair to compare an imperative and a persistence data
structure for performances. Of course you are going to use some extra
space if you need to keep old versions of the data stuctures valid.
But you are sharing *a lot* among the various versions. So if you are
manipulating several sets/maps with common ancestors at the same time,
you are saving memory w.r.t. other data structures such as hash tables.

Of course, if you are using a single data structure, in a linear way,
then yes a hash table is probably more efficient (provided you have a
good hash function, which is not always easy to achieve).

Regarding implementation of ocaml maps, I wouldn't say that it is
inefficient: I did my own benchmarls (on sets, but this is the same
code) and found that ocaml AVLs are really efficient, on the contrary.
It usually beats other implementations (e.g. red-black trees from the
SML stdlib), or even specialized structures such as Patricia trees (when
keys are integers) on some operations.

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/