java9-string-concat

Overview of java String concatenation compilation: java 8 vs java 9.

Reference: http://www.pellegrino.link/2015/08/22/string-concatenation-with-java-8.html
Reference: https://www.guardsquare.com/en/blog/string-concatenation-java-9-untangling-invokedynamic
Reference: https://www.guardsquare.com/en/blog/string-concatenation-java-9-conversion-confusion
Reference: https://arnaudroger.github.io/blog/2017/06/14/CompactStrings.html
Reference: https://stackoverflow.com/questions/46512888/how-is-string-concatenation-implemented-in-java-9

preface

String concatenation is one of the most well known caveat in Java.

java 8

all of the substrings building the final String are known at compile
time:

  @Test
  public void nonLoopConcatenation() {
      String a = "a";
      String b = "b";
      System.out.println(a + b);
  }

is compiled to:

  public nonLoopConcatenation()V
  @Lorg/junit/Test;()
   L0
    LINENUMBER 10 L0
    LDC "a"
    ASTORE 1
   L1
    LINENUMBER 11 L1
    LDC "b"
    ASTORE 2
   L2
    LINENUMBER 12 L2
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    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;
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
   L3
    LINENUMBER 13 L3
    RETURN
   L4
    LOCALVARIABLE this LStringConcatBenchmarkTest; L0 L4 0
    LOCALVARIABLE a Ljava/lang/String; L1 L4 1
    LOCALVARIABLE b Ljava/lang/String; L2 L4 2
    MAXSTACK = 3
    MAXLOCALS = 3

the most important part is:

  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;
  INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V

and it is also a bytecode of:

  String a = "a";
  String b = "b";
  System.out.println(new StringBuilder().append(a).append(b));

it is called: static string concatenation optimisation

substrings building the final String are NOT known at compile
time

@Test
public void loopConcatenation() {
    long start = System.currentTimeMillis();
    String result = "";
    for (int i = 0; i < 50_000; i++) {
        result += i;
    }
    System.out.println(result);
    System.out.println(System.currentTimeMillis() - start);
}

is compiled to:

public loopConcatenation()V
@Lorg/junit/Test;()
 L0
  LINENUMBER 25 L0
  INVOKESTATIC java/lang/System.currentTimeMillis ()J
  LSTORE 1
 L1
  LINENUMBER 27 L1
  LDC ""
  ASTORE 3
 L2
  LINENUMBER 29 L2
  ICONST_0
  ISTORE 4
 L3
 FRAME APPEND [J java/lang/String I]
  ILOAD 4
  LDC 50000
  IF_ICMPGE L4
 L5
  LINENUMBER 30 L5
  NEW java/lang/StringBuilder
  DUP
  INVOKESPECIAL java/lang/StringBuilder.<init> ()V
  ALOAD 3
  INVOKEVIRTUAL java/lang/StringBuilder.append (Ljava/lang/String;)Ljava/lang/StringBuilder;
  ILOAD 4
  INVOKEVIRTUAL java/lang/StringBuilder.append (I)Ljava/lang/StringBuilder;
  INVOKEVIRTUAL java/lang/StringBuilder.toString ()Ljava/lang/String;
  ASTORE 3
 L6
  LINENUMBER 29 L6
  IINC 4 1
  GOTO L3
 L4
  LINENUMBER 33 L4
 FRAME CHOP 1
  GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
  ALOAD 3
  INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
 L7
  LINENUMBER 35 L7
  GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
  INVOKESTATIC java/lang/System.currentTimeMillis ()J
  LLOAD 1
  LSUB
  INVOKEVIRTUAL java/io/PrintStream.println (J)V
 L8
  LINENUMBER 36 L8
  RETURN
 L9
  LOCALVARIABLE i I L3 L4 4
  LOCALVARIABLE this LStringConcatBenchmarkTest; L0 L9 0
  LOCALVARIABLE start J L1 L9 1
  LOCALVARIABLE result Ljava/lang/String; L2 L9 3
  MAXSTACK = 5
  MAXLOCALS = 5

where the most important part is:

FRAME APPEND [J java/lang/String I]
 ILOAD 4
 LDC 50000
 IF_ICMPGE L4
L5
 LINENUMBER 30 L5
 NEW java/lang/StringBuilder
 DUP
 INVOKESPECIAL java/lang/StringBuilder.<init> ()V
 ALOAD 3
 INVOKEVIRTUAL java/lang/StringBuilder.append (Ljava/lang/String;)Ljava/lang/StringBuilder;
 ILOAD 4
 INVOKEVIRTUAL java/lang/StringBuilder.append (I)Ljava/lang/StringBuilder;
 INVOKEVIRTUAL java/lang/StringBuilder.toString ()Ljava/lang/String;
 ASTORE 3
L6
 LINENUMBER 29 L6
 IINC 4 1
 GOTO L3

which is equivalent of .java:

for (int i = 0; i < 50_000; i++) {
    StringBuilder sb = new StringBuilder();
    sb.append(result);
    sb.append(i);
    result = sb.toString();
}

Note that StringBuilder is initialized, and converted to string
(sb.toString()) every time - java compiler can not push that stuff
outside the loop.

summary

no loop

  @Test
  public void nonLoopConcatenation() {
      String a = "a";
      String b = "b";
      System.out.println(a + b);
  }

is compiled to:

  @Test
  public void nonLoopConcatenation_usingStringBuilder() {
      String a = "a";
      String b = "b";
      System.out.println(new StringBuilder().append(a).append(b));
  }

loop

  @Test
  public void loopConcatenation() {
      long start = System.currentTimeMillis();
      String result = "";
      for (int i = 0; i < 50_000; i++) {
          result += i;
      }
      System.out.println(result);
      System.out.println(System.currentTimeMillis() - start);
  }

is compiled to:

  @Test
  public void loopConcatenation_usingStringBuilder() {
      long start = System.currentTimeMillis();
      String result = "";
      for (int i = 0; i < 50_000; i++) {
          StringBuilder sb = new StringBuilder();
          sb.append(result);
          sb.append(i);
          result = sb.toString();
      }
      System.out.println(result);
      System.out.println(System.currentTimeMillis() - start);
  }

Using Java 8 - `loopConcatenation()` takes: `6000-7000` ms

java 9

all of the substrings building the final String are known at compile
time:

  @Test
  public void nonLoopConcatenation() {
      String a = "a";
      String b = "b";
      System.out.println(a + b);
  }

is compiled to:

  public nonLoopConcatenation()V
  @Lorg/junit/Test;()
   L0
    LINENUMBER 10 L0
    LDC "a"
    ASTORE 1
   L1
    LINENUMBER 11 L1
    LDC "b"
    ASTORE 2
   L2
    LINENUMBER 12 L2
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 1
    ALOAD 2
    INVOKEDYNAMIC makeConcatWithConstants(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String; [
      // handle kind 0x6 : 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;
      // arguments:
      "\u0001\u0001"
    ]
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
   L3
    LINENUMBER 13 L3
    RETURN
   L4
    LOCALVARIABLE this LStringConcatBenchmarkTest; L0 L4 0
    LOCALVARIABLE a Ljava/lang/String; L1 L4 1
    LOCALVARIABLE b Ljava/lang/String; L2 L4 2
    MAXSTACK = 3
    MAXLOCALS = 3

the most important part is:

  ALOAD 1
  ALOAD 2
  INVOKEDYNAMIC makeConcatWithConstants(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String; [
    // handle kind 0x6 : 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;
    // arguments:
    "\u0001\u0001"
  ]
  INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V

the main difference to java 8 style is:

INVOKEDYNAMIC (instead of INVOKEVIRTUAL)
StringConcatFactory.makeConcatWithConstants (instead of
StringBuilder)

substrings building the final String are NOT known at compile
time

  @Test
  public void loopConcatenation() {
      long start = System.currentTimeMillis();
      String result = "";
      for (int i = 0; i < 50_000; i++) {
          result += i;
      }
      System.out.println(result);
      System.out.println(System.currentTimeMillis() - start);
  }

is compiled to:

  public loopConcatenation()V
  @Lorg/junit/Test;()
   L0
    LINENUMBER 25 L0
    INVOKESTATIC java/lang/System.currentTimeMillis ()J
    LSTORE 1
   L1
    LINENUMBER 27 L1
    LDC ""
    ASTORE 3
   L2
    LINENUMBER 29 L2
    ICONST_0
    ISTORE 4
   L3
   FRAME APPEND [J java/lang/String I]
    ILOAD 4
    LDC 50000
    IF_ICMPGE L4
   L5
    LINENUMBER 30 L5
    ALOAD 3
    ILOAD 4
    INVOKEDYNAMIC makeConcatWithConstants(Ljava/lang/String;I)Ljava/lang/String; [
      // handle kind 0x6 : 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;
      // arguments:
      "\u0001\u0001"
    ]
    ASTORE 3
   L6
    LINENUMBER 29 L6
    IINC 4 1
    GOTO L3
   L4
    LINENUMBER 33 L4
   FRAME CHOP 1
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 3
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
   L7
    LINENUMBER 35 L7
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    INVOKESTATIC java/lang/System.currentTimeMillis ()J
    LLOAD 1
    LSUB
    INVOKEVIRTUAL java/io/PrintStream.println (J)V
   L8
    LINENUMBER 36 L8
    RETURN
   L9
    LOCALVARIABLE i I L3 L4 4
    LOCALVARIABLE this LStringConcatBenchmarkTest; L0 L9 0
    LOCALVARIABLE start J L1 L9 1
    LOCALVARIABLE result Ljava/lang/String; L2 L9 3
    MAXSTACK = 5
    MAXLOCALS = 5

So conclusions are similar to nonLoopConcatenation()

summary

How string concatenation is done is a runtime decision, not a compile
time one anymore.

motivations

The reason to change the compiler now in this way is, from the project
description, to “enable future optimizations of String concatenation
without requiring further changes to the bytecode emitted by javac.”.
Dynamic method invocation is an ideal solution for that challenge, as
it delays method implementation to the runtime. The developers of the
Java runtime can then improve the implementation of the factory class,
without all other developers needing to recompile their projects.

Recall that dynamic method invocation in Java works as follows:
first, the compiler places an invokedynamic bytecode instruction
in your method body to indicate that we’re trying to use a dynamic
method there. That indy instruction refers to a bootstrap method,
which is a regular Java method that is stored in a special attribute
in the class file. During runtime, this bootstrap method is called
to dynamically create the method we’re trying to invoke and wrap it
in a container object called a CallSite. Finally, the JVM extracts
a MethodHandle for the newly generated method from the CallSite and
executes the method, manipulating the stack as if it were a regular
method invocation.

stategies

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.

Using Java 9 `loopConcatenation()` takes: `1000-1500` ms.

project description

We provide tests with benchmarks for above examples.

The default java version is 9, if you want to switch it to 8, you
have to modify build.gradle:

sourceCompatibility = 1.8

summary

Please note that irrelevant of java version using of well-known
StringBuilder construction (with preallocated space) is the best
possible approach to that problem.

@Test
public void loopConcatenation_usingStringBuilder_rightWay() {
    long start = System.currentTimeMillis();
    StringBuilder sb = new StringBuilder(60000);
    for (int i = 0; i < 50_000; i++) {
        sb.append(i);
    }
    System.out.println(sb);
    System.out.println(System.currentTimeMillis() - start);
}

java9-string-concat

preface

java 8

summary

Using Java 8 - loopConcatenation() takes: 6000-7000 ms

java 9

summary

motivations

stategies

Using Java 9 loopConcatenation() takes: 1000-1500 ms.

project description

summary

Using well written loop with StringBuilder problem takes just 40-50 ms

Using Java 8 - `loopConcatenation()` takes: `6000-7000` ms

Using Java 9 `loopConcatenation()` takes: `1000-1500` ms.

Using well written loop with StringBuilder problem takes just `40-50` ms