G1 String Deduplication Doesn't Fully Deduplicate Strings

Starting with Java 8u20, there is a feature for the G1 garbage collector to support string deduplication (using the VM argument XX:+UseStringDeduplication) as a memory saving optimization. In later Java versions, the Shenendoah and ZGC collectors also support the feature.

Over time, I've noticed a lot of unclarity about the scope of this feature. This piece aims to make it clear what GC based string deduplication accomplishes, and why it might still sometimes be useful to manually duplicate strings.

Why Deduplicate Strings?

Strings are a large portion of the data used by many applications and it's common to have certain strings you which are repeated throughout an application. ¹ These duplicated strings might be fragments of HTML, SQL statements, or strings for domain concepts like the USA.

If these duplicated strings all correspond to constants², then they might be replacable with an enum, but that's not necessarily possible for user data. Suppose thousands of users are entering the variants "USA", "United States" or "United States of America". Perhaps we don't know the variants users actually use ahead of time. Or alternatively, we know what users might use, but have a requirement to accurately round-trip user data. In either case, a string is the only data structure we can use.

Regardless of why, when we have to store large quantities of data as strings, a significant portion of our memory may be wasted storing copies of the same string. If we can replace these copies with shared references to a canonical instance, we can save a significant amount of memory.

A Caution About String.intern

String interning is a feature of the JVM that has existed forever. Some readers probably assume that I'm going to recommend it. Calling String.intern returns a canonical instance of a string. Two entirely separate pieces of code within the same JVM calling "abc".intern() will get back references to the same string. On the face of it, this is exactly what we want.

Unfortunately, in older versions of the JVM, misuse of String.intern could crash the JVM. Starting in Java 6 and 7, these crashes were fixed. This left only subtler performance problems as reasons to avoid String.intern, and led some developers to think it was a suitable way to save memory. In fact, using String.intern risks major slowdowns and increased GC pauses. I'll defer explaining in favor of Aleksey Shipilëv's excellent article, but will quote his summary:

In almost every project we were taking care of, removing String.intern() from the hotpaths, or optionally replacing it with a handrolled deduplicator, was the very profitable performance optimization. Do not use String.intern() without thinking very hard about it, okay?

Memory Use of Strings

In the open JDK implementation, each Java String contains two primitive fields and a reference to an array. Here are a String's fields as defined in the JDK Source, minus comments, annotations and newlines:

public final class String {
    private final byte[] value;
    private final byte coder;
    private int hash;
}

In a <= 32GB heap, the empty string uses 24 bytes for the String excluding the array, and another 16 bytes for the array, or 40 bytes total.^{3 4} A 1024 character ascii string also uses 24 bytes for the String excluding the array, but uses 1040 bytes for its array. ⁵ For small strings, the majority of the memory use is the string excluding the array, for longer strings, the array dominates.

GC Based String Deduplication

At a very high level, the idea behind the GC's string deduplication is very similar to String#intern. Repeated instances of the same string are replaced with one canonical copy. However, aside from using a different implementation that avoids the performance problems associated with String.intern, there is a further difference.

While String.intern canonicalizes the entire string object, GC based deduplication only modifies the backing byte[] array for strings. After the GC deduplicates strings, two copies of the same string will only have one array instance. But the two String instances will remain separate objects. Since the String object itself is not deduplicated, repeated ~String~s will have a significant overhead.⁶

With String.intern, we decide when and where to deduplicate strings. The GC, on the other hand, can arrange so that it tries to deduplicate each individual string exactly, after it's survived a number of garbage collections, or is being moved to the old generation (hotspot source).

The choice to deduplicate as part of the GC is designed to avoid overhead from duplicating short-lived strings. JVM implementations make it extremely cheap to allocate memory in the young generation. If a string doesn't survive past that generation, there's no advantage to deduplication. The initial allocation is cheap, and garbage collection of objects that don't survive the young generation is also cheap. By deferring the decision to deduplicate a string until garbage collection happens, you save CPU time for short-lived strings, at the expense of temporarily increased memory use and more frequent young collections.

Manual String Deduplication

For manual string deduplication, the idea is that when the application code handles data, and allocates new strings, it keeps a "pool" of string instances it's seen, and canonicalizes string instances it encounters. Using a map as the pool, this means code that looks like:

String deduplicate(ConcurrentHashMap<String, String> pool, String s) {
    String found = pool.putIfAbsent(s, s);
    return found != null ? found : s;
}

This results in having two local variables pointing at the same object. The first copy of the string will use the full memory, while the second copy will only cost a pointer.

The pool itself can be implemented with various structures--a simple ConcurrentHashMap, an LRU cache, etc.⁷ There are a lot of degrees of freedom about regarding the length of time that you store the strings, and the scope of what you deduplicate. The more strings your deduplicator sees, the more memory savings it can provide. However, the longer the deduplicator lives, the greater the potential it can hold on to strings that would otherwise be dead.

The most aggressive sort of deduplication would use a global static string pool, that stores all strings for any portion of your application and deduplicates them all. The downsides are obvious: a global pool is effectively a sort of memory leak, and if multiple subsystems use it, you're repeatedly checking a string to see if it's a duplicate.

More likely, to manually deduplicate strings, you should pick some component that loads data that may contain duplicate strings, and deduplicate as that component operates.⁸

Experiments

It seems obvious enough that GC based deduplication will save some memory, but that explicit deduplication might sometimes save more. Let's test that out.

We'll use a simple design, accumulating strings in a list of lists, and measuring the number of strings we can store before throwing an OutOfMemoryError.

The core of the code is:

try {
    var strings = new ArrayList<List<String>>();
    for (var i = 0; i < 1000000; i++) {
        var newStrings = new ArrayList<String>();
        for (var j = 0; j < 1000; j++) {
            var s = copyString(bh, j);
            seen++;
            newStrings.add(s);
        }
    strings.add(newStrings);
    return strings;
}
catch (OutOfMemoryError e) {
    System.out.println("TotalSeen=" + seen + ", Time=" + new Date());
    return null;
}

The copyString method reads from a preinitialized list of strings, and creates a copy. If the JMH parameter dedup is true, we deduplicate OutOfMemorythe string using ConcurrentHashMap.

private String copyString(Blackhole bh, int j) {
    var b = preAllocatedStrings.get(j % preAllocatedStrings.size()).getBytes();
    bh.consume(b);
    var s = new String(b);
    if (dedup) {
        s = stringMap.computeIfAbsent(s, Function.identity());
    }
    return s;
}

Our variables are:

1. Type of deduplication (none, G1, manual deduplication, G1 and manual deduplication)
2. The number of distinct strings (1, 1024, 65536)
3. The length of the strings (0, 16, 256, 2048)

We'll consider every permutation of our options. Code for the experiment can be found on GitHub.

Results

Before getting results, I wondered if it was worth running experiments. It was obvious that manual deduplication would save more memory than relying on GC based deduplication. Further, this effect would be most pronounced with smaller strings.

In fact, there were two surprises from the first run. Although neither one changes the overall conclusion, I found them interesting. Let's look at some selections from the results (full results):

First of all, when using the empty string, manual deduplication makes a difference, but GC string deduplication makes no difference. It turns out that the String constructor special cases the empty string, and uses a canonical backing array, regardless of any other JVM parameters. Effectively, regardless of the JVM parameters, GC deduplication is automatically applied while the 0-length string is constructed.

The next table comes from preliminary results:

The numbers from the first experiment don't seem right. There is a difference between using GC deduplication and no string deduplication, but it is relatively small. Moreover, the results don't seem internally consistent--with just one string, GC deduplication should give us almost identical results whether that string is 16 bytes or 2048 bytes (the extra 2032 bytes give us room to store less than 100 extra copies). But the results drop off precipitously, showing that deduplication isn't having the full effect it could.

The explanation is that GC deduplication only happens as part of the garbage collector's work. While processing data, the GC threads register strings, and a background thread processes them and deduplicates them.

Since our benchmark only allocates strings without generating other garbage, there isn't enough gc pressure to force deduplication. The solution is to create synthetic GC pressure, by allocating some data, and then throwing it away. Tests show that it was important to create short lived data to trigger young-gen collections. Calling System.gc() to trigger full collections had small effects.

So I added code to periodically trigger young generation churn:

accumulated += s.length();
if (accumulated >= gcFreq) {
    churnYoungGen(bh);
    accumulated = 0;
}

private void churnYoungGen(Blackhole bh) {
    for (int i = 0; i < 8192; i++) {
        byte[] bytes = new byte[1024];
        bh.consume(bytes);
    }
}

This worked--adding extra allocations made deduplication have a much larger effect.⁹ The fact that GC based string deduplication only works with another source of GC pressure is interesting, and could lead to missed memory savings. In practice, my instinct is that it would rarely matter.

Final Results

These results are in line with what we we expect. Manual deduplication lets us store many more copies of the same strings compared to using GC based string deduplication, which itself saves more than using no deduplication.

Conclusion

I've shown how gc based deduplication works, and that you can sometimes achieve larger memory savings with manual deduplication. That's all.

Should you use manual deduplication? Maybe, maybe not. How much benefit it can have depends on your application, and how it uses strings. Taking heap dumps and analyzing them for duplicated strings will show you the maximum possible savings.

There are also costs to manual duplication--manual deduplication requires having an idea about the type of strings your application uses, and their lifetime. The garbage collector design ensures that short-lived strings are not deduplicated, while each long-lived string is deduplicated exactly once. Finding a place to do that in your application may be difficult. Getting it wrong risks wasting cycles deduplicating strings that would've died young. In the worst case, the cache you use for deduplication can cause an unbounded memory leak. Though I didn't show any cases where manual deduplication made an application use more memory, it's easy to see that it's possible.

Instead of a recommendation, then, my goal is just to clarify what the GC does and doesn't provide, and make you aware that manual deduplication is a further technique that you can consider using.

Footnotes