[gclist] Buffy finalizer slayer.

Fergus Henderson fjh@cs.mu.OZ.AU
Sat, 12 Jun 1999 10:48:59 +1000

On 11-Jun-1999, Nick Barnes <Nick.Barnes@pobox.com> wrote:
> At 1999-06-11 16:55:08+0000, David Chase writes:
> > At 04:35 PM 6/11/99 +0100, Nick Barnes wrote:
> > 
> > >Finalization is much better if you have exact collection and a
> > >"collect the whole world now" function.  Then the mutator stands a
> > >better chance of telling that an object has a unique pointer according
> > >to language semantics.  But exact collection is a somewhat tricky
> > >notion with optimizing compilers.  With enough information from the
> > >compiler, you may be able to avoid looking at any registers, stack
> > >slots, or object slots that contain non-pointers, but it's much harder
> > >to avoid looking at values (registers and stack slots in particular)
> > >that contain values which might be no longer in use according to the
> > >language semantics.
> > 
> > It depends upon how you define "optimizing", of course, but we
> > (my employer, NaturalBridge) have done this.  The compiler emits
> > exact maps for all objects and for all points where the GC may
> > run, and takes into account the liveness information computed
> > by data flow analysis for registers and stack slots.
> Sure, and various people have done the same thing in various ways for
> SML.  It's even led to some interesting research (I'm thinking here of
> region inference).  But it generally doesn't get you all the way
> there.  There tends to be some corner in which all you can say is
> "this value escapes our local context", and unless you have global
> information, which you rarely do, you have to say "and must therefore
> be assumed to be live".  Ultimately, even with global information, it
> boils down to the halting problem.

Yes, but that's a quite separate issue.

Certainly liveness in the general sense is an undecidable property.
But a language can define a notion of pointer-reachability that _is_
decidable.  The question is whether the implementation obeys the language
semantics, i.e. collects everything that is not pointer-reachable,
not whether it collects everything that will never be used again.
Ensuring that all unused things which need to be garbage collected
are not pointer-reachable is up to the programmer, not the implementation.

Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@        |     -- the last words of T. S. Garp.