shanecrawford.org Home Grown in Austin

Generational Garbage

One of the strategies used by modern garbage collectors (GC) to collect memory is the usage of generations. There are a couple of key observations about objects that are capitalized on in order to make the GC more efficient through this strategy.

Exploiting Key Observations

First, the life of most objects tends to be short and the GC uses this knowledge to enhance its efficiency by subdividing objects into newer and older generations. Newer generations are scanned more frequently thus freeing more memory without having to scan through objects which will most likely not need collecting (the older generations).

The second key observation is that objects tend to point from newer objects to older objects and not the other way around. This is not to say that older objects do not point to newer objects just that this is the less frequent case for most applications. This trait makes it a lot less expensive to locate those newer objects as long as we can tell when a pointer from a newer object is written into an older object. Otherwise we would need to scan all of the older objects in order to locate these pointers which would counteract the first key observation. In order to track these pointers older objects are placed behind what is known as a write barrier.

Write Barriers

The job of the write barrier is to track those writes in which a newer object pointer is written into an older object. With the write barrier in place we now know that the only pointers from older to newer objects are those which it has tracked thus eliminating the need to scan older objects to locate pointers to newer ones.

Promoting objects to older generations

When the GC receives a request for an incremental collection it will scan the newer generations for any objects which cannot be reached from the root set (see Collecting Leopard’s Garbage) or from older objects (as tracked by the write barrier). Any unreachable objects are finalized and reclaimed and any objects that survive are promoted to the next older generation (the Cocoa GC runs with anywhere from 2 to 8 generations). In reality, it may be one to several scans before an object is promoted as defined by the GC but this is the general sequence of events.

Finally, the GC will periodically run a full collection and scan the older generations for objects needing collection. Via this strategic partitioning a generational garbage collector performs an efficient collection of its objects ultimately leading to a smoother end user experience.

Resources:
Garbage Collection Programming Guide
IECC GC FAQ