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 700E9BC84 for ; Wed, 30 Mar 2005 14:34:19 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2UCYIBZ021396 for ; Wed, 30 Mar 2005 14:34:18 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA28689 for ; Wed, 30 Mar 2005 14:34:18 +0200 (MET DST) Received: from alex.barettalocal.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2UCYH77008898 for ; Wed, 30 Mar 2005 14:34:17 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id AC78B2BAA29; Wed, 30 Mar 2005 14:34:18 +0200 (CEST) Message-ID: <424A9CCA.7030204@barettadeit.com> Date: Wed, 30 Mar 2005 14:34:18 +0200 From: Alex Baretta User-Agent: Debian Thunderbird 1.0 (X11/20050116) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jon Harrop Cc: Ocaml Subject: Re: [Caml-list] Impact of GC on memoized algorithm References: <424A65C4.2080507@barettadeit.com> <200503301303.46742.jon@ffconsultancy.com> In-Reply-To: <200503301303.46742.jon@ffconsultancy.com> X-Enigmail-Version: 0.90.0.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 424A9CCA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 424A9CC9.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; baretta:01 caml-list:01 memoized:01 baretta:01 garbage:01 incorrectly:01 hash:01 clashes:01 hash:01 iirc:01 hashtbl:01 rec:01 hashtable:01 hashtable:01 4096:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: Jon Harrop wrote: > On Wednesday 30 March 2005 09:39, Alex Baretta wrote: > >>I have come to think that the difference in performance might be >>attributable to the garbage collector. > > > Try to objectively quantify the performance bottleneck using profiling, rather > than speculating. Most of the time, most of the people speculate > incorrectly. :-) Might be. I'm just trying to analyze critically my own work. > 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? Alex -- ********************************************************************* http://www.barettadeit.com/ Baretta DE&IT A division of Baretta SRL tel. +39 02 370 111 55 fax. +39 02 370 111 54 Our technology: The Application System/Xcaml (AS/Xcaml) The FreerP Project