Generational Garbage Collection
Variously known as lifetime-based, tenured, promoting or new-space/old-space, are techniques that
attempt to partition allocated objects by their age or more accurately their order of
In many systems it is noted that most pointers between objects go from new objects to old objects,
for the simple reason that when an object is first created it can only have older
references stored in it.
It is also noted that most objects are short-lived, with longer-lived objects a rarity. It should
therefore be of benefit to concentrate on weeding out dead young objects more often than old dead
objects, because young objects are generally a minority of the total heap. GC can concentrate on
a smaller more active partition of objects, and hence be both more productive and less likely
to trigger page-faults on "dormant" areas.
In order to be able to collect a young heap generation without wading through
all the old objects, there needs to be a data-structure that enables efficient location
of all young objects that are pointed to by old objects (hopefully this is rare).
The simplest scheme involves maintaining a queue of entries each of which
contains information about such a reference (either the pointing object
or pointed-to object or both can be recorded). Such entry tables are maintained by
a write-barrier in the mutator, which notices each store of a "young" pointer into
an older generation object.
The GC has to tidy up these tables, however, for they may become stale, leading to dead
objects being retained. This is a general problem with generational collection---because
the technique only collects inter-generational cycles when the oldest generation is
collected, and because effort is concentrated on younger generations, dead objects
can hang around for a long time.
Eventually a young object has to grow old. There are two ways to do this
The latter technique tends to produce a large number of small generations,
and is more suited to systems where very few wrong-way pointers exist
(applicative or nearly-applicative programming languages such as ML).
- either move objects from younger to older generations every so often
- or age the generations wholesale and create a new youngest generation.
Objects do not have to be physically moved for promotion, but in order to
implement a sweep phase, there needs to be a way to iterate through all the
objects of a single generation.
Last updated by email@example.com
Tue 16 January 1996