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

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

On 10-Jul-2001, Chris Hecker <checker@d6.com> wrote:
> 
> 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.  I didn't write the code, but I'm sure that's the reason.
A list of pairs will use two two-word cells per list element,
whereas a bucketlist will use one three-word cell; as well as reducing
the amount of memory allocated, it also avoids an indirection.

P.S. We happen to use the same kind of trick in the Mercury standard library,
for lists of tokens in the Mercury lexer:

   % This "fat list" representation is more efficient than a list of pairs.
   :- type token_list      --->    token_cons(token, token_context, token_list)
                           ;       token_nil.

But note that we at least document why we do it! ;-)

-- 
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