[gclist] Finalization and object orientation.

[Hans Boehm]

On Mar 28,  8:15am, Eliot & Linda wrote:
> Hans Boehm wrote:
> >
[runFinalization semantics]
> > It would be hard to require it to do something precise without seriously
> > inhibiting optimization.  Certainly it could not require that unreachable
> > objects with finalize methods be finalized.  (Gosling, Joy, and Steele
> > define a reachable object to be one that "can be accessed in any potential
> > continuing computation from any live thread".  This is clearly undecidable
> > in general.)
>
> It is undecidable only in systems allowing the computation (forgery) of
> object pointers.
As Fergus pointed out this has little to do with the problem.  It is
undecidable whether a given in-scope pointer will ever be accessed again
by a program.  All garbage collectors compute an approximation to the notion of
reachability as defined in Gosling, Joy, and Steele.

We're not just picking nits here; this is an important point.  A large
difference in the "precision" of garbage collection has to do with which
variables are considered live at what point of the program.  There is some
evidence that for most programs this is a more important difference than
conservative vs. nonconservative collection.

This issue was discussed in Mark Weiser's and my SP&E '88 paper.  Is x seen
by the garbage collector during the call to g in

{ T x; f(x); g("abc"); }

For a naive compiler the answer is "yes".  For a CPS-based compiler, the answer
is "no".  For a typical compiler with global register allocation the answer is
"maybe".

There has been a significant amount of work on this kind of issue, especially
in the context of ML and logic programming languages.  (E.g. there was a paper
a few years back claiming significant space improvements in ML by treating
variables and data structure components with unconstrained type as dead.  Since
their type is unknown, they can'e be used for anything.  They can be safely
reclaimed, in spite of the fact that this leaves "dangling" pointers.  Appel is
careful to define a CPS-based notion of reachability for SML of NJ in order to
avoid some problems they observed with early version sof their system.)

Even in the case of a conservative garbage collector, I've often found that
more space was lost due to the lack of liveness information for registers and
stack locations than due to misidentification of other data as pointers.

Hans





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