GC principles & algorithms

Overview

Every garbage collector answers the same three questions: what is garbage (reachability from roots), when to collect (generations, allocation pressure), and how to reclaim (some combination of three canonical algorithms). The concrete collectors — compared here — are all recombinations of the machinery on this page; learn it once and every GC log, tuning guide and vendor pitch becomes readable.

Key points

• Garbage = unreachable, not unused: liveness is transitive reachability from GC roots — thread stacks, static fields, JNI handles, synchronization monitors. Java traces; it never reference-counts (counting can't collect cycles without a tracing backup).
• The weak generational hypothesis — most objects die young — is the single most load-bearing empirical fact in GC design: collect a small young generation often and cheaply (survivors are few), the big old generation rarely. Promotion after surviving enough young collections.
• Stop-the-world & safepoints: to trace a consistent graph, threads are paused at safepoints (compiler-inserted poll sites). Pause cost is the whole GC trade-off currency; a single thread slow to reach its safepoint stalls everyone (time-to-safepoint matters as much as the pause itself).
• The three canonical algorithms:
  • Mark-sweep — trace, then free unmarked blocks in place. No moving, but fragments; allocation needs free lists.
  • Mark-compact — trace, then slide the live set together. Defragments, restores bump-pointer allocation; costs extra passes over the heap.
  • Copying (evacuation) — trace and move live objects to an empty space; the old space is reclaimed wholesale. Cost proportional to survivors only — perfect for young generations, wasteful for stable old data.
• Generational bookkeeping needs a write barrier: collecting the young gen alone requires knowing about old→young pointers; a small hook on every reference store records the source region in a card table (or remembered set), so old→young edges act as extra roots.
• Concurrent marking is tri-color marking: white (unvisited) / grey (found, children pending) / black (done). Collect while the app runs and the mutator can hide a live object (black→white pointer with the grey path cut) — prevented by barriers: SATB write barriers (G1, Shenandoah — log overwritten references, collect the snapshot) or incremental-update / load barriers (ZGC — colored pointers checked on every reference load, fixing addresses lazily).
• Regional heaps (G1, ZGC, Shenandoah) replace fixed semi-spaces with many equal-sized regions — enabling incremental evacuation of the regions with the most garbage first ("garbage first", literally) and pause-time targeting.
• The trade-off triangle — throughput / latency / footprint, pick two: concurrent collectors spend CPU and barrier overhead to shrink pauses; throughput collectors pause hard but waste no cycles between; low footprint forfeits both. This triangle is the entire vocabulary of the collector comparison.

Concurrent marking's tri-color machine, and where the barriers step in:

stateDiagram-v2
    state "White (unvisited)" as White
    state "Grey (found, children pending)" as Grey
    state "Black (done)" as Black
    [*] --> White: marking begins
    White --> Grey: reached by the trace
    Grey --> Black: children all visited
    Black --> [*]: marking ends
    note right of Black
        The hazard while the app runs:
        the mutator creates a black to white
        pointer while the grey path is cut,
        hiding a live object.
    end note
    note right of White
        Prevented by barriers: SATB write
        barriers log overwritten references
        (collect the snapshot), load barriers
        check colored pointers on every
        reference load.
    end note

Related

• Java memory & GC — the map — the group overview.
• JVM memory anatomy — the heap these algorithms operate on; TLABs and allocation.
• Garbage collectors compared — the concrete HotSpot collectors assembled from these parts.
• Deep dive Java — parent theme note.
• Algorithms and data structures — graph traversal is the substrate of marking.
• Deep dive Go — Go's concurrent mark-sweep: same tri-color machinery, non-generational, non-moving — a deliberately different corner of the triangle.

Citations

[1] HotSpot GC Tuning Guide — Generations [2] Jones, Hosking, Moss — The Garbage Collection Handbook [3] Aleksey Shipilëv — JVM Anatomy Quarks (GC quarks)