Re: hash tables and GC

[Barry Margolin <barmar@Think.COM>]

    Date: Wed, 31 Aug 88 21:03 EDT
    From: David L. Andre <DLA@jasper.scrc.symbolics.com>

    Well, we haven't done it for standard architectures, but it would seem
    to be straightforward to add the feature to any copying garbage
    collector.  Simplisticly, all you have to do is modify the scavenger to
    make two passes:  The first pass skips any references from weak tables,
    and the second pass replaces oldspace references to the deleted objects
    with a null marker.  The overhead of the second pass can typically be
    minimized by always creating such tables in a special part of address
    space, so the second pass has little overhead.  There are many other
    possible optimizations.

    My point is, it has nothing to do with hardware support; it's at the
    next higher level.  Hardware support at best will just give you a better
    scavenger to build this on.

There's actually an even more trivial solution: don't implement them if
you don't want to!

The difference between weak tables and ordinary tables is that the
implementation is ALLOWED to GC entries in weak tables.  However, just
as Common Lisp never actually says that an implementation MUST have a
GC, it can't REQUIRE an implementation to GC entries in a weak table.
So, if your GC is not easily extended to support weak tables, you can
simply ignore the :WEAK (or whatever) option.  The only invalid way to
implement weak tables is to implement them in such a way that they GC
entries that they shouldn't; remembering too much should never bother a
valid CL program (unless it runs out of memory, but that's outside the
language spec).  (Hmm, this argument would justify a Lisp implementation
that used only a reference-count GC, but I expect that there would be
far fewer weak tables than circular structures, so the argument doesn't
really scale up.)

By the way, I assume that David meant that only key fields of tables
should be skipped.  Otherwise you could end up with keys whose values
have been GCed.

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.

The added passes of both the copying and mark/sweep GCs would be sped up
significantly if the implementation maintained a list of all weak tables
(or it could cons up such a list during the first pass), so that it
wouldn't have to make a full pass through memory to find them.

                                                barmar