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 LAA19771; Tue, 10 Jul 2001 11:00:55 +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 LAA19766 for ; Tue, 10 Jul 2001 11:00:54 +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 f6A90nX20357 for ; Tue, 10 Jul 2001 11:00:50 +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 TAA07913; Tue, 10 Jul 2001 19:00:45 +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 TAA15581; Tue, 10 Jul 2001 19:00:45 +1000 Date: Tue, 10 Jul 2001 19:00:45 +1000 From: Fergus Henderson To: Chris Hecker Cc: caml-list@inria.fr Subject: Re: [Caml-list] why does hashtbl not use lists? Message-ID: <20010710190045.A15552@hg.cs.mu.oz.au> References: <4.3.2.7.2.20010710013127.02c06600@shell16.ba.best.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0pre3i In-Reply-To: <4.3.2.7.2.20010710013127.02c06600@shell16.ba.best.com> Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On 10-Jul-2001, Chris Hecker 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 | "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