Evolution of Strings in Java to Compact Strings and Indify String Concatenation

Java 9 comes with 2 major changes on how String behaves to lower memory usage and improve performance.

Compact Strings
Indify String Concatenation

In the following we will put those changes into context and explore what they are and what their impact is.

Compact Strings

History

Java was originally developed to support UCS-2, also referred to as Unicode at the time, using 16 bits per character allowing for 65,536 characters. It’s only in 2004 with Java 5 that UTF-16 support was introduced by adding a method to extract 32 bits code point from chars.

UseCompressedStrings

In Java 6 Update 21 the UseCompressedStrings option was added to encode US-ASCII String on a byte per character. It was introduced to improve SPECjBB performance trading off memory bandwidth for CPU time, See.

The feature was experimental, not open-source, and only led to gains in a small number of cases as it needed to transform the US-ASCII byte[] array to a UTF-16 char[] to do most of its operations, See Q&A with Aleksey Shipilev. Due to the absence of real gain in production like environments, and the high maintenance cost, it was dropped from Java 7.

Java 9 Compact Strings

The JEP 254 goal was to build a more memory efficient String when possible that would have at least the same performance as the current implementation. Instead of switching between char[] and byte[], it is always backed by a byte[]. If it only contains LATIN-1 characters, each one is stored in one byte, otherwise, the characters are stored as UTF-16 on 2 bytes - a code point can expand over more than 2 bytes. A marker has also been added to store the coder used.

The String methods have a specialised implementation for LATIN-1 and UTF-16. Most of these methods will be replaced by an optimised intrinsic at runtime.

This feature is enabled by default and can be switch off using the -XX:-CompactStrings. Note that switching it off does not revert to a char[] backed implementation, it will just store all the Strings as UTF-16.

StringBuilder and StringBuffer are now also backed by a byte[] to match the String implementation.

Small Strings original https://www.flickr.com/photos/dhilowitz/27393588353

Java 9 String implementation

In Java 8 and previous - except for UseCompressedStrings - a String is basically

    private final char value[];

each method will access that char array. In Java 9 we now have

    private final byte[] value;
    private final byte coder;

where coder can be

    static final byte LATIN1 = 0;
    static final byte UTF16 = 1;

most of the methods then will check the coder and dispatch to the specific implementation.

    public int indexOf(int ch, int fromIndex) {
        return isLatin1() ? StringLatin1.indexOf(value, ch, fromIndex)
                          : StringUTF16.indexOf(value, ch, fromIndex);
    }
    
    private boolean isLatin1() {
            return COMPACT_STRINGS && coder == LATIN1;
    }

To mitigate the cost of the coder check and for some cases the unpacking of bytes to chars, some methods have been intrinsified, and the asm generated by the JIT has been improved.

This came with some counter intuitive results where indexOf(char) in LATIN-1 is more expensive than indexOf(String). This is due to the fact that in LATIN-1 indexOf(String) calls an intrinsic method and indexOf(char) does not. In UTF-16 they are both intrinsic.

Because it only affects LATIN-1 String, it is probably not wise to optimise for that. It is also a known issue that is targeted to be fixed in Java 10.

There is a lot more detailed discussion about the performance impact of this change here. The overall real life application impact is hard to guess as it depends on the kind of work being done and the kind of data being processed. It will also hard to directly compare with a Java 8 run as other Java 9 changes might impact the results.

String Concatenation

OptimizeStringConcat

In 2010 an Optimisation was introduced with Java 6 Update 18. The OptimizeStringConcat flag was officially documented from Update 20 and enabled by default in Java 7 Update 4 Bug 7103784.

The hotspot compiler tries to recognise String concatenation byte-code and replace it with an optimised version that removes the StringBuilder instantiation and create the String directly.

Indify String Concatenation

OptimizeStringConcat implementation is quite fragile and it’s easy to have the code fall outside the Abstract Syntax Tree pattern recognition - see for example Bug 8043677 -.

The Compact Strings changes cause a few issues highlighting the problem.

Indify String Concatenation addresses this problem by replacing the concatenation byte-code by an InvokeDynamic call, and a bootstrap method that will generate the concat call. Now the optimisation won’t depend on the AST analyses, and the code is generated from java making it easier to maintain.

The following

String str = foo + bar;

was generating the following byte-code

    NEW java/lang/StringBuilder
    DUP
    INVOKESPECIAL java/lang/StringBuilder.<init> ()V
    ALOAD 1
    INVOKEVIRTUAL java/lang/StringBuilder.append (Ljava/lang/String;)Ljava/lang/StringBuilder;
    ALOAD 2
    INVOKEVIRTUAL java/lang/StringBuilder.append (Ljava/lang/String;)Ljava/lang/StringBuilder;
    INVOKEVIRTUAL java/lang/StringBuilder.toString ()Ljava/lang/String;
    ASTORE 3

it now generates

     ALOAD 1
     ALOAD 2
     InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;
     ASTORE 3

the first time the InvokeDynamic is called the VM will replace it by the CallSite generated by the following bootstrap methods

BootstrapMethods:
  0: #28 REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
    Method arguments:
      #29 \u0001\u0001

The only caveat here is that you need to compile your code with JDK 9 to benefit from the change. A JDK 8 String concat will still be eligible for OptimizeStringConcat optimisation.

Strategies

StringConcatFactory offers different strategies to generate the CallSite divided in byte-code generator using ASM and MethodHandle-based one.

BC_SB: generate the byte-code equivalent to what javac generates in Java 8.
BC_SB_SIZED: generate the byte-code equivalent to what javac but try to estimate the initial size of the StringBuilder.
BC_SB_SIZED_EXACT: generate the byte-code equivalent to what javac but compute the exact size of the StringBuilder.
MH_SB_SIZED: combines MethodHandles that ends up calling the StringBuilder with an estimated initial size.
MH_SB_SIZED_EXACT: combines MethodHandles that ends up calling the StringBuilder with an exact size.
MH_INLINE_SIZED_EXACT: combines MethodHandles that creates directly the String with an exact size byte[] with no copy.

The default and most performant one is MH_INLINE_SIZED_EXACT that can lead to 3 to 4 times performance improvement. You can override the Strategy on the command line by defining the property java.lang.invoke.stringConcat.

It’s worth just having a look at the MH_INLINE_SIZED_EXACT: combines MethodHandles to see how we can now use MethodHandle to efficiently replace code generation.

Summary

The String related change comes from a long history of trying to optimize operation of String in the jvm. The last changes are more performance conscious and leverage the intrinsic, better jit. String concatenation also illustrate a new way of solving problems without being stuck in the intrinsic world, invoke dynamic allows to deliver performance improvement transparently without messing about with C2 code.