Cheney's Copying Collector
The Fenichel-Yochelson collector given in the CopyingGarbageCollector page has the disadvantage of using a recursive copying algorithm. Since Cheney's discovery of an efficient iterative technique for its implementation copying collection has proved popular with implementors. Although garbage collection technology has moved beyond simple stop-and-copy collection, this technique remains the most widely adopted basis for more sophisticated techniques, such as generational and incremental collectors.
flip() = Fromspace, Tospace = Tospace, Fromspace top_of_space = Tospace + space_size scan = free = Tospace for R in roots R = copy(R) while scan < free for P in Children(scan) *P = copy(*P) scan = scan + size (scan) copy(P) = if forwarded(P) return forwarding_address(P) else addr = free move(P,free) free = free + size(P) forwarding_address(P) = addr return addr
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
by Richard Jones and Rafael Sims