1. Garbage First Overview

This chapter is an introduction to the Garbage First (or G1) garbage collector (GC) along with a historical perspective on the garbage collectors in the Java HotSpot Virtual Machine (VM), hereafter called just HotSpot, and the reasoning behind G1’s inclusion in HotSpot. The reader is assumed to be familiar with basic garbage collection concepts such as young generation, old generation, and compaction. Chapter 3, “JVM Overview,” of the book Java™ Performance [1] is a good source for learning more about these concepts.

Serial GC was the first garbage collector introduced in HotSpot in 1999 as part of Java Development Kit (JDK) 1.3.1. The Parallel and Concurrent Mark Sweep collectors were introduced in 2002 as part of JDK 1.4.2. These three collectors roughly correspond to the three most important GC use cases: “minimize memory footprint and concurrent overhead,” “maximize application throughput,” and “minimize GC-related pause times.” One might ask, “Why do we need a new collector such as G1?” Before answering, let’s clarify some terminology that is often used when comparing and contrasting garbage collectors. We’ll then move on to a brief overview of the four HotSpot garbage collectors, including G1, and identify how G1 differs from the others.

The term stop-the-world means that all Java application threads are stopped during a GC event. A stop-the-world garbage collector is one that stops all Java application threads when it performs a garbage collection. A GC phase or event may be described as stop-the-world, which means that during that particular GC phase or event all Java application threads are stopped.

The term concurrent means that garbage collection activity is occurring at the same time as the Java application is executing. A concurrent GC phase or event means that the GC phase or event executes at the same time as the application.

A garbage collector may be described by any one or a combination of these three terms. For example, a parallel concurrent collector is multithreaded (the parallel part) and also executes at the same time as the application (the concurrent part).

Both the young and old generation collections in Parallel GC are parallel and stop-the-world. Old generation collections also perform compaction. Compaction moves objects closer together to eliminate wasted space between them, leading to an optimal heap layout. However, compaction may take a considerable amount of time, which is generally a function of the size of the Java heap and the number and size of live objects in the old generation.

At the time when Parallel GC was introduced in HotSpot, only the young generation used a parallel stop-the-world collector. Old generation collections used a single-threaded stop-the-world collector. Back when Parallel GC was first introduced, the HotSpot command-line option that enabled Parallel GC in this configuration was -XX:+UseParallelGC.

At the time when Parallel GC was introduced, the most common use case for servers required throughput optimization, and hence Parallel GC became the default collector for the HotSpot Server VM. Additionally, the sizes of most Java heaps tended to be between 512MB and 2GB, which keeps Parallel GC pause times relatively low, even for single-threaded stop-the-world collections. Also at the time, latency requirements tended to be more relaxed than they are today. It was common for Web applications to tolerate GC-induced latencies in excess of one second, and as much as three to five seconds.

As Java heap sizes and the number and size of live objects in old generation grew, the time to collect the old generation became longer and longer. At the same time, hardware advances made more hardware threads available. As a result, Parallel GC was enhanced by adding a multithreaded old generation collector to be used with a multithreaded young generation collector. This enhanced Parallel GC reduced the time required to collect and compact the heap.

The enhanced Parallel GC was delivered in a Java 6 update release. It was enabled by a new command-line option called -XX:+UseParallelOldGC. When -XX:+UseParallelOldGC is enabled, parallel young generation collection is also enabled. This is what we think of today as Parallel GC in HotSpot, a multithreaded stop-the-world young generation collector combined with a multithreaded stop-the-world old generation collector.

Parallel GC is a good choice in the following use cases:

1. Application throughput requirements are much more important than latency requirements.

A batch processing application is a good example since it is noninteractive. When you start a batch execution, you expect it to run to completion as fast as possible.

2. If worst-case application latency requirements can be met, Parallel GC will offer the best throughput. Worst-case latency requirements include both worst-case pause times, and also how frequently the pauses occur. For example, an application may have a latency requirement of “pauses that exceed 500ms shall not occur more than once every two hours, and all pauses shall not exceed three seconds.”

An interactive application with a sufficiently small live data size such that a Parallel GC’s full GC event is able to meet or beat worst-case GC-induced latency requirements for the application is a good example that fits this use case. However, since the amount of live data tends to be highly correlated with the size of the Java heap, the types of applications falling into this category are limited.

Parallel GC works well for applications that meet these requirements. For applications that do not meet these requirements, pause times can become excessively long, since a full GC must mark through the entire Java heap and also compact the old generation space. As a result, pause times tend to increase with increased Java heap sizes.

Figure 1.1 illustrates how the Java application threads (gray arrows) are stopped and the GC threads (black arrows) take over to do the garbage collection work. In this diagram there are eight parallel GC threads and eight Java application threads, although in most applications the number of application threads usually exceeds the number of GC threads, especially in cases where some application threads may be idle. When a GC occurs, all application threads are stopped, and multiple GC threads execute during GC.

Because of the low memory footprint, Serial GC is the default on the Java HotSpot Client VM. It also addresses the requirements for many embedded use cases. Serial GC can be explicitly specified as the GC to use with the -XX:+UseSerialGC HotSpot command-line option.

Figure 1.2 illustrates how Java application threads (gray arrows) are stopped and a single GC thread (black arrow) takes over to do the garbage collection work on a machine running eight Java application threads. Because it is single-threaded, Serial GC in most cases will take longer to execute a GC event than Parallel GC since Parallel GC can spread out the GC work to multiple threads.

In CMS GC, young garbage collections are similar to those of Parallel GC. They are parallel stop-the-world, meaning all Java application threads are paused during young garbage collections and the garbage collection work is performed by multiple threads. Note that you can configure CMS GC with a single-threaded young generation collector, but this option has been deprecated in Java 8 and is removed in Java 9.

The major difference between Parallel GC and CMS GC is the old generation collection. For CMS GC, the old generation collections attempt to avoid long pauses in application threads. To achieve this, the CMS old generation collector does most of its work concurrently with application thread execution, except for a few relatively short GC synchronization pauses. CMS is often referred to as mostly concurrent, since there are some phases of old generation collection that pause application threads. Examples are the initial-mark and remark phases. In CMS’s initial implementation, both the initial-mark and remark phases were single-threaded, but they have since been enhanced to be multithreaded. The HotSpot command-line options to support multithreaded initial-mark and remark phases are -XX:+CMSParallelInitialMarkEnabled and -XX:CMSParallelRemarkEnabled. These are automatically enabled by default when CMS GC is enabled by the -XX:+UseConcurrentMarkSweepGC command-line option.

It is possible, and quite likely, for a young generation collection to occur while an old generation concurrent collection is taking place. When this happens, the old generation concurrent collection is interrupted by the young generation collection and immediately resumes upon the latter’s completion. The default young generation collector for CMS GC is commonly referred to as ParNew.

Figure 1.3 shows how Java application threads (gray arrows) are stopped for the young GCs (black arrows) and for the CMS initial-mark and remark phases, and old generation GC stop-the-world phases (also black arrows). An old generation collection in CMS GC begins with a stop-the-world initial-mark phase. Once initial mark completes, the concurrent marking phase begins where the Java application threads are allowed to execute concurrently with the CMS marking threads. In Figure 1.3, the concurrent marking threads are the first two longer black arrows, one on top of the other below the “Marking/Pre-cleaning” label. Once concurrent marking completes, concurrent pre-cleaning is executed by the CMS threads, as shown by the two shorter black arrows under the “Marking/Pre-cleaning” label. Note that if there are enough available hardware threads, CMS thread execution overhead will not have much effect on the performance of Java application threads. If, however, the hardware threads are saturated or highly utilized, CMS threads will compete for CPU cycles with Java application threads. Once concurrent pre-cleaning completes, the stop-the-world remark phase begins. The remark phase marks objects that may have been missed after the initial mark and while concurrent marking and concurrent pre-cleaning execute. After the remark phase completes, concurrent sweeping begins, which frees all dead object space.

One of the challenges with CMS GC is tuning it such that the concurrent work can complete before the application runs out of available Java heap space. Hence, one tricky part about CMS is to find the right time to start the concurrent work. A common consequence of the concurrent approach is that CMS normally requires on the order of 10 to 20 percent more Java heap space than Parallel GC to handle the same application. That is part of the price paid for shorter GC pause times.

Another challenge with CMS GC is how it deals with fragmentation in the old generation. Fragmentation occurs when the free space between objects in the old generation becomes so small or nonexistent that an object being promoted from the young generation cannot fit into an available hole. The CMS concurrent collection cycle does not perform compaction, not even incremental or partial compaction. A failure to find an available hole causes CMS to fall back to a full collection using Serial GC, typically resulting in a lengthy pause. Another unfortunate challenge associated with fragmentation in CMS is that it is unpredictable. Some application runs may never experience a full GC resulting from old generation fragmentation while others may experience it regularly.

Tuning CMS GC can help postpone fragmentation, as can application modifications such as avoiding large object allocations. Tuning can be a nontrivial task and requires much expertise. Making changes to the application to avoid fragmentation may also be challenging.

In G1, the young generation is just a set of regions, which means that it is not required to be a consecutive chunk of memory. Similarly, the old generation is also just a set of regions. There is no need to decide at JVM launch time which regions should be part of the old or young generation. In fact, the normal operational state for G1 is that over time the virtual memory mapped to G1 regions moves back and forth between the generations. A G1 region may be designated as young and later, after a young generation collection, become available for use elsewhere, since young generation regions are completely evacuated to unused regions.

In the remainder of this chapter, the term available region is used to identify regions that are unused and available for use by G1. An available region can be used or designated as a young or old generation region. It is possible that after a young generation collection, a young generation region can at some future time be used as an old generation region. Likewise, after collection of an old generation region, it becomes an available region that can at some future time be used as a young generation region.

G1 young collections are parallel stop-the-world collections. As mentioned earlier, parallel stop-the-world collections pause all Java application threads while the garbage collector threads execute, and the GC work is spread across multiple threads. As with the other HotSpot garbage collectors, when a young generation collection occurs, the entire young generation is collected.

Old generation G1 collections are quite different from those of the other HotSpot collectors. G1 old generation collections do not require the entire old generation to be collected in order to free space in the old generation. Instead, only a subset of the old generation regions may be collected at any one time. In addition, this subset of old generation regions is collected in conjunction with a young collection.

Similar to CMS GC, there is a fail-safe to collect and compact the entire old generation in dire situations such as when old generation space is exhausted.

A G1 old generation collection, ignoring the fail-safe type of collection, is a set of phases, some of which are parallel stop-the-world and some of which are parallel concurrent. That is, some phases are multithreaded and stop all application threads, and others are multithreaded and execute at the same time as the application threads. Chapters 2 and 3 provide more detail on each of these phases.

G1 initiates an old generation collection when a Java heap occupancy threshold is exceeded. It is important to note that the heap occupancy threshold in G1 measures the old generation occupancy compared to the entire Java heap. Readers who are familiar with CMS GC remember that CMS initiates an old generation collection using an occupancy threshold applied against the old generation space only. In G1, once the heap occupancy threshold is reached or exceeded, a parallel stop-the-world initial-mark phase is scheduled to execute.

The initial-mark phase executes at the same time as the next young GC. Once the initial-mark phase completes, a concurrent multithreaded marking phase is initiated to mark all live objects in the old generation. When the concurrent marking phase is completed, a parallel stop-the-world remark phase is scheduled to mark any objects that may have been missed due to application threads executing concurrently with the marking phase. At the end of the remark phase, G1 has full marking information on the old generation regions. If there happen to be old generation regions that do not have any live objects in them, they can be reclaimed without any additional GC work during the next phase of the concurrent cycle, the cleanup phase.

Also at the end of the remark phase, G1 can identify an optimal set of old generations to collect.

The regions selected for inclusion in a CSet are based on how much space can be freed and the G1 pause time target. After the CSet has been identified, G1 schedules a GC to collect regions in the CSet during the next several young generation GCs. That is, over the next several young GCs, a portion of the old generation will be collected in addition to the young generation. This is the mixed GC type of garbage collection event mentioned earlier.

With G1, every region that is garbage collected, regardless of whether it is young or old generation, has its live objects evacuated to an available region. Once the live objects have been evacuated, the young and/or old regions that have been collected become available regions.

An attractive outcome of evacuating live objects from old generation regions into available regions is that the evacuated objects end up next to each other in the virtual address space. There is no fragmented empty space between objects. Effectively, G1 does partial compaction of the old generation. Remember that CMS, Parallel, and Serial GC all require a full GC to compact the old generation and that compaction scans the entire old generation.

Since G1 performs GC operations on a per-region basis, it is suitable for large Java heaps. The amount of GC work can be limited to a small set of regions even though the Java heap size may be rather large.

The largest contributors to pause times in G1 are young and mixed collections, so one of the design goals of G1 is to allow the user to set a GC pause time goal. G1 attempts to meet the specified pause time goal through adaptive sizing of the Java heap. It will automatically adjust the size of the young generation and the total Java heap size based on the pause time goal. The lower the pause time goal, the smaller the young generation and the larger the total heap size, making the old generation relatively large.

A G1 design goal is to limit required tuning to setting a maximum Java heap size and specifying a GC pause time target. Otherwise, G1 is designed to dynamically tune itself using internal heuristics. At the time of writing, the heuristics within G1 are where most active HotSpot GC development is taking place. Also as of this writing, G1 may require additional tuning in some cases, but the prerequisites to building good heuristics are present and look promising. For advice on how to tune G1, see Chapter 3.

To summarize, G1 scales better than the other garbage collectors for large Java heaps by splitting the Java heap into regions. G1 deals with Java heap fragmentation with the help of partial compactions, and it does almost all its work in a multithreaded fashion.

As of this writing, G1 primarily targets the use case of large Java heaps with reasonably low pauses, and also those applications that are using CMS GC. There are plans to use G1 to also target the throughput use case, but for applications looking for high throughput that can tolerate longer GC pauses, Parallel GC is currently the better choice.

If the initial and maximum Java heap sizes are far apart or if the heap size is very large, it is possible to have many more than 2000 regions. Similarly, a small heap size may end up with many fewer than 2000 regions.

Each region has an associated remembered set (a collection of the locations that contain pointers into the region, shortened to RSet). The total RSet size is limited but noticeable, so the number of regions has a direct effect on HotSpot’s memory footprint. The total size of the RSets heavily depends on application behavior. At the low end, RSet overhead is around 1 percent and at the high end 20 percent of the heap size.

A particular region is used for only one purpose at a time, but when the region is included in a collection, it will be completely evacuated and released as an available region.

There are several types of regions in G1. Available regions are currently unused. Eden regions constitute the young generation eden space, and survivor regions constitute the young generation survivor space. The set of all eden and survivor regions together is the young generation. The number of eden or survivor regions can change from one GC to the next, between young, mixed, or full GCs. Old generation regions comprise most of the old generation. Finally, humongous regions are considered to be part of the old generation and contain objects whose size is 50 percent or more of a region. Until a JDK 8u40 change, humongous regions were collected as part of the old generation, but in JDK 8u40 certain humongous regions are collected as part of a young collection. There is more detail on humongous regions later in this chapter.

The fact that a region can be used for any purpose means that there is no need to partition the heap into contiguous young and old generation segments. Instead, G1 heuristics estimate how many regions the young generation can consist of and still be collected within a given GC pause time target. As the application starts allocating objects, G1 chooses an available region, designates it as an eden region, and starts handing out memory chunks from it to Java threads. Once the region is full, another unused region is designated an eden region. The process continues until the maximum number of eden regions is reached, at which point a young GC is initiated.

During a young GC, all young regions, eden and survivor, are collected. All live objects in those regions are evacuated to either a new survivor region or to an old generation region. Available regions are tagged as survivor or old generation regions as needed when the current evacuation target region becomes full.

When the occupancy of the old generation space, after a GC, reaches or exceeds the initiating heap occupancy threshold, G1 initiates an old generation collection. The occupancy threshold is controlled by the command-line option -XX:InitiatingHeapOccupancyPercent, which defaults to 45 percent of the Java heap.

G1 can reclaim old generation regions early when the marking phase shows that they contain no live objects. Such regions are added to the available region set. Old regions containing live objects are scheduled to be included in a future mixed collection.

G1 uses multiple concurrent marking threads. In an attempt to avoid stealing too much CPU from application threads, marking threads do their work in bursts. They do as much work as they can fit into a given time slot and then pause for a while, allowing the Java threads to execute instead.

When a humongous object allocation occurs, G1 locates a set of consecutive available regions that together add up to enough memory to contain the humongous object. The first region is tagged as a “humongous start” region and the other regions are marked as “humongous continues” regions. If there are not enough consecutive available regions, G1 will do a full GC to compact the Java heap.

Humongous regions are considered part of the old generation, but they contain only one object. This property allows G1 to eagerly collect a humongous region when the concurrent marking phase detects that it is no longer live. When this happens, all the regions containing the humongous object can be reclaimed at once.

A potential challenge for G1 is that short-lived humongous objects may not be reclaimed until well past the point at which they become unreferenced. JDK 8u40 implemented a method to, in some cases, reclaim a humongous region during a young collection. Avoiding frequent humongous object allocations can be crucial to achieving application performance goals when using G1. The enhancements available in JDK 8u40 help but may not be a solution for all applications having many short-lived humongous objects.

The purpose of the initial-mark phase is to gather all GC roots. Roots are the starting points of the object graphs. To collect root references from application threads, the application threads must be stopped; thus the initial-mark phase is stop-the-world. In G1, the initial marking is done as part of a young GC pause since a young GC must gather all roots anyway.

The marking operation must also scan and follow all references from objects in the survivor regions. This is what the concurrent root region scanning phase does. During this phase all Java threads are allowed to execute, so no application pauses occur. The only limitation is that the scanning must be completed before the next GC is allowed to start. The reason for that is that a new GC will generate a new set of survivor objects that are different from the initial mark’s survivor objects.

Most marking work is done during the concurrent marking phase. Multiple threads cooperate to mark the live object graph. All Java threads are allowed to execute at the same time as the concurrent marking threads, so there is no pause in the application, though an application may experience some throughput reduction.

After concurrent marking is done, another stop-the-world phase is needed to finalize all marking work. This phase is called the “remark phase” and is usually a very short stop-the-world pause.

The final phase of concurrent marking is the cleanup phase. In this phase, regions that were found not to contain any live objects are reclaimed. These regions are not included in a young or mixed GC since they contain no live objects. They are added to the list of available regions.

The marking phases must be completed in order to find out what objects are live so as to make informed decisions about what regions to include in the mixed GCs. Since it is the mixed GCs that are the primary mechanism for freeing up memory in G1, it is important that the marking phase finishes before G1 runs out of available regions. If the marking phase does not finish prior to running out of available regions, G1 will fall back to a full GC to free up memory. This is reliable but slow. Ensuring that the marking phases complete in time to avoid a full GC may require tuning, which is covered in detail in Chapter 3.

G1 may increase the Java heap size for several reasons:

1. An increase in size can occur based on heap size calculations during a full GC.

2. When a young or mixed GC occurs, G1 calculates the time spent to perform the GC compared to the time spent executing the Java application. If too much time is spent in GC according to the command-line setting -XX:GCTimeRatio, the Java heap size is increased. The idea behind growing the Java heap size in this situation is to allow GCs to happen less frequently so that the time spent in GC compared to the time spent executing the application is reduced.

The default value for -XX:GCTimeRatio in G1 is 9. All other HotSpot garbage collectors default to a value of 99. The larger the value for GCTimeRatio, the more aggressive the increase in Java heap size. The other HotSpot collectors are thus more aggressive in their decision to increase Java heap size and by default are targeted to spend less time in GC relative to the time spent executing the application.

3. If an object allocation fails, even after having done a GC, rather than immediately falling back to doing a full GC, G1 will attempt to increase the heap size to satisfy the object allocation.

4. If a humongous object allocation fails to find enough consecutive free regions to allocate the object, G1 will try to expand the Java heap to obtain more available regions rather than doing a full GC.

5. When a GC requests a new region into which to evacuate objects, G1 will prefer to increase the size of the Java heap to obtain a new region rather than failing the GC and falling back to a full GC in an attempt to find an available region.

[2] “Code Tools: jol.” OpenJDK, circa 2014. http://openjdk.java.net/projects/code-tools/jol/.