BAKER'S ALGORITHM

Baker's algorithm illustrates the details of incremental collection. It is based on Cheney's copying collection algorithm, so it forwards reachable objects from from-space to to-space. Baker's algorithm is compatible with generational collection, so that the from-space and to-space might be for generation G₀, or might be G₀ +…+ G_k. To initiate a garbage collection (which happens when an allocate request fails for lack of unused memory), the roles of the (previous) from-space and to-space are swapped, and all the roots are forwarded; this is called the flip. Then the mutator is resumed; but each time the mutator calls the allocator to get a new record, a few pointers at scan are scanned, so that scan advances toward next. Then a new record is allocated at the end of the to-space by decrementing limit by the appropriate amount. The invariant is that the mutator has pointers only to to-space (never to from-space). Thus, when the mutator allocates and initializes a new record, that record need not be scanned; when the mutator stores a pointer into an old record, it is only storing a to-space pointer. If the mutator fetches a field of a record, it might break the invariant. So each fetch is followed by two or three instructions that check whether the fetched pointer points to from-space. If so, that pointer must be forwarded immediately, using the standard forward algorithm. For every word allocated, the allocator must advance scan by at least one word. When scan=next, the collection terminates until the next time the allocator runs out of space. If the heap is divided into two semi-spaces of size H / 2, and R < H / 4, then scan will catch up with next before next reaches halfway through the to-space; also by this time, no more than half the to-space will be occupied by newly allocated records. Baker's algorithm copies no more data than is live at the flip. Records allocated during collection are not scanned, so they do not add to the cost of collection. The collection cost is thus c₃ R. But there is also a cost to check (at every allocation) whether incremental scanning is necessary; this is proportional to H / 2 − R.

But the largest cost of Baker's algorithm is the extra instructions after every fetch, required to maintain the invariant. If one in every 10 instructions fetches from a heap record, and each of these fetches requires two extra instructions to test whether it is a from-space pointer, then there is at least a 20% overhead cost just to maintain the invariant. All of the incremental or concurrent algorithms that use a software write or read barrier will have a significant cost in overhead of ordinary mutator operations.