Re: Hash Tables and GC

[David L. Andre <DLA@JASPER.SCRC.Symbolics.COM>]

    Date: Tue, 6 Sep 88 19:50 PDT
    From: Gregor.pa@Xerox.COM

    As I understand it, finalization is a mechanism for recording a function
    which the garbage collector should call on an object when it is about to
    be GC'd.

    I find it surprising that no one has talked about finalization during
    this discussion.  This may not be facility we want to add to Common
    Lisp, but as near as I can tell, weak pointers and finalization are the
    primitives you need to build these kind of hash tables.

    In addition, finalization is a useful mechanism to have direct access
    to.

Finalization is certainly useful, but I'm not sure how any
implementation of a copying GC could implement it.  This is because the
function has to be called on an object which is in oldspace but it
cannot migrate the object to copyspace before examining it.

In a GC with hardware assistance, you have to bypass the transport
hardware to do this, which means you have to specially write the
function using implementation-dependent primitives.  (Note that
"conventional processors" may use "hardware assistance" such as read and
write traps.)  In all GCs, you have to ensure that the finalization
function does not cause a pointer to oldspace to be stored into anyplace
in memory.  This itself is a fairly severe restriction; it is certainly
not the same as "side-effect-free", but it is close.

I understand how to implement this feature, but I don't see how to do it
in an implemention-independent fashion in a copying garbage collector.
This is significant since most garbage collectors on the market today
are copying garbage collectors.  I also don't understand how to make it
safe enough to be a language feature.