原文はこちら。
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のみのデータを使うCharsetDecoderとCharsetEncoderのパフォーマンスをテストするための素朴なマイクロベンチマークを見てみましょう。
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)の方がはるかに速いということに帰結します。後者の使い方では、CharBufferとByteBufferを再利用することで、実質的にアロケーションフリーになるためです。この理由についての私の最初の推測は的外れでしたが、会話の中で、核心的な問題を実証する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のなかに、charをbyteに「圧縮」するために使われるものがあります（実際には、各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
Logico Inside 