JEP 404: Generational Shenandoah

Summary

Enhance the Shenandoah garbage collector with generational collection capabilities to improve sustainable throughput, load-spike resilience, and memory utilization.

Goals

• No trade-off between the memory frugality and elasticity of G1 vs. the short pause times of single-generation Shenandoah.

• Expand Java heap headroom to maintain Shenandoah pause time targets (typically below 10 ms) in line with G1 at its respective pause targets (typically above 100 ms).

• Sustain doubling of ephemeral object allocation rates compared to single-generation Shenandoah with similar heap size and tail latencies.

• Reduce CPU and power usage for a given workload compared to single-generation Shenandoah.

• Decrease the risk of incurring degenerated collections during allocation spikes.

• Less than 5% reduction in application throughput (i.e., additional mutator overhead) compared to single-generation Shenandoah.

• Continue to support compressed object pointers.

• Lay the foundation for a zero-tuning garbage collector.

• Initially support x64 and AArch64. Support for other instruction sets will be added later.

Non-Goals

• It is not a goal to make generations mandatory. The option to use single-generation Shenandoah will remain, without performance or functionality degradations.

• It is not a goal to improve performance for every conceivable workload. The generational system will dynamically adapt to approximate a single-generational system as needed, but for some workloads, starting out and remaining with a single generation may still be a superior option. Nevertheless, we expect the majority of use cases to benefit from generational collection.

• It is not a goal to improve CPU and power usage compared to G1 GC. If longer pauses can be tolerated, other collectors such as G1 may still provide more energy-efficient behavior. G1 seems in many ways to be designed to go out of its way not to collect, and it can perform compactions with maximum parallelism while the mutator rests. Generational Shenandoah can only approximate but never match these tactics when used as intended, given its mandates to keep pause times much lower and to avoid stop-the-world compactions entirely. However, Generational Shenandoah will fare much closer to G1 in this respect than single-generation Shenandoah.

• It is not a goal to maximize mutator throughput. If longer pauses can be tolerated, other collectors such as the Parallel collector may still provide superior throughput on certain platforms.

Success Metrics

• Generational Shenandoah will be compared to single-generation Shenandoah using SPECjbb2015 and SPECjvm2008.

• Operational envelopes (i.e., combinations of allocation rate, heap occupancy, and pause time target) for HyperAlloc, Extremem, or similar workloads will be compared to the other JDK garbage collectors. Successful runs must not contain any full or degenerated collections.

• Allocation stalls and evacuation stalls will be induced with Extremem or similar workloads and then profiled. Their mutator overhead contributions should not exceed those in single-generation Shenandoah, under respective normal load.

Motivation

Garbage collectors with concurrent compaction are capable of completely blending GC pause times into the single-digit millisecond range of other common JVM pauses, while also leaving mutator execution speed nearly unfettered. The Shenandoah garbage collector already provides this ideal GC behavior for latency-sensitive Java applications. However, it can only achieve this within limited operational envelopes (i.e., combinations of heap occupancy and allocation rate). In other words, Shenandoah is relatively CPU-hungry and memory-hungry, mostly the latter. Compared to the generational collectors G1, CMS, and Parallel, it tends to require more heap headroom and work harder to recover space occupied by unreachable objects.

A generational collector is not necessarily noticeably disadvantaged if the generational hypothesis, i.e., that most objects die young, does not hold. Auto-tuning in region-based collectors can adjust generation sizes and copying (i.e., promotion) policies dynamically, based on observed object demographics. In the worst case, surviving objects are copied a few times too often and this becomes the norm, not the exception. This cost is, however, dwarfed by the repeated concurrent marking of long-lived objects in the old generation. In that case, there is not much difference left compared to a single-generation collector.

A concurrent collector that is also generational and can dynamically adjust its young generation’s size, and related operational parameters can both achieve low pause times and stay competitive in all other performance aspects.

Description

This enhancement of the Shenandoah garbage collector separates the Java heap into two generations. As in other generational collectors, GC efforts then focus on the young generation, i.e., the one in which allocations by the mutator occur and where ephemeral objects can be reclaimed with reduced effort. We propose the following approaches for an initial implementation.

The collection algorithms operating on each generation are closely based on traditional Shenandoah. Within the young generation, Generational Shenandoah uses the same heuristics as traditional Shenandoah to distinguish areas of memory that hold newly allocated objects from areas of memory holding objects that survived one or more recent young-generation GC passes.

Each generation is formed by a subset of the Shenandoah heap’s regions. At any given time, a region is considered either free or dedicated to either the young or the old generation. The size of each generation is given by its occupied regions plus a quota of free regions. Overreach into the free quota of the respective other generation is tolerated, but it accelerates collection triggering and can lead to degenerated and full collections. We will refine the algorithms to control collection-phase scheduling, young-generation sizing, tenuring age, and other auto-tuning mechanisms based on tests, once a prototype is available.

Shenandoah has a unique Load Reference Barrier (LRB) that supports 32-bit builds and compressed 32-bit object pointers (“compressedOops”) in 64-bit builds. To constrain impact on the mutator we use this same LRB for both generations, without any changes, and use a single evacuator for both old and young collection efforts. Typical evacuation phases collect garbage either exclusively from young regions or from a combination of young and old regions. This behavior mimics G1’s young and mixed collections. The principal improvement over G1 is that generational Shenandoah’s young and mixed collections are concurrent to the mutator.

The generation-specific marking phases are largely decoupled from each other. Concurrent old-generation marking proceeds in the background during the time that young-generation marking and evacuation occurs multiple times. Old-generation marking can also be suspended as needed to execute other collection operations. Once old-generation marking has completed, subsequent evacuations and reference updates will include old-generation regions until the entire old-generation collection set has been processed.

For the remembered-set implementation, we use the existing card marking code and supplement code for remembered scanning that is concurrent with mutator execution.

Shenandoah’s existing SATB barriers are generalized to serve the combined needs of young-generation and old-generation concurrent marking. The post-processing of SATB buffers treats references to old-generation memory differently than references to young-generation memory, but the fast path through these barriers remains unchanged.

Building and Invoking

The new generational feature is part of the Shenandoah code base, but it has no runtime effect unless it is activated by the JVM command line option

-XX:ShenandoahGCMode=generational

in which case these existing options for generational garbage collectors (such as Parallel, G1, and CMS) go into effect:

-XX:NewRatio=<n>
-XX:NewSize=<size>
-XX:MaxNewSize=<size>

Please see the project wiki (once available) for more information on how to setup and tune Generational Shenandoah.

Alternatives

Azul Systems’ C4 collector is already generational, but not available in open source. A generational mode of ZGC is also under development. Neither of these options supports compressedOops. However, the vast majority of Java heaps that we see (e.g., in cloud services) are well below 32 GB in size and thus able to take advantage of this space-saving and performance-improving feature.

Testing

Most existing functional and stress tests are collector-agnostic and can be reused as-is. We will integrate additional test run configurations for the new generational mode along with new mode-specific functional, performance, and stress tests.

Risks and Assumptions

• Remembered-set operations, in particular scanning, may add to pause times.

• Remembered-set-related barriers may add to mutator overhead.

• Heuristics to automatically configure generation sizes, the object promotion policy, and the timing as well as the balancing of efforts dedicated to young- and old-generation collections have not yet been fully developed and have not been tested with real-world workloads.