[gclist] The old container problem

David Gadbois gadbois@cyc.com
Mon, 21 Sep 1998 11:26:51 -0500

I am currently trying to come up with a solution to what appears to be
a general problem.  Consider a long-lived container object such as a
hash table or queue to which freshly allocated objects are frequently
added.  In a generational GC system, after the container ages out of
the youngest generation, each addition of a new object to the
container exercises the write barrier trap.  The problem here is that
updates to the container violate the ordering assumption (that most
reference between objects are from newer objects to older objects) in
a big way.  This problem is exacerbated by the expensive remembered
set pointer recording mechanism I am using.

I see a couple of potential solutions:

1. Use a sufficiently cheap intergenerational pointer recording method
   that the write-barrier trap cost is not so high.  E.g., a card
   marking approach where every write, regardless of whether it is an
   old-to-new store, is noted.  The downsides are potentially greatly
   increased write traffic updating the cards and the extra scanning
   work to be done without precise old-to-new pointer recording.

2. Allocate the containers in a special "pre-natal" area that is
   younger than the youngest normal generation.  Collect this area by
   doing a straight non-generational GC at fairly infrequent
   intervals.  The downsides to this approach are that it requires
   what amounts to an extra, special-purpose collector and that it
   complicates already fragile storage system invariants.

Any other ideas?

--David Gadbois