hash tables and GC

[Jon L White <jonl@lucid.com>]

re: By the way, here is how I think weak tables could be implemented in a
    mark-sweep GC (are there any of those around any more?):
    During the mark phase, don't recurse through the keys of any weak
    tables.  Before the sweep phase, make another pass, deleting any weak
    table entries whose keys are not marked.

In fact, PDP10 MacLisp's OBARRAY (the hash-table for interned symbols)
was implemented in the obvious way so that "truly worthless atoms"
could be garbage collected, even though they were entered in the table.
[There was a mode switch -- (SSTATUS GCTWA t-or-nil) -- to turn this
capability on or off, since it did cost a marginal amount more of time].

The explicit step that is needed but not directly mentioned in your wording
of the algorithm is that "value" links must be recursed through during the 
mark phase (for MacLisp, this meant descending the value-cell and plist 
attributes of interned symbols, without marking the symbol itself).  That 
is, value links for entries that will not be deleted *may* contain the only 
pointers to other keys which protect those keys from undesired removal.

In many reference counting garbage collectors, it is possible to ask  "Is 
the reference count of this object equal to 1?" [and in the Deutsch/Bobrow 
variations, you can at least ask this question at scavenge time, even though
you may not be able to ask it an just any old time].  If the answer to this 
question is Yes for a key in a "weak" table, then it must be that the one 
pointer to it is the table entry itself; hence it may be deleted.

In VAX/NIL, we had devised a scheme for a sort of "weak pointer" table
even though the garbage collector was to be a copying one.  [It was
mostly in conjunction with an emulation of the MAKNUM function of PDP10 
MacLisp, which didn't do copying.]  But alas, as the GC was last on the 
implementation agenda . . . well, suffice it to say that we didn't ever 
find out what the performance implication of that scheme would be.


-- JonL --