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:
- Using a software check at each heap memory reference.
- Using a hardware check (typically by invalidating pages)
- By always having an extra level of indirection.
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 markt@chaos.org.uk
Fri 29 December 1995