Cheney's algorithm: Difference between revisions

Revision as of 12:59, 17 May 2022

Latest revision as of 22:06, 9 July 2025

(11 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Computer software algorithm}}

{{Use dmy dates|date=September 2021}}

{{more footnotes|date=April 2014}}

'''Cheney's algorithm''', first described in a 1970 [[Association for Computing Machinery|ACM]] paper by C.J. Cheney, is a [[stop and copy]] method of [[tracing garbage collection]] in computer software systems. In this scheme, the [[Memory management#DynamicManual memory allocationmanagement|heap]] is divided into two equal halves, only one of which is in use at any one time. Garbage collection is performed by copying live objects from one semispace (the from-space) to the other (the to-space), which then becomes the new heap. The entire old heap is then discarded in one piece. It is an improvement on the previous stop -and -copy technique.{{citation needed|date=April 2016}}

Cheney's algorithm reclaims items as follows:

Line 15 ⟶ 16:

The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process; when a reference to an object already in to-space (thus having a forwarding pointer in from-space) is found, the reference can be updated quickly simply by updating its pointer to match the forwarding pointer.

Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a ''[[breadth-first]]'' list copying garbage collection scheme.

==Sample algorithm==

<pre>

initialize() =

tospace = N/2

fromspace = 0

allocPtr = fromspace

scanPtr = whatever -- only used during collection

</pre>

<pre>

allocate(n) =

If allocPtr + n > fromspace + tospace

collect()

EndIf

If allocPtr + n > fromspace + tospace

fail “insufficient memory”

EndIf

o = allocPtr

allocPtr = allocPtr + n

return o

</pre>

<pre>

collect() =

swap(fromspace, tospace)

allocPtr = tospace

scanPtr = tospace

-- scan every root you've got

ForEach root in the stack -- or elsewhere

root = copy(root)

EndForEach

-- scan objects in the to-space (including objects added by this loop)

While scanPtr < allocPtr

ForEach reference r from o (pointed to by scanPtr)

r = copy(r)

EndForEach

scanPtr = scanPtr + o.size() -- points to the next object in the to-space, if any

EndWhile

</pre>

<pre>

copy(o) =

If o has no forwarding address

o' = allocPtr

allocPtr = allocPtr + size(o)

copy the contents of o to o'

forwarding-address(o) = o'

EndIf

return forwarding-address(o)

</pre>

== Semispace ==

Line 91 ⟶ 38:

|doi=10.1145/362790.362798

|s2cid=36538112

|doi-access=free

}}

* {{cite journal

Line 100 ⟶ 48:

|doi=10.1145/363269.363280

|s2cid=36616954

|doi-access=free

}}

* {{cite journal

Line 108 ⟶ 57:

|url=http://courses.cs.washington.edu/courses/csep521/07wi/prj/rick.pdf

}}

== External links ==

* {{youtube|1uLzSXWWfDg|Understanding Android Runtime (Google I/O'19)}} - Android uses a variant of the semi-space garbage collector.

{{Memory management}}