[gclist] Finalization, collection, etc.

[Jerry Leichter]

The problem of finalization running "soon enough" in a GC environment is a special case of an underlying problem.  David Gelernter wrote a couple of 
papers on some of these issues in the context of parallelism back in the early 
'80's.

Consider a variable and the value bound to it.  There are two separate 
attributes we can assign to it:  Its visibility - from what combination of
execution location and time the variable is visible - and its 
lifetime - the range of execution time over which its value must be preserved.  
In most languages today, we use static scoping, so only execution location, not 
time, determines visibility.  Give this, the two attributes are, in p
principle, decoupled:  Visibility is tied to space, lifetime to time.  However, 
in languages with stack allocation, *for the most part*, we bind the two 
together:  A variable's value remains live exactly as long as the variable 
itself remains visible (i.e., the stack frame it's in continues to exist).  For 
the most part, we specify visibility, imputing lifetime.  (The ALGOL OWN 
declaration - or the C static storage class for an object declared within a 
lexical scope - explicitly define lifetime.  In these, and in most cases, the 
only lifetime you can specify is "until the program exits".)

The notion that lifetime and scope are one and the same is so pervasive in 
traditional languages that people don't even realize that the two notions are 
distinct.  C++ constructors and destructors for stack-allocated objects, for 
example, are defined with this as the underlying assumption:  The constructor is 
called exactly when the object 
it constructs comes into scope; its destructor is called exactly when that 
object goes out of scope.  All sorts of C++ techniques rely on this close 
connection - e.g., classes that take out a lock on construction and release the 
lock on destruction.

Dynamically allocated objects in traditional, non-GC languages have a problem:  
Explicitly allocated memory has a lifetime that extends to its deletion point.  
This is completely independent of scoping, which is exactly why you can get both 
memory leaks and dangling pointers.

Languages with GC tie lifetime to accessibility, and accessibility is in turn 
the transitive closure of visibility.  *In principle*, the lifetime of an object 
ends the moment it is no longer accessible.  The problem is that, unlike 
visibility from a stack frame, accessibility is usually expensive to check.  
Only reference counting can practically detect loss of accessibility the moment 
it occurs (at least in the acyclic case).

Consider again C++ destructors for stack objects.  They execute only at block 
end, even in cases where one could detect that the object has become inacces-
sible earlier (i.e., just after the last reference to the variable in its 
declared block).  So C++ destructors don't execute "as soon as needed" either; 
in fact, a reference-counted implementation might very well execute finalizers 
much earlier than C++ would!

What the C++ design gives the programmer is a clear synchronization point:  At 
the end of the block, all destructors "pending" for the block are executed.  
This seems natural, again, because in C-like languages we identify visibility 
with lifetime.  For non-stack allocated objects, the delete statement is the 
(perhaps incorrect, as there may be other pointers) synchronization point.

In the general GC case, there are no obvious synchronization points.  One could, 
I suppose, call the GC at the exit from each block - recovering exactly the C++ 
destructor semantics for objects that were only accessed from locals within the 
block.  Combining a generational collector with appropriate compiler 
optimizations (escape analysis), this could probably even give decent 
performance.  For the general case, where the actual access pattern isn't really 
stack-like, there is no obvious synchronization point.  The programmer will have 
to provide one.  Using a delete statement as a hint - it not only kills the 
reference to the object, but if the object has a finalizer triggers a GC "very 
soon" to see if the finalizer needs to be called - will work, but puts the onus 
on the *user* of the abstraction, not is implementor.  The way to put it back on 
the implementor is to allow him to declare the object as "needing quick 
finalization".  Any time a pointer to such an object is deleted, a GC is 
triggered "very soon".  (Of course, we could just say that having a finalizer 
implies this treatment!  Simpler, but less flexible, since there are probably 
many finalizers that *don't* need special treatment.)  In a statically typed 
language where this flag is an attribute of the type, this can be implemented 
with little overhead.  (It's much more expensive in other cases.)

Of course, any such triggered GC'ing is unlikely to be compatible with 
incremental, much less real-time, collectors.  Reference counting seems to me 
the only hope in such cases.
							-- Jerry