A copying collector that traverses live objects with no recursion and no auxiliary stack: copy each root into to-space, leaving a forwarding pointer behind; then scan the copied objects breadth-first, using two pointers — scan (next to process) and free (next empty slot). The growing to-space is the work queue. It compacts (no fragmentation) and touches only live data.
THE TECHNIQUE copy roots; scan breadth-first; forward
Copy each root into to-space and leave a forwarding pointer in from-space. Then walk from scan to free: for each copied object, follow its children — if a child is already forwarded, use the forward; otherwise copy it (advancing free) and forward it. When scan catches free, done. Below: a from-space compacted into to-space. live demo
HISTORY & CREDIT Cheney removed the stack, not invented copying
“Cheney invented copying / semispace GC” — invented no; forwarding pointers and semispaces are Fenichel-Yochelson (1969). Cheney removed the recursion stack. cited
1963 · Marvin Minsky — the first copying collector (copies live cells out to disk and back). 1969 · Fenichel & Yochelson — the first in-core two-semispace copier, with forwarding pointers — but recursive. 1970 · C. J. Cheney — two pages: the to-space itself becomes the breadth-first work queue (scan/free pointers), so no recursion stack is needed. This is the dart. 1978 / 1984 · Baker makes it incremental / real-time (a read barrier); Ungar’s generation scavenging runs a Cheney copier over the young generation only. Moon (1984) names the cost: BFS order scatters children across pages, wrecking locality.
“No extra space” is a half-truth: no auxiliary stack, but a whole second semispace stands empty — ~2× address space traded for speed. Cheney, 1970
RECOMMEND FOR I-13 the queue is the to-space; scan/free are indices
The stackless BFS is two integer indices over a to-space array, with forwarding as a visited mask — and garbage is never touched:
$ i13 run cheney.i13 # roots {0}; 0->{1,2}, 1->{3}; garbage {4,5}
copied to-space (BFS order) = [0, 1, 2, 3] 4 live objects, compacted gapless
scan/free meet at 4 -> done garbage {4,5} is NEVER scanned or copied
Recommend:nothing new — to-space is an f64 array used as a queue; scan and free are two integer indices; a “forwarding pointer” is a visited-bit + the copy position; each object’s children are enqueued once (verified 4 objects copied in BFS order [0,1,2,3]; garbage {4,5} never enqueued). No recursion stack — the queue is the to-space, exactly Cheney’s trick. Note: pairs with mark-sweep (dart 139): both trace reachability from roots, but Cheney compacts (copies live, forwards, leaves gaps behind) where mark-sweep frees in place. A real heap wants a node arena (PS-015); the corpus runs the BFS + forwarding on arrays.