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 isn't strictly recursive, but it does reach all the objects referenced even indirectly from the stack. Essentially, the stack and the heap both act as components of a queue, with you adding to the end of the heap any copied items, then forwarding the pointer in the queue. This results in a breadth-first approach to reaching all the items, since you won't reach the 'end' of the heap/queue until no more objects require copying and no more pointers require forwarding..

Regarding Efficiency

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. If you need a KISS garbage collector and wish to avoid other structures and bit manipulations, Cheney's is about as simple as it gets. If you need a more optimal one, you'll need to look elsewhere.