Generations and the Write Barrier

Most objects die young#

Look at what a typical request handler creates: an iterator for one loop, a StringBuilder for one log line, an object to hold the request while it's handled. Every one of them is garbage a few milliseconds later, as soon as the request finishes. Meanwhile, a few objects live for the whole life of the program, like a cache, the configuration, or a pool of database connections.

Measure real programs and in most of them you see the same shape: most objects die very young, and only a few live long. That pattern is called the generational hypothesis.

Now put it together with Part 2. The cost follows live objects, and most new objects are already dead. So if the GC collects only the area where new objects are created, almost everything there is garbage. It marks and copies very little, and it frees a lot.

The generational heap#

        young generation                         old generation
[ Eden                     ][ S0 ][ S1 ]   [                                  ]
  new objects land here      survivor        objects that have lived a while
                             spaces

Every new object is created in Eden, with the same pointer bump from Part 2, inside each thread's own TLAB. When Eden fills up, the JVM collects only the young generation. That's called a minor GC, and in the collectors covered so far it stops the world while it runs:

1. Follow references from the roots through Eden and the survivor space currently in use, say S0.
2. Copy each live object into the empty survivor space, S1, the moment the walk reaches it. Marking and copying happen in the same walk. Each copied object's age goes up by 1; its age is how many minor GCs it has survived.
3. An object whose age reaches a threshold is copied into the old generation instead, or earlier, if the survivor space runs out of room. That's called promotion. The threshold is at most 15, because the age is stored in 4 bits of the object's header (a few bytes at the start of every object that the JVM uses for bookkeeping).
4. Eden and S0 now hold only garbage, so both are treated as empty again in one step. Next time, S0 and S1 swap roles.

For example, Eden holds a thousand objects and only twenty are still reachable. The minor GC copies those twenty, plus the survivors already in S0, and frees everything else at once. Its cost is twenty-odd copies, not a thousand.

This is Part 2's copying collector with a much smaller price. Instead of half the memory sitting empty, only one small survivor space does. In the Serial collector's default settings, each survivor space is about a tenth of the young generation.

The old generation fills slowly, only as objects get promoted. When it fills, the JVM collects it too, much less often, and in the simpler collectors that means mark-compact with the program stopped. Copying the whole old generation would be wasteful, because most old objects are still live (Part 5 shows a collector that copies only the old areas that are mostly garbage).

The blind spot: an old object pointing to a young one#

A minor GC is cheap because it only walks through the young generation. But that rule creates a hole:

static List<Order> orders = new ArrayList<>();  // created at startup; long since promoted to Old

void handle() {
    orders.add(new Order());   // new Order is in Eden
}                              // handle() returns: no local variable points to the Order

roots: [static orders]
              │
OLD:     [ArrayList] ──► [internal array] ──┐
                                            │
YOUNG:                         [Order] ◄────┘

A minor GC starts from the roots. The root orders leads into the old generation, and the minor GC doesn't walk the old generation, so it never reaches the Order and frees it. But the list still holds its address. That's the free-too-early bug from Part 1.

The obvious fix is to walk the whole old generation during every minor GC. The trouble is, the old generation can be gigabytes, so every minor GC would become as slow as collecting everything, and generations would be pointless.

So ask a sharper question: how can an old→young reference come into existence at all? Only two ways. Your code stores a reference into a field of an old object, which is exactly what orders.add did. Or the GC promotes an object that still points at young objects, but the GC does that copy itself, so it already knows. That means the JVM only needs to notice one thing: every time your code stores a reference into an object.

The write barrier and the card table#

When you write array[i] = order, the JIT compiler doesn't just emit the store. It adds a couple of extra instructions right after it:

store  order  into  array[i]                        // what you asked for
card_table[ address_of(array[i]) / 512 ] = DIRTY     // added by the JVM: the write barrier

• The old generation is treated as a row of 512-byte slices called cards.
• The card table is a byte array with one byte per card.
• Dividing the address of the field that was written to by 512 gives the number of the card it falls in, and the barrier marks that card's byte as dirty.

So a dirty card simply means: somewhere in these 512 bytes, a reference was stored since the last GC.

Why cards instead of a list of exact addresses? A list would grow without limit, fill with duplicates, and need coordination between threads. Writing one byte to a fixed spot costs the same every time. The trouble is, a card is imprecise: the GC later has to scan the whole card to find the reference. And the simplest collectors mark the card even when the value written is null or an old object, because checking would add a comparison to every write, and marking blindly is usually cheaper.

Now replay the minor GC. As before, it starts from the real roots, and it also treats every dirty card as a starting point, scanning the objects inside it. Any reference found there that points into the young generation is treated as one more root. This time it finds the old list's reference to the new Order, and the Order survives. Then the cards are cleared; a card that still holds a reference to a surviving young object stays dirty for next time.

The trade#

Every reference write in your program pays one tiny extra store. In return, a minor GC only looks at the young live objects and a few dirty cards, never the whole old generation. That's why allocating lots of short-lived objects in Java is cheap: they die in Eden and are never visited.

But the old generation still has to be collected eventually, and it's mostly live, possibly gigabytes of it. Marking all of that with the program stopped can take seconds. Part 4 shows how the JVM marks it while your program keeps running.

What generations cost#

If this comes up in an interview#