Java の + 演算子による文字列結合は、どのように処理されているのか

（この記事は [地平線に行く](https://yujisoftware.hatenablog.com/entry/2020/12/22/011817) とのマルチポストです）

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

```java
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](http://openjdk.java.net/jeps/254) に基づき、String クラスの内部で文字を以下のように保持するように変わりました。

* すべての文字が [LATIN1](https://ja.wikipedia.org/wiki/ISO/IEC_8859-1) の範囲内であれば、LATIN1（1文字 = 1byte）
* （日本語など）LATIN1 の範囲外の文字があれば、UTF-16 （1文字 = 2byte）

これについての詳細は、下記の記事でご確認ください。
[Java9 でも String クラスがリファクタリングされていました （JEP 254: Compact Strings 編） - 地平線に行く](https://yujisoftware.hatenablog.com/entry/20170921/1506021860)

# 処理の概要

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

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

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

# 匿名メソッドの処理

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

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

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

# 具体例

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

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

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

```java
{
  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](https://docs.oracle.com/javase/jp/15/docs/api/java.base/java/lang/invoke/MethodType.html) という型
    * 作成する匿名メソッドのシグネチャの情報が保持されている
        * この中の引数の情報 `parameterArray` に、結合する変数の型情報が保持されている
            * 今回の場合 `[ java.lang.Object.class, int.class ]`
* `recipe`
    * 変数に置換する箇所を `\0001` に、それ以外を結合した文字列
    * 今回の場合、 `"arg0: \u0001, arg1: \u0001"`

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


```java
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)` メソッドで文字列に変換しています。

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

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

```java
/**
 * 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 の順です。

```java
// 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` 型[^primitive]の処理をそれぞれ見ていきましょう。

[^primitive]: `float`, `double`, `Object` 型の変数は最初に文字列に変換しているので、ここでは文字列型の処理に入ります。

#### int 型の場合

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

```java
/**
 * 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)](https://github.com/openjdk/jdk/blob/aa9c136d67a32cebcdf031f50d8d5cccdd354bed/src/java.base/share/classes/java/lang/Integer.java#L550) というパッケージプライベートなメソッドを呼び出し、`value` を10進数の文字列にした時の長さを計算しています。

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

#### 文字列型の場合

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

```java
/**
 * 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ビット目[^32bit]はこのように文字コードが UTF-16 かどうかのフラグとして使います。

[^32bit]: 33ビット目では？と思われるかもしれませんが、0-indexed （最初を0ビットとして数える）ので32ビット目になります。

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

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

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

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

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

```java
/**
 * 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 の順です。

```java
// 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` 型[^primitive]の処理をそれぞれ見ていきましょう。

#### int 型の場合

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

```java
/**
 * 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)` の実装はこのようになっています。

```java
/**
 * 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](https://github.com/openjdk/jdk/blob/05a764f4ffb8030d6b768f2d362c388e5aabd92d/src/java.base/share/classes/java/lang/Integer.java#L486) または [StringUTF16.getChars](https://github.com/openjdk/jdk/blob/05a764f4ffb8030d6b768f2d362c388e5aabd92d/src/java.base/share/classes/java/lang/StringUTF16.java#L1533) で、`byte`配列に変数の値を詰めています。
詳しい解説は省きますが、これらの中では面白い実装によって `int` 型から10進数文字列に変換しています。
→ [Tech Tips: Integer.getCharsが面白い](http://techtipshoge.blogspot.com/2013/09/integergetchars.html)


#### 文字列型の場合

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

```java
/**
 * 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)` の実装はこのようになっています。

```java
/**
 * 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](https://github.com/openjdk/jdk/blob/05a764f4ffb8030d6b768f2d362c388e5aabd92d/src/java.base/share/classes/java/lang/String.java#L3608) メソッドを使って、`byte`配列に変数の値を詰めています。

### 配列を文字列にする

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

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

```java
/**
 * 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)` の実装はこのようになっています。

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


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

[^unsafe]: これはアンセーフな処理です。なぜなら、文字列の配列を外側からいじれるようになってしまい、String が不変でなくなってしまうためです。そのため、通常であれば配列をコピーしてから格納するのですが、今回は配列をいじることがないと保証できるため、コピーをしないアンセーフなコンストラクタを使っています。

# 落穂拾い

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

## 最適化

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

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

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

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

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

```java

    /**
     * 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` が使われている事がありえます。

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

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

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

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

## 引数の上限

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

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

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

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

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

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

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

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


デフォルトは、`indyWithConstants` です。

`indy` を指定した場合も、`indyWithConstants` とほぼ同じ処理が行われます。
違いは `recipe` を動的に作るかどうかです。最終的には `makeConcatWithConstants` が呼ばれます。
→ [makeConcat​(MethodHandles.Lookup, String, MethodType) の JavaDoc](https://docs.oracle.com/javase/jp/15/docs/api/java.base/java/lang/invoke/StringConcatFactory.html#makeConcat(java.lang.invoke.MethodHandles.Lookup,java.lang.String,java.lang.invoke.MethodType))

```java
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を使ったバイトコードを生成する。​<br/>加えて、必要な配列のサイズを「推定」する。​|
|BC_SB_SIZED_EXACT​|StringBuilderを使ったバイトコードを生成する。​​<br/>加えて、必要な配列のサイズを「正確に計算」する。​|
|MH_SB_SIZED​|MethodHandleベースのジェネレータを使って、最終的にStringBuilder を呼び出す。​​<br/>加えて、必要な配列のサイズを「推定」する。​|
|MH_SB_SIZED_EXACT​|MethodHandleベースのジェネレータを使って、最終的にStringBuilder を呼び出す。​​<br/>加えて、必要な配列のサイズを「正確に計算」する。​|
|MH_INLINE_SIZED_EXACT​|MethodHandleベースのジェネレータを使って、独自にbyte配列を構築する。​​<br/>必要な配列のサイズを「正確に計算」する。​|

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

# 参考資料

ここまで読んだうえで、 [StringConcatFactory の JavaDoc](https://docs.oracle.com/javase/jp/15/docs/api/java.base/java/lang/invoke/StringConcatFactory.html) とソースコードを読めば、文字列結合について詳しくなれる… ハズ！

* java.lang.invoke.StringConcatFactory
    * ソースコード : [jdk/StringConcatFactory.java at master · openjdk/jdk · GitHub](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/lang/invoke/StringConcatFactory.java)
* java.lang.StringConcatHelper
    * ソースコード : [jdk/StringConcatHelper.java at master · openjdk/jdk · GitHub](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/lang/StringConcatHelper.java)