Introduction

What is a garbage collector ?

The goal of a garbage collector is to automatically manage the memory allocated by the user, reclaiming it when necessary.

Why garbage collect ?

Garbage collection inception at the end of the 1950s has opened the road to a world of possibilities in language and compiler theory. It has allowed developers to write code without worrying about double frees, memory leaks, or painful memory management architecture.

Throughout decades of research, garbage collection algorithms were improved to provide ever faster throughput for user applications, while maintaining the advantage of safer and more readable code.

However, garbage collection keeps a bad reputation in low level or embedded development, and is often reduced to an abstraction penalty, inevitably reducing the speed and responsiveness of our code in favor of more comfort, compared to the “pure” unrestricted access to memory allowed by languages such as C.

But is this bad reputation justified ? Are garbage collected languages destined to be relegated to high level applications ? Could a language like Java be used aboard a spaceship or in a medical equipment ?

In this article, we will explore the many methods developed to improve the speed and reduce the latency cost of garbage collection, allowing garbage collected languages to be used in mission critical real time systems.

The Traditional Garbage Collection Approaches

How does a GC traditionally work?

Many garbage collection algorithms were developed to fit the different needs of the many different managed languages used in the industry, but they eventually can be seen as combinations of three fundamental algorithms:

• Reference Counting: A counter per object allocated, incremented on assignment, and decremented on destruction of a variable.
• Mark & Sweep
• Copy Collection

The two latter fall in the category of what we call tracing garbage collection: the heap is viewed as a directed graph, where nodes are allocated objects, and edges are pointers.

When a collection cycle runs, the graph is then traversed by the collector starting from a set of pointers called the root set, corresponding to every pointer in storage directly accessible to the mutator (the user application). In practice, these roots correspond to:

• local variables (stored on the stack / in registers)
• global variables in static storage.

Tracing algorithms are therefore based on the reachability of objects by the mutator. A reachable object must be preserved, but an unreachable object should be reclaimed.

In this figure, p and r are roots. The objects holding 15, 12, and 7 are reachable, while the object holding 59 is not.

Mark Sweep

When the allocator runs out of memory, the collector stops the world, and begins marking every object reachable through the graph traversal. This is the mark phase. This step can be implemented via a depth-first search (DFS) traversal through recursive calls, or a with an explicit stack. Due to the fact that the memory consumption is made smaller, the explicit approach is often preferred to recursive calls, especially in more advanced garbage collectors that require access to an explicit mark stack.

Once every reachable object is marked, the collector loops over the entire heap and frees every unreachable (unmarked) object. Reachable objects are also unmarked to be ready for the next cycle.

The mark sweep is the most fundamental algorithm of garbage collection, and can be very easily plugged over almost any language that supports dynamic memory allocation.

Complexity of mark sweep collection

Considering R words of reachable data in a heap of H words, it may appear that the cost of mark sweep is dominated by H, since R often represents a small fraction of H.

However, a notable limitation of mark-sweep is the unpredictable nature of memory interactions in the marking phase. An object may reference other unrelated objects far away in memory, contrary to the sweeping phase, which is way more predictable memory-wise, and can also be optimized / deferred more easily.

Copy collection

Copy collection is a more refined idea that may seem inefficient at first:

The heap is split in two spaces (from-space and to-space), and a collection cycle creates a functionally equivalent copy of the from-space containing only reachable objects in the to-space. The to-space then becomes the new from-space for the next collection and so-on.

Copied objects are stored contiguously in memory, without fragmentation.

Complexity of copy collection

A strong advantage of the copy-collection is the fact that the total size of the heap H does not change the complexity of the algorithm, which only cares about reachable objects.

In a way, we can see mark and sweep as a “clean your room” method, while copy collection would be “keep your valuables and switch to another empty room once the current becomes too dirty”.

But still, how could copying the entire reachable heap be faster than calling free on each object of the unreachable heap?

Some very efficient algorithms and heuristics…

The way methods such as copy collection can be very efficient comes from three essential points:

• Compiler optimizations
• Efficient management of virtual memory
• Heuristics regarding object lifetime

Compiler Optimizations

A notable advantage of garbage collected languages is the context they operate into. Since the programmer gives up their control over memory, the compiler gains ownership of these allocations and is free to remove/ coalesce them, and many optimizations that would break the semantic of a language like C now become sound.

For example, many Java compilers perform escape analysis to determine if an allocation can be placed on the stack instead of allocating it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Foo
{
    public int v;
    
    public Foo(int v)
    {
        this.v = v;
    }
}

class Bar{}

public static int baz() {
    Foo foo = new Foo(4); //alloc
    Bar bar = new Bar(); //alloc
    return foo.v;
}

Caching & Virtual memory

An issue memory allocation models based on free lists suffer from is fragmentation.

When many blocks have been allocated then freed, fresh memory available for a new allocation may be scattered into non-contiguous holes. In this case, it may be that enough space is available in total for a new allocation, but that no contiguous block exist where it fits. This is called external fragmentation.

On a computer system with virtual memory or a memory cache, fragmentation can cause various kinds of issues. Objects that would occupy a few cache lines if memory was properly packed may be spread around multiple lines and pages, causing more cache misses, and a potentially way worse memory consumption than is actually necessary.

In this context, the copying behavior of the copy collection algorithm can eliminate the caching issues by enforcing a strong locality of reference between objects: Copied objects are stored contiguously, and related objects (such as the nodes of a linked list) can be placed as close to each other as possible to take advantage of the fact that they will likely be loaded together from the same cache line.

Also, this particular way of collecting garbage allows the allocator to work via a simple pointer bump, making allocation constant time !

For this reason, a proper copy collection algorithm may often dominate the capacities of a standard mark sweep collector.

Still, that leaves us with a billion dollar question: How do we deal with large (multi-megabyte objects) in a copy collector ? Could the advantages of both worlds be combined ?

The best of both worlds: Generational Collection

Generational collection is based on the generational hypothesis: most objects die young. The heap is split into generations (G0, G1, …, Gn), where new allocations go into G0. Objects surviving multiple collections are “promoted” to older generations.

This greatly improves performance: most collection cycles run exclusively on the youngest generation, where objects die quickly. The youngest gen typically uses a copy collector, making reclamation nearly free.

Since old objects may reference young ones, collectors use write barriers to track these cross-generational pointers in a remember-set, avoiding full heap scans when collecting young generations.

Almost every modern garbage collected language implements generational collection, reaching high throughput, at the cost of potentially high latency in the worst case.

…But not suitable for real time

So, a properly implemented generational collector in a type safe language should be the absolute go-to for any application ?

Well, not really. For now, every optimization trick we saw only aimed at optimizing speed, throughput, and memory consumption, but none addressed the issue of prolonged pause time.

Even with a fine tuned generational collector that manages to occupy only a few percent of the overall computation time, and manages to optimize the memory layout, the collector may occasionally interrupt the program for long periods to do a full collection of all generations. Although acceptable for applications where we are only interested in the final output (such as a compiler written in Haskell), this issue becomes undesirable for interactive applications (such as a Web server written in Go).

An article written by James Fisher for Pusher presented a benchmark comparing multiple languages, including Go and Haskell, on their performance for a pub/sub message bus.

Overall, Go performed way better latency-wise than Haskell. But how did it manage to reach such low pause times ?

How to Minimize Garbage-Collection-Induced Latency

Incremental collection

Until now, most of the optimization techniques we studied were focused on improving the throughput of the program, through general optimizations of memory layout and work distribution.

But all these optimizations may fall short when an application starts requiring interactivity. A user moving their mouse in a GUI does not want to regularly see the cursor stuck for half a second because the collector got stuck in a collection for a bit too long.

MMU

An important measure used to evaluate the capacity of a collector to provide low pause time is the Minimum Mutator Utilisation (MMU), corresponding to the minimum CPU time (y) the mutator is guaranteed to have in a time window (x).

For example, an MMU of 80% at 5 milliseconds means that the mutator is guaranteed to run for at least 4 out of every 5 milliseconds, and:

MMU(w) = the minimum, over all time windows of width w in the execution, of the mutator utilization in that window. In this case MMU(5ms) = 0.8.

In order to improve the average MMU over the runtime of the application, we use incremental garbage collection instead of stopping the world.

What is incremental collection ?

An incremental algorithm is one in which the collector operates only when the mutator requests it. The collector only works by small bits when convenient to the user program, hopefully managing to collect enough memory on each small run to avoid large pauses.

As simple and attractive as this idea looks, turning one collection cycle into many smaller incremental cycles is made tricky by the fact that collection cycles are no longer atomic regarding the state of the object graph. The mutator may update several objects and therefore change reachability mid collection.

The tricolor marking abstraction

A mark and sweep or copy collection algorithm can be abstracted by assigning one of three colors to each object. An object is either:

• Grey: objects have been visited (marked or copied), but their children have not yet been examined.
• White: objects are not yet visited by the depth-first or breadth-first search
• Black: objects have been marked, and their children also marked

And every regular tracing algorithm naturally preserves the two following invariants:

1. No black object points to a white object.
2. Every grey object is on the collector’s work list (the grey-set)

The Garbage Collection Handbook: The Art of Automatic Memory Management, ©2023 Richard Jones, Antony Hosking, Eliot Moss.

In a mark sweep algorithm, marking is done once there is no more grey object. White objects are thus unreachable and freed, while black objects are unmarked.

Tricolor marking in an incremental setting

The correctness of incremental collection therefore depends on the preservation of these invariants, even through modifications made by the mutator. Similarly to generational collection, this is done through write barriers that check writes on the heap.

Dijkstra’s write barrier:

atomic Write (src, i, ref):
    src[i] <- ref
    if isBlack(src)
        shade(ref)

If a black object is modified, the modified field must be colored grey to be put on the worklist and properly processed. Only a few instructions are added on write barriers, and they often are completely disabled if the collector is not in a running cycle and doesn’t need to preserve invariants.

An incremental mark sweep collection cycle is therefore split into 4 main parts:

1. Stop every mutator thread to examine their stack and color roots grey.
2. Incremental slices of tracing until there are no more grey objects
3. Stop every mutator thread to examine remaining stack roots. If the stack is not entirely black, it means the mutator has modified a root during the cycle and we have to continue.
4. Lazy Sweeping: The collector does not sweep directly after marking, but instead delegates sweeping to the allocator that will look itself for a free block.

The actual cost of turning a standard method such as mark sweep into its incremental counterpart is therefore relatively low, and incremental collection can thus turn a 200ms collection pause into multiple few-milliseconds pauses, and bring an application to very low latency, for an unnoticeable tradeoff in speed.

How Unity prevents frame drops

A great example of incremental collection is the Unity garbage collector.

Since it is made to develop video games, it requires a high level of interactivity, and therefore uses the Boehm-Demers-Weiser garbage collector in incremental mode.

The average performances stay very similar, but incremental collection prevents spikes that dropped frame rate to around 15 frames per second:

Profiler without incremental collection - Screenshot from the Unity documentation

Profiler with incremental collection - Screenshot from the Unity documentation

Soft Real Time Garbage collection

Back in the beginnings of incremental collection, this method was often labeled as real-time, due to the fact that they were developed for applications where long pauses caused a degraded quality.

However, many of the mechanisms implemented by incremental collectors prevent them from guaranteeing progress at several steps, and therefore cannot be considered strictly real time by current definitions.

Real time systems

A real-time system is defined by three primary characteristics:

• Timeliness: The ability of the system to satisfy time constraints
• Predictability: The predictability of the response time
• Fault-tolerance: How the system should react to a missed deadline

In a soft real time system such as a game engine, missed deadlines can be tolerated, and will only cause a degraded quality of the service. On hard real time systems such as a medical device or an airbag, missed deadlines are considered to be a failure of the system.

How to make incremental collection viable for soft real time ?

A major concern of soft real time garbage collection is to be able to respect (most) deadlines. In our current incremental setting, we still have several limitations:

• Regular unbounded pauses: Standard incremental collectors require a final stack scan to ensure that every reachable object is properly colored, since the write barrier only covers writes to the heap.

• The collector decides when to stop: In an incremental collector, the mutator is the one that triggers the collection. It therefore has no notion of scheduling or deadline, and may impose too many slices in a period of time.

• Large objects: The capacity for low latency of an incremental collector is largely vulnerable to the presence of large objects on the heap. Scanning an object tens of megabytes large may cause an unacceptable pause.

  • Incremental collectors that compact memory used additional methods such as read barriers to lazily copy objects between the from-space and to-space, causing unpredictable pause time on load of large objects
  • Those who do not compact memory may suffer from fragmentation forcing either a full pause to run a compaction, or a longer allocation time.

Among these limitations, the two most prevalent are the initial and final stack scanning to color roots grey and check that every root is black respectively.

Stack Scanning

The solution implemented by the Go language to avoid a full stop the world root scan is not to directly run the scanning, but to instead delegate it to thread specific safepoints.

Since much of the work is decomposed into goroutines, the collector only stops the world to enqueue root-marking jobs, one per goroutine. The goroutine then finds a safepoint where it is most optimal to perform the stack scanning (mostly when in a blocked state), greatly reducing the cost of scanning.

Stack Rescanning

A modern solution to stack re-scanning implemented by Go is to use a hybrid barrier, where the Dijkstra write barrier is combined with Yuasa’s deletion barrier.

The goal of this barrier is to keep the set of reachable objects the exact same at the beginning and at the end of marking.

When a field of a white (possibly reachable) or grey (reachable) object is overridden, the field is conservatively greyed:

atomic Write(src, i, ref):
    if isGrey(src) || isWhite(src)
        color src[i] grey
    src[i] <- ref

This way, if the mutator makes src[i] (which was reachable) unreachable, it is still kept alive, and we do not need a rescan to take modifications of the root set into account.

…Constraints that do not fit hard real time

Still, can we call the Go garbage collector real-time ? Once again, no.

Many of these optimizations are best effort practices to reduce latency to a very low level, but do not guarantee any actual bound. A sudden rush of object allocations may unpredictably slow down the application and cause deadline miss, or the collector may stick too many collection slices in a too small time window.

To address these constraints, real-time systems need to ensure that every operation can be bounded. Therefore, a hard real time garbage collector must not have operations whose complexity depends on the size of the heap/stack, or any other unboundable value.

Hard Real-Time collection

The need to bound the worst-case execution time

The worst-case execution time of a task is the maximum time a task can take to execute.

Contrary to most applications aiming for soft real time / low latency, a hard real-time system needs to satisfy deadlines in a bounded time, and how fast it does that does not really matter. If the deadline for a task is 15ms, accomplishing it in 2ms or 13ms is the same regarding the correctness of the program.

Therefore, many algorithms used to make garbage collection truly real time do not hesitate to sacrifice (reasonable) performance to guarantee a bounded execution time of each collection task.

Bounding object size

One of the sticking issues of making garbage collection acceptable for hard real time is the need to do operations relative to the size of objects, particularly scanning. A solution to this issue used by many hard real time garbage collectors is the use of Arraylets:

Large arrays are split into one large spine array of bounded size that holds pointers to sub arrays of fixed size.

In a language with enough abstraction such as Java, classic array operations such as indexing or iterating can be rearranged by the runtime system to accommodate this new representation.

Work-Based Scheduling

Although we did not formalize it, every incremental technique we talked about until now is what we call work-based, meaning that the collector work is proportional to the allocation rate.

Jamaica VM

The Jamaica VM is an implementation of the Java Virtual Machine Specification that differs wildly from the others as it strives to provide hard real-time guarantees, and is based on the Real-Time Specification for Java.

It is widely used in industry such as car manufacturing, and in various IoT solutions.

Jamaica’s garbage collector is incremental to an extreme extent: single incremental steps correspond to scanning only 32 bytes of memory and have a worst-case execution time in the order of one microsecond. This is achieved through several key techniques:

Allocation

Being a work-based collector, the Jamaica VM must ensure that none of the work that is started cannot be bounded or interrupted.

To do this, the VM has a very special allocation policy, based on the arraylets technique.

The only chunks of memory available are 32 bytes long, and a larger object must be decomposed (at compile time) into several 32 bytes chunks. This makes any access boundable since the offset of a field in an object is a compile time constant.

When it allocates memory, the VM imposes a precisely calculated number of 32 bytes increments, so that the allocation “pays” for what it allocates.

Since the size of an object is also known at compile time, this number of increment can be analyzed to make this work based solution viable in a hard Real-time setting.

Root Arrays

Another major issue we have encountered multiple times is the scanning of roots. Although accommodable to soft real time, this step can never be fully bounded, and other tricks had to be found.

The approach to root scanning taken by Jamaica is quite radical: there is only one single root pointer, and all other references that are present locally in registers or on stacks also have to be present on the garbage collected heap.

For the mutator, this corresponds to storing every root in a separate data structure called the root array that would also be garbage collected. Each write to a reference on the stack would therefore need to be copied on this same data structure to preserve the soundness of the tracing.

This forces a relatively strong overhead on stack writes, but removes the complexity of stack scanning. According to Siebert, this process forces an 11.8% overhead on mutator work.

Time-Based Scheduling

The Metronome real time collector

Contrary to work-based collection, time-based real time collection takes the MMU as an input to its scheduling.

The Metronome garbage collector was developed by IBM. for Java to provide hard real-time guarantees with predictable, short pause times. Rather than triggering collection based on allocation pressure, Metronome schedules collection work in fixed time slices interleaved with mutator execution.

The way Metronome organizes its execution time is rather simple: a percentage of execution time is guaranteed to the mutator, and the remaining time can be used by the collector.

Time is split into quantum, a small fixed interval of work. Therefore, with a collector quantum C_T and a mutator quantum Q_T, the computation of the MMU becomes:

lim u_T(dt) = Q_T / (Q_T + C_T) as dt goes to inf

By default, Metronome enforces a MMU of 70% for 10ms, with a worst pause time of 1ms.

Two threads are used by Metronome to schedule the collector’s work:

• An alarm thread
• A collector thread

The alarm thread is a very lightweight thread that wakes up every 500 microseconds to check if a collector quantum should be scheduled. The collector thread does the actual collection work, and may be preempted when its quantum ends.

Conclusion

Overall, the choice of garbage collection algorithm to incorporate in a language depends vastly on the use cases, and Real-time garbage collection is not better because it requires more elaborate work.

Real-time collectors have to make sacrifices to fix strict boundaries that are vital to the applications they are designed for, but that do not matter to the average interactive application, for whom a less restrictive model will be a better option.

There is not a single good solution, and a large part of choosing a language for a task is choosing a memory management model, be it garbage collection or not.

Bibliography

• The Garbage Collection Handbook - The art of automatic memory management
• Andrew W. Appel - Modern Compiler Implementation in ML
• Jim Fisher - Low latency, large working set, and GHC’s garbage collector: pick two of three

Incremental garbage collection

• The Go garbage collector - Latency
• The Unity incremental collector
• The Boehm-Demers-Weiser garbage collector
• Dijkstra et al. - On-the-Fly Garbage Collection: An Exercise in Cooperation (1978)
• Yuasa - Real-Time Garbage Collection on General-Purpose Machines (1990)
• Lindström - Understanding and Improving Garbage Collection in Real-Time Java (2020)

Hard real time

• Schoeberl & Vitek - Garbage collection for safety critical Java (DTU)
• aicas - Jamaica VM
• Bacon, Cheng & Rajan - The Metronome: A Simpler Approach to Garbage Collection in Real-Time Systems (2003)
• IBM - Metronome GC Policy Documentation
• Bollella et al. - The Real-Time Specification for Java (2000)