Faster Charset Decoding

原文はこちら。
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)は、CharsetUS_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回繰り返されるように準備します。これは、xmm00x80808080をロードし、それをvpbroadcastdymm0の32ビットセグメントのそれぞれにブロードキャストすることで行われます。

なぜ0x80なのでしょうか?0x80は、最上位ビットが設定されたオクテット(バイト)です。Javaでは、最上位ビットが設定されたバイトは負の値になります。したがって、ymm0の値は、他のymmレジスタのバイトが負の値であるかどうかを検出するマスクとして使用できます。

そして、まさにこれが次のループで行われています。

  • vmovdqu (%rsi,%rcx,1),%ymm1) :入力配列から 32 バイトをymm1レジスタにロード
  • vptest %ymm0,%ymm1ymm0のマスクと先ほど読み込んだ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ベンチマークを設定しました。readStringReaderreadStringDirectよりも数倍遅いことを十分に予想していました。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 のスケールが悪いことも明らかになりました。

readStringReader vs readStringDirect

入力サイズが4096から25000へと6.1倍になったとき、readStringDirectベンチマークのコストは6.5倍になりました。これは、私が予想していた通りの結果です。ほぼ線形で、さまざまなキャッシュしきい値を超えたときに生じる小さな超線形効果があります。しかし、readStringReaderでは、コストが10倍になっています。

プロファイリングデータを調べてみると、バイトを1つずつbyte[]からchar[]にコピーするUS_ASCII$Decoder.decodeArrayLoopreadStringReaderはほとんどの時間を費やしていることも明らかになりました。

    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

以前と同じグラフを最適化されたバージョンでプロットすると、まったく違うイメージになります。

readStringReader vs readStringDirect

InputStreamReaderの一定のオーバーヘッドを考慮すると、readStringReaderreadStringDirectを約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.decodeASCIIhasNegativesinflateを融合した 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);

癖はありますが、より高レベルで読みやすいです。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中