Re: [Caml-list] Memory management dominates running time

["Jörgen Gustavsson" <gustavss@cs.chalmers.se>]

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