Cheney's algorithm: Difference between revisions

Revision as of 09:22, 22 March 2009

Latest revision as of 22:06, 9 July 2025

(55 intermediate revisions by 41 users not shown)

Line 1:

{{Short description|Computer software algorithm}}

'''Cheney's algorithm''', first described in a 1970 [[Association for Computing Machinery|ACM]] paper by C.J. Cheney, is a method of [[garbage collection (computer science)|garbage collection]] in computer software systems. In this scheme, the [[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.

{{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 [[garbagetracing collection (computer science)|garbage collection]] in computer software systems. In this scheme, the [[Memory management#Manual memory management|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:

* '''ObjectsObject references on the stack.''' Object references on the stack are checked. One of the two following actions is taken for each object reference that points to an object in from-space:

** If the object has not yet been moved to the to-space, this is done by creating an identical copy in the to-space, and then replacing the from-space version with a forwarding pointer to the to-space copy. Then update the object reference to refer to the new version in to-space.

** If the object has already been moved to the to-space, simply update the reference from the forwarding pointer in from-space.

* '''Objects onin the to-space.''' The garbage collector examines all object references ''in the objects that have been migrated to the to-space'', and performs one of the above two actions on the referenced objects.

Once all to-space references have been examined and updated, garbage collection is complete.

* '''Objects on the to-space.''' The garbage collector examines all object references ''in the objects that have been migrated to the to-space'', and performs one of the above two actions on the referenced objects.

The very clever thing about this algorithm is that it needs no stack and veryonly littletwo memorypointers outside of the from-space and to-space; it needs only: a pointer to the beginning of free space in the to-space, and a pointer to the next word in to-space that needs to be examined. The Fordata thisbetween reason,the it'stwo sometimespointers calledrepresents awork "two-finger"remaining collector ---for it only needs "two fingers" pointing into the to-space todo keep(those trackobjects ofare its''gray'' state. The data betweenin the twotri-color fingersterminology, representssee work remaining for it to dolater).

Once all to-space references have been examined and updated, garbage collection is complete.

The aforementioned forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process:; Whenwhen 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.

The very clever thing about this algorithm is that it needs no stack and very little memory outside of the from-space and to-space; it needs only a pointer to the beginning of free space in the to-space, and a pointer to the next word in to-space that needs to be examined. For this reason, it's sometimes called a "two-finger" collector --- it only needs "two fingers" pointing into the to-space to keep track of its state. The data between the two fingers represents work remaining for it to do.

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.

The aforementioned 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.

== Semispace ==

Cheney based his work on the ''semispace'' garbage collector, which was published a year earlier by R.R. Fenichel and J.C. Yochelson.

== Equivalence to [[Garbage_collection_(computer_science)#Basic_algorithm|Tritri-colourcolor abstraction]] ==

Cheney's algorithm is an example of a [[tracing garbage collection#Tri-color marking|tri-color marking]] 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.

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.

When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends.

== References ==

* {{cite journal

| last = Cheney | first = C.J.

| title = A Nonrecursive List Compacting Algorithm

| journal = Communications of the ACM

| volume = 13 | issue = 11 | date = November 1970 | pages = 677–678

| <!--doesn't seem to work properly-->doi={{doi|10.1145/362790.362798}}

|s2cid=36538112

| url = http://doi.acm.org/10.1145/362790.362798

|doi-access=free

| doi = 10.1145/362790.362798

}}

* {{cite journal

| last last1= Fenichel | first first1= R.R.

|last2=Yochelson |first2=Jerome C.

| title = A LISP garbage-collector for virtual-memory computer systems

| journal = Communications of the ACM

| volume = 12 | issue = 11 | date year= 1969 | pages = 611–612

| url = http://portal.acm.org/citation.cfm?id=363280

| doi = 10.1145/363269.363280

|s2cid=36616954

}}

|doi-access=free

* [http://www.cs.umd.edu/class/fall2002/cmsc631/cheney/cheney.html Tutorial] at the [[University of Maryland, College Park]]

}}

[[Category:Garbage collection (computer science)]]

* {{cite journal

|last=Byers |first=Rick

|title=Garbage Collection Algorithms

|journal=Garbage Collection Algorithms

|volume=12 |issue=11 |year=2007 |pages=3–4

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

[[Category:Automatic memory management]]