Understanding JVM Garbage Collector Performance

At its core, a garbage collector helps manage the free memory of a program, often called the heap. The memory of a program can be modelled as a linear sequence of storage locations, e.g. below where we have 16 slots in memory:

These storage locations can contain objects (below named foo, bar, qux, baz) that take up memory and may reference other objects (solid arrows). Furthermore, the values may be referenced from outside the heap (dashed lines), e.g. from the "stack" which represents local variables in methods that are currently being run (shown below) or from static global variables (not shown). We keep a free-memory pointer to the first empty slot on the right.

If we want to allocate a new object new1, we can simply put it at the location of the free-memory pointer (green below), and bump the pointer 1 slot to the right

Similarly, objects may stop being referenced, e.g. bar below no longer has a reference pointing at it from the stack. This may happen because a local variable on the stack is set to null, or because a method call returned and the local variables associated with it are no longer necessary

For the purposes of this example, we show all objects on the heap taking up 1 slot, but in real programs the size of each object may vary depending on the fields it has or if it’s a variable-length array.

The simplest kind of garbage collector splits the 16-slot heap we saw earlier into two 8-slot halves. If we want to allocate 4 more objects (new2, to new5), but there are only 3 slots left in that half of the heap, we will need to do a collection:

To do a collection, the GC first starts from all non-heap references (e.g. the STACK references above) often called "GC roots". It then traces the graph of references, highlighted red below:

Here, we can see that foo is not referenced ("garbage"), qux and new1 are referenced directly from the STACK, and baz is referenced indirectly from qux. bar is referenced by foo, but because foo is itself garbage we can count bar as garbage as well.

We then copy all objects we traced (often called the live-set) from HALF1 to HALF2, adjust all the references appropriately. Now HALF2 is the half of the heap in use, and HALF1 can be reset to empty.

This collection has freed up 5 slots, so we now have space to allocate the 4 new2 to new5 objects we wanted (green) starting from our free-memory pointer:

You may notice that the objects foo and bar disappeared. This is because foo and bar were not referenced directly or indirectly by any GC roots: they were unreachable, and thus considered "garbage". These garbage objects were not explicitly deleted, but simply did not get copied over from HALF1 to HALF2 during collection, and thus were wiped out when HALF1 was cleared.

As your program executes, the methods actively running may change, and thus the references (both from stack to heap and between entries on your heap) may change. For example, we may stop referencing qux, which also means that baz is now unreachable:

Although qux and baz are now "garbage", they still take up space in the heap. Thus, if we want to allocate two new objects (e.g. new6 and new7), and there is only one slot left on the heap (above), we need to repeat the garbage collection process: tracing the objects transitively reachable (new1, new2, new3, new4, new5), copying them from HALF2 to HALF1, adjusting any references to now use HALF1 as the new heap, and clearing anything that was left behind in HALF2. This then gives us enough space to allocate new6 and new7 (below in green):

This process can repeat as many times as necessary: as long as there are some objects that are unreachable, you can run a collection and copy the "live" objects to the other half of the heap, freeing up some space to allocate new objects. The only reason this may fail is that if you run a collection and there still isn’t enough space to allocate the objects you want; that means your program has run out of memory, and will fail with an OutOfMemoryError or similar.

Even this simplistic GC has a lot of interesting properties, and you may have heard these terms or labels that can apply to it:

Most modern GCs are considerably more complicated than this: e.g. they may have optimizations to avoid wasting half the heap by leaving it empty, or they may have optimizations for handling short-lived objects, but at their heart this is still what they do. And understanding the performance characteristics of this simple, naive GC can help give you an intuition in how GCs compare to other memory management strategies, and how modern GCs behave in terms of performance.

Program that use reference counting tend to find their heap getting more and more fragmented over time We can see this in the heap diagrams: the tracing garbage collector heaps above always had a single block of empty space to the right, and had the new objects allocated in ascending order from left-to-right:

In contrast, reference counted heaps (e.g. below) tend to get fragmented, with free space scattered about, and the allocated objects jumbled up in no particular order

There are two main ways this affect performance:

Objects that reference each other cyclically can thus cause memory leaks when their objects never get collected, resulting in the program running out of memory even though much of the heap could be cleaned up by a tracing garbage collector.

For example, consider the following heap, identical to the one we started with, but with an additional edge from bar to foo (green), and with the edge from the stack to bar removed:

Garbage Collection and Reference Counting have very different characteristics, and neither is strictly superior to the other in all scenarios. Many programming languages (e.g. Python) that use reference counting also have a backup tracing garbage collector that runs once in a while to clean up unreachable reference cycles and compact the heap, and most modern GCs (e.g. ZGC discussed below) use some reference-counting techniques as part of their implementation.

Running this on the default GC (G1), we get the followings numbers:

Pause Times

Throughput

As mentioned earlier, garbage collectors require some amount of free space in order to work well, and so we only ran the benchmarks where the heap-size was twice or more of the live-set size.

Above, we can see the behavior we discussed earlier in the theoretical performance analysis:

One additional GC behavior worth discussing is the "Generational Hypothesis". The idea is that "most" objects do not live a long time, e.g. objects allocated within a method are often collect when the method returns. Given that assumption, many GCs have made optimizations for the collection of objects that become garbage quickly, such that collecting them is much cheaper. Practically, that means that the same live-set and heap-size can have vastly different performance depending on how the allocations are structured:

Notable, "LRU" is one of the most common caching strategies, which it is possible for in-memory caches with LRU cache eviction to make GC problems worse!

The example Java benchmark above keeps objects around a while before they become garbage, by assigning new allocations to randomly indices in the liveSet array. We can instead always assign new allocations to indices via a Random Walk: randomly adjacent to the left or right of the previously-assigned allocation, meaning that recently allocated objects are likely to be over-written (becoming unreachable and eligible for garbage collection) more quickly by newer allocations in the same part of liveSet, while older objects in other parts of liveSet are less likely to be become unreachable. This lets us emulate the "generational" behavior that is common in real-world programs:

If we do this and measure the pause times and throughput of the example program, we get the following:

Pause Times

Throughput

Where the previous random-allocation benchmark has pause times of 10s to 100s to 1000s of milliseconds, this "generational" benchmark has pause times in the 1s to 10s. The program throughput is also significantly higher. This demonstrates that the default G1 garbage collector does in fact have optimizations that make it perform better for "generational" workloads.

Most GCs have some kind of optimization to make collecting recently-allocated objects cheaper than collecting long-lived objects; these are often called generational garbage collectors. Java’s G1GC is no different, and we can see that even with the same live-set size and heap sizes, shorter-lived objects are dramatically cheaper to collect than long-lived objects.

One interesting development in JVM garbage collectors is the Z Garbage Collector. This is a garbage collector that is optimized for lower pause times, exchange for requiring much more memory than the default G1GC. If we run the benchmarks above with ZGC, even without the Generational Optimizations, we get the numbers below:

Pause Times

Throughput

Some things worth noting with ZGC:

As mentioned in the discussion on Theoretical GC Performance, for most garbage collectors pause times are proportional to the live set, and increasing the heap size does not help at all (and according to our G1 Garbage Collector Benchmarks, may even make things worse!). This can be problematic, because there are many use cases that cannot tolerate long GC pause times, but at the same time may require a significant amount of live data to be kept in memory, so shrinking the live-set is not possible.

ZGC provides an option here, where if you are willing to provide significantly more memory than the default G1GC requires, perhaps twice as much, you can get your pause times from 10-100s of milliseconds down to 1-2 milliseconds. These pause times remain low for a wide range of heap sizes and live set sizes, and can be beneficial for a lot of applications that cannot afford to just randomly stop for 100ms at a time. But the extra memory requirement means it’s not a strict improvement, and it really depends on your use case whether the tradeoff is worth it.