Re: hash tables and GC

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

    Date: Wed, 31 Aug 88 21:47 EDT
    From: Barry Margolin <barmar@Think.COM>

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

Of course.

    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.

I can think of applications for weak-key, weak-value, and
weak-key-and-value hash tables.  Certainly weak-key is the most
generally useful.

    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.

Sounds reasonable given 10 seconds of thought.