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

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

[Chris Hecker]

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?

type ('a, 'b) t =
  { mutable max_len: int;                     (* max length of a bucket *)
    mutable data: ('a, 'b) bucketlist array } (* the buckets *)
and ('a, 'b) bucketlist =
    Empty
  | Cons of 'a * 'b * ('a, 'b) bucketlist

instead of 

type ('a, 'b) t =
  { mutable max_len: int;                     (* max length of a bucket *)
    mutable data: ('a * 'b) list array }      (* the buckets *)

Chris

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

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

[Fergus Henderson]

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

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

[Jean-Christophe Filliatre]

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

(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.)

-- 
Jean-Christophe Filliatre
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr
-------------------
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

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

[Fergus Henderson]

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

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

[Xavier Leroy]

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

Yes, it does.  Still, you save two stores at allocation time with the
flat representation -- in addition to the more significant time
savings at access time (one fewer indirection).

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

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

[Charles Martin]

At 07:42 PM 7/10/01 +1000, Fergus Henderson wrote:
>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?

In my experience, yes, every time: asmcomp/comballoc.ml



__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail
http://personal.mail.yahoo.com/
-------------------
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