how garbage collection works

the picture

you know how there are two kinds of people when it comes to cleaning a room? the ones who throw out the junk and leave everything else where it is, and the ones who push all the furniture against one wall so there's one big empty space. garbage collectors are like that, plus a third kind: the person who moves everything worth keeping into a fresh, empty apartment and just walks away from the old one.

• sweep: throw out the junk, leave the furniture. quick, but now there are gaps everywhere (fragmentation).
• compact: push everything together. one big free space, but you lifted every piece of furniture you kept.
• copy: move the keepers to a new place. you only lift what you keep, but you're paying rent on two apartments.

here's all three on the exact same heap. same objects, same two roots, same garbage cycle (H and I point at each other).

mark: the part they share

all three start the same way, the way the previous chapter showed: start at the roots, follow every reference, mark everything you reach. what's left unmarked is garbage. the mark costs time proportional to the live objects (and the references between them). garbage is never visited during marking. it's just whatever didn't get a mark.

three ways to reclaim

sweep walks the whole heap, live and dead, and puts every dead object's space on a free list. nothing moves, which is simple and safe. but the free space ends up chopped into holes between survivors, and allocation becomes "search the free list for a hole that fits". in the figure, 8 cells are free and a 3-cell object still can't be placed. that's fragmentation, and the cure is to move things.

compact slides every live object down to one end of the heap. it takes three passes: work out where each object will land (its forwarding address), rewrite every reference to the new addresses, then move. the objects keep their order, and afterwards the free space is one block: allocation is a pointer bump again. the price is touching every live object several times.

copy splits memory into two halves. it copies each live object from the current half (from-space) to the empty one (to-space) the moment it finds it, leaving a forwarding address behind so later references get fixed up. the to-space itself is the work queue: a scan pointer chases a free pointer, and when it catches up, everything live has been copied. dead objects are never looked at. then the whole old half is thrown away in one go.

see that last row? copying wins wherever most objects are dead, because its cost only depends on what survives. that's exactly the situation in a young generation (most objects die young). the "half the space sits empty" price gets paid in a smart way too: young gens copy into small survivor spaces, and region-based collectors like G1 copy into whichever regions happen to be free.

doing it while the app runs

everything so far assumed the app is frozen while the GC works: a stop-the-world pause. the JVM brings every thread to a safepoint, does the work, lets them go. simple and correct, but the pause grows with the live set. mark a 10 GB live set with every thread stopped and your p99 latency is gone.

so modern collectors mark concurrently, on GC threads, while the app keeps running and keeps changing references. that breaks something. the classic way to think about it is tri-color marking:

• white: not seen yet. at the end, white means garbage.
• grey: seen, but its fields haven't been scanned yet. this is the to-do list.
• black: seen and scanned. the GC is done with it and won't look again.

marking is done when there's no grey left. the danger is the app moving a reference behind the GC's back.

an object only gets lost when both of these happen during marking:

1. the app stores a reference to a white object into a black object (black never gets rescanned, so the GC misses it).
2. the app destroys every path from a grey object to that white object (so the GC can't find it the normal way either).

a write barrier is a few instructions the JIT adds around reference stores, and each style of barrier breaks one of the two conditions:

• incremental update breaks (1): when you store a reference into a black object, grey the target. CMS used a variant of this.
• snapshot at the beginning (SATB) breaks (2): before you overwrite a reference, log the old value. everything reachable when marking started gets marked. G1 and Shenandoah do this.

if (marking_is_active) {           // a thread-local flag, cheap to check
    old = obj.f
    if (old != null)
        satb_queue.add(old)        // "this was reachable at the start, keep it"
}
obj.f = v                          // the store you actually wrote

that's the deal every concurrent collector makes: a little bit of cost on every reference store (and, for ZGC and Shenandoah, on reference loads too) in exchange for not stopping the world for the long part.