Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] why does hashtbl not use lists?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] why does hashtbl not use lists?

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