overheads原文はこちら。Oracle)https://cl4es.github.io/2021/01/04/Investigating-MD5-Overheads.htmlBackground数週間前に、MessageDigest.getInstance("MD5")からの戻り値を静的フィールドにキャッシュすることで、java.util.UUID::nameUUIDFromBytesの高速化を意図したPRを受け取りました。#1821https://github.com/openjdk/jdk/pull/1821一見すると、このPRはちょっとした改善点のように思えます。それはMessageDigestオブジェクトがステートフルであることに気づく前のことで、何らかの同期メカニズムがなければ、静的に共有することはできません。このPRの正確性を修正するために、ThreadLocalを利用するようにPRを更新しましたが、これにはそれなりの問題があります。MessageDigestオブジェクトのインスタンスを無期限に保持する(これはThreadLocalに格納されているオブジェクトをSoftReferenceにラップすることで部分的に解決する可能性がありますが、複雑さと速度を犠牲が犠牲になっています)。Loomとの相性が悪い可能性がある。この理由から、予防措置としてOpenJDKチームはいくつかの怪しげなThreadLocalの最適化を慎重に削除している。Loomhttps://openjdk.java.net/projects/loom/しかし、PRをこき下ろしたり、完全に拒否したりするのは楽しいことではありません。ここには間違いなく改善の余地があるように思えます。この記事では、プロファイリングとプロトタイピングの作業の一部を探って、別の最適化を検討してみたいと思います。したら、もっと良い提案が生まれるかもしれません。現在のベストな改善点の組み合わせでPRを起草しましたが、最初から書いていきましょう。#1855https://github.com/openjdk/jdk/pull/1855に書いてみましたが最高のパフォーマンスを発揮する改善点の組み合わせでPRを起草しましたが、最初から始めてみましょう。MD5?MD5は暗号のハッシュ関数で、ここで見ているUUIDメソッドの他にもいろいろなものに使われています。Algorithmhttps://tools.ietf.org/html/rfc1321暗号の専門家ではありませんが、MD5が暗号的に壊れていて衝突攻撃の影響を受けやすいと考えられていることは知っています。そのため、セキュリティ上重要なことにはMD5ハッシュに頼るのは決して良い考えではありませんが、非常に高速なハッシュであり、整合性チェックのための人気のある選択肢であることに変わりはありません。OpenJDKのMD5の実装は、アルゴリズムの大部分を内部化することで最近最適化されました。x86https://bugs.openjdk.java.net/browse/JDK-8250902最初はx86のみですが、他のアーキテクチャへの実装も予定されているようです。内部化とは、コンパイル中にJVMがいくつかのJavaコードを手作業で最適化されたバージョンに置き換えるという、楽しいが複雑な(そして時には驚くような)テクニックです。16で追加される予定で、MD5ダイジェストを行う際のパフォーマンスを15~20%向上させると言われています。analysis何かを最適化しようとする前に、まず、最適化しようとしているもののパフォーマンスを理解しようとすることが重要です。MessageDigest.getInstance("MD5")に直接ズームインすることもできますし、元のPRが最適化しようとしていたパブリックAPIメソッドではなく、java.util.UUID.nameUUIDFromBytesを使用することもできます。どこから検討を開始すべきかという問いに正しい答えはありませんが、現実世界のユースケースから抽出したやや高レベルのAPIから詳細を掘り下げていくと、正しい方向に向かうことが多々あります。microbenchmarkjava.util.UUIDの以下のメソッドを考えてみましょう。}これは確かにMessageDigest.getInstanceとdigestのオーバーヘッドを調べるためだけでなく、これらのオーバーヘッドがUUIDオブジェクト自体の作成に対してどのように積み重なっているかを見るための入り口のように思えます。これは、各パーツがどれだけ貢献しているかを知るための良い出発点だと思いました。偶然にもUUID関連のマイクロベンチマークはOpenJDKのソースにあるので、これを拡張しない手はありません。シンプルにしましょう。test/micro/org/openjdk/bench/java/util/UUIDBench.javahttps://github.com/openjdk/jdk/pull/1855/files#diff-fcb56f7dd0c6f7fc1bdc199e3b41d492eba49b20fe198d898b97ca23024a9e9dR82ランダムなバイト列をセットアップ時に作成し、パブリックメソッドを呼び出しましょう。}ビルドおよびJMHの実行用にOpenJDKをセットアップ後、以下のコマンドを実行してマイクロベンチマークを実行します。build//images/test/micro/benchmarks.jarで直接実行もできます。gc)を付けて実行し、これをクイックチェックとして利用しています。これにより、各呼出しでどれぐらい割り当てがなされているかの概要を把握できます。バイト...無害なものにしてはかなりの量ですね。1.24から、async-profilerをサポートするようになりました(別途インストールする必要があります)。async-profilerhttps://github.com/jvm-profiling-tools/async-profilerこれは非常に強力なプロファイラで、JMHとのうまく連携します。CPUフレームグラフを生成する機能は使いやすくて良いです。microアロケーション・プロファイラー/サンプラーもありまして、この解析で試してみようと思います。もので遊んでみたいというのは、これ以上の理由はありません。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[]は空の可変長引数配列のように思われますが、それについてはまた今度...。improvement?MD5の実装コードが最近内部化されたと書きました。メソッドが内部化されたとき、見えるものが取得できるものとは限りません。この場合、現在のコードの状態を調べたときに驚きました。割り当てプロファイルにある大きなデータ構造の一つは、内部化されたコードでは全く使用されていません。それでも、それは常に割り当てられ、満たされ、クリアされています。}また、名前からして単にいくつかのチェックを行うだけのimplCompressCheckメソッドが、一時バッファxに値を読み込むことに副作用があるというのも少し間違っているように思えます。そこで、チェックのみを行うようにimplCompressCheckをリファクタリングし、一時的なバッファを取り除き、バッファからの値の読み込みをimplCompress0に移動し、冗長な2回の読み取りを避けるようにしました。これは、UUIDマイクロベンチマークにおいて有益であることがわかりました。B/op488B/opのベースラインに対して80B/op削減され、わずかながらスループットが向上しました。digestメソッドにズームインすると、別のマイクロベンチマークでその改善はかなり顕著であることがわかります。DEFAULT)この最適化の効果は、より大きな入力では減少します。数Kb以上のダイジェストではノイズの中に消えてしまいます。elimination)されていることを示唆していますが、xバッファの無意味な割り当てとクリアは排除できません。intsさきほどの実験のソースコードを見ていると、VarHandleを使ってbyte[]からintの値を読み取る方法に気づかれた方もいらっしゃるかもしれません。既存コードが行っていることと同じですが、その中ではもう少し儀式的なものとUnsafeを使用しています。VarHandleにはいくつかのクセがありますが、これを使用することで、私がここで「インライン化」しているByteArrayAccess::b2iLittle64メソッドのトリッキーなロジックとUnsafeの使用法のいくつかをうまくカプセル化できると思います。Unsafeと全く同じように実行されることがわかります。インタプリタで実行しているときに少しオーバーヘッド(〜30%)があります。このオーバーヘッドは、long値ではなく、int値を抽出することで、ほぼ半減し、より高い最適化レベルでも効果が落ちることはありませんでした。何らかの方法で起動時の影響を受けやすいコードを最適化していないのであれば、インタープリタ用に最適化することは、一般的には手間をかける価値がありません。そのVarHandle実装自体を改善する方法を考えるべきかもしれません。私がこの実験に基づいてパッチを完成させて提案するのであれば、まず最初にコードをできるだけ単純化して、より多くのハードウェアでより徹底的なテストを行いたいと思います。モダンでUnsafeでないAPIを使って改造しても良いのですが、リスクを伴います。APIなどの他のテクノロジーを使って、このbyteからintへの変換を実装して比較してみたり、sun.security.provider.ByteArrayAccessのレガシー実装のコードへの対処法での変更を統合したりするのも面白いでしょう。constraintsMD5.implCompress0の内部化の不幸な副作用として、MD5のint[]の状態配列に依存したHotSpotの内部化があります。これは、この配列を4つのintにフラット化するようなことを試すためには、それらが実装されているすべてのプラットフォームで、いくつかの厄介な内部コードを書き換えなければならないことを意味します。これが些細なことではなくなってしまったのは少し腹立たしいです。overheads一歩下がって、Provider::newInstanceUtilで見られた様々な割り当てにズームインしてみましょう。全体の12%(!?)の割合でObject[]を割り当てていたコードの中には、以下のようなものがあります。con.newInstance();セキュリティと整合性の理由から、clazz.getConstructor()は呼び出すたびに新しいConstructorを写し取り、ConstructorのnewInstanceの最初の呼び出しでは、呼び出すたびに高価なアクセスチェックが行われます。両メソッドとも可変長引数メソッドです。可変長メソッドを引数を付けずに呼び出すのは、javacが空のObject[]を生成し、それをメソッドに渡す、という意味です。これは、これを最適化することが「意味がある」ということかもしれません。con.newInstance(EMPTY_OBJ);HotSpotのJITコンパイラではこのような割り当てを最適化により除去することがよくあります。この場合は少々改善が見られました。B/op1回の呼出しあたり16バイト程度です。全体の約3.2%です。このメソッドに対してアロケーションプロファイリングが推定した12%ではありません。デフォルト設定の64ビットJVMで実験しているので、これは最小サイズのオブジェクトの割り当てが1つ少ないことに等しくなります。空の配列のようなものです。実際のアプリケーションでは、このような微細な最適化はほぼ時間の無駄になりそうですが、様々な方法で種々のパブリックAPIが利用する可能性のある内部JDKコードでは、考慮すべき合理的なことかもしれません。言っても、道に迷ってしまったのかもしれません...。コスト配分の面でより大きなコストがかかるのは、呼び出すたびにclazzからConstructorをコピーしていることでしょう。デフォルトのコンストラクタを呼び出す際には、コンストラクタをキャッシュする(非推奨の)省略版があります(clazz.newInstance())。B/opベースラインに比べて1回の呼出しあたり120バイトほどになりました。かなりのスループットの向上が期待できます。ドキュメントではclazz.newInstance()をclazz.getDeclaredConstructor().newInstance()で置き換えることを推奨していますが、後者の方がコピーや高価な(そして割り当てられた際の)初回アクセスチェックのためにパフォーマンスが低下する可能性があるようです。コンパイラの英雄的な力を借りないと簡単ではないかもしれませんが、それまでの間はProviderでデフォルトのコンストラクタをキャッシュする方が良いでしょう。クラスを弱参照するだけにする、つまりリークを避けながらClassValueを利用するのが効率的です。con.newInstance(EMPTY_OBJ);NoSuchMethodExceptionをRuntimeExceptionでラップしてからアンラップする必要があるのは少し残念ですが、これはトリックであり、非推奨のclazz.newInstance()に近い結果を得られます。B/opしかし、これでもまだProviderでかなりの時間を費やしています。オリジナルのPRに触発され、MessageDigest.getInstance("MD5")から返されたMessageDigestをUUIDのホルダーにキャッシュするものを試しに作成してみました。ThreadLocalの代わりに、使用前に共有MDをクローンしています。これはスレッドセーフで、比較的簡単で、ホットパス上でのリフレクションやProviderに起因するオーバーヘッドを回避します。これはclazz.newInstance()と比較すると、総割り当て量ではわずかな改善ですが、スループットでは大きな改善になります。B/opこれが安全にできる最善の方法かもしれません。一般的な最適化を行い、UUIDに特化した最適化を行わないようにするのが良いでしょう。up以下のベースラインから始めました。B/opキャッシュされたMD5オブジェクトをクローニングするというアイデアと、MD5から一時バッファxを削除するというアイデアを組み合わせることで、ベースラインよりもかなり大きな改善が得られました。-46%PR#1821で提案されたThreadLocalのアプローチは、このマイクロベンチマークではまだ勝利を収めています。独立したMD5の最適化と一緒に動作して、もう少し先に進むことができます。ライブラリでThreadLocalを使用することの現在および今後の欠点を考えると、ThreadLocalアプローチのPRがレビューを通過する可能性は低いと思われます。実用的な意味ではこれがベストなのかもしれません。私の意図は、時間が許す限り、今後数週間かけてこれまで探索した実験のいくつかをクリーンアップして統合することです。JDK16のためのランプダウン作業が優先されるかもしれません。ここでの理想は、何も悪化させることなく、ポイント修正に頼ることなく、特定のマイクロベンチマーク(の結果)に十分に近づいていくことです。コメントをキャンセルコメントを入力してください。以下に詳細を記入するか、アイコンをクリックしてログインしてください。アカウントを使ってコメントしています。アカウントを使ってコメントしています。新しいコメントがついたらメールで通知。Inside現在40人フォロワーがいます。購読管理このバーを折りたたむ%d人のブロガーが「いいね」をつけました。