From Wikipedia, the free encyclopedia

Cheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a method of 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.

Cheney's algorithm reclaims items as follows:

• Objects on the stack. Object references on the stack are checked, and one of the two following actions is taken for each one:
  • 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 referenced by objects on the stack. Once this has been done, 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 object.

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

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

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

• Cheney, C.J. (November 1970). "A Nonrecursive List Compacting Algorithm". Communications of the ACM 13 (11): 677–678. 
• Fenichel, R.R. (1969). "A LISP garbage-collector for virtual-memory computer systems". Communications of the ACM 12 (11): 611-612. 
• Tutorial at the University of Maryland, College Park