Introduction

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.

Trace the Live Objects

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">The <b>ROOT</b> is what your program can see directly. Arrows are references. Click an arrow to cut it (reassign a variable), then run the collector: it <b>marks</b> everything reachable from the root and <b>sweeps</b> the rest.</p>
<svg id="heap" viewBox="0 0 420 240" class="heap"></svg>
<div class="status" id="status">Cut an arrow, then mark & sweep.</div>
<div class="btns">
  <button id="run" type="button">Mark & Sweep</button>
  <button id="reset" type="button" class="ghost">Reset graph</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A tracing mark-and-sweep garbage collector over a tiny object graph.
// Nodes are heap objects; "root" is the program's entry point. An object is
// LIVE iff some path of (uncut) reference arrows reaches it from the root.
// mark() does a graph traversal (BFS) from the root; sweep() frees the rest.
// This is the McCarthy (1960) idea: reachability decides what survives.
const NODES = {
  root: { x: 60,  y: 120, label: 'ROOT', root: true },
  a:    { x: 170, y: 60,  label: 'A' },
  b:    { x: 170, y: 180, label: 'B' },
  c:    { x: 290, y: 60,  label: 'C' },
  d:    { x: 290, y: 180, label: 'D' },
  e:    { x: 390, y: 120, label: 'E' },
};
// Directed references. Cut any of these to drop a reference.
const BASE_EDGES = [
  ['root','a'], ['root','b'], ['a','c'], ['b','d'], ['c','e'], ['d','e'], ['c','d'],
];
let edges = BASE_EDGES.map(e => ({ from: e[0], to: e[1], cut: false }));
let marked = new Set();
let swept = false;

// Reachable set from root following only uncut edges (BFS).
function reachable() {
  const adj = {}; for (const k in NODES) adj[k] = [];
  edges.forEach(e => { if (!e.cut) adj[e.from].push(e.to); });
  const seen = new Set(['root']); const q = ['root'];
  while (q.length) { const n = q.shift();
    for (const m of adj[n]) if (!seen.has(m)) { seen.add(m); q.push(m); } }
  return seen;
}

function draw() {
  const svg = document.getElementById('heap');
  svg.innerHTML =
    '<defs><marker id="ah" markerWidth="9" markerHeight="9" refX="7" refY="3" orient="auto">' +
    '<path class="arrowhead" d="M0,0 L7,3 L0,6 z"/></marker></defs>';
  // edges first
  edges.forEach((e, i) => {
    const A = NODES[e.from], B = NODES[e.to];
    const dx = B.x - A.x, dy = B.y - A.y, len = Math.hypot(dx, dy);
    const ux = dx / len, uy = dy / len, r = 22;
    const x1 = A.x + ux * r, y1 = A.y + uy * r;
    const x2 = B.x - ux * (r + 8), y2 = B.y - uy * (r + 8);
    const line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
    line.setAttribute('x1', x1); line.setAttribute('y1', y1);
    line.setAttribute('x2', x2); line.setAttribute('y2', y2);
    line.setAttribute('marker-end', 'url(#ah)');
    line.setAttribute('class', 'edge' + (e.cut ? ' cut' : ''));
    line.addEventListener('click', () => { e.cut = !e.cut; swept = false; marked = new Set();
      setStatus('Reference cut. Now run Mark & Sweep.', 'info'); draw(); });
    svg.appendChild(line);
  });
  // nodes
  for (const k in NODES) {
    const n = NODES[k];
    const g = document.createElementNS('http://www.w3.org/2000/svg', 'g');
    let cls = 'node ' + (n.root ? 'root' : 'obj');
    if (swept) { if (marked.has(k)) cls = 'node marked'; else if (!n.root) cls = 'node swept'; }
    g.setAttribute('class', cls);
    const c = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
    c.setAttribute('cx', n.x); c.setAttribute('cy', n.y); c.setAttribute('r', 22);
    const t = document.createElementNS('http://www.w3.org/2000/svg', 'text');
    t.setAttribute('x', n.x); t.setAttribute('y', n.y + 4);
    t.setAttribute('text-anchor', 'middle'); t.textContent = n.label;
    g.appendChild(c); g.appendChild(t); svg.appendChild(g);
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function run() {
  marked = reachable(); swept = true;
  const freed = Object.keys(NODES).filter(k => !NODES[k].root && !marked.has(k));
  draw();
  const live = [...marked].filter(k => !NODES[k].root).map(k => NODES[k].label);
  if (freed.length === 0) setStatus(fmt('Marked %length% live object(s): %live%. Nothing to free.', { length: live.length, live: live.join(', ') }), 'ok');
  else setStatus(fmt('Swept %length% object(s): %map%. Live: %v%.', { length: freed.length, map: freed.map(k => NODES[k].label).join(', '), v: live.join(', ') || 'none' }), 'ok');
  console.log('reachable:', [...marked].join(','), '| freed:', freed.join(',') || 'none');
}
function reset() {
  edges = BASE_EDGES.map(e => ({ from: e[0], to: e[1], cut: false }));
  marked = new Set(); swept = false; setStatus('Cut an arrow, then mark & sweep.', 'info'); draw();
}
document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', reset);
draw();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/garbage-collection/Content licensed under CC BY-NC 4.0.