Garbage Collection
How a runtime reclaims memory you stopped using — without you ever calling free(). Eight algorithms, from the counter on every object to the collectors that run alongside your program.
What is Garbage Collection?
The 60-second primer
Garbage collection is the runtime reclaiming memory you can no longer reach — automatically, without you calling `free()`. When you write user = null in JavaScript or let a Python list fall out of scope, the object it held doesn't vanish on its own. Something has to notice it's unreachable and hand the memory back. That something is the garbage collector.
Every collector answers the same two questions: which objects are still alive, and how do I reclaim the rest? "Alive" almost always means reachable — you can get to the object by starting at the roots (local variables, globals, CPU registers) and following pointers. Anything you can't reach is garbage, even if it still points at other things. The algorithms differ in how they find the live set and what they do with the space the dead objects leave behind.
These eight algorithms are a ladder. Reference counting is the simplest idea that works — until it meets a cycle. Mark & sweep fixes cycles by tracing reachability, but leaves the heap fragmented. Mark-compact and copying collectors defeat fragmentation in two different ways. Generational collectors exploit the fact that most objects die young. And the last three — tri-color, incremental, concurrent — are all about one thing: collecting without freezing your program.
Why the algorithm choice matters
- Pause time — a naive collector freezes every thread while it works (a stop-the-world pause). For a game or a trading system, a 200ms pause is a disaster. Concurrent and incremental collectors exist to shrink that pause.
- Throughput — the fraction of CPU spent running your code versus collecting. Doing less collection work, or doing it in bulk, raises throughput — often at the cost of longer pauses.
- Memory overhead — copying collectors need a spare half-heap; reference counting needs a counter on every object; generational collectors need write barriers. Nothing is free.
- Fragmentation — mark & sweep leaves holes that can starve a large allocation even when total free memory is plenty. Compacting and copying collectors eliminate it.
- Cycles — reference counting alone leaks them. Every tracing collector handles them for free, because reachability doesn't care about cycles.
Where these live in real runtimes
CPython uses reference counting plus a cycle-detecting mark & sweep as backup. The JVM (G1, ZGC, Shenandoah) and Go use generational and concurrent tracing collectors. V8 (Chrome, Node) is generational with an incremental, concurrent mark-compact for the old space. Swift and Objective-C use reference counting (ARC) and simply forbid strong cycles. Almost every production GC is a hybrid of the ideas on this page.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Algorithm | How it finds garbage | Handles cycles? | Fragmentation | Best for |
|---|---|---|---|---|
01Reference Counting | Per-object counter hits zero | No — cycles leak | Yes (no compaction) | Predictable frees, no pauses |
02Mark & Sweep | Trace from roots, free unmarked | Yes | Yes (leaves holes) | Simple tracing baseline |
03Mark-Compact | Mark, then slide live together | Yes | None — heap is compacted | Long-lived, full heaps |
04Copying (Cheney's) | Copy survivors to a fresh half | Yes | None — survivors packed | Short-lived, sparse heaps |
05Generational | Collect young often, old rarely | Yes | Depends on sub-collector | Typical app workloads |
06Tri-Color / Incremental / Concurrent | Trace in steps or in parallel | Yes | Depends on sub-collector | Low-pause, latency-critical |
- How it finds garbage
- Per-object counter hits zero
- Handles cycles?
- No — cycles leak
- Fragmentation
Yes (no compaction)- Best for
- Predictable frees, no pauses
- How it finds garbage
- Trace from roots, free unmarked
- Handles cycles?
- Yes
- Fragmentation
Yes (leaves holes)- Best for
- Simple tracing baseline
- How it finds garbage
- Mark, then slide live together
- Handles cycles?
- Yes
- Fragmentation
None — heap is compacted- Best for
- Long-lived, full heaps
- How it finds garbage
- Copy survivors to a fresh half
- Handles cycles?
- Yes
- Fragmentation
None — survivors packed- Best for
- Short-lived, sparse heaps
- How it finds garbage
- Collect young often, old rarely
- Handles cycles?
- Yes
- Fragmentation
Depends on sub-collector- Best for
- Typical app workloads
- How it finds garbage
- Trace in steps or in parallel
- Handles cycles?
- Yes
- Fragmentation
Depends on sub-collector- Best for
- Low-pause, latency-critical
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
How to think about picking one
- You want simple, deterministic frees and can guarantee no cycles (or break them with weak references) → reference counting. Swift's ARC and C++
shared_ptrlive here. - You need a correct, cycle-safe baseline and don't care about pauses → mark & sweep. The teaching default and the fallback in many hybrids.
- Your heap fills up with long-lived objects and fragmentation is hurting you → mark-compact. One pass leaves you a clean, contiguous heap.
- Most of your objects die almost immediately → a copying collector, often as the young generation of a generational scheme. Allocation becomes a pointer bump and dead objects cost nothing to reclaim.
- You cannot tolerate long stop-the-world pauses (games, trading, interactive UIs) → incremental or concurrent collection built on the tri-color invariant.
Two axes, not one
It helps to separate how garbage is found (reference counting vs. tracing) from when the work happens (stop-the-world vs. incremental vs. concurrent) and what happens to survivors (left in place, compacted, or copied). Real collectors mix and match: V8's old space is a concurrent, incremental, compacting, generational mark-sweep. Each adjective is one decision from this list.
Concepts in this track
8 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
Reference Counting
Every object carries a count of who points at it. Hits zero, it dies — instantly, but cycles leak.
Mark & Sweep
Trace from the roots, mark everything reachable, then sweep the rest. The tracing collector in its purest form.
Mark-Compact
Mark the living, then slide them together to squeeze out the holes. Defeats fragmentation at a copying cost.
Copying — Cheney's Algorithm
Two half-heaps. Copy the survivors to the empty half with a tidy breadth-first scan, then swap. Allocation becomes a pointer bump.
Generational GC
Most objects die young, so collect the nursery often and the old guard rarely. The weak generational hypothesis, exploited.
Tri-Color Marking
White, grey, black — an invariant that lets a collector mark the heap while the program keeps mutating it.
Incremental GC
Slice the collection into tiny steps interleaved with the program, trading throughput for short pauses.
Concurrent Mark-Sweep
Run the collector on its own thread, in parallel with the application, with write barriers keeping the marking honest.
Related tracks
If this one clicks, try these next.
Memory Allocation
Before garbage collection ever runs, something has to hand out the memory. Six allocators — four ways to pick a hole, plus the two structured schemes real kernels actually ship.
Cache Write Policies
Three ways to handle a write when you have a cache in front of the store. Each policy is a different bet about durability, throughput, and how stale your data is allowed to get.
Cache Eviction
When the cache fills up, something has to go — and which one you pick decides your hit rate. Ten classic policies, side-by-side.