hash tables and GC

[Barry Margolin <barmar@Think.COM>]

    Date: Fri, 22 Jul 88 10:00:21 PDT
    From: jrose@sun.com (John Rose)

       Date: 22 Jul 88 10:13:34 EDT (Fri)
       From: gz@spt.entity.com (Gail Zacharias)

       This isn't much different from do-all-symbols in a lisp which does gctwa.
    I believe only the simplest symbols should be GC-ed; if a symbol is
    interned and has a nontrivial plist (say), GC-ing it will change
    the visible behavior of the program, since if a program re-creates
    it (via INTERN or READ), it will be missing its plist.

That's the definition of GCTWA (which stands for GC Truly Worthless
Atoms -- an atom is truly worthless if it is unbound, its function cell
is unbound, its property list is NIL, and the only reference to it is in
a package structure).  Such a GC is transparent as long as you don't use
DO-SYMBOLS or its variants and don't look at the second value of INTERN
and FIND-SYMBOL.

    Similarly, if hash table keys are being used to store information,
    as well as merely access it, they shouldn't be GC-ed.

    Putting weak links to keys in hash tables would make the EQUAL semantics
    I proposed impossible, since an isomorphism test depends strongly
    on MAPHASH.  (Or, before EQUAL is applied to test for isomorphism,
    normalize the two tables by performing a full GC! :@)
    Weak pointers are probably more useful than EQUAL isomorphism tests,
    but a reliable MAPHASH also seems indispensible.  Sounds to me
    like weakly-linked keys want to be another option to
    MAKE-HASH-TABLE.

He never said that this would be replacing hash tables; in fact, he said
it probably would NOT use the hash table interfaces.  A CL-compatible
hash table can't drop elements into the bit-bucket during GC.  This
feature would have to be an extension that would be invoked explicitly
when it is wanted.  The definition of EQUAL on GC-able hash tables might
have to be different from that for ordinary hash tables.

                                                barmar