Cheney's algorithm: Difference between revisions

Revision as of 08:00, 28 May 2017

Revision as of 22:47, 10 August 2017

Line 11:

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

The algorithm needs no stack and only two pointers outside of the from-space and to-space: 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 is sometimes called a "two-finger" collector --- itcollector—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.

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.