From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA21114; Tue, 10 Jul 2001 11:43:09 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA21108 for ; Tue, 10 Jul 2001 11:43:08 +0200 (MET DST) Received: from mumnunah.cs.mu.OZ.AU (mail-gate.cs.mu.oz.au [198.142.254.221]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f6A9gxX21219 for ; Tue, 10 Jul 2001 11:43:00 +0200 (MET DST) Received: from hg.cs.mu.oz.au (root@hg.cs.mu.OZ.AU [128.250.25.19]) by mumnunah.cs.mu.OZ.AU with ESMTP id TAA07946; Tue, 10 Jul 2001 19:42:56 +1000 (EST) Received: (from fjh@localhost) by hg.cs.mu.oz.au (8.9.3/8.9.3/SuSE Linux 8.9.3-0.1) id TAA15873; Tue, 10 Jul 2001 19:42:55 +1000 Date: Tue, 10 Jul 2001 19:42:55 +1000 From: Fergus Henderson To: Jean-Christophe Filliatre Cc: Chris Hecker , caml-list@inria.fr Subject: Re: [Caml-list] why does hashtbl not use lists? Message-ID: <20010710194255.A15865@hg.cs.mu.oz.au> References: <4.3.2.7.2.20010710013127.02c06600@shell16.ba.best.com> <15178.50493.314895.925129@pc803> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0pre3i In-Reply-To: <15178.50493.314895.925129@pc803> Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On 10-Jul-2001, Jean-Christophe Filliatre 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 | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: | -- 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