Talk:Cheney's algorithm

What is the difference between Cheney's garbage collector and the one proposed a year earlier by Fenichel? Why do we have an article on Cheney and not on Fenichel?

Fenichel, R.R. and Yochelson, J.C., A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, vol. 12, no. 11, pp. 611-612, 1969 --Philippe 09:05, 3 May 2007 (UTC)[reply]

Recursion

Is this algorithm recursive? Will it copy objects referred to by something referred to by something referenced from the stack? If so, it is not described that way. -- Beland 17:19, 24 May 2007 (UTC)[reply]

It is recursive - objects copied are handled after the objects on the stack by simply going through the new heap. This results in a breadth-first approach to reaching all the items, as both the stack and the heap itself act as queues of items to reach, and one is always adding to the end of the heap then scanning forward in either the stack or the heap.

Cheney's algorithm seems to produce among the worst possible structures if locality-of-reference is desired - objects referenced by other objects are neatly splattered across the entire heap due to the breadth-first-search implicit to the algorithm. And, yet, the lack of any requirement for a stack (which is necessary for a depth-first search) is part of what keeps Cheney's algorithm itself quite simple.