原文はこちら。
The original article was written by Claes Redestad (Principal Member of Technical Staff, Oracle)
https://cl4es.github.io/2021/01/04/Investigating-MD5-Overheads.html
Background
数週間前に、MessageDigest.getInstance("MD5")からの戻り値を静的フィールドにキャッシュすることで、java.util.UUID::nameUUIDFromBytesの高速化を意図したPRを受け取りました。
8258588: MD5 MessageDigest in java.util.UUID should be cached #1821
https://github.com/openjdk/jdk/pull/1821
一見すると、このPRはちょっとした改善点のように思えます。しかし、それはMessageDigestオブジェクトがステートフルであることに気づく前のことで、何らかの同期メカニズムがなければ、静的に共有することはできません。
このPRの正確性を修正するために、ThreadLocalを利用するようにPRを更新しましたが、これにはそれなりの問題があります。
- Every thread that has ever called
UUID::nameUUIDFromBytesを呼び出したことのある全てのスレッドはMD5MessageDigestオブジェクトのインスタンスを無期限に保持する（これはThreadLocalに格納されているオブジェクトをSoftReferenceにラップすることで部分的に解決する可能性がありますが、複雑さと速度を犠牲が犠牲になっています）。 ThreadLocalは、利用される仮想スレッド（virtual thread）の個数がより高い割合で増加することが予想されるため、Project Loomとの相性が悪い可能性がある。この理由から、予防措置としてOpenJDKチームはいくつかの怪しげなThreadLocalの最適化を慎重に削除している。
Project Loom
https://openjdk.java.net/projects/loom/
しかし、PRをこき下ろしたり、完全に拒否したりするのは楽しいことではありません。そして、ここには間違いなく改善の余地があるように思えます。この記事では、プロファイリングとプロトタイピングの作業の一部を探って、別の最適化を検討してみたいと思います。もしかしたら、もっと良い提案が生まれるかもしれません。
現在のベストな改善点の組み合わせでPRを起草しましたが、最初から書いていきましょう。
8259498: Reduce overhead of MD5 and SHA digests #1855
https://github.com/openjdk/jdk/pull/1855
に書いてみましたが最高のパフォーマンスを発揮する改善点の組み合わせでPRを起草しましたが、最初から始めてみましょう。
It’s 2021 – why bother with MD5?
MD5は暗号のハッシュ関数で、ここで見ているUUIDメソッドの他にもいろいろなものに使われています。
The MD5 Message-Digest Algorithm
https://tools.ietf.org/html/rfc1321
暗号の専門家ではありませんが、MD5が暗号的に壊れていて衝突攻撃の影響を受けやすいと考えられていることは知っています。そのため、セキュリティ上重要なことにはMD5ハッシュに頼るのは決して良い考えではありませんが、非常に高速なハッシュであり、整合性チェックのための人気のある選択肢であることに変わりはありません。
たまたまですが、OpenJDKのMD5の実装は、アルゴリズムの大部分を内部化することで最近最適化されました。
[JDK/JDK-8250902] Implement MD5 Intrinsics on x86
https://bugs.openjdk.java.net/browse/JDK-8250902
最初はx86のみですが、他のアーキテクチャへの実装も予定されているようです。内部化とは、コンパイル中にJVMがいくつかのJavaコードを手作業で最適化されたバージョンに置き換えるという、楽しいが複雑な（そして時には驚くような）テクニックです。
HotSpot Intrinsics
https://alidg.me/blog/2020/12/10/hotspot-intrinsics
この最近の最適化はJDK 16で追加される予定で、MD5ダイジェストを行う際のパフォーマンスを15～20%向上させると言われています。
Basic performance analysis
何かを最適化しようとする前に、まず、最適化しようとしているもののパフォーマンスを理解しようとすることが重要です。MessageDigest.getInstance("MD5")に直接ズームインすることもできますし、元のPRが最適化しようとしていたパブリックAPIメソッドではなく、java.util.UUID.nameUUIDFromBytesを使用することもできます。どこから検討を開始すべきかという問いに正しい答えはありませんが、現実世界のユースケースから抽出したやや高レベルのAPIから詳細を掘り下げていくと、正しい方向に向かうことが多々あります。
Pick (or create) a microbenchmark
java.util.UUIDの以下のメソッドを考えてみましょう。
public static UUID nameUUIDFromBytes(byte[] name) {
MessageDigest md;
try {
md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException nsae) {
throw new InternalError("MD5 not supported", nsae);
}
byte[] md5Bytes = md.digest(name);
md5Bytes[6] &= 0x0f; /* clear version */
md5Bytes[6] |= 0x30; /* set to version 3 */
md5Bytes[8] &= 0x3f; /* clear variant */
md5Bytes[8] |= 0x80; /* set to IETF variant */
return new UUID(md5Bytes);
}
これは確かにMessageDigest.getInstanceとdigestのオーバーヘッドを調べるためだけでなく、これらのオーバーヘッドがUUIDオブジェクト自体の作成に対してどのように積み重なっているかを見るための入り口のように思えます。これは、各パーツがどれだけ貢献しているかを知るための良い出発点だと思いました。
偶然にもUUID関連のマイクロベンチマークはOpenJDKのソースにあるので、これを拡張しない手はありません。シンプルにしましょう。
8259498: Reduce overhead of MD5 and SHA digests #1855 – test/micro/org/openjdk/bench/java/util/UUIDBench.java
https://github.com/openjdk/jdk/pull/1855/files#diff-fcb56f7dd0c6f7fc1bdc199e3b41d492eba49b20fe198d898b97ca23024a9e9dR82
ランダムなバイト列をセットアップ時に作成し、パブリックメソッドを呼び出しましょう。
@Benchmark
public UUID fromType3Bytes() {
return UUID.nameUUIDFromBytes(uuidBytes[index]);
}
ビルドおよびJMHの実行用にOpenJDKをセットアップ後、以下のコマンドを実行してマイクロベンチマークを実行します。
Using “make test” (the run-test framework) : Configuration
https://github.com/openjdk/jdk/blob/master/doc/testing.md#configuration
$ make test TEST=micro:UUIDBench.fromType3Bytes
...
Benchmark Score Error Units
fromType3Bytes 1.460 ± 0.089 ops/us
Run some quick diagnostics
catch-all MICRO=OPTIONS="… "を含む、典型的なJMHパラメータの多くはmakeベースのランナーで制御可能ですが、make build-microbenchmarkでmicrobenchmarksバンドルをビルドし、java -jar build//images/test/micro/benchmarks.jarで直接実行もできます。
Microbenchmark keywords
https://github.com/openjdk/jdk/blob/master/doc/testing.md#microbenchmark-keywords
JMH GC プロファイラ（-prof gc）を付けて実行し、これをクイックチェックとして利用しています。これにより、各呼出しでどれぐらい割り当てがなされているかの概要を把握できます。
Benchmark Score Error Units
·gc.alloc.rate.norm 488.042 ± 0.005 B/op
呼出しごとに488 バイト…無害なものにしてはかなりの量ですね。
Pick your profiler
JMH version 1.24から、async-profilerをサポートするようになりました（別途インストールする必要があります）。
async-profiler
https://github.com/jvm-profiling-tools/async-profiler
これは非常に強力なプロファイラで、JMHとのうまく連携します。CPUフレームグラフを生成する機能は使いやすくて良いです。
make test TEST=micro:UUIDB.from MICRO=OPTIONS="-prof async:output=flamegraph"
# generates flame-cpu-forward|reverse.svg in a folder named after the micro
アロケーション・プロファイラー/サンプラーもありまして、この解析で試してみようと思います。初めてのもので遊んでみたいというのは、これ以上の理由はありません。
$ make test TEST=micro:UUIDB.from MICRO=OPTIONS="-prof async:event=alloc"
...
--- 1291138320 bytes (24.90%), 923 samples
[ 0] int[]
[ 1] sun.security.provider.MD5.<init>
[ 2] jdk.internal.reflect.GeneratedConstructorAccessor1.newInstance
--- 1287651328 bytes (24.83%), 921 samples
[ 0] byte[]
[ 1] sun.security.provider.DigestBase.<init>
[ 2] sun.security.provider.MD5.<init>
[ 3] jdk.internal.reflect.GeneratedConstructorAccessor1.newInstance
--- 645300224 bytes (12.44%), 310 samples
[ 0] byte[]
[ 1] sun.security.provider.DigestBase.engineDigest
[ 2] java.security.MessageDigest$Delegate.engineDigest
--- 640256000 bytes (12.35%), 610 samples
[ 0] java.util.UUID
[ 1] java.util.UUID.nameUUIDFromBytes
[ 2] org.openjdk.bench.java.util.UUIDBench.fromType3Bytes
--- 640251904 bytes (12.35%), 609 samples
[ 0] java.lang.ref.WeakReference
[ 1] java.lang.reflect.AccessibleObject.slowVerifyAccess
[ 2] java.lang.reflect.AccessibleObject.verifyAccess
[ 4] java.lang.reflect.Constructor.newInstanceWithCaller
[ 5] java.lang.reflect.Constructor.newInstance
[ 6] java.security.Provider.newInstanceUtil
--- 639006720 bytes (12.32%), 305 samples
[ 0] java.lang.Object[]
[ 1] java.security.Provider.newInstanceUtil
[ 2] java.security.Provider$Service.newInstance
出力の一部をトリミングしてみました。挙げられている出力が、最もホットなアロケーションサイトのスタックトレースを逆にしたものばかりであることに気づくのに時間がかかりました。そして、現在のJMHの統合はallocイベントからのフレームグラフの生成をサポートしていないようで残念ですが、懸念されるいくつかの潜在的な領域をすぐに指摘してくれたので、これはまだとてもクールです…
最初の2個のスタックトレースはsun.security.provider.MD5インスタンスのインスタンス化に関連しており、割り当ての約半分を占めています。改良点を探すのに適した場所だと思われます。
次は、MD5でダイジェストを呼び出した時に割り当てられたバイト配列byte[]です。これはおそらくUUIDに返されるものです。UUIDコードはbyteの値を2つのlongの値に展開します。ダイジェストされたバイト値にビューを返すことで、これを回避することができるようにも思えますが、それは怪しげな利益のために難しいことをやることになるかもしれません。
次は、UUIDのアロケーションそのものです。おそらくはこれについて我々ができることはあまりないでしょう。
次の2個は興味深いものです。両方ともjava.security.Provider::newInstanceUtilに由来します。slowVerifyAccessと呼ばれるメソッドにおけるWeakReferencesの割り当てが怪しいように思われます。また、Provider.newInstanceUtilで割り当てられているObject[]は空の可変長引数配列のように思われますが、それについてはまた今度…。
MD5 – room for improvement?
MD5の実装コードが最近内部化されたと書きました。メソッドが内部化されたとき、見えるものが取得できるものとは限りません。この場合、現在のコードの状態を調べたときに驚きました。割り当てプロファイルにある大きなデータ構造の一つは、内部化されたコードでは全く使用されていません。それでも、それは常に割り当てられ、満たされ、クリアされています。
// temporary buffer, used by implCompress()
private int[] x; // will be cleared after a call to digest(byte[])
void implCompress(byte[] buf, int ofs) {
implCompressCheck(buf, ofs);
implCompress0(buf, ofs);
}
private void implCompressCheck(byte[] buf, int ofs) {
Objects.requireNonNull(buf);
// The checks performed by the method 'b2iBig64'
// are sufficient for the case when the method
// 'implCompressImpl' is replaced with a compiler
// intrinsic.
b2iLittle64(buf, ofs, x); // fills up x
}
// The method 'implCompress0 seems not to use its parameters.
// The method can, however, be replaced with a compiler intrinsic
// that operates directly on the array 'buf' (starting from
// offset 'ofs') and not on array 'x', therefore 'buf' and 'ofs'
// must be passed as parameter to the method.
@IntrinsicCandidate
void implCompress0(byte[] buf, int ofs) {
// regular java code uses x, but the intrinsic doesn't
}
また、名前からして単にいくつかのチェックを行うだけのimplCompressCheckメソッドが、一時バッファxに値を読み込むことに副作用があるというのも少し間違っているように思えます。
そこで、チェックのみを行うようにimplCompressCheckをリファクタリングし、一時的なバッファを取り除き、バッファからの値の読み込みをimplCompress0に移動し、冗長な2回の読み取りを避けるようにしました。これは、UUIDマイクロベンチマークにおいて有益であることがわかりました。
8259498: Reduce overhead of MD5 and SHA digests #1855 – src/java.base/share/classes/sun/security/provider/MD5.java
https://github.com/openjdk/jdk/pull/1855/files#diff-30a4459e7a46b540d576d9d00fdda9babfdcb177c90e0f39881e5197c658d3a9
Benchmark Score Error Units
fromType3Bytes 1.523 ± 0.066 ops/us
fromType3Bytes:·gc.norm 408.036 ± 0.003 B/op
488B/opのベースラインに対して80B/op削減され、わずかながらスループットが向上しました。digestメソッドにズームインすると、別のマイクロベンチマークでその改善はかなり顕著であることがわかります。
Benchmark Score Error Units
MessageDigests.digest 2719.049 ± 30.538 ops/ms
MessageDigests.digest 3241.352 ± 67.353 ops/ms
(digesterName: md5, length: 16, provider: DEFAULT)
この最適化の効果は、より大きな入力では減少します。数Kb以上のダイジェストではノイズの中に消えてしまいます。これは implCompressCheckで行われている作業（入力長に応じてスケーリングする）が JIT によってうまくデッドコード削除（Dead code elimination）されていることを示唆していますが、xバッファの無意味な割り当てとクリアは排除できません。
デッドコード削除（Dead code elimination）
https://ja.wikipedia.org/wiki/デッドコード削除
https://en.wikipedia.org/wiki/Dead_code_elimination
Handling conversion from bytes to ints
さきほどの実験のソースコードを見ていると、VarHandleを使ってbyte[]からintの値を読み取る方法に気づかれた方もいらっしゃるかもしれません。これは基本的には sun.security.provider.ByteArrayAccess で既存コードが行っていることと同じですが、その中ではもう少し儀式的なものとUnsafeを使用しています。VarHandleはJDK 9で追加されました。VarHandleにはいくつかのクセがありますが、これを使用することで、私がここで「インライン化」しているByteArrayAccess::b2iLittle64メソッドのトリッキーなロジックとUnsafeの使用法のいくつかをうまくカプセル化できると思います。
ByteArrayAccess::b2iLittle64
https://github.com/openjdk/jdk/blob/05a764f4ffb8030d6b768f2d362c388e5aabd92d/src/java.base/share/classes/sun/security/provider/ByteArrayAccess.java#L130
本質的に無効化されたこのコードで実験を実行すると、このクイックで美しくないVarHandleの実装が、私のハードウェア上で Unsafeと全く同じように実行されることがわかります。インタプリタで実行しているときに少しオーバーヘッド（〜30％）があります。このオーバーヘッドは、long値ではなく、int値を抽出することで、ほぼ半減し、より高い最適化レベルでも効果が落ちることはありませんでした。しかし、何らかの方法で起動時の影響を受けやすいコードを最適化していないのであれば、インタープリタ用に最適化することは、一般的には手間をかける価値がありません。そして、もしそうなら、そのVarHandle実装自体を改善する方法を考えるべきかもしれません。
とにかく、もし私がこの実験に基づいてパッチを完成させて提案するのであれば、まず最初にコードをできるだけ単純化して、より多くのハードウェアでより徹底的なテストを行いたいと思います。よりモダンでUnsafeでないAPIを使って改造しても良いのですが、リスクを伴います。ByteBuffersやインキュベーション中のForeign Access APIなどの他のテクノロジーを使って、このbyteからintへの変換を実装して比較してみたり、sun.security.provider.ByteArrayAccessのレガシー実装のコードへの対処法での変更を統合したりするのも面白いでしょう。
Accidental constraints
MD5.implCompress0の内部化の不幸な副作用として、MD5のint[]の状態配列に依存したHotSpotの内部化があります。これは、この配列を4つのintにフラット化するようなことを試すためには、それらが実装されているすべてのプラットフォームで、いくつかの厄介な内部コードを書き換えなければならないことを意味します。この配列を平坦化しても大きな違いがあるかどうかはわかりません（割り当てが少しだけ減り、クローン作成がより速くなります）が 、これが些細なことではなくなってしまったのは少し腹立たしいです。
Reflection overheads
一歩下がって、Provider::newInstanceUtilで見られた様々な割り当てにズームインしてみましょう。全体の12%（!?）の割合でObject[]を割り当てていたコードの中には、以下のようなものがあります。
Constructor<?> con = clazz.getConstructor();
return con.newInstance();
セキュリティと整合性の理由から、clazz.getConstructor()は呼び出すたびに新しいConstructorを写し取り、ConstructorのnewInstanceの最初の呼び出しでは、呼び出すたびに高価なアクセスチェックが行われます。
両メソッドとも可変長引数メソッドです。可変長メソッドを引数を付けずに呼び出すのは、javacが空のObject[]を生成し、それをメソッドに渡す、という意味です。これは、これを最適化することが「意味がある」ということかもしれません。
private static final Class<?>[] EMPTY_CLZ = new Class<?>[0];
private static final Object[] EMPTY_OBJ = new Class<?>[0];
Constructor<?> con = clazz.getConstructor(EMPTY_CLZ);
return con.newInstance(EMPTY_OBJ);
HotSpotのJITコンパイラではこのような割り当てを最適化により除去することがよくあります。しかしこの場合は少々改善が見られました。
Benchmark Score Error Units
fromType3Bytes 1.575 ± 0.497 ops/us
·gc.alloc.rate.norm 472.040 ± 0.029 B/op
1回の呼出しあたり16バイト程度です。または全体の約3.2%です。このメソッドに対してアロケーションプロファイリングが推定した12%ではありません。
デフォルト設定の64ビットJVMで実験しているので、これは最小サイズのオブジェクトの割り当てが1つ少ないことに等しくなります。例えば、空の配列のようなものです。実際のアプリケーションでは、このような微細な最適化はほぼ時間の無駄になりそうですが、様々な方法で種々のパブリックAPIが利用する可能性のある内部JDKコードでは、考慮すべき合理的なことかもしれません。そうは言っても、道に迷ってしまったのかもしれません…。
コスト配分の面でより大きなコストがかかるのは、呼び出すたびにclazzからConstructorをコピーしていることでしょう。また、デフォルトのコンストラクタを呼び出す際には、コンストラクタをキャッシュする（非推奨の）省略版があります（clazz.newInstance()）。
Benchmark Score Error Units
fromType3Bytes 1.576 ± 0.061 ops/us
·gc.alloc.rate.norm 368.031 ± 0.027 B/op
ベースラインに比べて1回の呼出しあたり120バイトほどになりました。いいですね。そして、かなりのスループットの向上が期待できます。
ドキュメントではclazz.newInstance()をclazz.getDeclaredConstructor().newInstance()で置き換えることを推奨していますが、後者の方がコピーや高価な（そして割り当てられた際の）初回アクセスチェックのためにパフォーマンスが低下する可能性があるようです。この問題を解決するには、JIT コンパイラの英雄的な力を借りないと簡単ではないかもしれませんが、それまでの間はProviderでデフォルトのコンストラクタをキャッシュする方が良いでしょう。
クラスを弱参照するだけにする、つまりリークを避けながらClassValueを利用するのが効率的です。
private static final ClassValue<Constructor<?>> DEFAULT_CONSTRUCTORS =
new ClassValue<>() {
@Override
protected Constructor<?> computeValue(Class<?> clazz) {
try {
return clazz.getConstructor();
} catch (NoSuchMethodException e) {
throw new RuntimeException(e);
}
}
};
private Constructor<?> getConstructor(Class<?> clazz)
throw NoSuchMethodException {
try {
return DEFAULT_CONSTRUCTORS.get(clazz);
} catch (RuntimeException re) {
if (re.getCause() instanceof NoSuchMethodException nsme) {
throw nsme;
}
throw re;
}
}
...
Constructor<?> con = getConstructor(clazz);
return con.newInstance(EMPTY_OBJ);
NoSuchMethodExceptionをRuntimeExceptionでラップしてからアンラップする必要があるのは少し残念ですが、これはトリックであり、非推奨のclazz.newInstance()に近い結果を得られます。
Benchmark Score Error Units
fromType3Bytes 1.575 ± 0.086 ops/us
·gc.alloc.rate.norm 368.034 ± 0.006 B/op
しかし、これでもまだProviderでかなりの時間を費やしています。オリジナルのPRに触発され、MessageDigest.getInstance("MD5")から返されたMessageDigestをUUIDのホルダーにキャッシュするものを試しに作成してみました。しかし、ThreadLocalの代わりに、使用前に共有MDをクローンしています。これはスレッドセーフで、比較的簡単で、ホットパス上でのリフレクションやProviderに起因するオーバーヘッドを回避します。これはclazz.newInstance()と比較すると、総割り当て量ではわずかな改善ですが、スループットでは大きな改善になります。
Benchmark Score Error Units
fromType3Bytes 2.018 ± 0.076 ops/us
·gc.alloc.rate.norm 344.029 ± 0.022 B/op
これが安全にできる最善の方法かもしれません。しかしながら、より一般的な最適化を行い、UUIDに特化した最適化を行わないようにするのが良いでしょう。
Summing up
以下のベースラインから始めました。
Benchmark Score Error Units
fromType3Bytes 1.460 ± 0.089 ops/us
·gc.alloc.rate.norm 488.042 ± 0.005 B/op
キャッシュされたMD5オブジェクトをクローニングするというアイデアと、MD5から一時バッファxを削除するというアイデアを組み合わせることで、ベースラインよりもかなり大きな改善が得られました。
Benchmark Score Error Units
fromType3Bytes 2.186 ± 0.228 ops/us # ~1.45-1.5x
·gc.alloc.rate.norm 264.023 ± 0.006 B/op # -46%
PR#1821で提案されたThreadLocalのアプローチは、このマイクロベンチマークではまだ勝利を収めています。また、独立したMD5の最適化と一緒に動作して、もう少し先に進むことができます。
8258588: MD5 MessageDigest in java.util.UUID should be cached #1821
https://github.com/openjdk/jdk/pull/1821
Benchmark Score Error Units
fromType3Bytes 2.578 ± 0.060 ops/us # ~1.75x
·gc.alloc.rate.norm 64.005 ± 0.001 B/op # -87%
このマイクロベンチマークでは、基本コードのオーバーヘッドを削減することでThreadLocalアプローチを打ち負かすことはできないでしょうが、JDK ライブラリでThreadLocalを使用することの現在および今後の欠点を考えると、ThreadLocalアプローチのPRがレビューを通過する可能性は低いと思われます。なので、実用的な意味ではこれがベストなのかもしれません。
私の意図は、時間が許す限り、今後数週間かけてこれまで探索した実験のいくつかをクリーンアップして統合することです。しかし、JDK16のためのランプダウン作業が優先されるかもしれません。
ここでの理想は、何も悪化させることなく、ポイント修正に頼ることなく、特定のマイクロベンチマーク（の結果）に十分に近づいていくことです。
Logico Inside 