Uniprocessor Garbage Collection Techniques

Recently, Baker [Bak92] has proposed a new kind of non-copying collector that with some of the efficiency advantages of a copying scheme. Baker's insight is that in a copying collector, the "spaces" of the collector are really just a particular implementation of sets. Another implementation of sets could do just as well, provided that it has similar performance characteristics. In particular, given a pointer to an object, it must be easy to determine which set it is a member of; in addition, it must be easy to switch the roles of the sets, just fromspace and tospace roles are exchanged in copy collector.

The basic idea is that only one heap exists, and blocks are linked in a doubly-linked list, and each block has a flag that indicates which "space" it belongs to. At gc time, live objects are unlinked from the list and their space flag is flipped to indicate they have been "moved".

Three basic cost components:

1. Initial work required at each collection, such as root set scanning.
2. Work done per unit of allocation.
3. Work done during garbage detection (tracing).

Basically: there is no clear winner among the simple collectors presented above. It depends on how your program is allocating memory, and on various constant factors for a particular implementation.

• Poor locality of allocation and reclamation cycles will generally cause paging. For example, if all pages in the heap must be allocated before a reclamation cycle begins. For this reason, it's generally not worthwhile to have a heap that's too large to fit in physical memory.
• By the time memory is reclaimed and reused, it's likely to have been paged out.
• Compaction is helpful, but generally "too little, too late." A simpleminded semispace copying collector is like to have more locality problems than mark-sweep simply because the copy collector uses twice the memory.
• GC pauses are annoying at best.

Garbage collection algorithms can be described as a process of traversing the graph of reachable objects and coloring them. The objects subject to garbage collection are conceptually colored white, and by the end of collection, those that will be retained must be colored black…

the mutator can't be allowed to change things "behind the collector's back" in such a way that the collector will fail to find all reachable objects.

To understand and prevent such interactions between the mutator and the collector, it is useful to introduce a third color, grey, to signify that an object has been reached by the traversal, but that its descendants may not have been…

The importance of this invariant is that the collector must be able to assume that it is "finished with" black objects, and can continue to traverse grey objects and move the wavefront forward. If the mutator creates a pointer from a black object to a white one, it must somehow coordinate with the collector, to ensure that the collector's bookkeeping is brought up to date.

Baker's collector is a variation of the simple copying scheme in § 2.4 that uses a read barrier for coordination with the mutator.

Breadth-first copying proceeds interleaved with mutator operation. Any allocations done by the mutator are placed in the tospace, and therefore won't be gc'ed until the next cycle.

In order to ensure that all live objects are copied before new allocations exhaust tospace, gc is tied to allocations so that an incremental amount of gc is done for each allocation.

Additionally, the mutator is prevented from storing pointers into fromspace. If the mutator attempts to read a pointer to an object in fromspace, it's immediately copied to tospace and the pointer is updated.

The read barrier has the downside of being slow compared to a direct pointer access, since every pointer read must be checked and possibly redirected. Brook's proposed a variation where every object is accesses via an indirection pointer contained in the object. If the object lives in tospace, the object's indirection pointer points to itself. If the object is an obsolete copy in the fromspace, the indirection pointer points to the new version in tospace. Always accessing the pointer through indirection is slightly cheaper than conditional indirection, but still expensive compared to normal pointer access.

The Treadmill scheme is a combination of Baker's scheme from the previous section and the non-copying collector described in § 2.5.

The basic idea is that the freelist, from-space, to-space, and new-space are all linked together in a circular structure. At the start of gc, the new-space and to-space are both empty. Root objects are moved from the from-space list to the to-space list and marked grey. Scanning proceeds through the to-space marking scanned objects black. Allocation during gc happens in the new-space by following a pointer to the next block on the freelist. Newly allocated objects are immediately marked black. At the end of the gc cycle, the from-space can be appended to the freelist, and the new-space and to-space will become the new from-space on the next cycle.

See also: http://www.pipeline.com/~hbaker1/NoMotionGC.html

When using a non-copying collector, there is no need for a read barrier. A write barrier can be used instead to prevent the mutator from overwriting a pointer to a live object.

Conceptually, at the beginning of GC, a virtual copy-on-write copy of the graph of reachable objects is made.

One simple and well-known snapshot algorithm is Yuasa's. If a location is written to, the overwritten value is first saved and pushed on a marking stack for later examination.

Best known algorithm due to Dijkstra et al. [DLM+78], which is similar to [Ste75], but simpler because it doesn't deal with compacting.

Rather than retaining everything that's live at the beginning of gc, incremental-update algorithms heuristically (and conservatively) attempt to retain all objects that are live at the end of gc. Objects that die during collection–and before being reached by marking traversal–are not traversed and marked.

Writes to pointers are trapped and the collector is notified if the mutator stores a pointer to a white object into a black object. The black object is then effectively greyed and re-scanned before gc terminates.

Thus, objects that become garbage during collection may be reclaimed at the end of the gc cycle, similar to Baker's read-barrier algorithm.

Incremental Update is less conservative than Baker or Yuasa's schemes w.r.t. newly allocated objects. In Baker's scheme, newly allocated objects are allocated "black", i.e. assumed to be live objects. In the Dijkstra et al. scheme, objects are allocated "white", and only marked when the set of roots is traversed.

The choice of a read- or write-barrier scheme is likely to be made on the basis of the available hardware. Without specialized hardware support, a write-barrier appears to be easier to implement efficiently, because heap pointer writes are much less common than pointer traversals.

Appel, Ellis and Li [AEL88] use virtual memory (pagewise) access protection facilities as a coarse approximation of Baker's read barrier…

Of write barrier schemes, incremental update appears to be more effective than snapshot approaches…

Careful attention should be paid to write barrier implementation. Boehm, Demers and Shenker's incremental update algorithm uses virtual memory dirty bits as a coarse pagewise write barrier…

In a system with compiler support for garbage collection, a list of stored-into locations can be kept, or dirty bits can maintained (in software) for small areas of memory…

In order for the generational scheme to work, it's necessary to be able to detect references from older generations to newer generations when scavenging, otherwise some live objects in the newer generation may be reclaimed, or else pointers to the object will not be updated when it's copied.

In the original generational scheme, no pointer in old memory may point directly to an object in new memory; instead it must point to a cell in an indirection table, which is used as part of the root set.

On stock hardware, the indirection table introduces an overhead similar to Baker's read barrier, in which case it might make more sense to use a pointer recording technique.

Rather than indirecting pointers from old objects to young ones, normal (direct) pointers are allowed, but the locations of such pointers are noted so that they can be found at scavenge time. This requires something like a write barrier; that is, the running program cannot freely modify the reachability graph by storing pointers into objects in older generation…

The important point is that all references from old to new memory must be located at scavenge time, and used as roots for the copying traversal…

As in an incremental collector, this use of a write barrier results in a conservative approximation of true liveness; any pointers from old to new memory are used as roots, but not all of these roots are necessarily live themselves.

Within a generational collector, the write barrier cost is likely to be the most expensive operation.

Several important questions regarding generational collectors remain:

1. Advancement policy. How long must an object survive in one generation before it is advanced to the next?
2. Heap organization. How should storage space be divided between and within generations? How does the resulting reuse pattern affect locality at the virtual memory level? At the cache level?
3. Traversal algorithms. In a tracing collector, the traversal of live objects may have an important impact on locality. In a copying collector, objects are also reordered as they are copied. What affect does this have on locality, and what traversal yields the best results?
4. Collection scheduling. For a non-incremental collector, how might we avoid disruptive pauses? Can we improve efficiency by opportunistic scheduling? Can this be adapted to incremental schemes to reduce floating garbage?
5. Intergenerational references. What is the best way to detect intergenerational references?