Summary

Reduce the Java heap live-data set by enhancing the G1 garbage collector so that duplicate instances of String are automatically and continuously deduplicated.

Non-Goals

It not a goal to implement this feature for garbage collectors other than G1.

Motivation

Many large-scale Java applications are currently bottlenecked on memory. Measurements have shown that roughly 25% of the Java heap live data set in these types of applications is consumed by String objects. Further, roughly half of those String objects are duplicates, where duplicates means string1.equals(string2) is true. Having duplicate String objects on the heap is, essentially, just a waste of memory. This project will implement automatic and continuous String deduplication in the G1 garbage collector to avoid wasting memory and reduce the memory footprint.

Description

String Deduplication

The String class has two fields:

private final char[] value
private int hash

The value field is implementation-specific and not observable from outside of the String class itself. The String class does not modify the contents of the char[] array, nor does it synchronize on the array object itself. This means that it can safely and transparently be used by multiple instances of String at the same time.

Deduplicating a String object is conceptually just an re-assignment of the value field, i.e., aString.value = anotherString.value. The actual re-assignment is however done by the VM, which in turn means that the final property of the value field is not a problem in practice.

We are not actually deduplicating the String objects, only their backing character arrays. Deduplicating the actual String object cannot be done safely, since such a change would be observable from the Java application and could cause problems if, for example, the application used that object for synchronization or in some other way relied on the object's identity.

String deduplication will not require any changes to the JDK class library or to any other existing Java code.

Expected Benefit

Measurements done on a large number of Java applications (big and small) have shown the following:

• Average percent of live heap data set occupied by String objects = 25%

• Average percent of live heap data set occupied by duplicate String objects = 13.5%

• Average String length = 45 characters

Given that we are only deduplicating character arrays we will still carry the overhead of the String objects (object header, fields, and padding). This overhead is platform/configuration dependent and varies between 24 and 32 bytes. However, given an average String length of 45 characters (90 bytes + array header) there is still a significant win to be had.

Taking the above into account, the actual expected benefit ends up at around 10% heap reduction. Note that this number is a calculated average based on a wide range of applications. The heap reduction for a specific application could vary significantly both up and down.

Implementation

Overview

When garbage collection is performed, live objects on the heap are visited. For each object we visit a check is applied to see if the object is a candidate for string deduplication. If the check indicates that this is a candidate then a reference to the object is inserted into a queue for later processing. A deduplication thread runs in the background and processes the queue. Processing a queue entry means removing it from the queue and attempting to deduplicate the String object it references. A hashtable is used to keep track of all unique character arrays used by String objects. When deduplicating, a lookup is made in this table to see if there is already an identical character array somewhere on the heap. If so, the String object is adjusted to point to that character array, releasing the reference to the original array allowing it to eventually be garbage collected. If the lookup fails the character array is instead inserted into the hashtable so that this array can be shared at some point in the future.

Candidate Selection

Candidate selection is done during young/mixed and full collections. This is a performance sensitive operation since it is applied to all visited objects. An object is considered a deduplication candidate if all of the following statements are true:

• The object is an instance of String,

• The object is being evacuated from a young heap region, and

• The object is being evacuated to a young/survivor heap region and the object's age is equal to the deduplication age threshold, or the object is being evacuated to an old heap region and the object's age is less than the deduplication age threshold.

Once a String object has been promoted to an old region, or its age is higher than the deduplication age threshold, it will never become a candidate again. This approach avoids making the same object a candidate more than once.

Interned strings are a bit special. These are explicitly deduplicated before being inserted into the StringTable (see below for details on why). These can later also become deduplication candidates if they reach the deduplication age threshold or are evacuated to an old heap region. The second attempt to deduplicate such strings will be in vain, but we have no fast way of filtering them out. This has been shown to not be a problem, as the number of interned strings is usually dwarfed by the number of normal (non-interned) strings.

Deduplication Age Threshold

It is assumed that String objects either live for a very short time or live for a long time. Deduplicating objects that will die soon is just a waste of CPU and memory resources. To avoid deduplicating strings too early the deduplication age theshold dictates how old a String object must be before it will be considered a candidate for deduplication. This threshold will have a reasonable default, but will also be configurable using a VM option.

Deduplication Queue

The deduplication queue actually consists of several queues, one queue per GC worker thread. This allows lock-free and cache-friendly enqueue operations by the GC workers. This is important since these operations are done during a stop-the-world phase.

Deduplication Hashtable

The deduplication hashtable is used to keep track of all unique character arrays (which are attached to String objects) found on the heap. When a deduplication candidate is processed, a lookup is made in the hashtable to see if an identical character array already exists. If the lookup is successful the String object's value field is updated to point to the character array found in the hashtable, allowing the garbage collector to eventually collect the original array. If the lookup fails the character array is instead added to the hashtable so that this array can be shared at some point in the future. A character array is removed from the hashtable when it is garbage collected, i.e., when all String objects referring to it have become unreachable.

The hashtable is dynamically resized to accommodate the current number of table entries. The table has hash buckets with chains for hash collision. If the average chain length goes above or below given thresholds the table grows or shrinks accordingly.

The hashtable is also dynamically rehashed (using a new hash seed) if it becomes severely unbalanced, i.e., a hash chain is significantly longer than average. This is similar to how StringTable handles an unbalanced hashtable.

For workloads that produce a large number of unique strings, where there is little opportunity for deduplication, the hashtable could consume more memory than deduplication frees. In those cases string deduplication should not be enabled. The deduplication statistics printed to the GC log will give guidance in making such decisions.

Deduplication Thread

The deduplication thread is a VM internal thread which runs concurrently with the Java application. This thread is where the actual deduplication work is done. It waits for String object references to appear on the deduplication queue and starts to dequeue them one by one. For each String it dequeues, it computes the string hash code (if needed), looks it up in the deduplication hashtable and possibly deduplicates the string. The deduplication thread maintains deduplication statistics (number of candidates inspected, number of strings deduplicated, etc) which it can print to the GC log.

Interned Strings

When a String is interned (String.intern() is invoked) it will be deduplicated before it is inserted in the StringTable. This ensures that once a String has been interned it will never be deduplicated again. Deduplicating a String after it has been interned has shown to be a bad idea since it will counteract compiler optimizations done for string literals. Some optimizations assume (and rightly so) that the String.value field is never changed to point to a different array. With this knowledge the compiler can emit code with the address of the character array as an immediate value. This optimization allows, for example, String.equals() to do a simple pointer comparison in a fast path. If the array is moved by the GC the address will be adjusted accordingly in such code blocks. However, if String.value is outside of the GC the optimization will silently fail and fall back to the normal (slower) character by character comparison.

Impact on GC Pause Times

The following items can/will affect GC pause times:

• Candidate selection is done in the hot path for marking (full collections) and evacuation (young/mixed collections).

• Both the deduplication queue and hashtable stores oops which are treated as weak references from a GC point of view. This means that the GC needs to traverse both structures to adjust or remove references to objects that were moved or garbage collected. Traversing the queue and the hashtable is the most performance-critical part of this feature. The traversal is done in parallel using all GC worker threads.

The assumption is that a high enough deduplication success rate will balance out most or all of this impact, because deduplication can reduce the amount of work needed in other phases of a GC pause (like reduced amount of objects to evacuate) as well as reduce the GC frequency (due to reduced pressure on the heap).

Command-line Options

The following new command-line options will be made available:

• UseStringDeduplication (bool) --- Enable string deduplication

• PrintStringDeduplicationStatistics (bool) --- Print detailed deduplication statistics

• StringDeduplicationAgeThreshold (uintx) --- String objects reaching this age will be considered candidates for deduplication

Alternatives

There are numerous other ways of deduplicating String objects.

• Deduplicate at String creation time

  The problem with this approach is that many or most String objects die young, and the overhead of computing the hash code and finding an existing equal character array is not insignificant.

• Use String.intern() explicitly in the code

  In some cases this is indeed the best way to avoid duplicated String objects to start with, but there are a few problems with this approach.

  One problem is that String.intern() returns the exact same String object for all equal strings. Unless extreme care is taken there may be functional regressions, for example in cases where String objects are used for synchronization.

  Another problem is that in many cases developers do not know where in the code they should use String.intern(), or it may even be hard to find the code and/or people responsible for the code and have the code updated in the first place.

  Finally, the current String.intern() implementation does not scale that well, which means the operation can be very expensive.

• Profile and inject the equivalent of String.intern() invocations

  One can also profile existing applications and find out where duplicated String objects are typically being stored, and use frameworks like java.lang.instrument to inject String.intern() calls in suitable places. This has the advantage of not having to update the source code itself, but rather change the byte code dynamically for the actual workload. One of the problems of doing this is that it is not as straightforward to understand how frequently fields are updated, so if the intern() invocations are injected in hot paths it may impact performance significantly. Also, if the source code is changed the profiling may need to be redone which could be a costly and, to some extent, manual effort.

• Deduplicate in String.equals() and String.compareTo()

  When two String objects are compared and the result shows that they are equal, before returning the result these methods could adjust one of the strings to use the other string's backing character array. A prototype for this was implemented, which worked fairly well. The main advantage of this approach is that there is zero memory overhead because there is no need to keep a deduplication hashtable around.

  There are, however, a few obvious limitations with this approach. First, two String objects need to be compared for deduplication to happen. This means a large part of all deduplication candidates are missed, because not all strings are compared. Further, the VM has compiler intrinsics for these methods, which complicates the implementation since it is not just about making adjustments to the String class itself. There are a few other technical issues, which all in all makes this a less attractive approach.

• One-off deduplication

  Instead of doing deduplication continuously it could also be done as a one-off operation. In short this could be implemented by locating all the String objects on the heap, building up a deduplication hashtable on the fly, deduplicate the String objects as needed and then release the hashtable and other temporary data structures. This is significantly easier to implement than continuous deduplication and also has the advantage of not adding to the memory footprint when deduplication is not being done. One could further imagine that, if there is a need, these one-off deduplication operations could be scheduled to execute occasionally, thereby making it semi-continuous.

  A prototype of this approach was developed which used JVMTI to scan the heap for String objects. There were a few problems. First, results from a large scale Java EE type of workload showed that it is beneficial to do deduplication continuously, not just now and then. If we end up executing this operation frequently then the overhead of scanning the whole heap and rebuilding the hashtable every time becomes significant. Further, doing this type of work with JVMTI is a bit too inflexible when it comes to selecting which String objects to deduplicate and when.

Testing

jtreg tests will be added to make sure the deduplication works as expected. System tests and performance tests are needed to assess the Java heap live data set reduction and performance regressions/improvements.

Risks and Assumptions

• It is assumed that the introduction of the "is deduplication enabled"-check in the hot path of the garbage collector marking/copying logic does not add a significant overhead. This needs to be verified.

• Normally a String object and its corresponding character array will be placed next to each other in memory, leading to good cache locality. After deduplicating a String object its character array will be further away, which might introduce a slight performance overhead. Initial measurements have, however, shown that this does not seem to be a problem. In fact, after deduplication the total amount of accessed memory is reduced which tends to result in improved cache hit rates.

Impact

• Performance/scalability: Changes might affect GC pause times and cache hit rate when accessing the backing character array of String objects. We'll need to run tests to assess performance impact.