Cheney's algorithm: Difference between revisions

Revision as of 19:55, 26 April 2023

Latest revision as of 22:06, 9 July 2025

(5 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Computer software algorithm}}

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

{{more footnotes|date=April 2014}}

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

scanPtr = fromspace

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