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 10398BC48 for ; Mon, 11 Apr 2005 17:48:50 +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 j3BFmnRF002091 for ; Mon, 11 Apr 2005 17:48:49 +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 RAA04894 for ; Mon, 11 Apr 2005 17:48:49 +0200 (MET DST) Received: from mail.barettadeit.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 j3BFmmGu019877 for ; Mon, 11 Apr 2005 17:48:48 +0200 Received: from [10.0.0.10] (alex.barettalocal.com [10.0.0.10]) by mail.barettadeit.com (Postfix) with ESMTP id D0555802B3C9 for ; Mon, 11 Apr 2005 17:48:47 +0200 (CEST) Message-ID: <425A9C66.3050802@barettadeit.com> Date: Mon, 11 Apr 2005 17:48:54 +0200 From: Alex Baretta User-Agent: Debian Thunderbird 1.0 (X11/20050116) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Ocaml Subject: Re: [Caml-list] Impact of GC on memoized algorithm 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> In-Reply-To: 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 425A9C61.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 425A9C60.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; baretta:01 caml-list:01 memoized:01 damien:01 baretta:01 heap:01 heap:01 memoization:01 hash:01 caching:01 wrote:01 wrote:01 doligez:01 functions:01 algorithm: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: Damien Doligez wrote: > On Mar 30, 2005, at 17:03, Alex Baretta wrote: > Anyway, the total cost of a major collection cycle is proportional to > the heap size, but the frequency of these cycles is inversely proportional > to the heap size. Hence, under reasonable assumptions, average GC cost is > constant for each word that you allocate. This is what I was hoping for. > Of course, the picture becomes entirely different if you have lots of > explicit calls to Gc.major, Gc.full_major, or Gc.compact. 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? 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