Next | Prev | Up

Incremental Copying Garbage Collection

This is really a very straight-forward adaption of the Simple copying GC algorithm. The prime difference is that the GC processing is time-sliced between periods of mutator activity, and forwarding pointers are visible to the mutator.

Clearly there is an efficiency penalty to pay, since every read and write to an object in mutator code has to involve a test for a forwarding pointer in some fashion. There are three general ways this can be done:

The software check is likely to be voluminous, since the forwarding pointer has to be identified as such, then followed, and finally the original pointer is overwritten with the forwarded value (to speed up future access).

The hardware solution on stock platforms is usually to write-protect pages that can contain forwarded objects. The page-trap handler then goes through and forwards all the objects referenced from the page, and can then retry the offending instruction.

The extra-level of indirection approach is really a variant of the software test, except that no conditional instructions are needed, only one extra load for each memory reference. Compare this with object-table techniques.

Advantages of Incremental Collection

The chief advantage of the interleaved nature of this method of collection is the much faster response-time of applications using the heap---the worst case delay due to collection activity can be almost arbitrarily small. Thus the applications are in interactive user environments/OSs and also hard real-time control applications.

There are ways to make other algorithms incremental, but none are as easy to design and implement as with copying. [INCOMPLETE]

Last updated by Fri 29 December 1995