G1: Cleaning a Piece at a Time

Moving objects still freezes the program#

Part 3's old-generation collection slid every live object together, with the program stopped, so the pause grew with the amount of live old data. Concurrent marking removed the marking part of that pause. The moving part remains.

The idea is simple: instead of cleaning the whole old generation in one long pause, clean a few pieces of it in each short pause. But for that, the heap has to be made of pieces that can be cleaned on their own.

Regions#

G1 cuts the heap into many equal-sized regions, typically 1 to 32 MB each, picked so the heap has around two thousand of them. An 8 GB heap might be 2,048 regions of 4 MB. At any moment, each region has one job:

[E][O][E][ ][O][S][O][ ][E][O][O][ ][H][H][O][E] ...
 E = Eden   S = Survivor   O = Old   H = Humongous   [ ] = empty

So the young and old generations are still there, but each is just a set of regions, scattered anywhere in the heap. A young collection works as before, only on regions: when the Eden regions fill, G1 pauses briefly and copies the live objects out of every Eden and survivor region into a few empty regions. Then all the regions it copied out of are empty again, in one step. Copying out of a region like this is called evacuation.

Garbage first#

Old regions slowly fill with promoted objects. Once the old generation passes a set share of the heap (45% by default, adjusted as G1 learns), G1 starts concurrent marking, as in Part 4, and counts how many live bytes are in each old region. Regions that turn out completely empty are freed right away, without moving anything. Most, though, are a mix. Compare two 4 MB regions:

The copies need space too, so emptying X gains almost ten times as much as emptying Y, for one eighteenth of the copying. So G1 empties the regions with the most garbage first, and by default it skips regions that are more than 85% live altogether, which is where the name comes from: Garbage-First. After marking, the next few pauses each empty all the young regions plus a handful of the old regions with the least live data. Those are called mixed collections, and pause by pause they clean the old generation, cheapest pieces first.

You also set how long each pause should take, with -XX:MaxGCPauseMillis (default 200 ms). G1 learns from earlier pauses how long copying a region tends to take, and adds regions to each pause until the predicted time reaches your target. So the pause follows your target, not your heap size. It's a prediction, though, so a pause can still run over.

Who points into this region?#

Emptying region X means updating every reference to the objects that move out of it, and those references could be anywhere in the heap. Scanning the whole heap on every pause would wipe out the benefit. It's Part 3's blind spot, only wider: not "who in the old generation points into the young one?" but "who anywhere points into this region?"

The fix is the same idea: a write barrier, this time after every reference store, with one check:

// you wrote:  obj.field = value;
obj.field = value
if (value != null and region_of(obj) != region_of(value))
    record "this card holds a reference into region_of(value)"

Background threads later take those records and file each one under the region it points into. So every region G1 might empty keeps a remembered set: the places elsewhere in the heap that hold references into it. To empty region X, G1 scans only X's remembered set.

So in G1, one reference store can run two barriers. Before it, and only while marking runs, the SATB barrier from Part 4 records the old value. After it, always, the cross-region barrier records where the new reference points. That's part of the price of short pauses.

Humongous objects, full GCs, and the limit#

Huge objects, like a big array, would be expensive to copy. So any object of at least half a region is humongous: it gets its own run of consecutive regions, and normal collections don't move it. When it dies, its regions are simply freed.

Evacuating needs somewhere to copy into, so G1 always needs some empty regions. If the program allocates faster than G1 cleans, or marking starts too late, they run out, and G1 falls back to a full GC: stop everything and compact the entire heap, the long pause all of this was designed to avoid. Full GCs in a G1 log usually mean the heap is too small or the allocation rate is too high for the collector to keep up.

And one limit remains. The copying itself still happens with the program stopped, so every pause has to copy at least the young survivors plus the old regions it chose. To go below that floor, a collector would have to move objects while the program keeps running. That's Part 6.

What G1 trades#

If this comes up in an interview#