Garbage Collection

Automatically determining at runtime which objects are no longer reachable and reclaiming them—from mark-sweep to generational to concurrent tri-color marking. Each GC algorithm strikes a different balance between throughput and latency, while write barriers must be embedded by the compiler at every pointer write.

Overview

Manual memory management (C/C++'s malloc/free, Rust's ownership system) places the responsibility for freeing memory on the programmer or the type system. Garbage Collection (GC) takes a different approach: automatically determining at runtime which objects are no longer reachable and reclaiming the memory they occupy. GC is the runtime foundation for all languages with GC (JVM/Go/.NET/JS/Python)—compilers must not only generate code but also embed GC collaboration points (safepoints, write barriers) into the generated code. This article covers four core GC algorithms and the requirements they impose on compilers.

Core Concepts: Reachability and the Root Set

The fundamental question of GC is: Which objects are still alive? Definition: Starting from the root set (global variables, local variables on the stack, registers), all objects reachable via pointers are considered alive; the rest are garbage.

Root Set = {Global Variables, Each Word on Each Thread's Stack, Active Registers}
Starting from the Root Set, trace pointers via BFS/DFS → Objects reached are marked as live
Unreached objects → Garbage, can be reclaimed

All GCs perform this traversal. The differences lie in when it happens, how unreached objects are reclaimed, and the impact on the mutator (application code).

Four Core Algorithms

1. Mark-Sweep: The Basics

Mark Phase:
  Starting from the root set, traverse the object graph,
  setting the mark-bit for each reached object

Sweep Phase:
  Traverse the entire heap,
  reclaim all unmarked objects,
  clear mark-bits (for the next round)

• Cost: The mark phase traverses the volume of live objects; the sweep phase traverses the entire heap (including dead objects), scanning even large amounts of unused memory.
• No object movement → No need to update pointers → Simple, suitable for languages like C/C++ where objects cannot be moved (e.g., Boehm GC).
• Fatal Flaw: Fragmentation—Alternating allocation and reclamation causes the heap to gradually fragment into small pieces. Even if total free memory is sufficient, large object allocations may fail.

2. Copying (Semispace, Cheney): Trading Space for Time and Compactness

Divide the heap into two halves (from-space and to-space), using only one half at any given time:

Collection:
  Starting from the root set, traverse live objects via BFS/DFS
  Copy live objects from from-space to to-space (packed tightly at one end)
  Update all pointers pointing to these objects (from old address → new address)
  Reclaim the entire from-space (for the OS, this is just one large block of memory)
  Swap the roles of from and to

• Compactness—Live objects are packed tightly together, eliminating fragmentation.
• The traversal process itself is BFS—Cheney's copying collector uses BFS traversal, which naturally achieves compactness.
• Cost: Only half the heap is usable, resulting in 50% memory utilization. For languages with GC (JVM, Go), this cost is worth it in exchange for no fragmentation and allocation that simply moves a pointer (bump allocator).

3. Generational GC: Leveraging "Most Objects Die Young"

Empirical observation (weak generational hypothesis): Most objects become garbage shortly after allocation (e.g., temporary objects allocated in loop bodies); a few long-lived objects tend to continue living.

Generational GC divides the heap into a Young Generation (nursery) and a Old Generation (tenured):

Young Generation: Frequent collection (e.g., triggered every few MB of allocation), using copying—few survivors, so the copying cost is low.
Old Generation: Infrequent collection (e.g., triggered only when memory is nearly full), using mark-sweep or mark-compact.
Objects that survive N collections in the young generation → promoted to the old generation.

Key Engineering Challenge: Cross-generational references. When an old generation object points to a young generation object, scanning only the young generation would miss this reference (since the root set does not include the old generation). Solution: The old generation maintains a remembered set—recording "which old generation cards (cards) might contain pointers to the young generation." During young generation GC, the old generation cards in the remembered set are added to the root set.

Write Barrier: Maintaining Cross-Generational References

A small piece of code is inserted by the compiler every time a pointer is written (*p = q):

write_barrier(p, q):
    if p is in the old generation and q is in the young generation:
        Mark the card containing p as dirty → GC will scan this card
    *p = q

This barrier is directly generated by the compiler at every pointer write—it is not interpreted at runtime but embedded as machine code. JVM's G1/Shenandoah, Go's GC, and V8's Oilpan all rely on the compiler inserting write barriers.

Compiler optimizations are friendly to write barriers: If the compiler can prove that p was just allocated (and thus must be in the young generation), it skips the barrier; if the same p is written to multiple times in a loop, the compiler may keep only the first barrier (subsequent writes do not change the card state).

Concurrent GC: Mutator Does Not Pause (or Pauses Briefly)

Both mark-sweep and copying require that "the mutator cannot modify the object graph during scanning"—this implies a Stop-The-World (STW) pause. Most of the work in modern GCs can run concurrently with the mutator:

Tri-Color Invariant

The theoretical foundation of concurrent mark algorithms, dividing objects into three categories:

• White: Not yet marked (initial state, could also be garbage)
• Gray: Marked, but its internal pointers have not yet been scanned (in the worklist)
• Black: Marked and all internal pointers have been scanned

Invariant: At the end of marking, no black object holds a pointer to a white object. Once this invariant is violated (e.g., the mutator writes a pointer to a white object into a black object that has finished marking), that white object may be missed → incorrectly reclaimed.

Ways to maintain the invariant: Either intercept writes that violate the invariant during scanning (using a write barrier to capture "black→white" pointer links), or allow brief missed markings and fix them up later (when the mutator writes p.field = q and p is black, q is white, mark q as gray and re-enqueue it). Go's GC uses the latter approach.

Read Barrier

While write barriers intercept "writes," read barriers intercept "reads": When reading a white object, mark it as gray first. Baker's concurrent copying collector uses read barriers—all pointers read by the mutator must point to to-space, and forwarding is performed at the moment of reading.

Choosing between write barrier and read barrier depends on whether writes or reads are more frequent—most systems choose write barriers (writes are fewer than reads, resulting in lower barrier overhead).

GC Requirements for Compilers

GC is not an independent module that works once the compiler is done—the compiler must embed GC support when generating code:

• Safepoints: GC cannot happen at any moment—the compiler inserts safepoint checks at loop back-edges (loop headers) or function calls. The GC suspends threads only at safepoints.
• Root Map: The compiler generates an active pointer map for local variables/registers for each safepoint (indicating which registers/stack locations currently hold GC-visible pointers). The GC uses this to scan the root set.
• Write Barrier Inlining: If barriers incur high overhead (e.g., function calls every time), they can slow down write-intensive code by 10×. Compilers implement barriers as inlined instructions, taking the slow path only when recording is necessary.

References

• Jones/Hosking/Moss: "The Garbage Collection Handbook" — The authoritative reference in the field of GC
• Wilson (1992): "Uniprocessor Garbage Collection Techniques" — An early survey of GC
• Go GC: src/runtime/mgc.go — Industrial-grade concurrent marking, with clear design documentation

Keywords: garbage collection, GC, mark-sweep, copying, semispace, Cheney, generational GC, weak generational hypothesis, write barrier, read barrier, card marking, remembered set, tri-color invariant, concurrent GC, stop-the-world, STW, safepoint, root map, compaction, fragmentation, bump allocator, nursery, tenure