From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 661E8BC84 for ; Wed, 30 Mar 2005 15:09:24 +0200 (CEST) Received: from KVIW13.KVI.nl (KVIW13.KVI.nl [129.125.15.45]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2UD9OUW025810 for ; Wed, 30 Mar 2005 15:09:24 +0200 Received: from KVIS10.KVI.nl ("port 35703"@KVIS10.KVI.nl [129.125.27.60]) by KVI.nl (PMDF V6.2-X17 #30869) with ESMTP id <01LMI8PUMFAEAEL6LA@KVI.nl> for caml-list@yquem.inria.fr; Wed, 30 Mar 2005 15:09:20 +0200 (MET DST) Received: from KVIW06.KVI.NL by KVIS10.KVI.nl (AvMailGate-2.0.2-10) id 13633-2C4ACE86; Wed, 30 Mar 2005 15:09:18 +0200 Received: from kvip88 ("port 33256"@KVIP88.KVI.nl [129.125.15.152]) by KVI.nl (PMDF V6.2-X17 #30869) with ESMTP id <01LMI8PPIZSAAEL6LA@KVI.nl> for caml-list@yquem.inria.fr; Wed, 30 Mar 2005 15:09:13 +0200 (MET DST) Date: Wed, 30 Mar 2005 15:09:01 +0200 From: "Alexander S. Usov" Subject: Re: [Caml-list] Impact of GC on memoized algorithm In-reply-to: <424A9CCA.7030204@barettadeit.com> To: caml-list@yquem.inria.fr Message-id: <200503301509.01571.A.S.Usov@kvi.nl> Organization: KVI MIME-version: 1.0 Content-type: text/plain; charset=iso-8859-1 Content-transfer-encoding: 7BIT Content-disposition: inline User-Agent: KMail/1.8 X-AntiVirus: checked by AntiVir MailGate (version: 2.0.2-10; AVE: 6.30.0.7; VDF: 6.30.0.55; host: kvi.nl) References: <424A65C4.2080507@barettadeit.com> <200503301303.46742.jon@ffconsultancy.com> <424A9CCA.7030204@barettadeit.com> X-Miltered: at nez-perce with ID 424AA504.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 memoized:01 baretta:01 hash:01 clashes:01 hash:01 iirc:01 hashtbl:01 rec:01 hashtable:01 hashtable:01 4096:01 pairs:01 hashes:01 ...:98 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: On Wednesday 30 March 2005 14:34, Alex Baretta wrote: > > In this case, if you are using an inappropriate data structure as the key > > to the hash table then you may be getting a lot of clashes. In which > > case, lots of time will be spent looking up elements in hash table's own > > list implementation. IIRC, most of the time will then be spent in the > > Hashtbl.find_rec function... > > This is rather unlikely. The key to the hashtable is a unique integer... > > Rather, what happens, time-wise, if I create a hashtable with 4096 slots > and end up filling it with several million key-value pairs? In the best case you end up with a few hundreds or even few thousands of elements per bucket. And it will make it really slow. You should better increase a hashtable size by at least an order of magnitude, or create a hash of hashes. -- Best regards, Alexander.