Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Cheney's algorithm
open-in-new
<h2 id="semispace">Semispace</h2> <p>Cheney based his work on the <i>semispace</i> garbage collector, which was published a year earlier by R.R. Fenichel and J.C. Yochelson. </p> <h2 id="equivalence-to-tri-color-abstraction">Equivalence to tri-color abstraction</h2> <p>Cheney's algorithm is an example of a <a href="/facts/Tracing_garbage_collection/qg7fK6w9">tri-color marking</a> garbage collector. The first member of the gray set is the stack itself. Objects referenced on the stack are copied into the to-space, which contains members of the black and gray sets. </p><p>The algorithm moves any white objects (equivalent to objects in the from-space without forwarding pointers) to the gray set by copying them to the to-space. Objects that are between the scanning pointer and the free-space pointer on the to-space area are members of the gray set still to be scanned. Objects below the scanning pointer belong to the black set. Objects are moved to the black set by simply moving the scanning pointer over them. </p><p>When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends. </p> <ul><li>Cheney, C.J. (November 1970). <a href="https://doi.org/10.1145%2F362790.362798">"A Nonrecursive List Compacting Algorithm"</a>. <i>Communications of the ACM</i>. 13 (11): 677–678. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F362790.362798">10.1145/362790.362798</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:36538112">36538112</a>.</li> <li>Fenichel, R.R.; Yochelson, Jerome C. (1969). <a href="https://doi.org/10.1145%2F363269.363280">"A LISP garbage-collector for virtual-memory computer systems"</a>. <i>Communications of the ACM</i>. 12 (11): 611–612. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F363269.363280">10.1145/363269.363280</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:36616954">36616954</a>.</li> <li>Byers, Rick (2007). <a href="http://courses.cs.washington.edu/courses/csep521/07wi/prj/rick.pdf">"Garbage Collection Algorithms"</a> (PDF). <i>Garbage Collection Algorithms</i>. 12 (11): 3–4.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://www.youtube.com/watch?v=1uLzSXWWfDg">Understanding Android Runtime (Google I/O'19)</a> on <a href="/facts/YouTube_video_(identifier)/db276jst">YouTube</a> - Android uses a variant of the semi-space garbage collector.</li></ul>