generation-based collection

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 allocation.

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.

Entry Tables

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.

Promotion

Eventually a young object has to grow old. There are two ways to do this

either move objects from younger to older generations every so often
or age the generations wholesale and create a new youngest generation.

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).

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. [INCOMPLETE]

Last updated by markt@chaos.org.uk Tue 16 January 1996