Re: [Caml-list] why does hashtbl not use lists?

[Fergus Henderson <fjh@cs.mu.OZ.AU>]

On 10-Jul-2001, Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> wrote:
> 
> Chris Hecker writes:
>  > 
>  > Why does hashtbl.ml (from  the standard library) use the bucketlist
>  > variant instead of just the built in lists with tuples? Is there an
>  > efficiency thing going on here?
> 
> Yes, it saves 33% of memory. Indeed, a list of tuples will give blocks
> like this:
> 
>      ______
>      |X|.|.|......>
>      ---.--     _______
>         ......> |X|a|b|
>                 -------
> 
> that is,  6 words for each  binding, whereas the  bucketlist type will
> give blocks like this:
> 
>      _________
>      |X|a|b|.|....>
>      ---------
> 
> that is, 4 words. (X stands for  the block header, which is 1 word and
> dots stand for pointers; sory for the ugly ASCII drawing).

No doubt you are right about it being 6 words vs 4 words,
rather than 4 words vs 3 words, as I said in my earlier mail;
I didn't recall that Ocaml used a header word here.

> (Beside saving  memory, you  also save time,  by allocating  one block
> instead of two  and also when destructuring the  block to look inside,
> since depth is 1 instead of 2.)

I thought about mentioning the time saving from the reduced number of
allocations, but then I wondered whether it would really save any time.
If you have a compacting garbage collector, as I'm pretty sure Ocaml does,
and a good compiler, then the compiler would be able to combine the two
allocations into a single one.  Does Ocamlopt do that?

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------------
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