Talk:Cheney's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.


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)

It seems to me that this article confounds Fenichel's work with Cheney's. Cheney's work is the application of breadth-first traversal to Fenichel's subspace solution which originally used a recursive algorithm to traverse live objects. The article could be modified to clearly delineate the work of Fenichel from that of Cheney. —Preceding unsigned comment added by (talk) 22:06, 3 November 2009 (UTC)


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..
The algorithm as shown is totally recursive (see the recursive call to copy(r)), and performs a depth first search. I believe this is an error in the article. The pseudocode should be updated to match your description. — Preceding unsigned comment added by (talk) 13:50, 20 April 2016 (UTC)

Regarding Efficiency[edit]

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.

It seems to me that thi algorithm is also not thread-save - the whole system has to stop for the gc. A big concern in today (e.g. in smartphones with 8 cores) (talk) 01:26, 15 March 2013 (UTC)

Breadth first search gives good locality of reference for most paths for accesses close to the root. Depth first search gives great locality of reference for a single path from the root, and awful locality for everything else. In most cases, I think BFS will actually perform better, not worse. In this case there is no such thing as *worst*: performance will vary between use cases. — Preceding unsigned comment added by (talk) 10:50, 4 July 2015 (UTC)

Algorithm Example[edit]

The algorithm example is recursive, and has no indentation. The whole idea behind Cheney is to avoid recursion. It needs to be replaced. SamRushing (talk) —Preceding undated comment added 08:51, 30 January 2016 (UTC)