[gclist] object identity & copying collection

William D Clinger will@ccs.neu.edu
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.