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 8A14CBC48 for ; Thu, 31 Mar 2005 16:41:42 +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 j2VEff1k029175 for ; Thu, 31 Mar 2005 16:41:42 +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 QAA04537 for ; Thu, 31 Mar 2005 16:41:41 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2VEffFs029327 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Thu, 31 Mar 2005 16:41:41 +0200 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 1EE0019E7D4; Thu, 31 Mar 2005 16:41:41 +0200 (CEST) Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 02456-08; Thu, 31 Mar 2005 16:41:41 +0200 (CEST) Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id 0AE0619E7D0; Thu, 31 Mar 2005 16:41:41 +0200 (CEST) Received: from pc8-142 (pc9-152 [129.175.9.152]) by smtp.lri.fr (Postfix) with ESMTP id 3EE90CED98; Thu, 31 Mar 2005 16:41:38 +0200 (CEST) Received: from filliatr by pc8-142 with local (Exim 3.36 #1 (Debian)) id 1DH0ra-0004dV-00; Thu, 31 Mar 2005 16:41:38 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16972.3106.484623.189533@gargle.gargle.HOWL> Date: Thu, 31 Mar 2005 16:41:38 +0200 To: Alex Baretta Cc: "Marcin 'Qrczak' Kowalczyk" , caml-list@inria.fr Subject: Re: [Caml-list] Impact of GC on memoized algorithm In-Reply-To: <424ABFAE.7080309@barettadeit.com> References: <424A65C4.2080507@barettadeit.com> <200503301303.46742.jon@ffconsultancy.com> <424A9CCA.7030204@barettadeit.com> <200503301509.01571.A.S.Usov@kvi.nl> <874qetdypa.fsf@qrnik.zagroda> <424ABFAE.7080309@barettadeit.com> X-Mailer: VM 7.18 under Emacs 21.3.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at nez-perce with ID 424C0C25.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 424C0C25.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 memoized:01 filliatre:01 filliatre:01 lri:01 ocaml's:01 hash:01 baretta:01 hash:01 conflicts:01 resizing:01 ocaml's:01 ocaml:01 syntax:01 recursive:01 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: Marcin 'Qrczak' Kowalczyk wrote: > > No, OCaml's hash tables are resized automatically. Alex Baretta writes: > > Ok. So, just as I expected, I am guaranteed that I have no hash > conflicts desperately degrading the performance of my algorithm. Note that it is true only if your hash function is good enough. I had once a code spending most of its time in the resizing of Ocaml's hash tables because of a bad hash function. This is particularly true of the ocaml default hash function on ``pure'' abstract syntax trees (recursive data types with few types such as int or strings). Writing my own hash function immediately solved the performance issue. (In your case, however, the problem seems to be elsewhere ince you are using unique integers as keys). As somebody already said, a profiling is a simple way to find out if the hash tables resizing is the issue. Best regards, -- Jean-Christophe