[gclist] Precise GC's performance

[Mike Spertus]

> Well, let's explain simply the rationale behind my experiment, because
> these considerations go far beyond my original ideas, and in a direction
> which I believe is not relevant.
> 
> - YAFL uses a precise GC, without copying. This GC is precise in the sense
>   that it keeps tracks of accessible instances at any time. It does not
>   more objects around. This keeps the design simpler, and some external
>   library (C) might have pointers to C objects.
> - There have been claims that the performance overhead of this "keeping track
>   of accessible data" was dramatic because it could forbid the C compiler
>   to perform some optimizations (register allocations)
> - So, I measured this performance overhead, which gave me an average of
>   17% (following some optimizations which have been suggested to me in this
>   mailing list, I even reduced this figure to under 15%), which I considered 
>   reasonable when compared to the advantage I saw in conservative GC, 
>   assuming that the actual GC could hardly be slower in a precise 
>   environment.
> 
> This was it. There was no more.
> 
I see I fell victim to jumping into a conversation in the middle without
looking at its whole history. My apologies. In any case, if you don't consider 
15% additional overhead to be a showstopper for your application, it is highly 
unlikely that performance will be a deciding factor in your conservative vs. 
precise gc question.

> By the way, I have been looking to see how to integrate a conservative GC
> in YAFL and I found a potential problem: YAFL supports a user-redefinable
> KILL method, which is invoked before the object is deallocated. This method 
> is mainly used to free system resources (Widgets, pipes, etc...) attached to 
> YAFL objects when it is deallocated. Ultimately, the KILL method might even
> cancel the deallocation, by setting a valid reference to the object it is
> being applied to. One can say that KILL is an asynchronous destructor.
> 
> 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.
> 
Yes. Pointers to all objects with a non-empty KILL method are 
stored in a hash table. Because conservative collectors are essentially
mark-and-sweep, the KILL method can be invoked before reclaiming the object's
memory. 

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.

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
strategies avoid this disadvantage or merely sweep it under the rug by allowing
KILL methods to run with loose pointers).

2) A 1000 element linked list of objects with non-empty kill methods will
take 1000 collection cycles to reclaim because only one element will be
removed per cycle.

We use this technique (which comes from the Boehm collector). This works very 
well if relatively few objects require killing (e.g. for the types of uses that 
you describe) but very poorly if most objects require killing. Is there any 
collection algorithm, precise or otherwise, that functions well if many objects 
require killing?

> Regards,
> 
> Darius
>