Talk:Cheney's algorithm: Difference between revisions

Revision as of 05:44, 8 May 2008

Revision as of 05:53, 8 May 2008

Line 7:

{{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 isisn't strictly recursive, -but objectsit copieddoes arereach handled afterall the objects onyou thename. stack byEssentially, simplythe goingstack throughand the new heap. both Thisact resultsas incomponents of a breadth-firstqueue, approachwith you adding to reachingthe allend of the heap any copied items, asthen bothforwarding the stackpointer andin the heapqueue. itself actThis asresults queuesin ofa itemsbreadth-first approach to reach,reaching andall onethe isitems, alwayssince addingyou towon't reach the 'end' of the heap/queue thenuntil scanningno forwardmore inobjects eitherrequire thecopying stackand orno themore heappointers 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.

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.