Cheney's algorithm

Cheney's algorithm is a stop-and-copy method of tracing garbage collection, first described by C. J. Cheney in a 1970 paper in Communications of the ACM. The heap is divided into two equal halves called semispaces, and only one of them is in use at any time. When collection runs, live objects are copied from the from-space into the to-space, which then becomes the new heap, and the whole old heap is discarded in one piece. Each moved object leaves behind a forwarding pointer, sometimes called a broken heart, so a later reference to the same object is simply updated to the new address. The method needs no stack and only two pointers beyond the semispaces, one marking the start of free space in the to-space and one marking the next word to examine, so it works through the live objects breadth first. Cheney based it on the semispace collector published a year earlier by Fenichel and Yochelson, and it is an instance of tri-color marking, with the region between the two pointers forming the gray set.