Making a string format-optimizing preprocessor by annotation processing

この記事は LINE Advent Calendar 2018 の 17 日目の記事です。

こんにちは、LINEのメッセンジャーアプリのサーバーサイド開発チームに所属して、Redisの運用やArmeria の開発を担当している井出真広(@imasahiro)です。

この記事ではJava言語において、Annotation Processingを使った、最適化されたString.formatメソッドを自動生成した事例を紹介します。

1. はじめに – String.format

Applicationを記述する上で、logging、APIのresponseを構築するためなどのために、様々なデータの変換が行われています。特に、データを特定の書式に文字を整形したり、数値を0 paddingするなど、入力された書式に基づいて文字列に変換することは日常的に行われています。 そのような目的を実現するため、Java言語ではJava5から書式付き文字列を生成するためメソッドとしてString.formatが導入されました。

String.formatは引数に指定されたobjectを書式文字列(書式指示子(例えば、%s%03d)を含んだ文字列)を元に整形して新たに文字列を生成するJava言語のメソッドです。このようなメソッドは多くのプログラミング言語に存在し、例えばC/C++言語ではsnprintfがあります。実際、String.formatは数値や文字列を整形するのに便利なので、よく使われるメソッドです。しかし、その実行は低速であり、場合によってはアプリケーション全体の実行に影響を与えます。そのためJava言語で文字列を構築する場合には考えなしにString.formatを使用するのを避け、StringBuilder+演算子を使ってHand optimizeされた書式付き文字列を構築するコードを書くことも少なくありません。

String.formatが登場したばかりのJava5の時代も今は昔、Just-In-Timeコンパイラも大きく進化したはずの現代においてそんなことは考える必要が無いのではないと信じていましたが、世の中はそう甘くはありません。未だにString.formatを避け、Hand optimizeをしなければいけない事実に不満を感じていました。現実問題として、整形された文字の構築を行う場面はログ出力を含めて日常的に遭遇します。そのためString.formatを最適化すれば、様々なApplicationがより高速に動作できるのでは?と考えるようになりました。

2. なぜ String.format は遅いのか?

本題に入る前に、なぜString.formatが遅いのかについて考えてみましょう。

String.formatは実際にはFormat.formatメソッドで実装されています。そして、このformatメソッドは大きく分けて2つのphaseで構成されています。1つ目のphaseでは書式文字列をパースします。OpenJDKのコードを確認してみると、正規表現を使いながらparseしていることが確認できます。 2つ目のフェーズでは、1つ目のフェーズで見つけた書式指示子に従って、実際の文字列に変換していきます。[code]

String.formatがどのような挙動をするか概要が掴めたところで、ほとんど自明ではありますが、実際に各フェーズがどの程度の時間を占めているかを計測してみましょう。以下はString.formatを使って数値を文字列に変換する例です。

import java.util.concurrent.ThreadLocalRandom;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.infra.Blackhole;

public class StringFormatBenchmark {
    @Benchmark
    public void benchmark(Blackhole bh) {
        bh.consume(String.format("%d + %d * %d / %d",
                                 ThreadLocalRandom.current().nextInt(),
                                 ThreadLocalRandom.current().nextInt(),
                                 ThreadLocalRandom.current().nextInt(),
                                 ThreadLocalRandom.current().nextInt()));
    }
}

そして、表1がasync-profilerを用いて計測した結果になります。ここで、サンプル数、percentが多いほどそのメソッドがより多くの実行時間を占めており、objectを文字列に変換をするFormatSpecifier.printの実行の他に、書式文字列を正規表現を用いてパースしている時間がかなり含まれていることが確認できます。

表1 String.format プロファイル結果

NS PERCENT SAMPLES TOP
1010000000 10.72% 101 java.util.Formatter$FormatSpecifier.print
880000000 9.34% 88 java.util.regex.Pattern$GroupHead.match
650000000 6.90% 65 java.util.Arrays.copyOf
600000000 6.37% 60 java.util.concurrent.ConcurrentHashMap.get
580000000 6.16% 58 java.util.regex.Pattern$Start.match
520000000 5.52% 52 java.util.regex.Pattern$BmpCharProperty.match
510000000 5.41% 51 java.util.Formatter.format
500000000 5.31% 50 java.util.Formatter$FormatSpecifier.index
330000000 3.50% 33 java.lang.Long.getChars
240000000 2.55% 24 java.util.regex.Pattern$Branch.match
240000000 2.55% 24 jshort_disjoint_arraycopy
240000000 2.55% 24 java.util.Formatter$FormatSpecifier.width
200000000 2.12% 20 java.util.Locale.getDefault
200000000 2.12% 20 java.lang.AbstractStringBuilder.<init>
200000000 2.12% 20 jlong_disjoint_arraycopy
180000000 1.91% 18 java.util.regex.Pattern$BranchConn.match
180000000 1.91% 18 arrayof_jint_fill
140000000 1.49% 14 java.util.ArrayList.add

このように、String.formatでは、単に文字列への変換だけでなく、書式文字列のパースを合わせて行なっています。多くの場合、String.formatで指定される書式文字列は変化しないと仮定すると、このパースの時間を削減できれば、トータルの実行時間を削減できます。

3. Annotation Processingによる書式付き文字列の変換

ここまでで、パース処理にかかる時間を削減できれば、formatの実行時間を削減できることがわかりました。それでは、どのように削減していけばいいでしょうか? 一つの方法は、正規表現のマッチで実現しているパース処理を高速化する方法です。この方法では、String.format 1回にかかる時間を削減できますが、パース処理を完全には削減できるわけではありません。そのため、繰り返しString.formatを呼び出された場合を考えると、削減された実行時間に比べて最適化の労力に見合わないかもしれません。

もう一つの方法はパース処理自体を事前に終わらせる方法です。こちらの方法ではパース処理は実行前に完了しておき、String.formatの呼び出しの際にはパース結果を使って文字列変換するだけです。そのため、String.formatが繰り返し呼び出された場合でも実行速度の点で満足できる結果を得られそうです。

都合の良いことにJava言語では、Annotation Processingと呼ばれる仕組みを使ってコードのコンパイル時に新たにコードを生成する仕組みを提供しています。 Annotation Processing はJava5ではJSR 175 Metadata facility for Java、Java6でJSR 269 Pluggable Annotation Processing APIとして導入された仕組みで、コンパイル時にAnnotationをscanして処理し、Javaコードを入力としてファイル(通常は.javaファイル)を出力します。

Annotation Processingの面白いところは、Javaコードに記述された内容をJava言語を使ってコンパイル時に新たにJavaコードを生成できる点です。現在では多くのJava libraryで広く利用されています。例えば、JPAはMetaModel生成に利用しており、またAutoValueではimmutableなvalue typeを生成するために利用しています。なお、注意点として、Annotation Processingではすでに存在するソースコードに対して変更を加えることはできず、常に新しいファイルを生成するための仕組みという点に注意が必要です。

本記事では、このAnnotation Processingを使って事前に書式文字列から、書式付き文字列を生成するJavaコードを生成するAnnotation Processor, auto-string-formatterを作成しました。

auto-string-formatterはAnnotation Processorの1つとして動作します。auto-string-formatterは@AutoStringFormatterのannotationに付随する書式文字列を解析し、StringBuilderを使用したJavaコードに変換します。

表2、表3のJavaコードはauto-string-formatterの使用例と変換後のJavaコードを示しています。書式文字列のパース処理はAnnotation Processing後ではJavaコードに変換されていることが確認できます。

表2 autostringformatterを用いたformatter

import com.github.imasahiro.stringformatter.annotation.AutoStringFormatter;
import com.github.imasahiro.stringformatter.annotation.Format;

public class StringFormatBenchmark {
    @AutoStringFormatter
    interface Formatter {
        @Format("%d + %d * %d / %d")
        String format(int a, int b, int c, int d);
    }
}

表3 auto-string-formatterを用いたformatterの変換結果

import java.lang.String;
import javax.annotation.Generated;
import javax.inject.Named;

public final class StringFormatBenchmark_Formatter implements StringFormatBenchmark.Formatter {
  public final String format(final int arg0, final int arg1, final int arg2, final int arg3) {
    final StringBuilder sb = new StringBuilder(16);
    sb.append(arg0);
    sb.append(" + ");
    sb.append(arg1);
    sb.append(" * ");
    sb.append(arg2);
    sb.append(" / ");
    sb.append(arg3);
    return sb.toString();
  }
}

そして、表4がasync-profileによるプロファイル結果となります。プロファイル結果からも、正規表現のマッチ処理が消えていることが確認できます。

表4 auto-string-formatterを用いたformatterのプロファイル結果

ns percent samples top
6550000000 65.57% 655 java.util.Arrays.copyOf
820000000 8.21% 82 jshort_disjoint_arraycopy
810000000 8.11% 81 com.github.imasahiro.stringformatter.processor.benchmark.IntegerStringifyBenchFormatter_Formatter.format
360000000 3.60% 36 java.lang.Integer.valueOf
310000000 3.10% 31 java.lang.AbstractStringBuilder.
270000000 2.70% 27 jlong_disjoint_arraycopy
130000000 1.30% 13 jshort_arraycopy
100000000 1.00% 10 com.github.imasahiro.stringformatter.processor.benchmark.IntegerStringifyBench.autoStringFormatter

最後に、表5にString.formatauto-string-formatterと、String.concat+演算子を用いてhand optimizeしたコードの実行時間を比較しました。String.contact+演算子を用いて手で最適化したものと等価とまではいきませんでしたが、formatの8.22倍と実用に耐えうるものになったのではないでしょうか?

表5 String.format, auto-string-formatter, String.concat, String.+のベンチマーク結果

Benchmark Mode Cnt Score Error Units
StringFormatBenchmark.javaStringFormat thrpt 20 530.650 ± 72.088 ops/ms
StringFormatBenchmark.autoStringFormatter thrpt 20 4355.464 ± 88.833 ops/ms
StringFormatBenchmark.javaStringConcat thrpt 20 4869.365 ± 89.785 ops/ms
StringFormatBenchmark.stringBuilder thrpt 20 5080.943 ± 71.112 ops/ms

4. おわりに

この記事では、String.formatの挙動となぜ遅いかについて説明しました。また、それを改善する手法の1つとして、書式文字列をいい感じのJavaコードに変換するAnnotation Processor「auto-string-formatter」を紹介しました。

auto-string-formatterはbintrayにpublishしており、Gradleであれば以下のように指定すれば利用可能です。

repositories { jcenter() }
annotationProcessor 'com.github.imasahiro:auto-string-formatter-processor:0.5.5'
compileOnly 'com.github.imasahiro:auto-string-formatter-processor:0.5.5'
compile 'com.github.imasahiro:auto-string-formatter-runtime:0.5.5'

明日はbitter_foxさんによる「Running HBase on JDK11 and evaluate ZGC for HBase」です。お楽しみに!

Related Post