Cheney's algorithm: Difference between revisions

Revision as of 22:49, 19 January 2009

Revision as of 09:22, 22 March 2009

Line 10:

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

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 --- perhaps it's a pointer, or perhaps it's a tag field, or perhaps it's a fixnum, but in any case, it's the next thing to look at. 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.

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.