Re: [Ocaml-lib-devel] Advancements

[Brian H. <bh...@sp...>]

On Tue, 25 Mar 2003, Nicolas Cannasse wrote:

> > > I'm currently still working on the List implementation... okay ,
> > > some words about it : I'm currently at Kyoto, and having everyday at
> lunch
> > > some ocaml-talks with Jacques Garrigue, and when I told him about this
> > > setcdr trick, is first reaction was that it would be nice but perhaps
> there
> > > is some GC issues since that can create pointers from the major to the
> minor
> > > heap, and then causing speed overhead.
> >
> > I'm only using setcdr on list elements I just recently allocated, which
> > makes it signifigantly less likely that I would be adding a pointer from
> > the major to the minor heap.  Possible, but not likely.
> 
> Actually, it depends !
> For example the map function is calling an user function, that can do lots
> of things, resulting a minor heap collection, and then back to ExtList.map
> your root has been moved to major heap. But Damien Doligez conclusion was
> that it will only occur once at a time, since next GC will put everything in
> the major heap, so the cost is very low.
> 

Even with append it's possible.  I have to allocate the next node in the 
list before calling setcdr (obviously).  Allocating the next node could 
cause a collection (minor heap being full) moving the previous node into 
the major heap.  Then, when I call setcdr, I'm still setting a pointer 
from the major heap to point to the minor heap.  So this is a problem that 
needs to be handled correctly no matter what.

On the other hand, it doesn't have to be the most efficient- because for 
every time we write a pointer into the major heap, we also have to do a 
garbage collection.  In your example, the map with a complex function, the 
cost of the function itself becomes a major cost.  These costs will 
overwhealm the cost of setting the pointer itself.

Some back of the envelope calculations.  Assume the minor heap is 16K 
words (64K bytes).  And we allocate 1 word every 6 instructions (about 
average for ML programs).  This means we do a GC every 96K instructions on 
average.  Even if setting a pointer from a major to a minor heap is 1K 
instructions, this is still less than 1% of the execution cost (not 
counting the cost of the garbage collection itself).

Which is, effectively, the conclusion you came to.

Brian