原文はこちら。
The original article was written by Claes Redestad (Principal Member of Technical Staff, Oracle)
https://cl4es.github.io/2021/02/14/Reducing-MD5-and-SHA-Overheads.html

Background

このエントリは先日のエントリ（Investigating MD5 Overheads – java.util.UUID::nameUUIDFromBytesの改善に関連して行った分析の一部を詳述しました）の続きです。この記事を書いている時点では、このPRはまだオープンの状態ですが、この周辺の事柄を大幅に改善するいくつかの最適化を統合しています。

Investigating MD5 overheads
https://cl4es.github.io/2021/01/04/Investigating-MD5-Overheads.html
https://logico-jp.io/2021/01/11/investigating-md5-overheads/
8258588: MD5 MessageDigest in java.util.UUID should be cached #1821
https://github.com/openjdk/jdk/pull/1821

Optimize MessageDigest.getInstance

（ java.security.Provider::getService の最適化による）

#1933 は、当時実施した解析の結果統合された初めてのPRです。

8259065: Optimize MessageDigest.getInstance #1933
https://github.com/openjdk/jdk/pull/1933

プロトタイプやその前に実施した解析が示唆する通り、主な改善点は、digestオブジェクトをインスタンス化するために使われるConstructorをキャッシュすることにあります。プロトタイプからの大きな違いは、ClassValueやThreadLocalにキャッシュするのではなく、java.security.Provider$Serviceオブジェクトにキャッシュする点です。これは余分なルックアップなどがないことを意味します。そして、そのために少々利益が得られます。

Objects.hashを放棄するなど、いくつかのマイナーな機能強化を追加します。Objects.hashは便利ですが、可変長配列を確保してしまいます。そのため、Objects.hashの放棄によりパフォーマンス向上が見込まれますが、いつものように、まずその重要性を確認すべきです。この特定のケースでは、いくつかのパブリックJDK APIのパフォーマンスにわずかに影響を与えますが、Objects.hashの放棄は合理的なことのように思えました。

全体として、MessageDigest.getInstanceの割り当てのオーバーヘッドがゼロになりました。MessageDigestだけを割り当てます。これはオペレーション毎に144バイトの割り当て圧力が減少したことを意味します。

この最適化は任意のjava.security.Provider$Serviceに対して一般的なものなので、これはMessageDigest.getInstanceが高速化されるだけでなく、Provider APIを使って取得される任意のセキュリティサービスも同様に改善されることを意味します。

しかし、このことを反映するために機能強化のサマリーを変更するには時が経ちすぎました…。

Shrink MD5 and SHA down to size

MD5自体を最適化するために作成したプロトタイプ（一時的な配列を取り除き、ダイジェストを生成するためにデータを読み取るコードを、内在化により置き換えられるメソッドに入れる）はうまくいきました。

MD5 – room for improvement?
https://cl4es.github.io/2021/01/04/Investigating-MD5-Overheads.html#md5—room-for-improvement

これにより、インスタンスサイズがかなり小さくなり、内在化による最適化で除去されなかったいくつかのアクティビティを回避することで、ダイジェスト生成のパフォーマンスが少々改善されています。ダイジェスト生成対象のデータが小さいときに最も顕著です。

そんなわけで、同じ（または少なくとも非常に類似した）最適化がSHAの実装のほとんどに適用できることをすぐに現実化するためだけに、プルリクエストを起草しました。

8259498: Reduce overhead of MD5 and SHA digests #1855
https://github.com/openjdk/jdk/pull/1855

主な違いは、SHA実装のために最適化で除去されるべき一時的な配列がかなり大きくなっている点で、それゆえ、配列のコードを完全に削除するのは面倒なことになります。しかし、組み込まれたメソッド内で配列の割り当てと使用を移動するということは、メソッドが JIT コンパイルされると、配列の割り当てが不要になることを意味します。

PRで追加したgetAndDigest microbenchmarkを-prof gcを付けて実行してみると、これが効果を発揮し、アロケーションを大幅に削減できることがわかります。

Benchmark                                 (digesterName)  (length)    Cnt     Score      Error   Units

Baseline
MessageDigests.getAndDigest:·gc.alloc.rate.norm      MD5        16     15   312.011 ±    0.005    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm    SHA-1        16     15   584.020 ±    0.006    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm  SHA-256        16     15   544.019 ±    0.016    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm  SHA-512        16     15  1056.037 ±    0.003    B/op

PR
MessageDigests.getAndDigest:·gc.alloc.rate.norm      MD5        16     15   232.009 ±    0.006    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm    SHA-1        16     15   584.021 ±    0.001    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm  SHA-256        16     15   272.012 ±    0.015    B/op
MessageDigests.getAndDigest:·gc.alloc.rate.norm  SHA-512        16     15   400.017 ±    0.019    B/op

（SHA-1の組み込みはデフォルトで有効化されていないので、割り当ての削減はありません）

MessageDigest.getInstanceの最適化で得られた、144b/op の割り当て削減とあわせて、SHA-256やSHA-512のようなより強力なダイジェストがフットプリントのオーバーヘッドを大幅に削減することを意味します。SHA-256では半分以上、SHA-512では3分の2です。

実にすばらしい。

Summing up

現在に戻って、PR#1855で追加したUUID::nameUUIDFromBytesのマイクロベンチマークを実行してみると、この小さな冒険を始めた特定の操作でそれなりの利益を得ることができたことが明白です。

8259498: Reduce overhead of MD5 and SHA digests #1855
https://github.com/openjdk/jdk/pull/1855

Before:

Benchmark                 (size)   Mode  Cnt  Score   Error   Units
UUIDBench.fromType3Bytes     128  thrpt   15  1.620 ± 0.048  ops/us

After:

Benchmark                 (size)   Mode  Cnt  Score   Error   Units
UUIDBench.fromType3Bytes     128  thrpt   15  2.309 ± 0.049  ops/us

入力の大きさに依存するとはいえ、およそ40～50％のスピードアップです。

内部のより深い部分を分析して改善点を見つけようとしたことにより、セキュリティ領域全般を改善するパッチを提供できました。MD5の改善点を様々なSHA実装に変換したことも大きな成功でした。これらの改善のいくつかは、うまくいけば、いくつかの仮想的な実際のアプリで実際の利益につながることを期待しています。

素晴らしいことですが、これらの改善は必ずしもjava.util.UUID::nameUUIDFromBytesのMD5オブジェクトのキャッシングを排除するものではありません。キャッシュ保持により、マイクロベンチマークではまだ便益があります。

8258588: MD5 MessageDigest in java.util.UUID should be cached #1821
https://github.com/openjdk/jdk/pull/1821

Benchmark                 (size)   Mode  Cnt  Score   Error   Units
UUIDBench.fromType3Bytes     128  thrpt   15  2.632 ± 0.080  ops/us

しかし、特定のコールサイトにスレッドローカルキャッシュを追加しようとは思わないでしょう。スレッドローカルを追加することの真のコストを分析するのは難しいためです。多くのスレッドを持つ大規模なアプリケーションではフットプリントがじわじわ大きくなるかもしれませんし、GCによってキャッシュされたオブジェクトが移動された場合にパフォーマンスのペナルティがあるかもしれませんが、これはマイクロベンチマークで適切に捕捉するのは困難です。