Garbage Collection

Every running program is a small economy of memory. It asks the system for space to hold an object, wires that object to others, and moves on. But space is finite — sooner or later someone has to give it back. Do it too eagerly and you free memory another part of the program still needs (a crash); do it too late, or never, and the program slowly swells until it falls over (a leak).

Garbage collection automates the hard half of that bargain. The key insight, due to John McCarthy in 1960 for the Lisp language, is deceptively simple: an object is garbage not when you say so, but when nothing can reach it anymore. If no chain of references leads from a live variable to an object, your code can never touch it again — so its memory is safe to reclaim.

That turns memory management into a question about a graph: starting from the roots (local variables, globals, the call stack), which objects are still reachable? Everything reachable lives; everything else is garbage. The most classic algorithm for answering it is mark-and-sweep.

Below is a tiny heap. The ROOT is what your program can directly see — local variables and globals. Arrows are references: object A keeps object B alive only if there's a path of arrows from the root to B.

<p class="hint">{{hint}}</p>
<svg id="heap" viewBox="0 0 420 240" class="heap"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.heap { width: 100%; height: auto; background: #f4f7fa; border-radius: 10px; }
.node circle { stroke-width: 2; transition: all .25s; }
.node text { font: 700 13px ui-monospace, monospace; fill: #fff; pointer-events: none; }
.node.obj circle { fill: #6c7a89; stroke: #55626f; }
.node.root circle { fill: #1d3557; stroke: #142844; }
.node.marked circle { fill: #0a7d33; stroke: #075c25; }
.node.swept circle { fill: #e6e9ec; stroke: #c3c9cf; }
.node.swept text { fill: #aeb6bd; }
.edge { stroke: #8a98a6; stroke-width: 2.4; cursor: pointer; transition: stroke .15s; }
.edge:hover { stroke: #e63946; stroke-width: 3.4; }
.edge.cut { display: none; }
.arrowhead { fill: #8a98a6; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Click an arrow to cut a reference — as if your code reassigned a variable. Then press Mark & Sweep. The collector starts at the root and marks everything it can reach by following arrows; anything it never reaches is swept (freed). Notice that cutting a single arrow can free a whole cluster at once — objects that were only kept alive through the link you removed. Reachability, not reference counts, is what decides life and death.

At its core, garbage collection is a solved problem with a clean algorithm — but the engineering around it is endless.

• The core is easy. Mark-and-sweep is just a graph traversal from the roots: it runs in time proportional to the number of objects and references, O(objects + edges). Deciding reachability is not the hard part.
• Reference counting isn't enough. A tempting alternative — count how many references point at each object and free it at zero — is cheap but misses cycles: two dead objects that point at each other keep each other's count above zero forever. Tracing collectors avoid this because an unreachable cycle is still simply unreachable.
• The real cost is when. A naive collector must stop the world — pause your whole program while it traces. Modern collectors (generational, incremental, concurrent) work hard to shrink those pauses, collecting young objects often and old ones rarely.
• And fragmentation. Sweeping leaves holes; compacting collectors move survivors together, which means rewriting every reference that points at them.

So the decision of what to free is computationally easy, unlike the genuinely intractable problems behind P vs NP. What's hard is doing it fast, predictably, and without freezing the program — which is why garbage collection has been an active research field for over sixty years.

You almost certainly run a garbage collector every day, even if you've never written one:

• Managed languages: Java, C#, JavaScript, Python, Go, Ruby and many more free memory automatically. The reason you rarely think about free() is that a collector is doing it for you.
• Reachability beyond memory: the same "what can I get to from the roots?" traversal underlies dead-code elimination in compilers, finding orphaned files in storage systems, and detecting unused records in databases.
• Real-time and games: where a pause of a few milliseconds is unacceptable, engineers tune or replace the collector — this is exactly why pause-free collection is such a prized goal.
• Security: use-after-free and double-free bugs are a huge source of vulnerabilities in manually managed code; automatic collection removes a whole class of them.

Garbage collection is graph reachability wearing a hard hat. The same kind of traversal shows up in shortest-path and connectivity problems all across computing.

Garbage collection rests on one beautiful idea from 1960: memory you can no longer reach is memory you'll never use again, so it's safe to take back. Turn the heap into a graph, trace from the roots, keep what you can reach, sweep the rest. The decision is easy; the algorithm is linear.

The hard part was never what to free — it was doing it quickly and invisibly, without freezing the program at the wrong moment. That tension between a simple idea and a demanding implementation is the heartbeat of systems programming, and it's why, six decades on, smart people are still inventing better collectors.