2020/05/01

Java の文字列連結の変遷とベンチマーク

Java で文字列を連結するときは、+ 演算子ではなく StringBuffer や StringBuilder を使え、ということがよく言われてきました。
しかし、そうしなければならない理由や、しなくてもいいケース、あるいは + 演算子の方が良いケースもあることが、正しく理解されていないように思います。ベンチマークも交えて詳しく説明します。

文字列連結演算子「+」の仕様

Java における文字列連結演算子「+」の仕様は、String と何か任意の値をオペランドに取り、文字列表現に変換して連結するという仕様です。
初期の頃から一貫して、最適化について以下のように定められています。
An implementation may choose to perform conversion and concatenation in one step to avoid creating and then discarding an intermediate String object. To increase the performance of repeated string concatenation, a Java compiler may use the StringBuffer class or a similar technique to reduce the number of intermediate String objects that are created by evaluation of an expression.
日本語訳:
実装においては、中間的な String オブジェクトの作成と破棄を避けるために、変換と連結を1ステップで行うことが選択できます。反復的な文字列連結のパフォーマンスを向上させるために、Java コンパイラは StringBuffer クラスまたは同様の手法を使用して、式の評価によって作成される中間の String オブジェクトの数を削減できます。
 この仕様に沿って、ほぼ全ての Java コンパイラは、余分な String オブジェクトを生成しないような形で + 演算子を実装しています。

+ 演算子の内部処理の変遷

+ 演算子の内部処理は、Java のバージョンが進むにつれて、だんだん効率的な実装に変わってきています。

J2SE 1.4 以前

J2SE 1.4 以前は、StringBuffer を使うことが一般的でした。StringBuffer は mutable な文字シーケンスを管理するクラスで、append() により文字列を連結していくことができます。append() を行うと、内部では byte[] に追記されていきます。最後に toString() することで String オブジェクトが取得できる仕様です。
a + b + c が new StringBuffer().append(a).append(b).append(c).toString() と変換されていました。

Java 5 から Java 8

Java 5 では StringBuilder というクラスが導入されました。StringBuffer は全体的に同期化されていて、オーバーヘッドがありました。多くのシチュエーションで、同期化は必要ないとの考えから、同期化のない StringBuilder が導入されました。
+ 演算子の処理は単一スレッド内で完結するので、常に StringBuilder を使うことが適切ということになりましたので、ほぼ全てのコンパイラが + 演算子に対して StringBuilder を使うようになりました。

Java 9 以降

Java 9 では、JEP 280: Indify String Concatenation が導入されました。動的に文字列連結メソッドを生成する仕組みです。連結する文字列の個数や、連結に関連する定数が予め分かっているので、効率的な動作をするメソッドが生成できます。初回動作時にはメソッド生成のオーバーヘッドが生じますが、2回目以降は高速に動作します。
OpenJDK や OracleJDK の Java コンパイラでは、+ 演算子の処理にこれを用いるようになっています。しかし、Eclipse Compiler for Java (ECJ) では、使用しないようで、引き続き StringBuilder を使用する実装になっています。

+ を使うか StringBuilder を使うか

まず初めに

文字列連結式が何度も実行されるようなケースで、中間的に生成される String オブジェクトが不要な場合は、当然 StringBuilder を使ってください。
bad() のようなことをしてはダメです。good() のようにやりましょう。

  public static final String bad(final String[] strs) {
    String result = "";
    for (String s : strs) {
      result += s;
    }
    return result;
  }

  public static final String good(final String[] strs) {
    StringBuilder result = new StringBuilder();
    for (String s : strs) {
      result.append(s);
    }
    return result.toString();
  }

単独の文字列連結式の場合

以下の2つのメソッドは、いずれも引数 a, b として与えられた文字列を連結して返すメソッドです。

public static final String concatenate1(final String a, final String b) {
  return "[" + a + b + "]";
}

public static final String concatenate2(final String a, final String b) {
  return new StringBuilder("[").append(a).append(b).append("]").toString();
}

文字列結合は StringBuilder を使うべきだ、という話に愚直に従うと、常に concatenate2() のように書くべきだと考えてしまいがちです。
しかし Java 5 以降、Indify String Concatenation が使われないコンパイラでは、この2つのメソッドのバイトコードは以下のようになっています。

public static final java.lang.String concatenate1(java.lang.String a, java.lang.String b);
   0  new java.lang.StringBuilder [16]
   3  dup
   4  ldc <String "["> [18]
   6  invokespecial java.lang.StringBuilder(java.lang.String) [20]
   9  aload_0 [a]
  10  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  13  aload_1 [b]
  14  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  17  ldc <String "]"> [27]
  19  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  22  invokevirtual java.lang.StringBuilder.toString() : java.lang.String [29]
  25  areturn

public static final java.lang.String concatenate2(java.lang.String a, java.lang.String b);
   0  new java.lang.StringBuilder [16]
   3  dup
   4  ldc <String "["> [18]
   6  invokespecial java.lang.StringBuilder(java.lang.String) [20]
   9  aload_0 [a]
  10  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  13  aload_1 [b]
  14  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  17  ldc <String "]"> [27]
  19  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [23]
  22  invokevirtual java.lang.StringBuilder.toString() : java.lang.String [29]
  25  areturn

見ていただくと分かる通り、まったく同じバイトコードが生成されています。Indify String Concatenation が使われる Java 9 以降の OpenJDK, Oracle JDK ならば、concatenate1() は Indify されるので、むしろより効率的なコードになります。一応バイトコードを示すと、以下のようになっています。

public static final java.lang.String concatenate1(java.lang.String, java.lang.String);
  Code:
     0: ldc           #7                  // String [
     2: aload_0
     3: aload_1
     4: ldc           #9                  // String ]
     6: invokedynamic #11,  0             // InvokeDynamic #0:makeConcat:(Ljava/lang/String;Ljava/lang/String;Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;
    11: areturn

つまり、このようなケースでは concatenate2() のように書くのは、可読性を損ね、場合によってはパフォーマンスも悪くなっていることになります。
実は concatenate1() のケースで、new StringBuilder("[") で始まらず、new StringBuilder().append("[") となるコンパイラもありますが、微々たる差なので、ここは可読性を取りましょう。

ベンチマーク

さて、StringBuffer, StringBuilder, Indify String Concatenation がどれくらいの性能差になるのか、気になってきました。測定してみました。

ソースコード

今回は JMH (Java Microbenchmark Harness) で書いてみました。JMH の説明は割愛します。いずれ機会があれば別の記事で。

import (省略)
@BenchmarkMode(Mode.All)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Warmup(iterations = 1)
@Measurement(iterations = 1)
public class MyBenchmark {
  private static String a = "abcdefg";
  private static String b = "hijklmn";
  private static String c = "opqrstu";
  private MethodHandle concatenator = null;

  public static void main(final String[] args) throws Exception {
    Options opt = new OptionsBuilder().include(MyBenchmark.class.getSimpleName()).forks(1).build();
    new Runner(opt).run();
  }

  @Setup
  public void setUp() throws StringConcatException {
    concatenator = StringConcatFactory.makeConcatWithConstants(MethodHandles.lookup(), "",
        MethodType.methodType(String.class, new Class[] { String.class, String.class, String.class, long.class }), "\1\2\1\2\1\2\1",
        '-', '/', '+').dynamicInvoker();
  }

  @Benchmark
  public void byStringBuffer(final Blackhole bh) {
    bh.consume(new StringBuffer(a).append('-').append(b).append('/').append(c).append('+').append(System.currentTimeMillis()).toString());
  }

  @Benchmark
  public void byStringBuilder(final Blackhole bh) {
    bh.consume(new StringBuilder(a).append('-').append(b).append('/').append(c).append('+').append(System.currentTimeMillis()).toString());
  }

  @Benchmark
  public void byIndy(final Blackhole bh) throws Throwable {
    bh.consume(concatenator.invoke(a, b, c, System.currentTimeMillis()));
  }
}

説明

byStringBuffer(), byStringBuilder(), byIndy() の3つの実装を用意して、それぞれ測定しています。全て同様の文字列結合をするように作られています。
bh.consume() は、JIT 最適化によりメソッド呼び出しごと消去されてしまうことを防ぐため、メソッド外とのインタラクションを持たせる JMH のトリックです。つまり、気にしないてください。
byStringBuffer(), byStringBuilder() については見ての通りなので説明はしません。
byIndy() は、Indify String Concatenation を模倣しています。予め StringConcatFactory を用いて、ここでやりたいこと専用の文字列結合メソッドを動的に生成しておきます (20〜22行目)。JMH の @Setup を使えば、ベンチマークに先立って実行してくれます。本当の Indify String Concatenation の場合は、結合式が初めて評価されるときに行われています。今回の文字列結合は、動的な部分式とリテラルの混在した結合になっているので、StringConcatFactory::makeConcatWithConstants を用いています。動的な部分式の箇所を '\1'、リテラルの部分を '\2' としたレシピと呼ばれる文字列を作っておき、リテラル部分は makeConcatWithConstants() の引数としてメソッド生成時にセットしてしまいます。動的な部分はこれを invoke() するときの引数として渡します (37行目)。

結果

結果は以下のようになりました。

Benchmark                                              Mode     Cnt        Score    Error   Units
MyBenchmark.byIndy                                    thrpt                0.010           ops/ns
MyBenchmark.byStringBuffer                            thrpt                0.006           ops/ns
MyBenchmark.byStringBuilder                           thrpt                0.007           ops/ns
MyBenchmark.byIndy                                     avgt               98.126            ns/op
MyBenchmark.byStringBuffer                             avgt              159.741            ns/op
MyBenchmark.byStringBuilder                            avgt              148.244            ns/op
MyBenchmark.byIndy                                   sample  385108      148.898 ± 15.915   ns/op
MyBenchmark.byIndy:byIndy?p0.00                      sample               73.000            ns/op
MyBenchmark.byIndy:byIndy?p0.50                      sample              127.000            ns/op
MyBenchmark.byIndy:byIndy?p0.90                      sample              141.000            ns/op
MyBenchmark.byIndy:byIndy?p0.95                      sample              144.000            ns/op
MyBenchmark.byIndy:byIndy?p0.99                      sample              194.000            ns/op
MyBenchmark.byIndy:byIndy?p0.999                     sample             1727.128            ns/op
MyBenchmark.byIndy:byIndy?p0.9999                    sample            14619.117            ns/op
MyBenchmark.byIndy:byIndy?p1.00                      sample          1146880.000            ns/op
MyBenchmark.byStringBuffer                           sample  238982      210.144 ± 17.522   ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.00      sample              166.000            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.50      sample              180.000            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.90      sample              202.000            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.95      sample              211.000            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.99      sample              300.000            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.999     sample             7225.360            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p0.9999    sample            19977.763            ns/op
MyBenchmark.byStringBuffer:byStringBuffer?p1.00      sample          1247232.000            ns/op
MyBenchmark.byStringBuilder                          sample  285453      179.668 ±  3.853   ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.00    sample              127.000            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.50    sample              157.000            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.90    sample              177.000            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.95    sample              183.000            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.99    sample              250.000            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.999   sample             5872.048            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p0.9999  sample            21530.227            ns/op
MyBenchmark.byStringBuilder:byStringBuilder?p1.00    sample           230912.000            ns/op
MyBenchmark.byIndy                                       ss            52613.000            ns/op
MyBenchmark.byStringBuffer                               ss            60385.000            ns/op
MyBenchmark.byStringBuilder                              ss             9313.000            ns/op

スループット (Mode が thrpt となっている行) を見ると、Indy > StringBuilder > StringBuffer となっていて、Indy 版の速さが確認できました。
当然ですが、平均実行時間 (Mode avgt) を見ても、同様の結論です。
一方、最後に出てくる Mode ss というのは Single shot、つまり単発実行時の処理時間なのですが、Indy が StringBuilder にだいぶ負けています。おそらく、StringBuilder はベンチマークの開始に至るまでにそれなりの実行回数を重ねていて、JIT 最適化がかかっているのではないかと思います。Indy は動的にコードを生成したばかりですから、最適化されておらず、遅かった、ということではないでしょうか。

まとめ

中間オブジェクトを捨てるだけの複数の式に分かれている場合 (ループさせているとか、条件分岐で結合するものを変えているとか) は、もちろん StringBuilder が優位ですが、単純な文字列結合式は、素直に + 演算子で書いた方が読みやすい上に性能が出る可能性もあるということがお分かりいただけたかと思います。