[R6RS] Hashing questions

[William D Clinger]

Mike wrote:
> If I may ask with an eye towards our own implementation: In a
> generational (or otherwise incremental) GC how do you keep track of
> what objects that are moved occur in an eq? hash table and thus may
> need rehashing there?

That's going to be pretty implementation-dependent, but
here's how the Larceny prototype does it.  First of all,
hash tables are represented as a linked list of tablets,
which must all be searched before a lookup can conclude
that some key is not in the table.  There are several
reasons for doing this, but the one that's most relevant
here is that this allows the hash table to mimic the
behavior of most generational garbage collectors.

Larceny maintains several counters that keep track of
how many garbage collections have been performed, and
of how many of them were minor or major collections.
(One of these counters can be accessed by a single
machine instruction; the other should be, but isn't.)
For the purpose of this message, the main thing to
know about a minor collection is that, once an object
has survived a collection of either kind, it will not
be moved by a minor collection.

Invariant of the hash table:  If a tablet is not the
first tablet in the table, then all of its keys have
survived at least one garbage collection.

Each tablet in a hash table contains a field that
records the time at which it was last rehashed, where
this time is represented as the number of collections
and major collections that had occurred prior to the
conclusion of the last rehash.  Every operation on a
tablet compares this field against the current values
of the gc counters.  If no collections have occurred
since the tablet was rehashed, then the tablet can be
used without rehashing.

Tablets other than the first must be rehashed only if
a major collection has occurred since they were last
rehashed.

If any kind of collection has occurred since the first
tablet in the list was rehashed, then that tablet must
be rehashed.  When it is rehashed, its entries are
promoted, either by moving them into the second tablet
or by adding a new tablet in front of the rehashed
tablet.  Either way, the first tablet in the list will
be empty following a rehash of the previous first tablet.

New keys are added to the first tablet in the table,
because they might not have survived a collection yet.

Will