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