From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA26601; Wed, 8 Jan 2003 13:58:39 +0100 (MET) 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 NAA26655 for ; Wed, 8 Jan 2003 13:58:38 +0100 (MET) Received: from pheidippides.md.chalmers.se (pheidippides.md.chalmers.se [129.16.237.91]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h08Cwcr04763 for ; Wed, 8 Jan 2003 13:58:38 +0100 (MET) Received: from muppet20.cs.chalmers.se (muppet20.cs.chalmers.se [129.16.226.71]) by pheidippides.md.chalmers.se (8.10.1/8.10.1) with ESMTP id h08CwbI20731; Wed, 8 Jan 2003 13:58:37 +0100 (MET) Received: from localhost (gustavss@localhost) by muppet20.cs.chalmers.se (8.8.5/8.8.5) with ESMTP id NAA19703; Wed, 8 Jan 2003 13:58:36 +0100 (MET) X-Authentication-Warning: muppet20.cs.chalmers.se: gustavss owned process doing -bs Date: Wed, 8 Jan 2003 13:58:36 +0100 (MET) From: =?ISO-8859-1?Q?J=F6rgen_Gustavsson?= To: Chet Murthy cc: Subject: Re: [Caml-list] Memory management dominates running time In-Reply-To: <200301051135.h05BZHiY009447@nautilus-chet.watson.ibm.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, 5 Jan 2003, Chet Murthy wrote: > By using gprof, and doing a little careful counting, you can > often find out where egregious allocations are happening, and > eliminate them. I am afraid that is not my problem right now. I know where the allocations are and they are necessary in the algorithm we are currently implementing. The problem is (I believe) that the cost of each allocation is not atomic. Instead each allocation can under certain circumstances become more and more expensive as the program runs and eventually the program hardly does anything but searching for free blocks of memory to allocate. (I think this happens when data is moved from the minor heap to the major heap during the minor garbage collection. The free memory in the major heap is kept in a linked list which is searched linearly for a block of the right size.) It could actually help to introduce a space leak because it might lead to less fragmentation. Thus, when you reason about the asymptotic run time complexity of your ocaml programs you have to take the internals of the garbage collector into account which I think is unfortunate. Is it impossible to avoid this problem with a mark-sweep garbage collector? (With a simple two-space copying collector the problem disappear.) In any case we have found a temporary solution to the problem. By setting max_overhead in the gc control record to 0 one can force heap compaction to take place at the end of each major GC cycle. This makes the garbage collector behave like a compacting collector and it becomes very slow (90% of running time) but the asymptotic problem goes away so it is good enough for prototyping. Regards, Jörgen Gustavsson. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners