Talk:Cheney's algorithm: Difference between revisions

Revision as of 05:54, 8 May 2008

Latest revision as of 09:56, 22 February 2025

(14 intermediate revisions by 11 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

{{WikiProject Computer science|importance=Low}}

}}

==Untitled==

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

--[[User:On5deu|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. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.173.236.232|128.173.236.232]] ([[User talk:128.173.236.232|talk]]) 22:06, 3 November 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==Recursion==

{{Expand|date=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. -- [[User:Beland|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.. <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:66.75.233.189|66.75.233.189]] ([[User talk:66.75.233.189#top|talk]] • [[Special:Contributions/66.75.233.189|contribs]]) 01:53, 8 May 2008 (UTC)</small>

::: 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. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.66.40.164|86.66.40.164]] ([[User talk:86.66.40.164|talk]]) 13:50, 20 April 2016 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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

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)

[[Special:Contributions/212.95.7.81|212.95.7.81]] ([[User talk: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. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/82.132.224.134|82.132.224.134]] ([[User talk:82.132.224.134|talk]]) 10:50, 4 July 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Algorithm Example ==

The algorithm example is recursive, and has no indentation. The whole idea behind Cheney is to avoid recursion. It needs to be replaced. [[User:SamRushing|SamRushing]] ([[User talk:SamRushing|talk]]) <span style="font-size:smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|undated]] comment added 08:51, 30 January 2016 (UTC)</span><!--Template:Undated--> <!--Autosigned by SineBot-->