Generational Collection and the Write Barrier That Enables It

Every tracing collector described so far pays a cost proportional to the live set. That is the right cost to pay when most of the heap is garbage, and the wrong one when most of it is live. Real programs do not present a uniform mix: a small fraction of the objects, allocated recently, accounts for the overwhelming majority of the garbage, while the objects that have already survived for a while tend to keep surviving. Collectors that exploit this distribution collect the young region frequently and the old region rarely, and the mechanism that makes the split sound is a small amount of bookkeeping on pointer stores.

The hypothesis, and what it is not

The weak generational hypothesis states that most objects die young. Ungar’s 1984 generation scavenger is the design that made the idea practical, and the hypothesis itself is an empirical regularity rather than a theorem, and it fails in specific, recognisable ways: a program that builds a large long-lived structure incrementally allocates objects that all survive, and a program that caches everything defeats the hypothesis entirely. A generational collector still works in those cases; it simply spends more time on young collections that promote most of their input, and the promotion machinery becomes the dominant cost.

The important consequence for design is that the hypothesis justifies a ratio, not a guarantee. A young generation sized at a few megabytes, collected when it fills, will usually find that most of its contents are dead and will copy only a small surviving set into the old generation. The collection’s cost is then proportional to the survivors rather than to the size of the young region, which is why a young collection can complete in a time that does not grow with the heap.

Objects that survive a small number of young collections are promoted: copied into the old generation and thereafter left alone by young collections. The threshold is usually expressed as an age counter in the object header, incremented on each survival, and the promotion age is chosen by the runtime rather than fixed by the design. A higher threshold keeps more objects in the cheap region but copies them more often; a lower one promotes earlier and burdens the old generation with objects that would have died. The trade is measurable only against a workload, which is why runtimes expose it as a tuning parameter.

Why a young-only collection is unsound on its own

Suppose the collector decides to trace only the young generation, treating the old generation as a set of roots. That is wrong: an old object may hold the only reference to a young object, and the old object’s fields are not scanned, so the young object would appear unreachable and be collected while still in use.

Scanning the entire old generation on every young collection would restore correctness and destroy the point of the exercise, since the old generation is the large part of the heap. The alternative is to record, at the moment a pointer from old to young is stored, enough information to find that pointer later. That record is the remembered set, and the code that maintains it is the write barrier.

The invariant to preserve is directional: a young collection needs to know about every old-to-young reference. References from young to old are harmless, because the young object is scanned as part of the collection and its fields lead into the old generation where tracing stops. References from old to old are irrelevant. So the barrier fires only when a store creates or destroys a pointer that crosses the generational boundary.

/* Card marking barrier: the store side, called by compiled code. */
static inline void store_ref(struct obj *container, struct obj **field,
                             struct obj *value) {
    *field = value;
    if (value && in_old_gen(container) && in_young_gen(value)) {
        size_t card = ((char *)field - old_gen_base) >> CARD_SHIFT;
        card_table[card] = DIRTY;      /* one byte per 512-byte card */
    }
}

The check in_old_gen(container) && in_young_gen(value) is the reason barriers are described as conditional. A store into a young object never dirties anything, because young objects are scanned wholesale. A store of an old pointer into an old object is also irrelevant. Only the cross-generational case needs recording, and it is rare enough that the branch predicting “not taken” is usually correct.

Card marking versus precise remembered sets

Two families of implementation exist, and they differ in how much space the record takes and how much work the collection does to interpret it.

Card marking divides the old generation into fixed-size units, commonly 128, 256 or 512 bytes, and keeps one byte per unit in a side table. The barrier computes the card index from the field’s address and stores a dirty value. During a young collection, every dirty card is treated as a root region: the collector scans the objects within that card and follows any pointers into the young generation. Cards that contain no cross-generational pointers are dirtied anyway, so the collector scans some old objects that did not need scanning. The over-approximation is the price of a barrier that is one store and no allocation.

The card table’s size is a simple ratio: at 512-byte cards and one byte per card, the table is 1/512 of the heap, about 0.2 percent. At 128-byte cards it is 0.8 percent. Smaller cards reduce the false sharing of dirty regions, at the cost of a larger table and more entries to clear after each collection.

A precise remembered set stores the addresses of the fields or objects that contain cross-generational pointers, in a side data structure with insertion and iteration. The barrier must insert an entry, which is more expensive than a byte store and may allocate, and the set must be pruned when entries become stale. The benefit is that the collector scans exactly the objects that need scanning, with no over-approximation, and the set can be maintained per region for a region-based collector.

A third form, used in some collectors, is a store buffer of recently written pointers with no deduplication; the collector filters the buffer when it processes it. That has the cheapest possible barrier, an append to a thread-local buffer, but the buffer can fill, and the collector must handle overflow by falling back to a full scan.

The barrier’s placement, and its effect on optimization

The barrier’s cost depends on where it is emitted. In a compiler that generates code for a managed language, the barrier is inserted at every store to a reference field, which means every field assignment in the source becomes a call or an inline sequence. The optimizer can remove the barrier only when it can prove that the store cannot cross the generational boundary, which requires knowing the generation of both the container and the value. Neither is a compile-time property in a runtime that promotes objects dynamically, so the barrier usually survives optimization intact.

The barrier also constrains other optimizations. A store cannot be reordered past a safepoint in a way that would make the remembered set stale at the point the collector reads it, and a store cannot be eliminated if the object might be scanned, because the collector relies on the stored value being visible. Escape analysis that removes an allocation can also remove the barrier for stores into the escaped-away object, since the object never reaches the heap, and that is one of the reasons escape analysis is valuable in managed runtimes.

There is a subtler interaction with concurrency. A barrier that reads the container’s generation and the value’s generation without synchronization can observe a torn state during a concurrent store. Implementations either accept the imprecision, because a spurious dirty card is harmless, or use an unconditional barrier that dirties without the check. The correctness requirement is one-sided: the barrier may record extra work but must never miss a genuine cross-generational pointer.

Promotion, and the failure mode of premature tenuring

Promotion moves an object from young to old. In a copying young collector, such as the Cheney semispace design, promotion is the same operation as survival: the object is copied into the old generation instead of the survivor space. That means the young collector must allocate in the old generation during a collection, and if the old generation is full the young collection cannot complete. The usual response is to trigger an old-generation collection first, or to fail the promotion and leave the object in the young generation for another cycle.

The failure mode worth naming is premature promotion. An object that is promoted after two survivals but dies shortly afterwards ends up in the old generation, where it is only reclaimed by an expensive old collection. A workload that allocates medium-lived objects, such as session state, parsed configuration, or per-request buffers held across a slow call, can promote a large fraction of its allocation and turn the old generation into a churn region. The symptom is an old-generation collection frequency that rises with allocation rate rather than with live-set growth.

Mitigations include a larger young generation (so objects die before promotion), adaptive tenuring thresholds that observe survivor sizes, and a third space between young and old for objects that survive one collection but not many. The adaptive approach measures the survival rate at each age and moves the promotion threshold to where the marginal benefit disappears, which is a policy decision made from collection statistics rather than from source-level knowledge.

Where the split stops paying

Generational structure assumes the young region is small relative to the old. When the live set is genuinely large, as with a heap holding a multi-gigabyte in-memory index, the old generation dominates, old collections are expensive, and the young collections that are cheap do not help enough. At that point the collector must make old collections incremental or concurrent, which is the subject of concurrent marking and tri-colour barriers.

The same structure also interacts badly with large objects. An object larger than the young region cannot be allocated there, so it goes directly to the old generation, where it contributes nothing to the young collection’s efficiency and may hold pointers into the young generation that the barrier must record. Runtimes handle this with a separate large-object space and a specific rule for the barrier: stores from large objects are recorded unconditionally, or the large-object space is scanned as part of the root set.

Finally, the remembered set must be cleared or pruned after each young collection, and that clearing is itself proportional to the number of dirty cards or remembered entries, not to the number of live objects. A program that writes into old objects heavily dirties many cards and makes each young collection scan a large root region, which erodes the generational advantage from the other direction. The generational hypothesis covers allocation, not mutation, and a mutation-heavy program is the case where the split costs more than it saves.