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 4AA09BC48 for ; Thu, 14 Apr 2005 11:52:18 +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 j3E9qI9U028766 for ; Thu, 14 Apr 2005 11:52:18 +0200 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 LAA12429 for ; Thu, 14 Apr 2005 11:52:17 +0200 (MET DST) Received: from [IPv6:::1] (yquem.inria.fr [128.93.8.37]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j3E9qHKF028763 for ; Thu, 14 Apr 2005 11:52:17 +0200 Mime-Version: 1.0 (Apple Message framework v619.2) In-Reply-To: <425A9C66.3050802@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> <425A9C66.3050802@barettadeit.com> Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Damien Doligez Subject: Re: [Caml-list] Impact of GC on memoized algorithm Date: Thu, 14 Apr 2005 11:52:47 +0200 To: Ocaml X-Mailer: Apple Mail (2.619.2) X-Miltered: at nez-perce with ID 425E3D52.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 425E3D51.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; damien:01 damien:01 caml-list:01 memoized:01 baretta:01 memoization:01 hash:01 caching:01 hash:01 hashing:01 arbitrarily:01 48,:98 wrote:01 doligez:01 doligez: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: On Apr 11, 2005, at 17:48, Alex Baretta wrote: > No, I don't, so the cost of memoization should only impact the > multiplicative constant and not the complexity class of my algorithm. > This is good. Now I'll have to experiment with Maps and Hashtbls with > and without custom hash functions to find the most efficient caching > scheme. Any suggestions? Assuming you are going to use hash tables: In my experience, it is important to pay attention to the cost of the hashing function. If you can avoid going through the whole structure to compute the hash, you'll save a lot of time. It may also be a good idea to limit the number of cache entries, instead of just letting the cache grow arbitrarily large. I've had good results by deleting some entries at random when the cache gets too big. -- Damien