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 LAA20024; Tue, 10 Jul 2001 11:05:03 +0200 (MET DST) 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 LAA20019 for ; Tue, 10 Jul 2001 11:05:02 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f6A952X20452 for ; Tue, 10 Jul 2001 11:05:02 +0200 (MET DST) Received: from pc803.lri.fr (IDENT:root@pc803 [129.175.8.114]) by ext.lri.fr (8.11.1/jtpda-5.3.2) with ESMTP id f6A951517804 ; Tue, 10 Jul 2001 11:05:01 +0200 (MET DST) Received: by pc803.lri.fr (8.9.3/feuille) id LAA27651 ; Tue, 10 Jul 2001 11:05:01 +0200 X-Authentication-Warning: localhost.localdomain: filliatr set sender to filliatr@pc803 using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15178.50493.314895.925129@pc803> Date: Tue, 10 Jul 2001 11:05:01 +0200 (MEST) To: Chris Hecker Cc: caml-list@inria.fr Subject: Re: [Caml-list] why does hashtbl not use lists? In-Reply-To: <4.3.2.7.2.20010710013127.02c06600@shell16.ba.best.com> References: <4.3.2.7.2.20010710013127.02c06600@shell16.ba.best.com> X-Mailer: VM 6.49 under Emacs 20.4.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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