A simple incremental low-pause GC design §

Intended characteristics §

There are a few characteristics the desired collector should meet:

• It should be incremental. Since my toy lisp is single-threaded, interleaving the execution of mutator and the collector is the only option. The simplest way to achieve that is to run a small number of steps every time the mutator allocates, so that's what I'll go with.
• It should have a dynamically resizeable heap. I dislike having to guess at startup how much memory will a program require, so I want to avoid that. It should also promptly release unused memory to the operating system, to avoid memory-hogging.
• It should, as mentioned previously, minimize the pause time.
• It should be compacting to combat heap fragmentation. This also means it should be precise, as conservative moving collectors are possible, but difficult to get right.
• It should not be generational. There are real world workloads, such as LRU caches, that don't perform well with generational collectors.

Do note that throughput is not a goal. While good throughput obviously would be nice, minimizing latency and footprint is more important.

With these in mind, I decided on a mostly-concurrent incremental regionalized mark-copy collector described in more detail below.

Heap layout §

Since the heap is intended to be dynamically resizeable in both directions, using a contiguous heap is not a possibility, as growing a contiguous heap would essentially require a huge stop-the-world pause to copy everything over and update the references.

Instead, the heap is allocated and freed one region at a time, where each region is a large-ish chunk of memory, arbitrarily sized at 16 megabytes to allow the usage of hardware's huge pages for backing each region on pretty much every architecture out there. This value may need experimental tuning to achieve the best performance.

Objects are allocated by taking a fresh region, called nursery, and bumping a pointer. Once the free space in the current nursery runs out, another one is allocated, and a collection cycle may be started.

Objects too big to fit in a standard region, such as large arrays, are allocated separately in a region of their own, termed a humongous region, which holds only that single object. In fact, a limit smaller than the entire size of a standard region is probably better, to minimize the wasted space in standard regions in presence of frequent large allocations, such as one quarter or even one eighth of a standard region.

C++
struct region {
    void* region_start;
    size_t region_size;
    dynamic_bitset mark_bits;
    bool is_humongous;
};

Phases §

Like any tracing garbage collector, this collector works in phases. Most of the work is done in the concurrent phases, due to low-latency focus.

1. Mark roots: a stop-the-world phase where the objects pointed to from the root set are marked reachable and added to the scanning queue. Marking roots concurrently is hard, and since the size of the root set tends to stay constant no matter the heap size, pausing the mutator is not too big of a deal.
2. Incremental mark: an incremental phase where the objects in the scanning queue are scanned for references, marking the pointed-to objects and putting them in the scanning queue. This is where most of the classical marking work is done.
3. Remark roots: a stop-the-world phase where the root set is scanned again to pick up any possible changes in the live set. This very rarely results in any significant amount of work, because almost everything has already been marked. Additionally, regions that don't contain any live objects are immediately freed in this stage, and a collection set of regions that contain both live objects and enough dead objects to warrant collection is constructed.
4. Incremental evacuation: an incremental phase where the live objects are copied from regions in the collection set to freshly-allocated regions. This is where most of the classical evacuation work is done. An important thing to note is that once an object has been copied no reads or written happen to the copy in the collection set, all using the fresh copy instead.
5. Update roots: a stop-the-world phase where the references that point to the collection set in the root set are updated to point to the fresh object copies instead. Similar caveats as with the mark roots phase apply.
6. Update references: an incremental phase where a heap walk is performed to replace every references to a live object in the collection set with one to the fresh copy.
7. Cleanup: the collection set regions are simply freed.

Invariants and barriers §

Since this collector is incremental, it requires cooperation with the mutator to ensure that certain properties are never violated. These invariants are enforced by injecting barriers (nothing to do with processor memory barriers!) into the mutator for certain operations. There are two notable invariants that require barriers in this design:

• The tri-color invariant: during marking, objects are split into three sets: black, gray and white.
  • Black objects are those that are known to be reachable and have already been traversed. In this collector, these are the objects whose mark bit is set and are not in the scanning queue.
  • Gray objects are those that are known to be reachable, but have not yet been traversed. This corresponds to objects whose mark bit is set and are in the scanning queue.
  • White objects are those that haven't yet been determined to be reachable, this corresponds to object whose mark bit is clear. All objects that remain white after remarking roots are dead.
  The invariant is therefore no black objects points to a white object.
• The strong to-space invariant: during evacuation and reference updating, all reads and writes happen to/from the fresh copy of an object.

The mutator can freely read and modify the heap with no restrictions during the incremental phases, so every time a potentially problematic operation occurs — a write in case of the tri-color invariant, a reference read in case of the strong to-space invariant — the collector needs to execute a barrier to have a chance to maintain the invariants.

Somewhat arbitrarily I chose to have the regions created during incremental marking be assumed black, so they're not scanned. If they contain garbage, this garbage won't be reclaimed until the next cycle, but is otherwise harmless.

As a consequence of the strong to-space invariant, the objects created after the stop-the-world update roots phase are guaranteed to not contain pointers to the collection set, because there is no way to obtain such pointers anymore. This lets the incremental reference update skip those object, saving some work.

C++
void garbage_collector::write_barrier(object& referrer, object& old_referent)
{
    if(!is_marking()) {
        // No need to do anything if not in marking phase.
        return;
    }
    if(is_marked(referrer) && !is_marked(old_referent)) {
        mark(old_referent);
        scanning_queue.push(old_referent);
    }
}

C++
reference garbage_collector::load_reference_barrier(reference& ref)
{
    if(!in_evacuation() && !in_update_references()) {
        // Nothing to do here, maybe check if the object has no forwarding
        // pointer for debugging.
        return ref;
    }
    if(!collection_regions.contains(region_of_object(ref))) {
        // Ditto.
        return ref;
    }
    if(!is_forwarded(ref)) {
        assert(in_evacuation());
        ref = evacuate_object(ref);
    } else {
        ref = get_forwarding_pointer(ref);
    }
    return ref;
}

Conclusion §

That's about it for the design. While it certainly is more complicated than just a stop-the-world mark-and-sweep, it's also significantly better in many important ways such as latency, and is not too hard to understand, it just has many moving parts.

I am currently in the process of implementing it, to see how well it performs in practice, and how well it's amenable to tuning. I'll come back with measurements once that's ready.