[gclist] Finalization and object orientation.

[Hans Boehm]

On Mar 31, 10:23am, Charles Fiterman wrote:
> Subject: Re: [gclist] Finalization and object orientation.
> David Chase wrote:
> >
> >topoSort is topological sort,
> >and yes, it detects cycles.  Any introductory computer science text
> >on algorithms ought to explain it.
>
> I found it there. The overhead was extreme. This is why I haven't
> found any collectors that actually do that.

A topological sort can be performed in linear time, with a small constant.
The most significant overhead will be in building up and tearing down the
data structures.  (An explicit topological sort based on the points-to
relation is a bit harder, because you need to deal with nonfinalizable objects
that affect reachability between finalizable objects.)

The reasons collectors (at least my collector anyway) don't do an explicit
topological sort are:

1. It doesn't handle resurrection correctly.  Nor does it handle finalizers
that change ordering between other finalizable, but not yet finalized, objects.

2. You get topologically ordered finalization (w.r.t the points-to relation)
essentially for free out of a conventional collector, with cycle detection,
even.  And it handles resurrection, etc.  The downside is you get one "layer"
of finalization per GC cycle.  But millions of lines of code have been written
in such systems, and this doesn't seem to be an insurmountable problem.

> In the case where a list of finalizer objects each writes to a
> report only knowledge of the desired order of the report determines
> the correct order of the finalizers.
I don't think that's a reasonable use of finalization.  It relies on exact
knowledge of when objects become inaccessible.  It won't work with generational
collection, conservative collection, or programming languages that don't define
reachability (all of them?).

> Safe finalization implies the existence of post finalized objects
> visible by the mutator, assuming finalizers are run at all.
Could you clarify?  Presumably you are talking about resurrection?
It's reasonable to require that "resurrected" objects be in a consistent
state.  Saying that all finalized objects are potentially still accessible
imposes MUCH stronger constraints.

Since a very common use of finalizers is to interface to libraries that
require explicit memory management, accidental access to post finalized objects
is a very bad thing, since it often implies access to dangling pointers.
It's possible to code defensively against this.  But normally I shouldn't have
to.

Hans




-- 
Hans-Juergen Boehm
boehm@mti.sgi.com