Talk:Cheney's algorithm

From Wikipedia, the free encyclopedia

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)

[edit] Recursion

Please help improve this article or section by expanding it. Further information might be found on the talk page or at requests for expansion. (June 2007)

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)

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..

[edit] 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.