[gclist] object identity & copying collection
William D Clinger
Wed, 10 Dec 1997 13:47:16 -0500 (EST)
Fergus Henderson asked about hashing on object addresses with a
copying gc. As he observed, part of the solution is never to
give out the actual hash of an object. Here are some of the
alternatives to the methods he listed for mapping the address of
an object to its associated information (which might be a hash
value that is given out, or might be something else).
* Using weak pointers and an after-gc interrupt, every
address-based hash table can be rehashed after every gc.
* To avoid rehashing tables that aren't in current use, the
after-gc interrupt can just mark each table invalid, and
let the first operation on an invalid hash table do the
* A more widely applicable solution involves adding a field
to each address-based hash table that records the time or
serial number of the gc that established the addresses on
which that table's hashing was based. All hash table
operations compare this to the time or serial number of
the most recent gc; if they don't match, then the table is
* With a generational collector, the previous idea can be
refined by keeping a field for each generation, and by
segregating the entries by generation. Then a partial gc
requires only part of the table to be rehashed.