[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
hash tables and GC
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 --