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 CB42ABC84 for ; Wed, 30 Mar 2005 17:03:09 +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 j2UF39SK030102 for ; Wed, 30 Mar 2005 17:03:09 +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 RAA01347 for ; Wed, 30 Mar 2005 17:03:09 +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 j2UF38Qg008761 for ; Wed, 30 Mar 2005 17:03:08 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id 8619D2BAA29; Wed, 30 Mar 2005 17:03:10 +0200 (CEST) Message-ID: <424ABFAE.7080309@barettadeit.com> Date: Wed, 30 Mar 2005 17:03:10 +0200 From: Alex Baretta User-Agent: Debian Thunderbird 1.0 (X11/20050116) X-Accept-Language: en-us, en MIME-Version: 1.0 To: "Marcin 'Qrczak' Kowalczyk" Cc: caml-list@inria.fr 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> In-Reply-To: <874qetdypa.fsf@qrnik.zagroda> 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 424ABFAD.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 424ABFAC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; baretta:01 caml-list:01 memoized:01 hashtable:01 alas:01 worst-case:01 bytecode:01 ocamlc:01 ocamlopt:01 hashtable:01 4096:01 pairs:01 iirc:01 ocaml's:01 hash: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: Joh Harrop wrote: >>> This is rather unlikely. The key to the hashtable is a unique integer... > > So not a [0|1] list like the /. troll then? ;-) No, definitely not. Actually, I am trying to use as much of the bonuses of functional programming to further speed up a fairly fast (but, alas, worst-case exponential) cutting stock algorithm. The present one works as a bytecode library to our AS/Xcaml application server, and provides performance comparable to that of the most widely available commercial implementations. Yet, it is necessary to do better to win the market over, and it it takes a little more effort than switching from ocamlc to ocamlopt ;) >>> Rather, what happens, time-wise, if I create a hashtable with 4096 slots >>> and end up filling it with several million key-value pairs? > > > The hashtable will dynamically double its size each time it feels full. This > incurs an O(n) cost at exact solutions of n = 2^p - 1 for integer p>0, IIRC. > This will cause the program to stutter but should not adversely impact > overall performance. This would be a problem for real-time applications. Marcin 'Qrczak' Kowalczyk wrote: > "Alexander S. Usov" writes: > > No, OCaml's hash tables are resized automatically. Ok. So, just as I expected, I am guaranteed that I have no hash conflicts desperately degrading the performance of my algorithm. But what is the amortized complexity of an insertion into a resizable hashtable? Am I right in stating that it is O(log n)? Or is it maybe O(n) due to saturation of number of buckets available to the hashtable? Then, in this case, I would need to expand the number of buckets by allocating a super-hashtable implemented as a hashtable of hashtables (as someone already suggested) or an array of hashtables. And, then again, how does the Gc.full_major scale as the "cache" for the algorithm fills up with millions of key-value pairs? Is the GC linear on the number of *reclaimed* blocks, or is it linear in the *total* number of allocated blocks? 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