Major GC: mark, sweep, compact

Why old space needs a different collector

A copying Scavenger needs a second region the size of the live set to copy into; that is fine for a few megabytes of young objects but impossible for a gigabyte-sized old generation. So old space uses mark-sweep-compact (MSC): find the live objects in place (mark), reclaim the dead in place (sweep), and only occasionally relocate survivors to fight fragmentation (compact). A major GC traces the entire reachable graph, not just a small region, which is why its cost is fundamentally larger — and why V8 invests so heavily in hiding that cost.

Marking: the tri-color abstraction

Marking is graph traversal with a twist that makes it pausable. Every object is conceptually one of three colors (stored as two mark bits):

• white — not yet reached (presumed dead);
• grey — reached, but its outgoing references have not been scanned yet (on the work queue / “marking worklist”);
• black — reached and fully scanned (all its references have been greyed/processed).

The algorithm:

1. Color everything white. Color the roots’ direct referents grey (push them on the worklist).
2. Pop a grey object, scan its references — color each white referent it points to grey — then color the object itself black.
3. Repeat until no grey objects remain.
4. Every object still white is unreachable → garbage.

The grey set is the frontier of the wavefront sweeping through the graph; when it drains, the trace is complete. The crucial invariant this maintains: a black object must never point directly to a white object (the “tri-color invariant”). If that held only for a stop-the-world trace it would be trivial — but V8 does not stop the world to mark, which is where it gets interesting.

Incremental and concurrent marking

A naive MSC stops all JavaScript, marks the whole heap, then resumes — a stop-the-world pause of hundreds of milliseconds on a large heap. V8 attacks this on two fronts:

• Incremental marking breaks the trace into small steps interleaved with JS execution. The engine marks a little, runs JS, marks a little more — amortising the work so no single pause is long. Steps are scheduled into idle time and during allocation.
• Concurrent marking goes further: background helper threads walk the object graph while the main thread keeps running JavaScript. The bulk of the marking work happens off the main thread entirely.

Both create the same hazard: the main thread can mutate the object graph mid-trace — store a pointer that the marker has not seen — and break the tri-color invariant by making a black object point to a white one. The marker would then finish, see that white object as unreached, and wrongly collect a live object. The fix is the write barrier, the entire subject of the next lesson: it intercepts pointer stores during marking and re-greys the affected object so the invariant holds. Hold that thread; here, just register that incremental/concurrent marking is only correct because of write barriers.

After concurrent marking, a short final atomic pause (“finalize”) re-scans the roots and any objects the barriers flagged, draining the last grey set. This final pause is single-digit milliseconds even on large heaps — that is the win.

Sweeping: reclaim white into free lists

Once marking finishes, every white object is dead. Sweeping walks the old-space pages and adds the memory occupied by white objects to per-size-class free lists — the bookkeeping that lets future old-space allocations find a hole of the right size. Sweeping does not move anything; it just records free regions. V8 sweeps concurrently and lazily: free lists are rebuilt on background threads, and a page can be swept on demand the first time an allocation needs space from it. Because sweeping touches dead objects (which are not referenced) it is naturally parallelizable and largely off the critical path.

Compaction: evacuate to defragment

Mark-sweep alone leaves fragmentation: live and dead objects are interleaved, so over time old space becomes Swiss cheese — plenty of free bytes, but no contiguous hole big enough for a large allocation. Compaction fixes this by evacuation: pick the most fragmented pages, copy their live objects to a fresh page packed tightly, and update every pointer that referenced the moved objects. This is the same copy-and-forward machinery as the Scavenger, applied selectively. Compaction is expensive (it moves objects and rewrites pointers), so V8 does it selectively — only on pages whose fragmentation justifies it, not the whole heap every cycle.