Tracing: Mark, Then Reclaim

Marking costs live objects, not garbage#

Start from Part 1's picture. The roots are your local variables and static fields, and an object is live if you can reach it by following references from a root. Tracing walks exactly that: it starts at every root, follows every reference, and marks each object it reaches, skipping any object that's already marked. When the walk ends, marked means live and unmarked means garbage.

Look at what the walk never does. It never visits a garbage object, because nothing live leads to one. Marking never finds garbage; garbage is simply whatever didn't get marked.

That gives tracing its most important property: its cost grows with the number of live objects, not with the amount of garbage. Say the heap holds a million objects and only ten thousand are still reachable. Marking touches those ten thousand and never looks at the other 990,000. Double the garbage, and marking takes about as long.

roots ──► [■] ──► [■]        [■] ◄── roots
                       │
                       ▼
                      [■]

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]   ← garbage: never visited
■ = marked (4 objects visited)    [ ] = never touched

Keep this property in mind. Everything later in this series, including the split into generations in Part 3, is built on it.

Three ways to get the space back#

Marking only tells the GC which objects are garbage. The memory they occupy still has to be turned into free space that new can use. There are three ways to do it.

Sweep. Walk through the heap and add every unmarked object's space to a list of free gaps, called a free list. That's simple, but the gaps stay where the dead objects were:

[live][free 16 B][live][free 24 B][live][free 8 B]

There are 48 bytes free in total, yet a 32-byte object fits nowhere, because no single gap is big enough. This is called fragmentation. Allocation also gets slower, because every new has to search the list for a gap that fits.

Compact. Slide every live object toward one end of the heap, so all the free space becomes one continuous block at the other end. The trouble is that moving an object changes its address, so every reference to it has to be updated, both inside other objects and in the variables on every thread's stack. In the simplest design, all of that happens before the program is allowed to continue (Part 6 shows a collector that fixes references lazily instead).

before:  [A][ ][B][  ][C @0x2F00][ ]      stack: order ──► 0x2F00
after:   [A][B][C @0x1A80][            ]      stack: order ──► 0x1A80  (updated)

The JVM can do this because it knows exactly which memory slots hold references and which hold plain numbers. The JIT compiler (the part of the JVM that turns frequently run code into machine code) records where the references are at the points where a thread can be stopped (the last section explains those points). C can't do this: in C, an address and an ordinary number look exactly the same, so a collector can't safely rewrite either.

Copy. Split the space into two halves and only ever allocate in one. When the GC runs, it copies each live object into the empty half, packed tightly, and updates the references. Now the old half holds nothing but garbage, so the whole half is simply treated as empty again, in one step, with no walking at all. The cost depends only on how much is live, which, as the first section showed, is the part you want to pay for. But it has a real price: in this simple two-halves version, half the memory sits unused. (Part 3 shows how the JVM shrinks that to one small spare area.)

Why one free block makes new cheap#

Compacting and copying both end with one continuous free block, and that turns allocation into almost nothing. The JVM keeps a pointer to the start of the free block, often called top. To allocate an object of N bytes, it hands out the current pointer and moves it forward by N. This is called bump-pointer allocation, and it takes a few machine instructions.

[ live objects ][ Order 40 B ][ User 24 B ][        free         ]
                                            ▲ top
new Order() → address = top; top = top + 40
new User()  → address = top; top = top + 24

There's one catch. With many threads, all of them would be moving the same pointer, and they'd have to take turns. So each thread gets its own private chunk of the free block, called a TLAB (thread-local allocation buffer), and bumps its own pointer inside it, without any locking. When a thread's chunk runs out, it grabs a new one.

So new in Java is cheap, and that's a direct result of how the GC reclaims space. A sweep-only design, with a free list it has to search, can't match that.

The pause#

All of this happens while your program is supposedly running, and that's a problem. Tracing walks a web of references, and your threads keep changing that web: storing a new reference here, dropping one there. If the program moves a reference at the wrong moment, the walk can miss a live object, and the GC would free memory that's still in use. (Part 4 shows exactly how that happens, and how modern collectors prevent it.)

The simplest fix is to stop every application thread, run the GC, and then let them continue. That's called stop-the-world, or STW. It's always correct, because nothing can change while the GC works. But your program freezes, and the freeze gets longer with more live data to mark and more objects to copy.

Stopping a thread isn't instant. The JVM can't freeze a thread at any random machine instruction, because at most instructions it doesn't know which CPU registers are holding references at that moment. So the JIT adds a quick check at specific places in the compiled code, such as when a method returns and when a loop jumps back to its start (for very long counting loops, once every batch of iterations). At those places, called safepoints, the JVM knows exactly where every reference is.

           GC raises flag
                 │
thread 1  ───────┼──■ parked
thread 2  ───────┼──────■ parked
thread 3  ───────┼────────────■ parked (finished its loop iteration)
native    ░░░░░░░┼░░░░░░░░░░░░  counts as stopped
                 │◄──────────►│ time to safepoint, then the GC works

To stop the world, the GC sets a flag. Each thread sees it at its next safepoint and parks itself, meaning it stops and waits. The GC begins only once every thread running Java code has parked; threads off in native code, or already waiting, count as stopped. So a pause is mostly two parts: the time for the slowest thread to reach a safepoint, plus the GC's own work.

Two goals, and what's next#

From here on, every collector balances two goals:

• Throughput: the share of CPU time your program gets for its own work, rather than for GC. A nightly batch job cares about this: finish as fast as possible, and long pauses are fine.
• Latency: the length of the longest single pause. A web service cares about this, because a two-second pause is a two-second request for whoever hit it.

So far, every collection marks all live objects and then sweeps, compacts or copies, with the program stopped. The cost tracks live data, and that raises the obvious question: where in the heap are the fewest live objects? If the GC could collect just that area, it would do little work and free a lot. Part 3 shows that such an area exists, and what it takes to collect it on its own.

If this comes up in an interview#