Objects on the heap form a directed reference graph G = (V, E): an edge o → p means field/variable o holds a pointer to p. A fixed set of roots (stack variables, globals — shown gold) anchors the graph. An object is live iff it is reachable from some root:
Live(o) = true iff ∃ path root ⇒ o in G
Mark phase (BFS from roots), O(|V| + |E|):
R ← roots ; visited ← {}
while R not empty:
o ← R.pop(); if o in visited: continue
visited.add(o); mark(o) = true
for each edge o → p: R.push(p)
Sweep phase, O(|V|):
for every object o in heap:
if mark(o) == false: free(o) // unreachable ⇒ garbage
else: mark(o) ← false // reset for next cycle
Anything not visited during the mark BFS has no path from a root — even if other garbage objects still point to it — so the whole disconnected component is reclaimed together. That's why dropping one reference can free a cluster of objects at once, not just the one whose pointer was cleared.
Reference counting (toggle above) is the naive alternative: every object tracks how many live pointers target it, and frees itself the instant that count hits zero, cascading to whatever it pointed to. It's cheap and needs no scan of the whole heap — but a cycle of objects that only point to each other, with no path from any root, keeps every member's count at 1 or more forever. Create Unreachable Cycle builds exactly that: two or three objects referencing each other with no incoming edge from a root or any reachable object. Run the reference-counting collector on it and watch the count never reach zero — the cluster leaks. Switch back to mark-and-sweep on the same graph and the BFS correctly reclaims it, because reachability from roots — not local refcounts — is what mark-and-sweep actually tests.
Node positions are computed with a force-directed layout, the same technique used by real graph-visualization and heap-inspector tools: a Coulomb-like repulsion keeps every pair of objects apart, a Hookean spring pulls referenced objects together, and a weak centering force keeps the whole graph in frame.
F_repel(i,j) = k_r / d(i,j)² (push apart, all pairs)
F_spring(i,j) = k_s · (d(i,j) − L0) (pull together, only for i→j edges)
F_center(i) = −k_c · pos(i) (weak pull to origin)
v ← (v + F·dt) · damping ; pos ← pos + v·dt
- Allocate Object — mallocs a new node with 0–2 random outgoing references, wired into the live graph.
- Add / Drop Reference — the mutator rewiring a pointer; dropping the last reference into a subgraph turns it into garbage instantly, even though nothing is deleted until the collector runs.
- Create Unreachable Cycle — spawns 2-3 objects that reference only each other, with no path from any root: real cyclic garbage that reference counting cannot free.
- Run Mark & Sweep — animates the BFS wavefront (green pulse spreading from the gold roots), then shrinks and ejects every node the wavefront never reached, cycles included.
- Reference counting mode — swaps the collector for naive refcounting: frees any object whose incoming-pointer count is zero, cascading through its own references, but never touches an unreachable cycle.
- Auto-collect — triggers a cycle automatically once heap usage crosses the threshold, the way a real allocator schedules collections under memory pressure.