[gclist] Buffy finalizer slayer.

[Hans Boehm]

On Jun 14,  6:48am, Charles Fiterman wrote:
> First topological reachability can be partially evaluated at class
> definition time. That is when I design a class I know what it will require
> to finalize. This allows turning n*n*n topological sorts into n*log(n)
> qsorts or even non sorts which are the most common case.
>
To avoid misunderstandings here:

A topological sort is linear in the number of vertices + edges.  Garbage
collectors that finalize in topological order still run each GC in linear time.
 The process becomes nonlinear (in a sense) because we can generally only
finalize one "layer" of objects per GC.

The reason is that finalizers may change reachability.  If we assume that
finalizers do not create new edges (e.g. in a call-by-value functional
language), we could enqueue objects for finalization in topological order in
linear time.  If you are really worried about finalization running time, this
may even be a reasonable approach.  (I would guess the reason neither Modula-3
nor Cedar went this route is basically that it solves a non-problem with a
(minor) loss in safety guarantees.  I haven't thought about it very hard, but
an implementation doesn't seem to be terribly difficult.)

If you allow for finalizers to change topology, and hence ordering of other
finalizations, you end up with a quadratic process for a chain of n finalizable
objects.  If you factor objects into finalizer-accessible and
finalizer-inaccessible objects, or you use Charles' proposal, this seems
extremely unlikely to ever be a real issue.  I don't know how you get a cubic
one given that both topological sorting and cycle detection are linear.

Hans


-- 
Hans-J. Boehm
boehm@sgi.com