[gclist] Buffy finalizer slayer.

Charles Fiterman cef@geodesic.com
Fri, 11 Jun 1999 13:58:36 -0500

At 11:01 AM 6/11/99 -0700, you wrote:
>Why it's essentially equivalent to topologically ordered finalization:
>I will generally need a (strong) pointer form the watched object to the
>object, since the finalizer is likely to need access to some of the state
>manipulated by other operations on the object.  (Even if it's not strictly
>needed, it affects reachability only if the finalizer needs information that
>the object otherwise doesn't, an unlikely scenario.)
>The watcher will need pointers to anything needed during finalization.  There
>isn't really a need for anything to refer to the watcher except the object
>itself, and the list of objects to scan after notification that a GC has
>completed.  If we simply turn the watcher object into a finalizable
object, and
>forget about the list of objects to be scanned, the watcher object will
>only finalizer reachable precisely when the watchee becomes inaccessible.

Why would I turn the watcher into a finalizable object? The point is to
eliminate finalizers from the system as an active danger. What happens at
end of job? What environment do finalizers run in? What if they throw an

When the watchee becomes inaccessible the weak pointer in the watcher zeros
and the mutator at a time of its choosing scans the watchers and discovers
it. The mutator then becomes responsible for any sorting and knows the
semantics of the problem. The mutator may simply put numbers in the watcher
objects and qsort them which costs only C*n*log(n). All file objects get 2
buffer objects get 1 everything else 0. Big deal, the user built these
watcher objects and knows their relationships.

>Similarly we can go from a topological order finalization scheme to the
>watcher-based scheme by splitting objects into two, with the watcher
>data needed by finalization, the watchee containing any other data, and a
>pointer to the watcher.  Object pointers turn into watchee pointers.  (This
>split is a good idea anyway, since it reduces finalization dependencies.)
>Note that this doesn't eliminate problems with finalization cycles.  It
>their occurrence to the genuine problem cases.  But I can also do that by
>splitting objects with topologically ordered finalization.  If I
previously had

Agreed it leaves genuine problem cases. Those must be solved by the user.
They are a problem in the semantics of the mutator. Eliminating finalizers
faces the user with his own bug.

>Similarly long finalization chains can still exist (though I have yet to
see a
>real case where those are a problem no matter what the finalization model).

Agreed they can exist. But sorting them with qsort costs C*n*log(n) with a
very small C. And the user determines the order. Those finalizers may be
putting lines on a report. But worst case topological sort is either C*n*n
in your version which has cycles and fails to report them or C*n*n*n in
versions that correctly report cycles. In your version C is very large, you
run a whole collection cycle. While in the reporting version C is small but
n*n*n can explode.

I believe the only reason for the topological sort is not understanding the
semantics of the mutator. If the user writes the sort there will generally
be an invocation of qsort at worst. There may be cases where the user needs
a topological sort and can't get around it. That should be the user's
problem. Maybe the user needs simulated annealing to sort finalizers.

And the user may want a sequence very different from topological sort. Its
the user's call.

Charles Fiterman		  Geodesic Systems
414 North Orleans Suite 410	  Phone 312 832 2015
Chicago IL 60610-4418           FAX   312 832 1230

...computers in the future may have only 1,000 vacuum tubes 
and weigh only 1/2 tons.  --  Popular Mechanics, March 1949