Cheney's Algorithm is a method of performing a copying garbage collection
using semi-spaces, that is, it works by splitting heap memory into two parts and
only using one at a time.
Essentially, at any given moment there is an active part of memory from which
new objects are allocated. When conditions get such that a garbage collection
is needed, the live objects of the active part of memory are copied to the other
memory part, which is marked active, and then old active part is marked inactive
and reclaimed in one big chunk.
Cheney's algorithm provides a method of doing this collection. The two parts of
the heap are labeled the from-space and the to-space, which
correspond to the old active part (called "from-space" because objects are
copied from it during the collection)
and the new active part (called the "to-space" because objects are copied to
it during the collection). To begin the to-space is empty and the from-space
contains both live and garbage objects. Cheney's algorithm will check each
object reference on the stack (which by definition refer to live objects),
and will take one of two actions:
Once all the stack object references have been scanned, the algorithm will scan any
object references in the new to-space objects that were created. The algorithm will
use the same two actions listed above on these references. Once all to-space object
references have been scanned, the collection is complete and the entire from-space may be
- Forward the referred object to to-space if it has not already been forwarded.
This means allocating an identical object in to-space and copying the object data over.
In addition, a forwarding pointer is left at the object's old location in
from-space which will point to its new location in to-space.
- Simply update the object reference if the referred object has already been forwarded.
This is a simple matter of following the forwarding pointer.
The algorithm is illustrated by the applet below using a simplified model where
only one type of object, called a cons cell, may be allocated. A cons cell
is simply a structure with a left and right pointer that point either to null or to
other cons cells.
The applet shows the state of memory before collection begins. The top
row is the set of stack objects, called the root set. The second row is the from-space, which is
the collection of heap objects -- some of which might be garbage. The bottom row is the
to-space and begins empty, but will grow as live objects are copied from the from-space.
Press the button to step through the collection process. At each step another object reference,
marked in yellow, will be scanned and updated. When the reference is updated, cells will
be marked in green to indicate the old value of the yellow reference, and when cells are
copied into the to-space. As the collection proceeds, references are marked in pink to
indicate they have been scanned. Eventually, all root and to-space references will be
pink and the collection will be complete.
The applet also allows the collection to be stepped through backwards in order to review
earlier parts of the process. The text window at the bottom shows a description of each
of the steps taken so far.