[gclist] Precise GC's performance

[Mark Tillotson]

Darius??? originally wrote:
> Does anyone have any idea on how to implement this KILL method on top of
> a conservative GC ? I guess it must be possible, but I don't know how.
> 
mps@geode.geodesic.com (Mike Spertus) replied:

> An important finesse in the mark phase is to treat all the objects
> with non-empty KILL methods as roots (i.e., anything they point to is marked,
> even if they aren't marked themselves). 
> There are two benefits to this approach: 
> 
> 1) If A points to B, then A will be killed before B, preventing
> its KILL method from running with loose pointers. 
> 
> 2) If A's kill function cancels the deallocation, you can just cancel the pending
> deallocation of A's memory in the sweep phase. Everything that A uses has 
> already been protected.

I don't see how you can detect this without mutator cooperation... (or
at least a write-barrier).  You are implicitly saying that you
deallocate all finalizable objects during the sweep phase directly
after their "kill methods" are run?

> 
> There are also two disadvantages to this approach:
> 
> 1) Cycles of finalizable objects will not be reclaimed unless the programmer
> manually breaks the cycle. (It is not clear whether other memory management
I am not clear how you arrange to detect these cycles - are you
marking _from_ all the finalizable objects but not directly marking them
themselves? 

> strategies avoid this disadvantage or merely sweep it under the rug by allowing
> KILL methods to run with loose pointers).
> 

There is a straightforward method that DTRT for finalization, although
it does delay collection of finalizable objects somewhat: (hopefully
I'll get this right...)

You start by marking from all the real roots (precisely or
conservatively, it shouldn't matter), and then look at your list
(or whatever) of finalizable objects.  Any marked finalizable objects
stay on the list, but unmarked ones are _moved_ to a new "pending
finalizations" list.  These are the ones known to be inaccessable at
the point the GC was entered.

You then (and only then) mark (and mark from) all the objects on this
pending list.  (You need to do this because they are accessible to the
finalization code, which is part of the mutator).

At this point you have a safe situation where all accessible objects
are fully marked. 

Then you do the sweep, and go through the pending list calling the
finalization code just before returning to the mutator.

If during the execution of finalization code you have to re-enter the
GC, you simply replace the unfinalized objects onto the list of
finalizable objects.  Otherwise those objects get finalized and
removed from the list.

Any memory for finalized objects will not get reclaimed until next
time round (unless, of course, the finalization code makes them
accessible again).

There is no problem with loose pointers nor with cycles.

Finalization code only gets called once on an object (unless it
re-registers the object for finalization).

Mark Tillotson
[ markt@harlequin.co.uk | http://www.harlequin.co.uk/ | +44 1223 873829   ]
[ homepage http://www.hal.com/services/juggle/home/markt@harlequin.co.uk/ ]