# How Garbage Collectors Actually Work

> The engineering deep dive behind automatic memory management: reference counting vs. mark-and-sweep, why generational and concurrent collectors exist, and how to read a real GC log and tune the knobs that matter.


---

# How Garbage Collectors Actually Work

You know garbage collection exists: you allocate objects, stop referencing them, and eventually the memory comes back without a `free()` call. [Memory & Garbage Collection, Explained](/guides/memory-and-garbage-collection) covers that mental model - reachability, a gentle pass at mark-and-sweep, why pauses happen. This guide starts where that one stops. It's the algorithm-level view: the two competing ideas GC is built from, why almost no production collector uses either one in its pure form, and what to actually do when a GC log says your service is spending too much time collecting.

This is language-agnostic on purpose. Whether you write [Java](/guides/java-from-zero), [C#](/guides/csharp-from-zero), [Go](/guides/go-from-zero), [Python](/guides/python-from-zero), or [JavaScript](/guides/javascript-from-zero), your runtime's collector is some combination of the ideas in these three phases. [Rust](/guides/rust-from-zero) is the interesting exception - no GC at all - and Phase 3 explains why that trade-off works.

## The phases

1. **[Reference Counting and Mark-Sweep, the Two Basic Ideas](01-reference-counting-and-mark-sweep.md)** - the two foundational strategies: count references and free at zero, or trace reachability from roots and sweep the rest. What each gets right, and the cycle problem that reference counting can't solve alone.
2. **[Generational and Concurrent Collectors](02-generational-and-concurrent-collectors.md)** - why "most objects die young" reshapes the whole design, and how tri-color marking lets a collector work while your program keeps running instead of freezing it.
3. **[Reading and Tuning a Real GC](03-reading-and-tuning-a-real-gc.md)** - what a GC log actually tells you, the few settings worth touching, and why reducing allocations beats fighting the collector. Plus Rust's alternative: no collector, ownership enforced at compile time.

By the end, a GC log stops being noise, a `-Xmx` flag stops being folklore, and "why doesn't X language just use a GC" has a real answer instead of a vibe.


---

# Reference Counting and Mark-Sweep, the Two Basic Ideas

Every garbage collector, from CPython's to the JVM's most exotic low-latency engine, is answering one question: which heap objects can the program no longer reach? There are exactly two independent ways to answer it, discovered decades ago and still the foundation of everything built since. One counts. The other traces. Understanding both - and precisely where the first one breaks - explains almost every GC design decision that follows in this guide.

## Reference counting: count who points at you

The idea is mechanical and local. Every object carries a hidden counter: how many references currently point at it. Each time a reference is created - assigned to a variable, stored in a list, passed as an argument - the counter goes up. Each time a reference goes away - the variable goes out of scope, gets reassigned, the containing object is freed - the counter goes down. The moment a counter hits zero, nothing in the program can reach that object anymore, so it's freed immediately, right there, synchronously - no separate collection pass, no pause where the whole program stops to hunt for garbage, just reclamation spread evenly across execution instead of bunched into a collection cycle.

CPython uses this as its primary mechanism. Every Python object has a `refcount` field baked into its C struct; `sys.getrefcount()` reads it directly.

```python
import sys

a = []
print(sys.getrefcount(a))   # 2: one for `a`, one for the getrefcount() argument itself

b = a
print(sys.getrefcount(a))   # 3: a, b, and the call argument

del b
print(sys.getrefcount(a))   # back to 2
```

*What just happened:* assigning `b = a` didn't copy the list - it added a second reference to the same object, and the refcount went up. `del b` removed that reference and the count dropped. If it had reached zero, CPython would have freed the list's memory on the spot, no separate GC pass involved.

**Why it's attractive.** Reclamation is immediate and spread out - no stop-the-world pause because there's no "the world" to stop, just one decrement at a time. An object's lifetime is exactly the span during which something points at it. This is part of why Swift and Objective-C chose reference counting (ARC) as their entire memory model, not just a helper: predictable, immediate deallocation matters where a GC pause would be a dropped frame.

**Why it's not enough on its own.** Every reference count change is extra work on every mutation - assign a pointer, touch a counter, and under multithreading that counter needs synchronized increments, which is genuinely expensive (part of why CPython's GIL exists in the shape it does). But the disqualifying flaw is structural, not a performance tax: **reference counting cannot collect cycles.**

## The cycle problem

Picture two objects that reference each other and nothing external references either of them anymore.

```python
class Node:
    def __init__(self):
        self.other = None

a = Node()
b = Node()
a.other = b   # a's refcount: 1 (from variable `a`)
b.other = a   # b's refcount: 2 (from variable `b` AND a.other)
              # a's refcount is now 2 (from variable `a` AND b.other)

del a
del b
# a and b are both unreachable from any root now -
# but a.other still points to b, and b.other still points to a.
# Neither refcount ever reaches zero. Pure reference counting leaks this.
```

*What just happened:* deleting the variables `a` and `b` removed the *external* references, but the two objects still reference each other. Each one's count drops from 2 to 1 - never to 0. A pure reference-counting collector would leave this pair sitting in memory forever: unreachable from the program, yet mutually "alive" by the counting rule. This is the exact shape of a doubly-linked list, a parent-child UI tree with back-pointers, an observer that holds its subject and vice versa - all common, all cyclic.

📝 **Terminology.** A **reference cycle** is a set of objects that reference each other (directly or through a chain) but that no root - no live variable, no global, no stack frame - reaches from outside the set. They're garbage by any reasonable definition, but invisible to counting alone.

**CPython's real answer.** Because pure refcounting leaks cycles, CPython runs two collectors, not one. Refcounting handles the vast majority of objects (strings, temporaries, non-circular structures) and frees them instantly. Layered on top is a periodic **cycle detector** - a generational tracing collector (Phase 2's subject) that runs occasionally, specifically to find and break cycles that counting missed. `gc.collect()` triggers it manually; it also runs automatically based on allocation thresholds.

## Mark-and-sweep: trace from the roots instead

The other founding idea sidesteps the counting problem by asking a global question instead of a local one: not "does anything point at me," but "can the program reach me *at all*, by any path, starting from what it definitely still needs?"

📝 **Roots** are the starting points a collector trusts as automatically live: local variables on every thread's call stack, global/static variables, and CPU registers holding a reference at the moment of collection. Nothing else gets to start a chain.

The algorithm runs in two explicit passes:

**Mark.** Start at every root. Follow each reference to the object it points at, flag that object as reachable, then follow every reference *that* object holds, and so on - a graph traversal (depth-first or breadth-first, either works) that visits every object reachable by any path at all. When it's done, every live object carries a mark.

**Sweep.** Walk the entire heap linearly, object by object. Anything without a mark was never reached from any root by any path - it's garbage, full stop, cycle or no cycle - and its memory returns to the allocator's free list. Clear all marks in preparation for the next cycle.

```mermaid
flowchart LR
  Roots["roots<br/>(stack, globals)"] --> A --> B
  Roots --> D
  B <--> C["cyclic pair<br/>B ↔ C"]
  E["E ↔ F<br/>(unreachable cycle)"] <--> F
```

*Reading this:* `A`, `B`, `D` are reached by tracing from the roots, so they're marked live - including `B`, even though it's part of a `B ↔ C` cycle, because `B` is *also* reachable from `A`. `C` gets marked too, by extension. `E` and `F` reference each other but nothing traces to either of them from a root - unmarked, and swept. This is the direct answer to Phase 1's cycle problem: mark-and-sweep doesn't care whether objects reference each other, only whether a root can reach them - a cycle with no root reference is exactly as dead as a single unreferenced object.

**The cost profile is the mirror image of reference counting.** No per-mutation overhead - assigning a pointer is a plain pointer assignment, nothing to increment. But reclamation isn't immediate: garbage sits unreclaimed until the next full trace runs, and that trace needs a moment where the object graph holds still - the root of the stop-the-world pause from the intro-level guide. Making that trace fast, frequent, and non-disruptive without giving up its cycle-safety is where the rest of this guide goes next.

Try it yourself - allocate objects, drop a root, and step through mark-and-sweep deciding what survives:

```playground-gc
```

```quiz
[
  {
    "q": "Two objects, A and B, reference only each other. No variable or global references either one. What does pure reference counting do?",
    "choices": ["Frees both immediately, since neither is reachable from a root", "Leaks both - their counts never reach zero because they reference each other", "Frees only A, since it was created first", "Throws an error because a cycle was detected"],
    "answer": 1,
    "explain": "Reference counting only tracks how many pointers reference an object, not whether a root can reach it. A and B keep each other's count above zero forever, even though nothing external can reach either one."
  },
  {
    "q": "In mark-and-sweep, what makes an object eligible to be swept?",
    "choices": ["Its reference count reached zero", "It was allocated more than one collection cycle ago", "No root can reach it by any chain of references, cyclic or not", "It has no methods that mutate its own fields"],
    "answer": 2,
    "explain": "Mark-and-sweep traces reachability from roots. Anything not visited during the mark phase - regardless of how many other objects reference it, including cyclically - gets swept."
  },
  {
    "q": "Why does CPython run a separate cycle-detecting collector on top of reference counting instead of relying on refcounts alone?",
    "choices": ["Refcounting is too slow for large objects", "Refcounting cannot detect or free reference cycles, since mutual references never bring a count to zero", "The cycle detector is only used for debugging, not real collection", "Refcounting only works for integers and strings"],
    "answer": 1,
    "explain": "Refcounting handles acyclic garbage instantly and cheaply, but structurally can't see cycles - two objects that only reference each other never hit zero. CPython layers a periodic tracing collector on top specifically to catch what counting misses."
  }
]
```


---

# Generational and Concurrent Collectors

Phase 1 left mark-and-sweep with a real weakness: to trace reachability safely, it wants the object graph to hold still, and tracing the *entire* heap every time is slow. Two independent insights fix this, and nearly every collector shipping today - the JVM's, Go's, V8's, .NET's - is built from some combination of them. One shrinks the *amount* of heap you trace on a typical pass. The other lets you trace *while the program keeps running*, instead of freezing it. They're separate ideas that compose.

## The generational hypothesis

Watch any real program's allocations and a pattern jumps out: the overwhelming majority of objects die almost immediately. A temporary string built inside a loop, a request object that lives for one HTTP call, an iterator that exists for a single `for` loop - allocated, used briefly, unreachable within microseconds. A small minority - caches, long-lived services, configuration objects - stick around for the life of the program. This observation has a name.

📝 **The generational hypothesis**: most objects die young. Empirically true across almost every language and workload measured, which is why it drives the internal structure of most production collectors.

If most garbage is young garbage, tracing the *whole* heap to find it is wasted effort - you're re-scanning a pile of old, long-lived objects over and over just to confirm, again, that they're still alive. The fix: stop treating the heap as one region. Split it by age.

```mermaid
flowchart LR
  subgraph Young["Young generation"]
    Eden["Eden (new allocations)"]
    Surv["Survivor space"]
  end
  Old["Old generation (long-lived)"]
  Eden -->|"survives a few collections"| Surv
  Surv -->|"keeps surviving"| Old
```

New objects are born in the **young generation**. A **minor collection** traces and sweeps *only* that region - it's small, so it's fast, and because most young objects are already dead, a minor collection reclaims a lot of memory for very little work. Objects that survive several minor collections get promoted into the **old generation**, which is collected far less often by a **major** (or full) collection - a bigger, slower pass, but one that runs rarely because the old generation mostly holds things that actually are still needed.

The payoff compounds: the young generation gets collected constantly at near-zero cost per collection, while the expensive full-heap trace happens rarely enough that its cost amortizes away. This single design decision - separating by age and collecting the young generation disproportionately often - is responsible for most of the practical performance of a modern tracing GC. It's why a JVM service doing heavy allocation still keeps sub-millisecond typical pause times: nearly every pause is a cheap minor collection, and full collections are the rare exception, not the rule.

One wrinkle: an old object can reference a young one (a long-lived cache pointing at a freshly allocated value). A naive minor collection that only scans the young generation would miss that reference as a root and wrongly reclaim the young object. Collectors handle this with a **write barrier** - a small check inserted at every pointer write that records old-to-young references in a side table (a "remembered set"), so a minor collection can treat those recorded slots as extra roots without re-scanning the entire old generation.

## Concurrent collection and the tri-color invariant

Generations shrink *how much* gets traced. The other lever is *whether the program has to stop* while tracing happens at all. A naive mark phase needs a stable graph - if your code mutates references while the collector is mid-trace, the collector can lose track of what's reachable and free something still in use. The blunt fix is stop-the-world - freeze every thread, trace, resume; the refined fix is to trace **concurrently**, marking objects while application threads keep running, which is where modern low-pause collectors (Go's, the JVM's ZGC and Shenandoah, .NET's) spend their engineering effort.

To mark concurrently without corrupting the trace, collectors use **tri-color marking**, a bookkeeping scheme that makes "am I done, and is it still correct?" answerable at every point mid-trace, not just at the end.

📝 **Tri-color marking**: every object is white (not yet visited - assumed garbage), grey (visited, but its own references not yet scanned), or black (visited *and* fully scanned - confirmed live). Marking starts with all objects white and the roots grey, and proceeds by picking a grey object, scanning its references (turning any white targets grey), then coloring it black. Marking is complete when no grey objects remain: everything left white is genuinely unreachable.

```mermaid
flowchart LR
  R["roots"] --> A["A (black)"]
  A --> B["B (grey - queued)"]
  B --> C["C (white - not yet seen)"]
  D["D (white - unreachable)"]
```

*Reading this:* `A` has been fully scanned (black). `B` was discovered through `A` and is queued to have its own references scanned (grey). `C` hasn't been reached yet but will be, once `B` is processed. `D` is white and reachable from nothing - if marking ends with `D` still white, it's swept as garbage.

The danger with concurrent marking is a mutation that happens *during* the trace: your program runs a line of code that makes a black (already-scanned, "done") object point at a white (not-yet-seen) object, while simultaneously dropping the only grey-or-black reference to that white object. The collector, having already finished scanning the black object, never revisits it - so it never discovers that new white target, and incorrectly sweeps something still reachable. This is the exact bug tri-color marking exists to prevent.

📝 **The tri-color invariant**: a black object must never point directly at a white object. The instant application code would create that edge, the collector intervenes.

The mechanism is the same write barrier from the generational section, doing different work: on every pointer write during a concurrent mark phase, the barrier checks whether it's about to break the invariant, and if so, either colors the new target grey immediately (so it gets scanned) or colors the source object back to grey (so its references get re-checked). Either fix keeps the invariant intact without stopping the world. Real concurrent collectors still take brief stop-the-world pauses - to snapshot the initial roots, and to finalize - but the bulk of the marking work, the part that used to freeze your whole program, happens while it keeps running.

Watch reachability get traced and swept step by step:

```playground-gc
```

```quiz
[
  {
    "q": "Why does splitting the heap into young and old generations make garbage collection faster overall?",
    "choices": ["It lets the collector skip tracing altogether for old objects forever", "Most objects die young, so frequently collecting only the small young generation reclaims most garbage cheaply, while the rare full-heap trace amortizes its cost", "It reduces the total amount of memory the program can allocate", "Old objects are automatically assumed to be garbage without checking"],
    "answer": 1,
    "explain": "The generational hypothesis says most objects die young. Collecting the young generation often and cheaply catches most garbage; the old generation is traced far less often because it mostly holds things still genuinely in use."
  },
  {
    "q": "In tri-color marking, what does it mean for an object to be grey?",
    "choices": ["It has been permanently deemed garbage", "It hasn't been visited by the collector at all yet", "It has been visited but its own outgoing references haven't been scanned yet", "It's an old-generation object being demoted back to young"],
    "answer": 2,
    "explain": "Grey is the 'in progress' state: the collector has reached the object but still needs to scan its references before marking it black (fully processed)."
  },
  {
    "q": "What does a write barrier prevent during concurrent marking?",
    "choices": ["The program from allocating any new objects during collection", "A black (fully scanned) object from ending up pointing directly at a white (unscanned) object, which would hide it from the collector", "Two threads from allocating memory at the same address", "The old generation from ever being collected"],
    "answer": 1,
    "explain": "That edge violates the tri-color invariant - if a black object gains a pointer to a white object with no grey/black reference keeping it visible, the collector may never revisit it and could wrongly sweep something still reachable. The write barrier intercepts the pointer write and fixes the coloring."
  }
]
```


---

# Reading and Tuning a Real GC

Phases 1 and 2 built the theory: counting versus tracing, generations, concurrent marking. None of it matters if you can't look at a running system and tell whether the collector is a problem. This phase closes the loop - reading the log a real collector emits, knowing which settings are worth touching, and the move that beats tuning almost every time.

## What a GC log actually says

Every production collector can emit a log line per collection. The fields differ by runtime, but the shape is universal - strip away the syntax and a JVM G1 log line and a Go GC trace line are reporting the same four facts.

```text
[12.487s][info][gc] GC(42) Pause Young (Normal) (G1 Evacuation Pause)
    5120M->1830M(8192M) 14.221ms
```

Read it left to right: **what** ran (a young/minor collection - cheap, expected to be frequent, versus a full/major collection - expensive, rare), **heap before → heap after** (5120 MB live before, 1830 MB after - the difference, 3290 MB, is what got reclaimed), **heap capacity** (8192 MB total, so this heap is nowhere near full), and **pause time** (14.221ms - how long application threads were actually stopped for this collection).

Three questions answer almost everything you need from a stream of these lines:

- **Which generation keeps collecting?** If you see wall-to-wall young collections and almost no full collections, the generational split is working as intended. If full collections show up often, objects are being promoted to the old generation faster than expected - which usually means something is living longer than it should (a cache, a listener, an accidental reference), the exact leak shape from the intro-level guide's Phase 3.
- **Is the heap shrinking back down after each collection, or creeping up over time?** `5120M->1830M` shrinking back to roughly the same floor every time is healthy - garbage in, garbage out. A floor that rises collection after collection (`1830M`, then `2400M`, then `3100M`, never coming back down) is the log-level signature of a real leak: reachable memory that's growing, not being missed by the collector.
- **Are pause times acceptable for what you're building?** 14ms is invisible to a batch job and possibly noticeable in an audio pipeline. "Good" pause time is entirely defined by your latency budget, not by a universal number.

## The knobs that matter, and the ones that don't

**Heap size** is the one setting nearly every runtime exposes and the one most worth setting deliberately (the JVM's `-Xmx`/`-Xms`, Go's `GOGC` and newer `GOMEMLIMIT`, Node's `--max-old-space-size`). A heap that's too small forces frequent, sometimes full, collections because the collector is constantly under pressure to reclaim space; the CPU cost of collection rises to fill the gap. A heap that's too large means the collector rarely triggers - fewer pauses - but a full collection, when it finally happens, has more live data to trace, so each individual pause takes longer. In containers, set this explicitly: a JVM that doesn't know it's confined to a 512MB container will assume it owns the whole host and get OOM-killed, not garbage-collected out of the problem.

**Generation sizing** (the young/old ratio, where the runtime exposes it) is worth touching only after you've read the logs and confirmed objects are getting promoted before they should. A young generation too small promotes short-lived objects into the old generation because they didn't die fast enough to be caught by a minor collection - undoing the entire benefit of Phase 2's generational split. This is a real, measurable problem, but a narrow one: diagnose it from promotion rates in the log, don't guess at it.

**What rarely helps:** switching collector algorithms (G1 vs. ZGC, say) as a first move, or hand-tuning a dozen obscure flags copied from a blog post without reading your own logs first. Different collectors trade throughput for pause time in different ways, and that trade-off is real - but it's the second move, made after you know *what* is wrong from the logs, not the first move made instead of looking.

## The move that beats tuning: allocate less

Here's the plain order of operations, and it's the same one both the Java and Go per-language guides land on independently: **the collector's total cost is roughly proportional to how much garbage you create**, not to any setting you can flip. A collector spending too much time collecting is very often a program creating unnecessary short-lived garbage in a hot path - a string concatenated in a loop instead of built once, an object allocated per iteration that could be reused, a data structure copied when a reference would do.

Reducing allocation pressure fixes the actual cause: fewer objects born means fewer minor collections, less promotion pressure, and a smaller working set for any eventual full collection. Tuning a heap size or collector flag around a wasteful allocation pattern treats the symptom - it can buy headroom, but the underlying cost is still there, and it comes back the moment load increases. Profile allocations first (both Java and Go guides show the tools for this in their own performance phases); tune the collector second, with log evidence in hand for what specifically is going wrong.

## Rust's different bet: no collector at all

Every collector in this guide - counting, tracing, generational, concurrent - exists to answer one question automatically at runtime: is this object still reachable? [Rust](/guides/rust-from-zero) answers a version of that question at **compile time** instead, through ownership and borrowing: every value has exactly one owner, the compiler tracks when that owner goes out of scope, and memory is freed deterministically at that point - no tracing, no pause, no runtime collector thread at all.

This isn't a smaller or faster garbage collector. It's the reference-counting insight from Phase 1 (deallocation tied to a countable, trackable notion of "still needed") pushed to its extreme: instead of a runtime counter checked at each mutation, the compiler proves ownership statically and inserts the `drop` calls itself. The trade is real and openly acknowledged by the language: you spend more effort upfront satisfying the borrow checker, in exchange for zero GC pauses and no runtime tracing cost, ever. For latency-critical systems where even ZGC's sub-millisecond pauses are unacceptable, that trade is often exactly right; for a good part of everyday application code, a well-tuned generational collector is genuinely less work for a comparable result. Both are legitimate engineering answers to the same underlying problem - they just move the cost to a different phase of the program's life.

```quiz
[
  {
    "q": "A GC log shows the heap floor after each collection rising from 1830M to 2400M to 3100M over time, never returning to its earlier level. What does this most likely indicate?",
    "choices": ["The heap size is set too high and should be lowered", "A real memory leak - reachable memory is genuinely growing, not just failing to be collected promptly", "The collector is broken and not running at all", "This is normal and expected behavior for any long-running program"],
    "answer": 1,
    "explain": "A shrinking-back-down floor after each collection is healthy. A floor that climbs collection after collection means live, reachable memory keeps growing - the collector is doing its job correctly, but something in the program keeps holding references it should release."
  },
  {
    "q": "According to this phase, what should you check before reaching for heap-size flags or switching collector algorithms?",
    "choices": ["Whether the CPU has enough cores", "Whether the program is allocating more short-lived garbage than necessary in its hot paths", "Whether the operating system's page cache is large enough", "Whether the source code compiles with optimizations enabled"],
    "answer": 1,
    "explain": "Collector cost scales with how much garbage the program creates. Reducing unnecessary allocation in hot paths addresses the root cause; tuning heap size or swapping collectors first treats the symptom and the cost returns as load grows."
  },
  {
    "q": "How does Rust avoid needing a garbage collector at all?",
    "choices": ["It uses reference counting for every single value automatically", "The compiler tracks ownership statically and inserts deallocation calls at compile time, with no runtime tracing", "It relies on the operating system to reclaim memory when the process exits", "It requires the programmer to call free() manually on every allocation"],
    "answer": 1,
    "explain": "Rust's ownership and borrowing rules let the compiler prove, at compile time, exactly when a value is no longer needed, and insert the drop there. There's no runtime collector thread, no tracing pass, and no GC pause - the cost moves to compile-time borrow checking instead."
  }
]
```