JEP 192: String Deduplication in G1
|Component||hotspot / gc|
|Discussion||hotspot dash gc dash dev at openjdk dot java dot net|
|Reviewed by||Bengt Rutisson, John Coomes, Jon Masamitsu|
|Endorsed by||Mikael Vidstedt|
|Relates to||JEP 254: Compact Strings|
Reduce the Java heap live-data set by enhancing the G1 garbage collector so that
duplicate instances of
String are automatically and continuously deduplicated.
It not a goal to implement this feature for garbage collectors other than G1.
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
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
String deduplication in the G1 garbage collector to avoid
wasting memory and reduce the memory footprint.
String class has two fields:
private final char value; private int hash;
value field is implementation-specific and not observable from outside of
String class itself. The
String class does not modify the contents of
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.
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
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.
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
Stringobjects = 25%
Average percent of live heap data set occupied by duplicate
Stringobjects = 13.5%
Stringlength = 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.
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
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
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.
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.
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.
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
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.
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.
String is interned (
String.intern() is invoked) it will be
deduplicated before it is inserted in the
StringTable. This ensures that once
String has been interned it will never be deduplicated again. Deduplicating
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,
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
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).
The following new command-line options will be made available:
bool) --- Enable string deduplication
bool) --- Print detailed deduplication statistics
Stringobjects reaching this age will be considered candidates for deduplication
There are numerous other ways of deduplicating
The problem with this approach is that many or most
Stringobjects die young, and the overhead of computing the hash code and finding an existing equal character array is not insignificant.
String.intern()explicitly in the code
In some cases this is indeed the best way to avoid duplicated
Stringobjects to start with, but there are a few problems with this approach.
One problem is that
String.intern()returns the exact same
Stringobject for all equal strings. Unless extreme care is taken there may be functional regressions, for example in cases where
Stringobjects 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
One can also profile existing applications and find out where duplicated
Stringobjects are typically being stored, and use frameworks like
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.
Stringobjects 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
Stringobjects 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
Stringclass itself. There are a few other technical issues, which all in all makes this a less attractive approach.
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
Stringobjects on the heap, building up a deduplication hashtable on the fly, deduplicate the
Stringobjects 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
Stringobjects. 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
Stringobjects to deduplicate and when.
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.
Stringobject and its corresponding character array will be placed next to each other in memory, leading to good cache locality. After deduplicating a
Stringobject 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.
- Performance/scalability: Changes might affect GC pause times and cache hit
rate when accessing the backing character array of
Stringobjects. We'll need to run tests to assess performance impact.