From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 29165BC84 for ; Wed, 30 Mar 2005 11:41:18 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2U8dWBB010329 for ; Wed, 30 Mar 2005 10:39:32 +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 KAA24046 for ; Wed, 30 Mar 2005 10:39:32 +0200 (MET DST) Received: from alex.barettalocal.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2U8dVBd024717 for ; Wed, 30 Mar 2005 10:39:31 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id 895DE2BAA3C for ; Wed, 30 Mar 2005 10:39:32 +0200 (CEST) Message-ID: <424A65C4.2080507@barettadeit.com> Date: Wed, 30 Mar 2005 10:39:32 +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: Impact of GC on memoized algorithm 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 concorde with ID 424A65C4.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 424A65C3.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; baretta:01 memoized:01 ocaml:01 recursive:01 memoized:01 hashtable:01 inputs:01 garbage:01 malloc:01 model:01 malloc:01 baretta:01 slower:01 slower: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: I am trying to fine tune a "cut stock" optimization algorithm which I have written for Ocaml. It so happens that the vanilla recursive implementation is quite fast, relatively to other implementations I've seen, whereas the memoized implementation is very slow. The vanilla implementation has a memory footprint of only a few megabytes, whereas the memoized version takes up some 60 MB on the same input. Quite obviously, the hashtable used to cache the results suffers from the combinatorial explosion of possible inputs. Now, given this, it is expected that the memoized version be as slow or slightly slower than the non memoized version, but it is not obvious why it would be a couple of orders of magnitude slower. I have come to think that the difference in performance might be attributable to the garbage collector. This might be the case if the complexity of a collection is proportional to the total allocated memory, because the overall allocation/reclaiming cost of a fresh block would be proportional to the total number of allocated blocks. Is my diagnosis correct? That is, is the GC collection a O(n) algorithm? Would the C-language malloc/free model be any faster here? As far as I know malloc keeps a linked list of free blocks, which is also O(n). 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