Re: Hash Tables and GC

[Michael Greenwald <Greenwald@STONY-BROOK.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.  

I guess my previous mail did not get through.  I'll recap.  We had an
uninstalled version of finalization (not the name we used, but
"finalization" is better) and weak pointers in the SWIFT system.  SWIFT
wasn't written in LISP, but it is still applicable (CLU is another GC'd
language, which you can consider sort of Lisp with syntax, strong
typing, and compile time type checking, for the purpose of this
conversation).

There are only two points about finalization that I feel should be
brought up.  First, we found it useful to allow the finalization funarg
to return a value indicating whether or not to *really* GC the object.
The finalization funarg was called on every GC pass when the only
pointers to an object were weak pointers.  If it returned FALSE, then
the object survived the GC, TRUE then the storage was reclaimed.
Second, given a finalization funarg, it is possible to lie to the GC
(keep, or create, another reference to the object).  Therefore, the GC
reclaimed weak-pointer objects by clearing the pointer to the object in
the weak pointer, so that if there *really* are no other references to
the object it would be reclaimed on the next pass.

We had a non-compacting, mark and sweep, parallel ("real time") GC, FYI,
since someone asked about this before.

			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.

Yes.  It's not just useful in hash tables, and it allows multiple
weak-pointers to the same object.  It was mainly useful for unlinking
and caching.  (SWIFT ran in a single address space, so if you wanted to
flush some application completely from the world, you had to make sure
that you didn't leave a pointer to some data structure squirreled away
somewhere in the bowels of the operating system.  Weak pointers (it was
actually more like "weak objects" (or "GCable objects")) solved this
problem.)  In a lisp application where each process gets its own address
space that is killed when the process is killed, I'm not sure if there
is an advantage in having multiple weak-pointers to the same object, but
still, weak-pointers and finalization provide a lot more flexibility
than simply implementing temporary hash tables.