Re: hash tables and GC

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

    Date: Tue, 30 Aug 88 00:03:57 EDT
    From: smh@EMS.MEDIA.MIT.EDU (Steven Haflich)

       From: David L. Andre <DLA@JASPER.SCRC.Symbolics.COM>
       Subject: Re:  hash tables and GC
   
	   0. Can such tables be implemented?
   
       Proof by existence:  We have had such tables prototyped internally at
       Symbolics for a year or so, but have not had the resources to qualify
       them for release to customers.  They can be quite efficient, and of
       course can significantly improve the efficiency of some kinds of
       programs.

    But perhaps this isn't exactly the right question for such a late date
    in the CL standards process.  Rather:

       Can such tables be implemented with reasonable performance
       in *all* existing CL implementations, without breaking the GC
       strategies upon which they depend?

    I myself have no idea which way this question would fall, but unless
    it could confidently be answered in the affirmative I feel X3J13 would
    have to exclude these `weak-pointer' tables from the standard.  The
    *real* problem is that it would be incumbent on the *proposer* to
    prove practicality.  This would not be an easy proof.

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.