COPYING COLLECTION

The reachable part of the heap is a directed graph, with records as nodes, and pointers as edges, and program variables as roots. Copying garbage collection traverses this graph (in a part of the heap called from-space), building an isomorphic copy in a fresh area of the heap (called to-space). The to-space copy is compact, occupying contiguous memory without fragmentation (that is, without free records interspersed with the reachable data). The roots are made to point at the to-space copy; then the entire from-space (garbage, plus the previously reachable graph) is unreachable. Image 13.7 illustrates the situation before and after a copying collection. Before the collection, the from-space is full of reachable nodes and garbage; there is no place left to allocate, since next has reached limit. After the collection, the area of to-space between next and limit is available for the compiled program to allocate new records. Because the new-allocation area is contiguous, allocating a new record of size n into pointer p is very easy: Just copy next to p, and increment next by n. Copying collection does not have a fragmentation problem.
Image 13.7: Copying collection.

Eventually, the program will allocate enough that next reaches limit; then another garbage collection is needed. The roles of from-space and to-space are swapped, and the reachable data are again copied. Initiating a collection To start a new collection, the pointer next is initialized to point at the beginning of to-space; as each reachable record in from-space is found, it is copied to to-space at position next, and next incremented by the size of the record. Forwarding The basic operation of copying collection is forwarding a pointer; that is, given a pointer p that points to from-space, make p point to to-space (Algorithm 13.8).ALGORITHM 13.8: Forwarding a pointer.

function Forward(p)
 if p points to from-space
 then if p. f₁ points to to-space
 then return p. f₁
 else for each field f_i of p
 next. f_i � p. f_i
 p. f₁ ← next
 next ← next+ size of record p
 return p. f₁
 else return p

There are three cases:

If p points to a from-space record that has already been copied, then p. f₁ is a special forwarding pointer that indicates where the copy is. The forwarding pointer can be identified just by the fact that it points within the to-space, as no ordinary from-space field could point there.
If p points to a from-space record that has not yet been copied, then it is copied to location next; and the forwarding pointer is installed into p. f₁. It's all right to overwrite the f₁ field of the old record, because all the data have already been copied to the to-space at next.
If p is not a pointer at all, or if it points outside from-space (to a record outside the garbage-collected arena, or to to-space), then forwarding p does nothing.

Cheney's algorithm The simplest algorithm for copying collection uses breadth-first search to traverse the reachable data (Algorithm 13.9, illustrated in Image 13.10). First, the roots are forwarded. This copies a few records (those reachable directly from root pointers) to to-space, thereby incrementing next.
Image 13.10: Breadth-first copying collection. ALGORITHM 13.9: Breadth-first copying garbage collection.

scan ← next ← beginning of to-space
for each root r r ← Forward(r)
while scan < next
 for each field f_i of record at scan
 scan. f_i Forward(scan. f_i)
 scan ← scan+ size of record at scan

The area between scan and next contains records that have been copied to to-space, but whose fields have not yet been forwarded: In general, these fields point to from-space. The area between the beginning of to-space and scan contains records that have been copied and forwarded, so that all the pointers in this area point to to-space. The while loop (of Algorithm 13.9) moves scan toward next, but copying records will cause next to move also. Eventually, scan catches up with next after all the reachable data are copied to to-space. Cheney's algorithm requires no external stack, and no pointer reversal: It uses the to-space area between scan and next as the queue of its breadth-first search. This makes it considerably simpler to implement than depth-first search with pointer reversal. Locality of reference However, pointer data structures copied by breadth-first have poor locality of reference: If a record at address a points to another record at address b, it is likely that a and b will be far apart. Conversely, the record at a + 8 is likely to be unrelated to the one at a. Records that are copied near each other are those whose distance from the roots are equal. In a computer system with virtual memory, or with a memory cache, good locality of reference is important. After the program fetches address a, then the memory subsystem expects addresses near a to be fetched soon. So it ensures that the entire page or cache line containing a and nearby addresses can be quickly accessed. Suppose the program is fetching down a chain of n pointers in a linked list. If the records in the list are scattered around memory, each on a page (or cache line) containing completely unrelated data, then we expect n difference pages or cache lines to be active. But if successive records in the chain are at adjacent addresses, then only n/k pages (cache lines) need to be active, where k records fit on each page (cache line). Depth-first copying gives better locality, since each object a will tend to be adjacent to its first child b, unless b is adjacent to another "parent" a′. Other children of a may not be adjacent to a, but if the subtree b is small, then they should be nearby. But depth-first copy requires pointer-reversal, which is inconvenient and slow. A hybrid, partly depth-first and partly breadth-first algorithm can provide acceptable locality. The basic idea is to use breadth-first copying, but whenever an object is copied, see if some child can be copied near it (Algorithm 13.11).ALGORITHM 13.11: Semi-depth-first forwarding.

function Forward(p)
 if p points to from-space
 then if p. f₁ points to to-space
 then return p. f₁
 else Chase(p); return p. f₁
 else return p
function Chase(p)
 repeat
 q next
 next ← next+ size of record p r ← nil
 for each field f_i of record p q. f_i ← p. f_i
 if q. f_i points to from-space and q. f_i . f₁ does not point to to-space
 then r ← q. f_i
 p. f₁ ← q p ← r
 until p = nil

Cost of garbage collection Breadth-first search (or the semi-depth-first variant) takes time proportional to the number of nodes it marks, that is, c₃ R for some constant c₃ (perhaps equal to 10 instructions). There is no sweep phase, so c₃ R is the total cost of collection. The heap is divided into two semi-spaces, so each collection reclaims H = 2 − R words that can be allocated before the next collection. The amortized cost of collection is thus Java ScreenShot

instructions per word allocated.

As H grows much larger than R, this cost approaches zero. That is, there is no inherent lower bound to the cost of garbage collection. In a more realistic setting, where H = 4R, the cost would be about 10 instructions per word allocated. This is rather costly in space and time: It requires four times as much memory as reachable data, and requires 40 instructions of overhead for every 4-word object allocated. To reduce both space and time costs significantly, we use generational collection.