（この記事は地平線に行くとのマルチポストです）

Java 9 以降 JEP 280: Indify String Concatenation に基づき、 + 演算子による文字列結合は以下のようにコンパイルされるように変わりました。

invokedynamic #7,  0
// InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/Object;I)Ljava/lang/String;

（InvokeDynamic を使うように変更された理由は、「Java の + 演算子による文字列結合で、StringBuilder は使われなくなりました。」を参照）

この InvokeDynamic によって、最終的にどのように文字列結合が行われているのでしょうか。

環境

Adopt OpenJDK 15 で調査しました。

openjdk version "15" 2020-09-15
OpenJDK Runtime Environment (build 15+36-1562)
OpenJDK 64-Bit Server VM (build 15+36-1562, mixed mode, sharing)

前提知識

Java 9 以降 JEP 254: Compact Strings に基づき、String クラスの内部で文字を以下のように保持するように変わりました。

すべての文字が LATIN1 の範囲内であれば、LATIN1（1文字 = 1byte）
（日本語など）LATIN1 の範囲外の文字があれば、UTF-16 （1文字 = 2byte）

これについての詳細は、下記の記事でご確認ください。
Java9 でも String クラスがリファクタリングされていました（JEP 254: Compact Strings 編） - 地平線に行く

処理の概要

invokedynamic #7,  0
// InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/Object;I)Ljava/lang/String;

この部分が最初に実行された時、ブートストラップメソッド StringConcatFactory.makeConcatWithConstants によって、文字列結合を行う匿名メソッドが作られます。
そして、以降は InvokeDynamic の代わりにその匿名メソッドが呼ばれるようになります。

なお、最終的にこの匿名メソッドは呼び元のメソッドにインライン展開されます（たぶん…）。

匿名メソッドの処理

匿名メソッドは、以下の処理を行います。

double, float, Object 型の変数を文字列に変換
（最終的に出来上がる）文字数と文字コードを調べる
文字を格納するのに必要な長さの byte 配列を作成
byte 配列に、文字を詰る
byte 配列を文字列にする

つまり、文字列結合というのは、最終的に 文字を byte 配列に詰める処理 になります。

具体例

下記のソースコードを例に、具体的に見ていきます。

public static String call(Object foo, int bar) {
    return "arg0: " + foo + ", arg1: " + bar;
}

このメソッドをコンパイルしたクラスファイルを、 javap で逆アセンブルします。
すると、以下のように invokedynamic が使われていることが分かります。

{
  public static java.lang.String call(java.lang.Object, int);
    descriptor: (Ljava/lang/Object;I)Ljava/lang/String;
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=2, args_size=2
         0: aload_0
         1: iload_1
         2: invokedynamic #7,  0              // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/Object;I)Ljava/lang/String;
         7: areturn
}
BootstrapMethods:
  0: #26 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:
      #32 arg0: \u0001, arg1: \u0001

この invokedynamic は、ブートストラップメソッドとして、 StringConcatFactory#makeConcatWithConstants(MethodHandles.Lookup lookup, String name, MethodType concatType, String recipe, Object... constants) が指定されています。

ここで重要なのは、引数の concatType, recipe です。
今回は、以下の値が渡されています。

concatType
- MethodType という型
- 作成する匿名メソッドのシグネチャの情報が保持されている
  - この中の引数の情報 parameterArray に、結合する変数の型情報が保持されている
    - 今回の場合 [ java.lang.Object.class, int.class ]
recipe
- 変数に置換する箇所を \0001 に、それ以外を結合した文字列
- 今回の場合、 "arg0: \u0001, arg1: \u0001"

このブートストラップメソッドによって、以下の動的メソッドが作られます。

String anonymous(Object foo, int bar) {
    // 引数を文字列に変換
    String t4 = StringConcatHelper.stringOf(foo);

    // 文字数と文字コードを調べる
    long t6 = StringConcatHelper.mix(14L, bar);
    long t8 = StringConcatHelper.mix(t6, t4);

    // 必要なサイズの byte 配列を作成
    byte[] t10 = StringConcatHelper.newArray(t8);

    // 配列に文字列を詰める
    long t12 = StringConcatHelper.prepend(t8, t10, foo, ", arg1: ");
    long t14 = StringConcatHelper.prepend(t12, t10, t4, "arg0: ");

    // 配列を文字列にする
    return StringConcatHelper.newString(t10, t14);
}

これを細かく見ていきましょう。

文字列への変換

結合する変数が double, float, Object 型の場合、以下のメソッドを呼び出して文字列に変換します。

double → String.valueOf(double)
float → String.valueOf(float)
Object → StringConcatHelper.stringOf(Object)

なお、boolean, char, byte, short, int, long の場合、あとで直接 byte 配列に格納するため、ここで文字列に変換しません。

今回の例では、引数の Object 型の変数 foo を StringConcatHelper.stringOf(Object) メソッドで文字列に変換しています。

String t4 = StringConcatHelper.stringOf(foo);  // args: Object

この StringConcatHelper.stringOf(Object) の実装はこのようになっています。

/**
 * We need some additional conversion for Objects in general, because
 * {@code String.valueOf(Object)} may return null. String conversion rules
 * in Java state we need to produce "null" String in this case, so we
 * provide a customized version that deals with this problematic corner case.
 */
static String stringOf(Object value) {
    String s;
    return (value == null || (s = value.toString()) == null) ? "null" : s;
}

引数が null ならば "null" という文字列を、引数が null でなければ value.toString() した文字列を返しています。

文字数と文字コードを調べる

次に、結合する各変数の文字数と文字コードを、StringConcatHelper#mix メソッドを使って後ろから順に調べていきます。
今回だと、bar → foo の順です。

// MEMO:
//   bar: 結合する int 型の変数
//   t4: 結合する Object 型の変数を文字列にしたもの (`foo.toString()`) 
long t6 = StringConcatHelper.mix(14L, bar);  // args: long, int
long t8 = StringConcatHelper.mix(t6, t4);  // args: long, String

StringConcatHelper#mix メソッドは、戻り値として「第一引数の値 + 第二引数で渡した変数の文字数（※）」を返します。
それを、次の第一引数に渡します。
（※ 正確には、後述の lengthCoder という、文字数と文字コードの両方を保持した値です。この点は、後述します）

なお、最初は recipe から \u0001 を取り除いた長さを渡します。今回は recipe = "arg0: , arg1: " なので、14 です。
匿名メソッドを作る際に計算しているので、ここでは定数になっています。

StringConcatHelper#mix メソッドの実装は、第二引数で渡す変数の型によって若干処理が異なります。
今回は、上記の例で使われている int 型と String 型¹の処理をそれぞれ見ていきましょう。

int 型の場合

StringConcatHelper.mix(long, int) の実装はこのようになっています。

/**
 * Mix value length and coder into current length and coder.
 */
static long mix(long lengthCoder, int value) {
    return checkOverflow(lengthCoder + Integer.stringSize(value));
}

Integer.stringSize(int) というパッケージプライベートなメソッドを呼び出し、value を10進数の文字列にした時の長さを計算しています。

これを、第一引数と足した値を戻り値としています。
ただし、この値が int の範囲を超えていたら OutOfMemoryError("Overflow: String length out of range"); をスローします。

文字列型の場合

StringConcatHelper.mix(long, String) の実装はこのようになっています。

/**
 * Mix value length and coder into current length and coder.
 */
static long mix(long lengthCoder, String value) {
    lengthCoder += value.length();
    if (value.coder() == String.UTF16) {
        lengthCoder |= UTF16;
    }
    return checkOverflow(lengthCoder);
}

まず、文字列の長さを String#length() で取得し、lengthCoder に足しています。

次に、引数の文字列の文字コードを確認します。
もし文字コードが UTF-16 ならば、lengthCoder の32ビット目を 1 にします。
このように「文字列の長さ」として使うのは long 型の下位32ビットだけで、32ビット目²はこのように文字コードが UTF-16 かどうかのフラグとして使います。

そうしてできた値を、戻り値としています。
（オーバーフローの処理は先ほどと同様です）

必要なサイズの byte 配列を作成

// MEMO:
//   t8: さきほどの戻り値 (`lengthCoder`)
byte[] t10 = StringConcatHelper.newArray(t8);  // args: long

ここまでで確定した文字数と文字コードをもとに、byte 配列を作成しています。

この StringConcatHelper.newArray(long) の実装はこのようになっています。

/**
 * Allocates an uninitialized byte array based on the length and coder information
 * in indexCoder
 */
@ForceInline
static byte[] newArray(long indexCoder) {
    byte coder = (byte)(indexCoder >> 32);
    int index = (int)indexCoder;
    return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, index << coder);
}

必要な byte 配列の長さは、文字コードによって異なります。

LATIN なら 1文字 = 1byte なので、必要な byte 配列の長さ = 文字数
UTF-16 なら 1文字 = 2byte なので、必要な byte 配列の長さ = 文字数 × 2

その計算をやっているのが index << coder です。
coder には、LATIN1 なら 0、UTF-16 なら 1 が格納されているので、UTF-16 の時だけ1ビット左シフト、つまり値が倍になるという仕組みです。

なお、配列の作成は new byte[length] ではなく、UNSAFE.allocateUninitializedArray(Class<?>, int) で行っています。
なぜかというと、new byte[length] だと配列を作った後に要素をゼロで初期化する処理を行ってしてしまうためです。
今回の処理では必ずあとですべての要素に書き込むので、ゼロ初期化するのは無駄です。
そのため、アンセーフなメソッドを使ってゼロ初期化を省いて配列を作っています。

配列に文字列を詰める

出来上がった配列に、結合する各変数を StringConcatHelper#prepend メソッドを使って後ろから順に詰めていきます。
今回だと、bar → foo の順です。

// MEMO:
//   t8: さきほどの戻り値 (`lengthCoder`)
//   t10: 文字列を詰め込む byte 配列
//   bar: 結合する int 型の変数
//   t4: 結合する Object 型の変数を文字列にしたもの (`foo.toString()`) 
long t12 = StringConcatHelper.prepend(t8, t10, bar, ", arg1: ");  // args: long, byte[], int, String
long t14 = StringConcatHelper.prepend(t12, t10, t4, "arg0: ");  // args: long, byte[], String, String

StringConcatHelper#prepend メソッドは、第二引数で渡された byte 配列に第一引数で指定された位置のひとつ前から文字を詰め込みします。
詰め込む内容は、第三引数で渡された変数、および第四引数で渡された文字列です。

このように、結合する変数と\u0001 で区切った recipe をまとめて渡すことで、メソッドの呼び出し回数を削減しています。

StringConcatHelper#prepend メソッドの実装は、第三引数で渡す変数の型によって若干処理が異なります。
今回は、上記の例で使われている int 型と String 型¹の処理をそれぞれ見ていきましょう。

int 型の場合

StringConcatHelper.prepend(long, byte[], int, String) の実装はこのようになっています。

/**
 * Prepends constant and the stringly representation of value into buffer,
 * given the coder and final index. Index is measured in chars, not in bytes!
 */
static long prepend(long indexCoder, byte[] buf, int value, String prefix) {
    indexCoder = prepend(indexCoder, buf, value);
    if (prefix != null) indexCoder = prepend(indexCoder, buf, prefix);
    return indexCoder;
}

この prepend(long, byte[], int) の実装はこのようになっています。

/**
 * Prepends the stringly representation of integer value into buffer,
 * given the coder and final index. Index is measured in chars, not in bytes!
 */
private static long prepend(long indexCoder, byte[] buf, int value) {
    if (indexCoder < UTF16) {
        return Integer.getChars(value, (int)indexCoder, buf);
    } else {
        return StringUTF16.getChars(value, (int)indexCoder, buf) | UTF16;
    }
}

Integer.getChars または StringUTF16.getChars で、byte配列に変数の値を詰めています。
詳しい解説は省きますが、これらの中では面白い実装によって int 型から10進数文字列に変換しています。
→ Tech Tips: Integer.getCharsが面白い

文字列型の場合

StringConcatHelper.prepend(long, byte[], String, String) の実装はこのようになっています。

/**
 * Prepends constant and the stringly representation of value into buffer,
 * given the coder and final index. Index is measured in chars, not in bytes!
 */
static long prepend(long indexCoder, byte[] buf, String value, String prefix) {
    indexCoder = prepend(indexCoder, buf, value);
    if (prefix != null) indexCoder = prepend(indexCoder, buf, prefix);
    return indexCoder;
}

この prepend(long, byte[], String) の実装はこのようになっています。

/**
 * Prepends the stringly representation of String value into buffer,
 * given the coder and final index. Index is measured in chars, not in bytes!
 */
private static long prepend(long indexCoder, byte[] buf, String value) {
    indexCoder -= value.length();
    if (indexCoder < UTF16) {
        value.getBytes(buf, (int)indexCoder, String.LATIN1);
    } else {
        value.getBytes(buf, (int)indexCoder, String.UTF16);
    }
    return indexCoder;
}

String#getBytes メソッドを使って、byte配列に変数の値を詰めています。

配列を文字列にする

// MEMO:
//   t10: 文字列を詰め込んだ byte 配列
//   t14: 文字列の先頭を指した状態の `indexCoder`
return StringConcatHelper.newString(t10, t14);

この StringConcatHelper.newString(byte[], long) の実装はこのようになっています。

/**
 * Instantiates the String with given buffer and coder
 */
static String newString(byte[] buf, long indexCoder) {
    // Use the private, non-copying constructor (unsafe!)
    if (indexCoder == LATIN1) {
        return new String(buf, String.LATIN1);
    } else if (indexCoder == UTF16) {
        return new String(buf, String.UTF16);
    } else {
        throw new InternalError("Storage is not completely initialized, " + (int)indexCoder + " bytes left");
    }
}

このnew String(byte[], byte) の実装はこのようになっています。

/*
 * Package private constructor which shares value array for speed.
 */
String(byte[] value, byte coder) {
    this.value = value;
    this.coder = coder;
}

引数の byte 配列はコピーすることなく、そのままフィールドに格納しています。³

落穂拾い

以下、雑多な点を記載します。

最適化

以下の両方の条件を満たす場合、処理が最適化されます。

文字列と1つの変数を結合する、または 2つの変数を結合する
変数はプリミティブ型ではない

public String optimized(String foo) {
    // 文字列と1つの変数を結合する
    return "Hello " + foo;
}

public String optimized(String foo, String bar) {
    // 2つの変数を結合する
    return foo + bar;
}

この場合、StringConcatHelper#simpleConcat(Object, Object) であらかじめ用意されたパターンが使われます。
（出来上がる匿名メソッドの処理の流れは、通常の場合と同じ）


    /**
     * Perform a simple concatenation between two objects. Added for startup
     * performance, but also demonstrates the code that would be emitted by
     * {@code java.lang.invoke.StringConcatFactory$MethodHandleInlineCopyStrategy}
     * for two Object arguments.
     */
    @ForceInline
    static String simpleConcat(Object first, Object second) {
        String s1 = stringOf(first);
        String s2 = stringOf(second);
        // start "mixing" in length and coder or arguments, order is not
        // important
        long indexCoder = mix(initialCoder(), s1);
        indexCoder = mix(indexCoder, s2);
        byte[] buf = newArray(indexCoder);
        // prepend each argument in reverse order, since we prepending
        // from the end of the byte array
        indexCoder = prepend(indexCoder, buf, s2);
        indexCoder = prepend(indexCoder, buf, s1);
        return newString(buf, indexCoder);
    }

文字列に `\0001` を含む場合

上記した通り、 StringConcatFactory#makeConcatWithConstants(MethodHandles.Lookup lookup, String name, MethodType concatType, String recipe, Object... constants) の recipe に、結合する文字列のフォーマットを渡します。
このフォーマットは、変数を埋め込む箇所に \u0001 を指定するというものでした。

しかし、下記のように文字列の中に \u0001 が使われている事がありえます。

"Hello\u0001 " + foo + "!";

この場合は、該当の文字列を \u0002 に置き換えて、 \u0001 を含む文字列を引数の constants に格納します。

recipe: "\u0002\u0001!"
constants: [ "Hello\u0001 " ]

これを受け取った StringConcatFactory は、recipe をパースする際に \u0002 となっている個所に constants の値を埋め込み、フォーマットを再構築します。

引数の上限

結合する変数が200個以上の場合、処理が分割されます。
例えば、300個の変数を文字列結合する場合は以下の順で処理されます。

199個の変数を結合
101個の変数を結合
1 と 2 で出来上がった文字列を結合

この点は、JavaDoc にも明記されています。

APIのノート:
JVMの制限があります(クラス・ファイル構造制約): 255個以上のスロットで呼び出すことはできません。これは、ブートストラップ・メソッドに渡すことができる静的および動的引数の数を制限します。 MethodHandleコンビネータを使用する可能性のある連結ストラテジがあるので、一時的な結果をキャプチャするためにパラメータ・リストに空のスロットをいくつか予約する必要があります。これは、このファクトリのブートストラップ・メソッドが200を超える引数スロットを受け入れない理由です。連結で200以上の引数スロットを必要とするユーザーは、大きな連結をより小さな式で分割することが予想されます。
StringConcatFactory (Java SE 15 & JDK 15)

コンパイルオプション（実装の選択）

コンパイル時に、オプション-XDstringConcat=inline を付けると、過去の StringBuilder を使った実装を使うようにもコンパイルできます。

ちなみに、このオプションには以下の値を指定できます。

値	処理内容
inline	StringBuilder で処理する。
indy	InvokeDynamic で動的に処理を作る。ブートストラップメソッドとして`StringConcatHelper#makeConcat` を使う。
indyWithConstants	InvokeDynamic で動的に処理を作る。ブートストラップメソッドとして`StringConcatHelper#makeConcatWithConstants` を使う。

デフォルトは、indyWithConstants です。

indy を指定した場合も、indyWithConstants とほぼ同じ処理が行われます。
違いは recipe を動的に作るかどうかです。最終的には makeConcatWithConstants が呼ばれます。
→ makeConcat(MethodHandles.Lookup, String, MethodType) の JavaDoc

public static CallSite makeConcat(MethodHandles.Lookup lookup,
                                  String name,
                                  MethodType concatType) throws StringConcatException {
    // This bootstrap method is unlikely to be used in practice,
    // avoid optimizing it at the expense of makeConcatWithConstants

    // Mock the recipe to reuse the concat generator code
    String recipe = "\u0001".repeat(concatType.parameterCount());
    return makeConcatWithConstants(lookup, name, concatType, recipe);
}

実行時オプション（作成する匿名メソッドの選択）

Java 9 ～ Java 14 まで、Java の実行時に VM オプション –D:java.lang.invoke.stringConcat=(ストラテジー名) を付けることで、上記以外の実装も選ぶことがでました。

ストラテジー	概要
BC_SB	StringBuilderを使ったバイトコードを生成する（既存と同様）
BC_SB_SIZED	StringBuilderを使ったバイトコードを生成する。加えて、必要な配列のサイズを「推定」する。
BC_SB_SIZED_EXACT	StringBuilderを使ったバイトコードを生成する。加えて、必要な配列のサイズを「正確に計算」する。
MH_SB_SIZED	MethodHandleベースのジェネレータを使って、最終的にStringBuilder を呼び出す。加えて、必要な配列のサイズを「推定」する。
MH_SB_SIZED_EXACT	MethodHandleベースのジェネレータを使って、最終的にStringBuilder を呼び出す。加えて、必要な配列のサイズを「正確に計算」する。
MH_INLINE_SIZED_EXACT	MethodHandleベースのジェネレータを使って、独自にbyte配列を構築する。必要な配列のサイズを「正確に計算」する。

デフォルトは、MH_INLINE_SIZED_EXACT です。
ただし、このオプションは Java 15 で削除されました。

参考資料

ここまで読んだうえで、 StringConcatFactory の JavaDoc とソースコードを読めば、文字列結合について詳しくなれる… ハズ！

java.lang.invoke.StringConcatFactory
- ソースコード : jdk/StringConcatFactory.java at master · openjdk/jdk · GitHub
java.lang.StringConcatHelper
- ソースコード : jdk/StringConcatHelper.java at master · openjdk/jdk · GitHub

float, double, Object 型の変数は最初に文字列に変換しているので、ここでは文字列型の処理に入ります。 ↩ ↩²
33ビット目では？と思われるかもしれませんが、0-indexed （最初を0ビットとして数える）ので32ビット目になります。 ↩
これはアンセーフな処理です。なぜなら、文字列の配列を外側からいじれるようになってしまい、String が不変でなくなってしまうためです。そのため、通常であれば配列をコピーしてから格納するのですが、今回は配列をいじることがないと保証できるため、コピーをしないアンセーフなコンストラクタを使っています。 ↩

環境

前提知識

処理の概要

匿名メソッドの処理

具体例

文字列への変換

文字数と文字コードを調べる

int 型の場合

文字列型の場合

必要なサイズの byte 配列を作成

配列に文字列を詰める

int 型の場合

文字列型の場合

配列を文字列にする

落穂拾い

最適化

文字列に \0001 を含む場合

引数の上限

コンパイルオプション（実装の選択）

実行時オプション（作成する匿名メソッドの選択）

参考資料

文字列に `\0001` を含む場合