 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
Untitled edit
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 128.173.236.232 (talk) 22:06, 3 November 2009 (UTC)
Recursion edit
- 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 86.66.40.164 (talk) 13:50, 20 April 2016 (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..
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)
212.95.7.81 (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 82.132.224.134 (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)