原文はこちら。
The original article was written by Claes Redestad (Principal Member of Technical Staff, Oracle).
https://cl4es.github.io/2021/02/23/Faster-Charset-Decoding.html
最近、byte[]をStringに変換する方法について、いくつかのマイナーなOpenJDKの改善を行っていました。その中には、StringCoding.Result構造体の削除や、いくつかのレガシーなCharsetDecoderのオーバーヘッドの削減などを含みます。
Remove Result cache from StringCoding
https://bugs.openjdk.java.net/browse/JDK-8259842
Reduce decoder creation overheads for sun.nio.cs.ext Charsets
https://bugs.openjdk.java.net/browse/JDK-8261418
この領域で実験すると、パフォーマンス上の相違が見られました。new String(bytes, charset)は、InputStreamReaderを使って同じStringを作成するよりも何倍も速いことが多く、一見しただけでは妥当とは思えないほどでした。
その理由を分析し、できる限りの最適化を行った結果、かなり顕著な改善が見られました。
8261744: Implement CharsetDecoder ASCII and latin-1 fast-paths #2574
https://github.com/openjdk/jdk/pull/2574
TL;DR: JEP 254: Compact Stringsをサポートするために実装されたいくつかの組み込みメソッドを再利用することで、ASCII互換の
CharsetDecoderをマイクロベンチマークで最大10倍まで高速化することができました。これらの最適化は JDK 17 に搭載される予定です。
Compact Strings
実施したことを深く理解するためには、数年前、JDK 9でCompact Stringsを（再）導入する作業へさかのぼる必要があります。
JDK 8では、Stringはその内容をchar[]に格納しており、プレーンかつシンプルでした。しかし、Javaのcharは16ビットのプリミティブで、その値は（大体）UTF-16に対応しています。多くのソフトウェアでは、多くの（あるいはほとんどの）文字列は、最下位の7ビット（ASCII）または8ビット（ISO-8859-1）しか使用しないため、格納された文字ごとに約1バイトを無駄にしています。
確かに、多くの一般的なコードポイントの多くで、UTF-16で8ビットや16ビット以上を必要とするロケールもありますが、経験上、ほとんどのロケールのアプリケーションでは、ASCIIのみの文字列が大量に存在します。これらをよりコンパクトな形で保存すれば、かなりのフットプリント削減になります。特に、1文字あたり2バイト以上を必要とする文字列に対してコストなし、もしくはほとんどかからないのであれば、それに越したことはありません。
よりスペース効率の良い表現を使うことは、以前から検討され、実装されていました。JDK 6には、-XX:+UseCompressedStringsがあり、Stringが透過的にbyte[]またはchar[]を使用するように変更されました。この実装は、私がOpenJDKに取り組み始める前に廃止されましたが、メンテナンスの悪夢であり、非ASCII文字列の割合が多いアプリケーションを実行すると、パフォーマンスが大幅に低下することが知られていたと聞いています。
Support for Compressed Strings being Dropped in HotSpot JVM?
https://stackoverflow.com/questions/8833385/support-for-compressed-strings-being-dropped-in-hotspot-jvm
JDK 9で、新しい試みとして、JEP 254のCompact Stringsが考案されました。
JEP 254: Compact Strings
https://openjdk.java.net/jeps/254
必要に応じてbyte[]とchar[]を切り替えるのではなく、Stringは常に簡単なスキームを使ってchar値のマッピング先であるbyte[]で下支えされます。
- すべての文字がISO-8859-1エンコーディングで表現できる場合、それらを「圧縮」して
charごとに1バイトを使用する - それ以外の場合は、すべての文字を2つのバイトに分割し、それらを背中合わせにして保存する。これでも効果的にUTF-16にエンコードされる。
マッピングのロジックを追加してできあがりです。
さて、フットプリントを減らすことはそれだけで素晴らしいことですが、パフォーマンスを適切に保つことも必要です。
ISO-8859-1に収まる文字列のスピードアップにより、UTF-16エンコーディングを必要とする文字列の（パフォーマンスに）大きな犠牲を及ぼすのはあまり良いことではありません。このような懸念を解消するために、JEP 254はかなりの努力をしました。この統合では9人の共著者と12人のレビュアーが関わっていますが、QAなどでさらに多くのエンジニアが関わっていたことでしょう。
8141132: JEP 254: Compact Strings
https://github.com/openjdk/jdk/commit/7af927f9c10923b61f746eb6e566bcda853dd95a
Intrinsically fast
char[]からbyte[]への圧縮、byte[]からchar[]へのインフレーションなどの組み込みメソッドを実装することでパフォーマンスを最適化しました。多くの場合、JDK 8のベースラインよりもパフォーマンスが最適化されています。
JDKでいうところの組み込みメソッドとは、OpenJDK HotSpotのようなJVMが、高度に最適化された手作業で作成されたメソッドに置き換え可能なJavaメソッドのことです。このような手作業による最適化は大変な作業ですが、ある特定の、非常にパフォーマンスに敏感なケースでは、JVMが正しい動作をすることを保証できます。
JEP 254に実装されているメソッドの場合、主な利点は、最新のSIMD命令をカスタマイズして使用できることです。SIMDとは、Single Instruction, Multiple Dataの略で、一度に多くのビットのデータを操作するハードウェア命令を総称しています。例えば、IntelのAVX2拡張では、256ビットのデータを一度に処理することができます。このような命令を使用することで、場合によっては大幅な高速化が可能になります。
Deep Dive: new String(bytes, US_ASCII)
どのSIMD命令を実行しているかを確認するために、簡単なシナリオを試してみましょう。
最近のJDKでは、new String(byte[], Charset)は、CharsetがUS_ASCIIの場合にこのようになります。
if (COMPACT_STRINGS && !StringCoding.hasNegatives(bytes, offset, length)) {
this.value = Arrays.copyOfRange(bytes, offset, offset + length);
this.coder = LATIN1;
} else {
byte[] dst = new byte[length << 1];
int dp = 0;
while (dp < length) {
int b = bytes[offset++];
StringUTF16.putChar(dst, dp++, (b >= 0) ? (char) b : REPL);
}
this.value = dst;
this.coder = UTF16;
}
ifの分岐でCompactStringsが有効であることを確認し、StringCoding.hasNegativesを呼び出しています。
@IntrinsicCandidate
public static boolean hasNegatives(byte[] ba, int off, int len) {
for (int i = off; i < off + len; i++) {
if (ba[i] < 0) {
return true;
}
}
return false;
}
これは、入力の中に負の値があればtrueを返すという簡単なチェックです。負のバイトがなければ、入力はすべてASCIIであり、続いて入力をStringの内部配列byte[]にコピーできます。
Experimental setup
シンプルながらも興味深いシナリオがreadStringDirectというJMHマイクロベンチマークにあります。
Java Microbenchmark Harness (JMH)
https://github.com/openjdk/jmh
@Benchmark
public String readStringDirect() throws Exception {
return new String(bytes, cs);
}
上述のUS-ASCIIのファストパスにズームインするために、-p charsetName=US-ASCII -p length=4096をつけてこのベンチマークを実行することにしました。
筆者の実験環境は、古いHaswellベースのLinuxワークステーションです。MacやWindowsの場合は、これらの手順を変更する必要があるかもしれませんし、新しい（または古い）ハードウェアでは結果が異なるかもしれません。
また、確実に共有ライブラリhsdisと共に使うようにJDKを準備しました。-XX:+PrintAssemblyをつけてコンパイル済みメソッドの逆アセンブルを有効にできます。（OpenJDKの一部ではありますが、様々なライセンス上の理由から、hsdisのビルドは配布できません。バイナリが見つからない場合に自分でビルドする方法については、Gunnar Morlingによる素晴らしいガイドがあります）。
Building hsdis for OpenJDK 15
https://www.morling.dev/blog/building-hsdis-for-openjdk-15/
続いて、マイクロベンチマークを -prof perfasm をつけて実行します。この優れたビルトインプロファイラは、Linuxのperfプロファイラと、-XX:+PrintAssemblyで収集したデータを使用して、マイクロベンチマークが実行する最もホットなコード領域を非常に詳細に記述します。
perf: Linux profiling with performance counters
https://perf.wiki.kernel.org/index.php/Main_Page
Experimental Results
プロファイラの出力を見て、ホット・コードを探してみたところ、このコードが特にホットでした。
│ 0x00007fef79146223: mov $0x80808080,%ebx
0.02% │ 0x00007fef79146228: vmovd %ebx,%xmm0
│ 0x00007fef7914622c: vpbroadcastd %xmm0,%ymm0
0.21% │↗ 0x00007fef79146231: vmovdqu (%rsi,%rcx,1),%ymm1
13.16% ││ 0x00007fef79146236: vptest %ymm0,%ymm1
11.34% ││ 0x00007fef7914623b: jne 0x00007fef791462a3
1.63% ││ 0x00007fef7914623d: add $0x20,%rcx
│╰ 0x00007fef79146241: jne 0x00007fef79146231
x86アセンブリーですね。それではブレイクダウンしてみましょう…。
最初の列は、各命令の実行にかかった相対的な時間を示しています。これらの値には多少の誤差はありますが、1つの命令に10％以上の時間がかかっているのは珍しいことです。
2列目のASCIIアートの矢印は、ループの先頭へのジャンプなど、制御フローの遷移を示しています。3列目はアドレスの一覧、残りの部分は、各アドレスのx86アセンブラを逆アセンブルしたものです。
最初の3つの命令は、256ビットのymm0ベクトルレジスタに0x80という値が32回繰り返されるように準備します。これは、xmm0に0x80808080をロードし、それをvpbroadcastdでymm0の32ビットセグメントのそれぞれにブロードキャストすることで行われます。
なぜ0x80なのでしょうか？0x80は、最上位ビットが設定されたオクテット（バイト）です。Javaでは、最上位ビットが設定されたバイトは負の値になります。したがって、ymm0の値は、他のymmレジスタのバイトが負の値であるかどうかを検出するマスクとして使用できます。
そして、まさにこれが次のループで行われています。
vmovdqu (%rsi,%rcx,1),%ymm1)：入力配列から 32 バイトをymm1レジスタにロードvptest %ymm0,%ymm1：ymm0のマスクと先ほど読み込んだ32バイトの間で論理 AND を取る- いずれかのバイトが負の値であれば、次の命令（
jne）でループを抜ける - そうでなければ、入力の32バイト先にスキップし、
rcxが0になるまで繰り返す
この図にはありませんが、rcxの値が32の倍数であることを確認するための設定と、最大31バイトの後続バイトを処理しています。
このように、私たちが実行するコードがAVX2命令を利用していることはわかりました。しかし、これがマイクロベンチマークのパフォーマンスにどの程度貢献しているのでしょうか？
Benchmarking the effect of the intrinsic
偶然にも、intrinsicsはオフにすることができます。これにより、C2が手作業で作成したintrinsicを使用しない場合のパフォーマンスと比較できます。（問題の1つは、HotSpotがこれらのintrinsicをどのように呼んでいるかを把握することです。これが_hasNegativesで識別されていることを見つけるために、OpenJDKのソースコードを grepする必要がありました）。
Benchmark Score Error Units
readStringDirect 1005.956 ± 36.044 ns/op
-XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_hasNegatives
readStringDirect 4296.533 ± 870.060 ns/op
hasNegativesのintrinsicのベクトル化により、このシンプルなベンチマークで4倍以上の高速化を実現しました。
Enter the InputStreamReader
上記のことはどれも最近まで記憶に残っていませんでした。「熱心な野次馬」がカウントされないかぎり、筆者がJEP254に関与することはありませんでした。しかし偶然にも最近、InputStreamReaderのパフォーマンスオーバーヘッドを評価するために、いくつかの関連する実験を始めました。あるアプリケーションのプロファイルを見て、ちょっとした疑念を抱いたことが動機となりました。
このあたりをちょっと思いつきました。
@Benchmark
public String readStringReader() throws Exception {
int len = new InputStreamReader(
new ByteArrayInputStream(bytes), cs).read(chars);
return new String(chars, 0, len);
}
これは、意図的にI/Oを避けたシンプルで合成されたマイクロベンチマークです。InputStreamのポイントは通常I/Oを扱うことなので、あまり現実的ではありませんが、それでも非I/Oのオーバーヘッドを測定するには興味深いものです。
また、今回の性能評価のベースラインとして、上記の実験で使用したreadStringDirectベンチマークを設定しました。readStringReaderがreadStringDirectよりも数倍遅いことを十分に予想していました。InputStreamReaderは、読み取ったバイトをまず文字列にデコードし、次にStringコンストラクタでバイトに圧縮して戻す必要があるからです。しかし、測定された12倍の差には驚かされました。
Benchmark Score Error Units
readStringDirect 1005.956 ± 36.044 ns/op
readStringReader 12466.702 ± 747.116 ns/op
Analysis
その後、いくつかの実験を行ったところ、より小さな入力に対して readStringReader はかなりの一定のオーバーヘッドを持つことが明らかになりました。主に、内部バッファとして使用される8Kbのbyte[]を割り当てるためです。しかし、InputStreamReader のスケールが悪いことも明らかになりました。
入力サイズが4096から25000へと6.1倍になったとき、readStringDirectベンチマークのコストは6.5倍になりました。これは、私が予想していた通りの結果です。ほぼ線形で、さまざまなキャッシュしきい値を超えたときに生じる小さな超線形効果があります。しかし、readStringReaderでは、コストが10倍になっています。
プロファイリングデータを調べてみると、バイトを1つずつbyte[]からchar[]にコピーするUS_ASCII$Decoder.decodeArrayLoopでreadStringReaderはほとんどの時間を費やしていることも明らかになりました。
while (sp < sl) {
byte b = sa[sp];
if (b >= 0) {
if (dp >= dl)
return CoderResult.OVERFLOW;
da[dp++] = (char)b;
sp++;
continue;
}
return CoderResult.malformedForLength(1);
}
ホットパス上にいくつかのブランチがあることは赤信号であり、コストが超直線的に増加する原因となっている可能性があります。
Reuseable intrinsics
今になってみると、その解決策は明らかです。byte[]からchar[]へのコピーは、JEP 254が良好なパフォーマンスを確保するために多くの労力を費やして最適化しなければならなかったものの一つです。これらのintrinsicsを再利用することは、実際に実現可能であることがわかれば、当然のことのように思えます。
物事をきれいに保ち、実装の詳細が漏れるのを最小限にするため、結局、sun.nio.csのデコーダが使用する、java.langの2つの内部メソッドだけを公開する PR を作成しました。
8261744: Implement CharsetDecoder ASCII and latin-1 fast-paths #2574
https://github.com/openjdk/jdk/pull/2574
decodeASCIIは入力のbyte[]と出力のchar[]を取り、可能な限りデコードを行う。効率および簡単のため、Stringの新たなパッケージプライベートなメソッドを使って実装されている。
static int decodeASCII(byte[] sa, int sp, char[] da, int dp, int len) {
if (!StringCoding.hasNegatives(sa, sp, len)) {
StringLatin1.inflate(sa, sp, da, dp, len);
return len;
} else {
int start = sp;
int end = sp + len;
while (sp < end && sa[sp] >= 0) {
da[dp++] = (char) sa[sp++];
}
return sp - start;
}
}
inflateBytesToCharsは、StringLatin1.inflateの組み込みメソッドをそのまま公開する。これは特に、ISO_8859_1$Decoderが利用できるようにするためである。
US_ASCII$Decoder.decodeArrayLoop のwhileループを以下のように書き直すことができます。
int n = JLA.decodeASCII(sa, sp, da, dp, Math.min(sl - sp, dl - dp));
sp += n;
dp += n;
src.position(sp - soff);
dst.position(dp - doff);
if (sp < sl) {
if (dp >= dl) {
return CoderResult.OVERFLOW;
}
return CoderResult.malformedForLength(1);
}
return CoderResult.UNDERFLOW;
セマンティクスは同じですが、作業の大部分はdecodeASCIIメソッドに委ねられ、SIMD intrinsicsのおかげでスピードアップが図られるはずです。
Results
以前と同じグラフを最適化されたバージョンでプロットすると、まったく違うイメージになります。
InputStreamReaderの一定のオーバーヘッドを考慮すると、readStringReaderはreadStringDirectを約2.2倍引き離し、同様のスケーリングを示しています。
入力サイズが25,000のデータポイントでは、最適化によりUS-ASCIIで約10倍のスピードアップが図られました。前述のPR（現在は統合済みです）では、適用可能なすべてのビルトインCharsetDecoderを改善しようとしました。
8261744: Implement CharsetDecoder ASCII and latin-1 fast-paths
https://github.com/openjdk/jdk/commit/433096a45ea847e2e2ae8cd5a100971939f6a11f
おそらく、それらの多くは最適化できるいくつかの基本型を継承しているので、思ったよりも作業は少ないでしょう。その結果、多くのCharsetデコーダがASCIIを読む際に、このようなintrinsicsを使うfast pathを取ることができるようになりました。
【変更前】
Benchmark (charsetName) (length) Cnt Score Error Units
readStringReader US-ASCII 256 10 2085.399 ± 66.522 ns/op
readStringReader US-ASCII 4096 10 12466.702 ± 747.116 ns/op
readStringReader US-ASCII 25000 10 123508.987 ± 3583.345 ns/op
readStringReader ISO-8859-1 256 10 1894.185 ± 51.772 ns/op
readStringReader ISO-8859-1 4096 10 8117.404 ± 594.708 ns/op
readStringReader ISO-8859-1 25000 10 99409.792 ± 28308.936 ns/op
readStringReader UTF-8 256 10 2090.337 ± 56.500 ns/op
readStringReader UTF-8 4096 10 11698.221 ± 898.910 ns/op
readStringReader UTF-8 25000 10 66568.987 ± 4204.361 ns/op
readStringReader ISO-8859-6 256 10 3061.130 ± 120.132 ns/op
readStringReader ISO-8859-6 4096 10 24623.494 ± 1916.362 ns/op
readStringReader ISO-8859-6 25000 10 139138.140 ± 7109.636 ns/op
readStringReader MS932 256 10 2612.535 ± 98.638 ns/op
readStringReader MS932 4096 10 18843.438 ± 1767.822 ns/op
readStringReader MS932 25000 10 119923.997 ± 18560.065 ns/op
【変更後】
Benchmark (charsetName) (length) Cnt Score Error Units
readStringReader US-ASCII 256 10 1556.588 ± 37.083 ns/op
readStringReader US-ASCII 4096 10 3290.627 ± 125.327 ns/op
readStringReader US-ASCII 25000 10 13118.794 ± 597.086 ns/op
readStringReader ISO-8859-1 256 10 1525.460 ± 36.510 ns/op
readStringReader ISO-8859-1 4096 10 3051.887 ± 113.036 ns/op
readStringReader ISO-8859-1 25000 10 11401.228 ± 563.124 ns/op
readStringReader UTF-8 256 10 1596.878 ± 43.824 ns/op
readStringReader UTF-8 4096 10 3349.961 ± 119.278 ns/op
readStringReader UTF-8 25000 10 13273.403 ± 591.600 ns/op
readStringReader ISO-8859-6 256 10 1602.328 ± 44.092 ns/op
readStringReader ISO-8859-6 4096 10 3403.312 ± 107.516 ns/op
readStringReader ISO-8859-6 25000 10 13163.468 ± 709.642 ns/op
readStringReader MS932 256 10 1602.837 ± 32.021 ns/op
readStringReader MS932 4096 10 3379.439 ± 87.716 ns/op
readStringReader MS932 25000 10 13376.980 ± 669.983 ns/op
おそらく今日最も広く使われているエンコーディングのひとつであるUTF-8は、そのデコーダの実装においてすでにASCIIのfast-pathを持っていたことに注意してください。このfast-pathでは、いくつかの分岐を回避し、他の文字セットデコーダよりもスケーリングしているようです。一定のオーバーヘッドを差し引いても、4096バイトの入力と25000バイトの入力を比較すると、6.5倍のコスト増になっています。しかしUTF-8の場合でも、筆者の環境ではintrinsicsを再利用することで大幅に改善されました（25000バイトの入力で約5倍）。
最終的に、この特定のマイクロベンチマークでは、小さな入力サイズであれば1.3倍、大きな入力サイズであれば10倍以上の改善が見られました。
他にもいくつかのマイクロベンチマークを追加して、入力に非ASCII文字を追加したときのマイクロベンチマークの動作を調べました（入力の先頭、末尾、または入力の中に混ぜた場合。変更前と変更後の結果）。*Readerマイクロベンチマークのパフォーマンスは、*Directマイクロベンチマークの動作とほぼ同じですが、入力を8kBのチャンクで処理することでReaderマイクロベンチマークのパフォーマンスが向上している点が異なります。
特に混在した入力を扱う場合には、さらにコードを改善する方法があるでしょう。char[]にデコードするときに、String.decodeASCIIをhasNegativesとinflateを融合した intrinsicsに変えるのは理にかなっています。というのも、負のバイトを見つけたときに、実際に救済して再起動する必要がないためです。しかし、この機能拡張はすでに大きな進歩を遂げているので、さらなる利益を得たいという誘惑には勝てませんでした。少なくともちょっと時間が必要です。
Real world implications?
あるユーザーから、彼らのプロファイルでdecodeArrayLoopが多用されていたので、彼らのアプリケーションでこの機能を試してみないかと持ちかけられました。OpenJDKのPRをソースからビルド後、彼らはパッチが統合される前にテストでき、CPU使用率の合計を約15～25％削減できたと報告してくれました。
しかし、彼らの設定ではI/Oがボトルネックになっていることが多いことがわかりました。そのため、CPUの削減効果は大きいものの、多くのテストではスループットの向上にはつながりませんでした。状況によって異なる、ということです（YMMV：Your mileage may vary.）。すべてのI/Oが同じとは限りませんし、最適化によりレイテンシーに良い影響があるかもしれません。
最終的には、たとえスループットがあまり向上しなくても、CPUの削減だけで十分満足していただけたように思います。何はともあれ、これが電力とコストの削減につながることでしょう。
Acknowledgements
この記事を書くにあたり、多くの質問に答えてくれたTobias Hartmannに特に感謝したいと思います。そして、Tobiasと並んで、Vivek Deshpande、Vladimir Kozlov、Sandhya Viswanathanにも、これらのHotSpotの本質的な部分について優れた仕事をしてくれたことに感謝しています。筆者はただ単にこの新たな場所で活用できたにすぎないのですが。また、レビュー、議論、PRの統合に協力してくれたAlan BatemanとNaoto Sato、そして多くの編集上の提案をしてくれたDavid Delabasseeにも感謝します。
Appendix: Internals of a C2 intrinsic
逆アセンブルの私の理解が意味をなしているかどうかを知りたいと思いましたが、うまくいきませんでした。C2のコードは、コード生成に大きく依存しているため、回避や工夫が難しいのですが、他ならぬこのintrinsicの多くを書いたと思われるTobias Hartmannは、正しい場所を親切に教えてくれました。それがC2_MacroAssembler::has_negativesです。
これは、手元のハードウェアでできるだけ早くこの特定のJavaコードを実行するための、カスタムビルドのx86アセンブラを発行するルーチンです。このコードを調べてみると、マクロアセンブラを見つけることができるでしょう。これは、先ほどのコード（C2_MacroAssembler::has_negatives）3408行目をプロファイリングした際に見つけたホットピースコードを生成するために使われます。
movl(tmp1, 0x80808080); // create mask to test for Unicode chars in vector
movdl(vec2, tmp1);
vpbroadcastd(vec2, vec2, Assembler::AVX_256bit);
bind(COMPARE_WIDE_VECTORS);
vmovdqu(vec1, Address(ary1, len, Address::times_1));
vptest(vec1, vec2);
jccb(Assembler::notZero, TRUE_LABEL);
addptr(len, 32);
jcc(Assembler::notZero, COMPARE_WIDE_VECTORS);
癖はありますが、より高レベルで読みやすいです。
Logico Inside 