The first garbage collector, and the plainest statement of what “alive” means: mark every object reachable from the roots (a graph traversal), then sweep the whole heap and free everything left dark. Reachability is survival. Its one real win over reference counting: it reclaims cyclic garbage — a ring of objects pointing at each other but at nothing the program can still see.
THE TECHNIQUE trace from roots; free the dark
Start from the roots and follow every pointer, marking each object reached. Then walk the whole heap: anything unmarked is unreachable — free it. Below: a heap where objects 0–3 are reachable from the root, and 4→5→6→4 form a garbage cycle that no root can reach (reference counting would leak it forever). live demo
HISTORY & CREDIT the first GC; a separate copying lineage
“Mark-sweep runs with one bit and no stack” — only with pointer reversal, which is McCarthySchorr-Waite’s (1967), not the 1960 algorithm. cited
1959–60 · John McCarthy — GC for Lisp on the IBM 704, the original mark-sweep, coins “garbage collection.” (Implemented 1959, published April 1960.) Dec 1960 · George Collins — reference counting: a different family (count incoming pointers, not trace reachability), and it leaks cycles. 1967 · Schorr & Waite (and Deutsch ~1965) — pointer reversal: mark with a mark bit + a direction bit per cell and no auxiliary stack (hence “Deutsch-Schorr-Waite”). 1963 / 1969 / 1978 · a separate lineage: Minsky (first copying, via disk), Fenichel-Yochelson (in-core semispace, dart 140), Dijkstra et al. (incremental tri-color, dart 141).
Classic mark-sweep is strictly stop-the-world and leaves the heap fragmented — it flips bits, it does not move objects. McCarthy, 1960
RECOMMEND FOR I-13 the heap is adjacency; mark = DFS; sweep = mask
The object graph is successor bitmasks; marking is a DFS from the roots; the sweep is one bitwise complement:
$ i13 run mark.i13 # roots {0}; 0->{1,2}, 1->{3}; garbage cycle 4->5->6->4
reachable / survivors = {0,1,2,3} = mask 15 (DFS from the root)
freed = 127 - 15 = 112 = {4,5,6} the cycle -- refcounting would LEAK it
Recommend:nothing new — each object’s children are a successor bitmask; mark is a DFS that ORs each reached object into a “marked” mask (recursion, guarded by the already-marked bit); sweep is the bitwise complement within the heap (verified survivors {0,1,2,3}=15, freed {4,5,6}=112). The garbage cycle 4→5→6→4 is collected — the exact case reference counting leaks. Note: reachability-from-the-root is the corpus’s own shape — every inhabitant folds to ROOT_0; here what folds to a root survives. A real heap of pointer objects is a node arena (PS-015); the corpus runs the reachability on adjacency masks.