原文はこちら。
The original article was written by Claes Redestad (OpenJDK stuff, Oracle).
https://cl4es.github.io/2020/04/27/Zip-Lookups.html
ここ数週間はこの人のおかげで楽しく過ごせました。
TL;DR: we didn’t settle for 35% （35％で落ち着かなかった）
JAR内のエントリ・ルックアップは大きなJavaアプリケーションが起動時に実行するもののうちかなりの部分を占めています。Spring PetClinicサンプルアプリケーションではおそらく起動時間の10％がエントリ・ルックアップに使われています。ほとんどの場合クラスファイルです。
A sample Spring-based application
https://github.com/spring-projects/spring-petclinic
アプリケーションがクラスパスの多数のJARファイルで構成されている場合、何が起こるでしょうか。ルックアップのほとんどは失敗します。何百ものJARファイルで構成されている場合、一回のヒットで何百回ものヒットミスが発生することになるかもしれません。
そのため、失敗したルックアップのコストを気にするのは理にかなっています。
このエントリでは、最近の、とはいえそれほど最近ではありませんが、この領域における改善点を見ていきます。
Background
JARファイルは至るところにあります。JARファイルは基本的にZIPファイルの一種です。そのため、クラスファイルやリソースのロード時にZIPファイルからエントリをルックアップし読み取っています。
歴史的に、ZIPファイルのロジックはほとんどネイティブCで実装されました。一部ではrt.jarではなくランタイムイメージからJDK自身を起動するようになったこともあり、ネイティブのZIP実装はJDK 9でJavaに移植されました。
JEP 220: Modular Run-Time Images
https://openjdk.java.net/jeps/220
To bring j.u.z.ZipFile’s native implementation to Java to remove the expensive jni cost and mmap crash risk [2]
https://bugs.openjdk.java.net/browse/JDK-8146693
安定性の向上は、この取り組みの大きな原動力となりましたが、パフォーマンスの向上にもつながりました。
C is fast – but JNI can be slow
JavaはCより高速なのでしょうか。その答えはYesでありNoです。
先頃マイクロベンチマークを記述し、ZipFileのルックアップのパフォーマンスを調査しようとしました。説明を飛ばして、JDK 8とJDK 9の違いを説明するためにこのマイクロベンチマークを使ってみましょう。
| JDKバージョン | Hit (ns/op) | MISS |
|---|---|---|
| JDK 8 | 589 | 210 |
| JDK 9 | 185 | 165 |
このマイクロベンチマークでは、ZIPファイルもしくはJARファイル中のエントリのルックアップの時間を計測します。ネイティブライブラリからJava実装への移植により、ルックアップの性能がおよそ3倍に向上したようです（小さい値ほど性能が高い）。
なので、ネイティブコード自身は非常に高速であるものの、Javaとネイティブ間のJNIによる行き来によるオーバーヘッドが顕著であるようです。何度も何度もこれが繰り返されるとなれば、コストがすぐにのっかります。それぞれのミスは1回のJNI呼び出しだったのに対し、ヒットする場合にこのコストが顕著に現れていました。
Setting the stage
| JDKバージョン | Hit (ns/op) | MISS |
|---|---|---|
| JDK 8 | 589 | 210 |
| JDK 9 | 185 | 165 |
| JDK 11 | 125 | 109 |
時間の経過とともに、特にJDK 11に至るまでにいくつかの追加の改善がありました。JDK 8の場合に比べ、JDK 11では、ヒット時の所要時間はJDK 8のおよそ1/5、ヒットミス時の所要時間はおよそ半分です。また、JDK 11からJDK 14で10%ほどリグレションしたように見えますが、ZipFile自体にはほとんど変更がなかったので、その理由はよくわかりません。
The recent past
数週間前、Eirik BjørsnøsがOpenJDKのメーリングリストに投稿しました。最初のリリースでは、マルチリリースJARファイルのエントリをより速く検索できるように改良されています。
Improve JarFile.getEntry performance for multi-release jar files
https://bugs.openjdk.java.net/browse/JDK-8242596
Bloom filters?
彼の最初のパッチをプッシュするための変更の前に、前述のPetClinicでの改善を示すデータと一緒に、存在しないエントリを探すのに時間を費やすのを避けるためのブルームフィルタを使用したパッチが届きます。それはまだ月曜日だったかな。。
Improving ZipFile.getEntry performance using Bloom filters
https://mail.openjdk.java.net/pipermail/core-libs-dev/2020-April/065788.html
誰よりも良いブルームフィルタを楽しんでいますが、ブルームフィルタにフットプリントのオーバーヘッドが追加されるかもしれません。そして、ルックアップがヒットすることがわかっている場合、追加のテストが余分なコストになるでしょう。例えばuber JARを使うといった、ヒットミスを避けるためのいくつかの方法が広く展開されているので、ヒット性能を犠牲にしないよう、堅実にヒットミスの改善をするべきです。
Slash and fold
まずは、試した上でフットプリントとルックアップヒットのパフォーマンスに関して中立であろうとする最適化でどこまでできるかを確認することを提案しました。
冗長な配列コピーを避けることにより、これは数日のうちに実を結びました。その後、”name”と “name/”の連続したルックアップを折り返す最適化により改善しました。
Avoid reallocating name when checking for trailing slash in ZipFile.getEntryPos
https://bugs.openjdk.java.net/browse/JDK-8242842
Optimize ZipFile.getEntry by folding lookups for name and name+’/’
https://bugs.openjdk.java.net/browse/JDK-8242959
これに先立ち、Eirik からパッチが次々と送られてきました。それらを丹念にマージし、クリーンアップし、テストし、時には改良を加えました。
ヒットミス時の所要時間が35％減りました（124ns/op -> 81ns/op）。1.5倍速度が上がったともいえます。
Going for allocation-free misses
私は今、この最適化の長い物語の次のステップをまとめているところです。このパッチのほとんどを書いている間に、Eirikが多くの提案と実験をして支え、代替案をチェックしてくれました。
Lazily encode name in ZipFile.getEntryPos
https://bugs.openjdk.java.net/browse/JDK-8243469
エンコードされたバイト配列（byte[]）を積極的に割り当てないようにするために、似たようなことができるかもしれないと早い段階で気がつきました。いくつかのバリエーションを検討しましたが、現在レビューのために公開されているパッチに落ち着きました。
- String.hashCodeと一致するハッシュ値を計算
- すべての場所に仮想的に ‘/’ を追加して、”name”と”name/”の単一ルックアップを実行できるようにする
- ハッシュ値が完全に一致する場合のみ、ZIPファイルに格納されている値をデコードして比較
このマイクロベンチマークでヒット時の時間ならびにヒットミス時の時間の両方が低下しています。しかも大幅にです。ヒットミスの場合では所要時間はおよそ1/6とパフォーマンス向上を確認しています（124 ns/op -> 20 ns/op）。
これは些か誇張があります。ルックアップはString.hashCodeを使用するようになり、Stringsは独自のハッシュ値をキャッシュするようになったので、マイクロベンチマークはハッシュを計算するためのコストを表示しないからです。
ハッシュ値がキャッシュされないように常に新しい文字列を作成するバリエーションを追加しました。すると、相対的な違いは – その文字列を作成するためのコストを除くと、このテストでは約25ns/opです。もし常にハッシュ値を計算しなければならないと仮定した場合、ヒットミスの場合は~45ns/op、ヒットの場合は約109ns/opで、それでも両方のケースで大幅に改善しています。
しかし、私たちは複数の場所でエントリを検索している可能性が高く、時には何度も検索していることもあります。そのため、典型的なケースでは、平均的にはここで見る数字にかなり近いと考えるのが妥当です。
Digression: Instrumenting the gain
いくつかのPerfCountersを追加して、ルックアップのヒット時とヒットミス時の所要時間を測定するという彼のアプローチを試した際には、Eirikが報告していたような速度向上は確認できませんでした。
PerfCounterを追加する、というアプローチ
http://cr.openjdk.java.net/~redestad/scratch/perfcounters_zip.patch
この方法では、私の環境ではヒット時とヒットミス時の両方で~1.1μs/op余分に要することがわかりましたが、彼の環境ではオーバーヘッドが少ないように思われます。EirikがPetClinicで~35%の改善を確認したケースでは、私の環境では~15%程度の改善を確認しました。
こうした、PerfCountersでPetClinicのようなものを測定・計測する際に遭遇したもう一つの問題は、ヒットミスに対して行った最適化の一部が、ヒットのコストが逆行しているように見える、というものです。JDK-8243469用に作成したマイクロベンチマークでは、これらのリグレッションはどこにも見当たりませんでした。
この説明は、以前”ヒット”パスに共有されていた”ヒットミス”パスから離れて最適化した場合、ヒット時にはウォームアップされていないパスを取るように呼び出す可能性が高くなるというものです。つまり、ヒット時には以前と比べてインタプリタでの時間が長くなるため、作業量はほぼ同じか、もう少し少なくても、コストが高く見えます。
Conclusion
JDK 9でのJavaへのZIP実装の移行により、一連の最適化を開始、継続してきました。getEntryの速度を見てみると、JDK 15ではJDK 8と比較して、ヒット時の速度は7倍、ヒットミス時の速度は12倍に向上しています。
Spring PetClinicアプリケーションの場合、これらの改善により起動時間が数百ミリ秒改善しました。誰かがそれを評価してくれることを願っています。
協力してくれた Eirik Bjørsnøs に感謝します。そして、パッチのレビューを手伝ってくれた Lance Andersen、Volker Simonis、その他の人たちにも感謝します。
数年前に作成した以下のRFEも修正する価値があるかもしれないですね…。
Use of Function in JarFile hides capturing of the Jar-/ZipFile
https://bugs.openjdk.java.net/browse/JDK-8193066
Logico Inside 
Who are you?
web-readiness.slack.com
________________________________
いいねいいね