Introduction: A copying collector reserves, ahead of time, space to which the objects can move, thus breaking the dependency between tracing and finding free space.
The memory space is partitioned into two semispaces, A and B. The mutator allocates memory in one semispace, say A, until it fills up, at which point the mutator is stopped and the garbage collector copies the reachable objects to the other space, say B. When garbage collection completes, the roles of the semispaces are reversed. The mutator is allowed to resume and allocate objects in space B, and the next round of garbage collection moves reachable objects to space A. The following algorithm is due to C. J. Cheney.
Algorithm: Cheney's copying collector.
INPUT: A root set of objects, and a heap consisting of the From semispace, containing allocated objects, and the To semispace, all of which is free.
OUTPUT: At the end, the To semispace holds the allocated objects. A free pointer indicates the start of free space remaining in the To semispace. The From semispace is completely free.
METHOD: The algorithm is shown in Fig. 7.28. Cheney's algorithm finds reachable objects in the From semispace and copies them, as soon as they are reached, to the To semispace. This placement groups related objects together and may improve spatial locality.
Before examining the algorithm itself, which is the function Copying Collector m. Fig. 7.28, consider the auxiliary function Look up New Location in lines (11) through (16). This function takes an object o and finds a new location for it in the To space if o has no location there yet. All new locations are recorded in a structure New Location, and a value of NULL indicates o has no assigned location.5 As in Algorithm 7.15, the exact form of structure New Location may vary, but it is fine to assume that it is a hash table.
If we find at line (12) that o has no location, then it is assigned the beginning of the free space within the To semispace, at line (13). Line (14) increments the free pointer by the amount of space taken by o, and at line (15) we copy o from the From space to the To space. Thus, the movement of objects from one semispace to the other occurs as a side effect, the first time we look up the new location for the object. Regardless of whether the location of o was or was not previously established, line (16) returns the location of o in the to space.
Now, we can consider the algorithm itself. Line (2) establishes that none of the objects in the from space have new addresses yet. At line (3), we initialize two pointers, unscanned and free, to the beginning of the To semispace. Pointer free will always indicate the beginning of free space within the To space. As we add objects to the To space, those with addresses below unscanned will be in the Scanned state, while those between unscanned and free are in the Unscanned state. Thus, free always leads unscanned, and when the latter catches up to the former, there are no more Unscanned objects, and we are done with the garbage collection. Notice that we do our work within the To space, although all references within objects examined at line (8) lead us back to the From space.
Lines (4) and (5) handle the objects reachable from the root set. Note that as a side effect, some of the calls to Lookup New Location at line (5) will increase free, as chunks for these objects are allocated within To. Thus, the loop of lines (6) through (10) will be entered the first time it is reached, unless there are no objects referenced by the root set (in which case the entire heap is garbage). This loop then scans each of the objects that has been added to To and is in the Unscanned state. Line (7) takes the next unscanned object, o. Then, at lines (8) and (9), each reference within o is translated from its value in the From semispace to its value in the To semispace. Notice that, as a side effect, if a reference within o is to an object we have not reached previously, then the call to Lookup New Location at line (9) creates space for that object in the To space and moves the object there. Finally, line (10) increments unscanned to point to the next object, just beyond o in the To space.