Faster Charset Encoding

原文はこちら。
The original article was written by Claes Redestad (Principal Member of Technical Staff, Oracle).
https://cl4es.github.io/2021/10/17/Faster-Charset-Encoding.html

TL;DR:

JDK 17でCharsetDecoderは数倍速くなりましたが、CharsetEncoderは取り残されました。いくつかの失敗とコミュニティからの助けを得て、CharsetEncoderを同様に高速化するトリックが見つかりました。これにより、将来的にあなたのアプリがスピードアップするかもしれませんし、しないかもしれません。

これは技術的な読み物であると同時に、失敗して再挑戦する過程の物語でもあります。グラフはなく、ソースコードへの気が散るようなリンクがたくさんあります。すみません。でもいいことがありますよ。

Decoding / Encoding

以前、JDK 17での文字セットのデコードの改善についてブログを書きましたが、そこではJEP 254を最適化するために元々追加されたintrinsicsをいくつかの場所で使用し、局所的に10倍以上のスピードアップを実現しました。

Faster Charset Decoding
https://cl4es.github.io/2021/02/23/Faster-Charset-Decoding.html
JEP 254: Compact Strings
https://openjdk.java.net/jeps/254

しかし、テキストの扱いには双方向性があります。あるテキストデータをcharに変換するとき、Java APIは内部表現(JEP 254以降はISO-8859-1またはUTF-16の変形)にデコードします。外部と通信する際には、これらの文字を内部表現から外部で期待されるcharにエンコードする必要があります。

JDK 17では、文字のエンコードはほとんど変更されませんでしたが、これは既存のintrinsicsを(デコードの場合と)同様に高速化するための簡単な方法がなかったためです。既存のintrinsicsはISO-8859-1に対してのみ動作します。

これまでISO 8859-1を使って育ってきました。このエンコーディングは、すべてのサポート対象文字でシングルバイトを使い、絵文字を持たないすべてのサポート対象の文字をエンコードするような優れた特性を持つレガシーなエンコーディングです。また、latin-1のようなかわいいニックネームもあります。しかし、最近では世界中の多くの人々が別のものを使用しています。UTF-8を使うのが妥当でしょう。

ISO/IEC_8859-1
https://en.wikipedia.org/wiki/ISO/IEC_8859-1
https://ja.wikipedia.org/wiki/ISO/IEC_8859-1

Performance check: JDK 17

CharsetEncodeDecodeという、ASCIIのみのデータを使うCharsetDecoderCharsetEncoderのパフォーマンスをテストするための素朴なマイクロベンチマークを見てみましょう。

CharsetEncodeDecode.java
https://github.com/openjdk/jdk17u/blob/master/test/micro/org/openjdk/bench/java/nio/CharsetEncodeDecode.java

テスト対象のエンコーディングを選ぶことができるので、最も一般的なものを選んでみましょう。W3Techs.comによると、これらは公共のウェブサイトで使用されているトップ10です(x86ワークステーションでOracle OpenJDK 17を使って実行しました)。

Usage statistics of character encodings for websites
https://w3techs.com/technologies/overview/character_encoding
JDK 17.0.1 General-Availability Release
http://jdk.java.net/17/

CharsetEncodeDecode.encode:
      (type)  Mode  Cnt   Score   Error  Units
       UTF-8  avgt   30  12.019 ± 0.430  us/op
  ISO-8859-1  avgt   30   2.983 ± 0.197  us/op
Windows-1251  avgt   30  41.315 ± 0.715  us/op
Windows-1252  avgt   30  41.845 ± 1.406  us/op
      GB2312  avgt   30  45.914 ± 1.043  us/op
   Shift-JIS  avgt   30  46.328 ± 1.617  us/op
  ISO-8859-9  avgt   30  41.519 ± 0.776  us/op
Windows-1254  avgt   30  41.589 ± 0.911  us/op
      EUC-JP  avgt   30  64.199 ± 3.368  us/op
      EUC-KR  avgt   30  46.412 ± 1.367  us/op

このASCIIを中心としたテストでは、ISO-8859-1へのエンコーディングが他のどのエンコーディングよりも速くなっています。UTF-8に比べて4倍、他のどのエンコーディングと比べても10倍以上速くなっています。これは、JDK 8ですでに実装されていたimplEncodeISOArrayメソッドが組み込まれたおかげです。

[JDK-6896617] Optimize sun.nio.cs.ISO_8859_1$Encode.encodeArrayLoop() with SSE instructions on x86
https://bugs.openjdk.java.net/browse/JDK-6896617

UTF-8エンコーダーには便利なASCII fast-pathがあり、他のエンコーディングに比べてUTF-8でのエンコーディング速度の低下が著しく小さい理由を説明しています。

            // ASCII only loop
            while (dp < dlASCII && sa[sp] < '\u0080')
                da[dp++] = (byte) sa[sp++];

ASCIIと互換性のあるすべての文字セットは、同様にすることで利益を得られる可能性がありますが、意外なことにほとんどの文字セットにはそのようなファストパスがありません。

それはともかく、ASCIIと互換性のある(ASCIIをエンコードするときに1バイトのストリームを生成する)エンコードは、基本的にこのベンチマークで同じことをしていますが、結果は大きく異なっています。その違いとは、ISO-8859-1とISO-8859-1だけを高速化するISO-8859-1 intrinsicです。これはあまりいいことではありませんが、JDK 8以降はそういうことになっています。

Dropping the ball

charsetデコーダを最適化した後は、誇らしい気持ちになりました。私はOpenJDKのパフォーマンス・エンジニアとして働いてきましたが、10倍の最適化を実現できることは非常に稀であり、ましてや多くのアプリケーションで中心的な役割を果たすものではありません。HotSpot JVMはあらゆる面で優れたパフォーマンスを発揮しているため、わずか数パーセントのパフォーマンス向上のためには、多大なエンジニアリングの努力が必要です。

しかし、同じような方法でエンコードを高速化する方法は見当たりませんでした。何か方法があるはずだとは思っていましたが、デコーダを最適化する際には、基本的にJDK内部のJava APIにすでに存在していたintrinsicsを再利用しました。また、エンコーディングのためのintrinsicsは、基本的に前述のimplEncodeISOArrayのみで、ISO-8859-1以外には直接適用できませんでした。

本当の意味でのリグレッションが見えない中、他のことが優先されました。また、私はしばらく育児休暇を取り、楽しい夏休みを過ごしました。

Nudged back into the game

見直すきっかけは、意外なところからやってくるものです。Twitterもそのひとつです。

(もしかしたら、誰かが私のブログを読んでいたのかもしれません)。また、他の人からも、私が彼らの悩みを解決する方法を見つけたかどうかを聞きたがっているような、いくつかのpingをもらいました (やあ、@yazicivoさん!)。

この問題は、CharsetEncoderを使うよりもString.getBytes(UTF8)の方がはるかに速いということに帰結します。後者の使い方では、CharBufferByteBufferを再利用することで、実質的にアロケーションフリーになるためです。この理由についての私の最初の推測は的外れでしたが、会話の中で、核心的な問題を実証するJMHテストケースが生まれました。

Benchmark OutputStreamWriter against OutputStream
https://github.com/carterkozak/stringbuilder-encoding-performance/pull/4

報告されたパフォーマンスの問題は、JDK 9で特定のStringメソッドが大幅に改善されたことに起因する、JDK 8とそれ以降のJDKとの間の不一致がほとんどでした。しかし、これらのマイクロベンチマークのいくつかでは、JDK 8に比べて5~10%程度の後退があったようです。

きれいに書かれた、よく定義されたマイクロベンチマークです。そして、いくつかのバリエーションで顕著なリグレッションが発生しました。JDK 9の最高のパフォーマンス機能の一つが原因ですか?よし、やってみましょう。

Reluctantly crouched at the starting line

Compact StringsのString.getBytesは、UTF-8やISO-8859-1などのいくつかの組み込み文字セットにエンコードするための特別な実装を持っていますが、これらが性能で上回るのは難しい可能性があります。すべてのStringは内部的にISO-8859-1バイナリ・フォーマットで表現される可能性があるためです。このようなStringからのISO-8859-1へのエンコードは、単純にArrays.copyOfを使用します。UTF-8へのエンコーディングは、StringすべてASCIIであれば、配列のコピーになります。

        if (!StringCoding.hasNegatives(val, 0, val.length))
            return Arrays.copyOf(val, val.length);

配列の割り当てとコピーがかなり速いという場合は、私の言葉を信じてもらう必要があります。StringCoding.hasNegativesはHotSpotの組み込みメソッドで、手作業で最適化されたベクトル命令を使用して、Stringのバイト配列内の負のバイトをチェックします。負のバイトがなければ、それはすべてASCIIであることを意味し、高速なコピーが可能です。

StringEncodeのJDKマイクロベンチマーク(String.getBytesをターゲットにしたもの)を見ると、これはJDK 8に比べてかなりスピードアップすることがわかります。

StringEncode.java
https://github.com/openjdk/jdk17u/blob/master/test/micro/org/openjdk/bench/java/lang/StringEncode.java

StringEncode.WithCharset.encodeCharset:
JDK (charsetName)  Mode  Cnt    Score   Error  Units 
  8         UTF-8  avgt   15  128.070 ± 5.013  ns/op
 17         UTF-8  avgt   15   68.964 ± 5.236  ns/op

これらの最適化は、CharsetEncoderで使用されるコードにはありません。数ヶ月前の状態に戻ってしまいました。最適化しようとしたユースケースとは完全に相容れないと思われる、ある場所で使われている最適化された一連の組み込みメソッドを見つめていました。残念ながら…もしかしたら、途中まで行く方法があるかもしれません。

He’s going the distance

以前に調べたintrinsicsのなかに、charbyteに「圧縮」するために使われるものがあります(実際には、各charの上位バイトを捨てているので、上位バイトがすべてゼロであることを確認していない限り、多大な損失が発生します)。これが、UTF-8エンコーダーでこの問題を解決しようとする最初の試みにつながりました。

8274242: Implement fast-path for ASCII-compatible CharsetEncoders on x86 #5621
https://github.com/openjdk/jdk/pull/5621/commits/4da3d71efadff9d2f3db235c5e838c6af0a66a7e

            while (lastAscii < slASCII && sa[lastAscii] < '\u0080') {
                lastAscii++;
            }
            if (lastAscii > sp) {
                int len = lastAscii - sp;
                JLA.compressCharsToBytes(sa, sp, da, dp, len);
                sp = lastAscii;
                dp += len;
            }

つまり、入力されたcharをスキャンし 非ASCII文字が出てきたら、StringUTF16.compressメソッド(ここでJavaLangAccess.compressCharsToBytesとして公開したものです)を使って圧縮し、コピーします。

非ASCII文字のスキャンが明示的にStringCoding.hasNegativesに類似したものを使ってベクトル化されなかったにも関わらず、この微調整はかなりのスピードアップになりました。Carter Kozakのマイクロベンチマークでは1.45倍、CharsetEncodeDecode.encodeでは1.65倍近くになりました。

      (type)  Mode  Cnt  Score   Error  Units
       UTF-8  avgt   30  7.134 ± 0.336  us/op

いいですね。でも完全に組み込まれたISO-8859-1のエンコーディングは依然として遙かに高速でした。

He’s going for speed

そこで、ISO-8859-1の組込み関数が実際に何をしているのか、じっくりと調べてみました。そして、ようやく気がついたのです。今になってみれば当たり前のことなんですが。

x86では、implEncodeISOArrayは、0xFF00を8回、16回、32回繰り返すビットマスクを設定することにより実装されています(ハードウェアの性能に依存します)。そのビットマスクをcharのチャンクと論理和をとったときにビットが検出されない限り、それらのcharはすべてISO-8859-1でエンコードされていることを意味します。

フィルターを通過したすべてのチャンクは、AVXのマジックによって、すべてのバイトが宛先にコピーされます(vpackuswb + vpermq = …)。ありがたいことに、その部分は気にする必要はありません。私たちのニーズに合わせて異なる必要があるのは、これらのビットマスクだけです。そしてそれは簡単に見つけることができました。

ここで必要なのは、まったく同じことですが、非ASCIIのchar (0xFF80) を検出するような(繰り返しの)ビットマスクです。

C2コードのさまざまな場所からコードをコピー&ペーストするのに数時間かかりましたが、最終的にはすべてが適切に接着され、_encodeAsciiArrayという非常に派生的な新しいintrinsicを作成することができました。この最初のバージョンは、ハックや冗長なscaffloldingも含めて、Pull Requestのchangelogにすべて記載されています。

8274242: Implement fast-path for ASCII-compatible CharsetEncoders on x86 #5621
https://github.com/openjdk/jdk/pull/5621/commits/cef05f44fd482646c5df496a50bdf78527d908cb

しかしながらうまくいきました!

実装をきれいにして(Tobias Hartmannからの必要な情報に感謝します!)、ほとんどのASCII互換の文字セットが同じように処理されるようにした後は、数字が素晴らしすぎますね。

CharsetEncodeDecode.encode:
        (type)  Mode  Cnt   Score   Error  Units
         UTF-8  avgt   30   3.246 ± 0.192  us/op
    ISO-8859-1  avgt   30   3.028 ± 0.202  us/op
  Windows-1251  avgt   30   2.922 ± 0.092  us/op
  Windows-1252  avgt   30   2.880 ± 0.196  us/op
        GB2312  avgt   30  46.004 ± 0.903  us/op
     Shift-JIS  avgt   30  46.130 ± 1.142  us/op
    ISO-8859-9  avgt   30   3.112 ± 0.304  us/op
  Windows-1254  avgt   30   3.016 ± 0.235  us/op
        EUC-JP  avgt   30  64.867 ± 3.100  us/op
        EUC-KR  avgt   30  47.918 ± 1.847  us/op

UTF-8 では 4 倍高速です。レガシーエンコーディングは15倍になっているものもあります。私が期待していた結果ではありませんが、非常に素晴らしいです。

Combined effect

マイクロベンチマークは素晴らしいツールですが、実際のアプリケーションがどのように動作するかを予測する力は驚くほど弱いものです。特定のテストで大きなスピードアップがあっても、それがたまたまボトルネックになっていなければ、実際にはほとんど意味がないかもしれません。それはありえないことです。あるアプリケーションでは、JDK 17のデコーダーの最適化によってCPU時間が大幅に短縮されましたが、スループットは改善されませんでした。StringのエンコードとデコードはI/Oの際によく行われますが、ボトルネックはおそらくネットワークかディスクでしょうから、それほど驚くことではありません。通常のマイクロベンチマークでは触れないようなものです。

単純に現実世界を少しでもエミュレートしようと、EncodeDecodeLoopを用意しました。これはASCIIデータのチャンクを生成し、それをエンコードしてファイルに書き込み、読み返してからデコードするというシンプルなプログラムです。以下の数値はWindows-1251で、1つのファイルを使って、10万回繰り返したときのものです。

          Real time   User time
JDK 11      31.149s      9.511s
JDK 17      27.526s      6.850s
JDK 18      21.586s      1.820s

想定通りuser timeが大幅に小さくなっているだけでなく、real timeの結果も高速になっています。ベンチマークがディスクI/Oでボトルネックになるという最悪の事態にもかかわらずです。本質的には、これもまたマイクロベンチマークのひとつなのですが、これらの最適化を組み合わせることで、一部のアプリケーションではノイズを無視して見ることができるほど強力になるかもしれないことを示唆しています。たとえ目に見えるスピードアップがなくても、同じ作業をより少ないCPUサイクルで行うことができれば、それに越したことはありません。

Future Work

この最適化をx86でしか実行していません。どのプラットフォームでもアセンブラコード(アセンブリ?)を読むのが苦手で、ましてや書くのは苦手です。x86のルーチンを修正する簡単な方法を見つけたときは、本当にラッキーでした。Aarch64 での修正のためにフォローアップバグ作成し、このバグを、何をしているかを知っている人々が現在見てらっしゃいます。

また、TOP10リストにあるいくつかのエンコーディングを見てみましたが、少なくともいくつかのエンコーディングは実際にASCII互換で、実装が異なるだけだということがわかりました。私はEUC-JPエンコーディングにパッチを当てていますが、他のいくつかのエンコーディングにも目を向けています。

そして最後に、この作業はインパクトがあり、安全でJDK 17uにバックポートするのに議論の余地のないものであるべきだと思います。最終的には、ベースラインの中のベースラインであるJDK 8から大きく改善され、いくつかのリグレッションも解消されました。

Edit 2021-10-15: DoubleByte encodings

上記で高速化が見られなかったエンコーディングのほとんどはDoubleByteを実装しており、ASCII互換と表示されている(つまり、ASCIIを実際にはシングルバイトでエンコードしている)ことがわかっています。したがって、これらのエンコーディングを高速化するのは、思ったよりも簡単でした。皮肉なことに、私が最初に見た EUC-JP は例外で、特別な注意が必要でした。私は Pull Request (#6102) を作成し、トップ 10 のすべてのエンコーディングは ISO-8859-1 の数分の一にまで改善しました。

8275863: Use encodeASCII for ASCII-compatible DoubleByte encodings #6102
https://github.com/openjdk/jdk/pull/6102

Benchmark                   (size)      (type)  Mode  Cnt  Score   Error  Units
CharsetEncodeDecode.encode   16384  ISO-8859-1  avgt   30  2.856 ± 0.078  us/op
CharsetEncodeDecode.encode   16384   Shift-JIS  avgt   30  5.287 ± 0.209  us/op
CharsetEncodeDecode.encode   16384      GB2312  avgt   30  5.490 ± 0.251  us/op
CharsetEncodeDecode.encode   16384      EUC-JP  avgt   30  7.657 ± 0.368  us/op
CharsetEncodeDecode.encode   16384      EUC-KR  avgt   30  5.718 ± 0.267  us/op

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

%s と連携中