[インデックス 14029] ファイルの概要
このコミットは、Go言語の標準ライブラリに含まれる crypto/sha256 および crypto/sha512 パッケージにおけるSHA-256およびSHA-512ハッシュ関数のパフォーマンスを約1.3倍向上させるための最適化を実装しています。具体的には、ハッシュ計算のブロック処理において、中間計算で繰り返し参照される配列要素の値を一時変数にキャッシュすることで、メモリアクセスを効率化し、全体的な処理速度を改善しています。
コミット
commit b459afe843d7350822276fc8db50e7b04f1458e9
Author: Dmitry Chestnykh <dchest@gmail.com>
Date: Fri Oct 5 17:04:48 2012 -0400
crypto/sha256, crypto/sha512: 1.3x speedup
SHA-256:
benchmark old ns/op new ns/op delta
BenchmarkHash1K 21686 16912 -22.01%
BenchmarkHash8K 173216 135020 -22.05%
benchmark old MB/s new MB/s speedup
BenchmarkHash1K 47.22 60.55 1.28x
BenchmarkHash8K 47.29 60.67 1.28x
SHA-512:
benchmark old ns/op new ns/op delta
BenchmarkHash1K 14323 11163 -22.06%
BenchmarkHash8K 114120 88693 -22.28%
benchmark old MB/s new MB/s speedup
BenchmarkHash1K 71.49 91.73 1.28x
BenchmarkHash8K 71.78 92.36 1.29x
R=golang-dev, agl
CC=golang-dev
https://golang.org/cl/6584071
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/b459afe843d7350822276fc8db50e7b04f1458e9
元コミット内容
crypto/sha256, crypto/sha512: 1.3x speedup
SHA-256:
benchmark old ns/op new ns/op delta
BenchmarkHash1K 21686 16912 -22.01%
BenchmarkHash8K 173216 135020 -22.05%
benchmark old MB/s new MB/s speedup
BenchmarkHash1K 47.22 60.55 1.28x
BenchmarkHash8K 47.29 60.67 1.28x
SHA-512:
benchmark old ns/op new ns/op delta
BenchmarkHash1K 14323 11163 -22.06%
BenchmarkHash8K 114120 88693 -22.28%
benchmark old MB/s new MB/s speedup
BenchmarkHash1K 71.49 91.73 1.28x
BenchmarkHash8K 71.78 92.36 1.29x
R=golang-dev, agl
CC=golang-dev
https://golang.org/cl/6584071
変更の背景
このコミットの主な背景は、Go言語の標準ライブラリが提供する暗号学的ハッシュ関数であるSHA-256およびSHA-512のパフォーマンスを向上させることです。ハッシュ関数は、データの完全性検証、デジタル署名、パスワードの保存など、多くのセキュリティ関連アプリケーションで広く利用されています。これらの関数が高速であることは、システム全体のパフォーマンスに直接影響するため、継続的な最適化が重要です。
特に、SHA-256とSHA-512のような計算量の多いアルゴリズムでは、わずかなコードの変更でも大きな性能改善につながることがあります。このコミットでは、ハッシュ計算のコア部分であるブロック処理ループ内のメモリアクセスパターンに着目し、冗長なメモリアクセスを排除することで、実測で約1.3倍の速度向上を達成しています。これは、特に大量のデータをハッシュ化するアプリケーションにおいて顕著なメリットをもたらします。
前提知識の解説
1. 暗号学的ハッシュ関数 (Cryptographic Hash Function)
暗号学的ハッシュ関数は、任意の長さの入力データ（メッセージ）を受け取り、固定長の短い出力（ハッシュ値またはメッセージダイジェスト）を生成する数学的なアルゴリズムです。以下の重要な特性を持ちます。
- 一方向性 (One-way property): ハッシュ値から元のメッセージを効率的に復元することは計算上不可能である。
- 衝突耐性 (Collision resistance): 異なる2つのメッセージが同じハッシュ値を生成することは計算上困難である（弱衝突耐性）。また、与えられたメッセージと同じハッシュ値を持つ別のメッセージを見つけることも計算上困難である（強衝突耐性）。
- 原像計算困難性 (Preimage resistance): 与えられたハッシュ値に対して、そのハッシュ値を生成する元のメッセージを見つけることは計算上困難である。
- 第二原像計算困難性 (Second preimage resistance): 与えられたメッセージに対して、それと同じハッシュ値を持つ別のメッセージを見つけることは計算上困難である。
これらの特性により、ハッシュ関数はデータの改ざん検出、デジタル署名、パスワードの安全な保存などに利用されます。
2. SHA-256とSHA-512
SHA (Secure Hash Algorithm) は、アメリカ国家安全保障局 (NSA) によって設計され、NIST (National Institute of Standards and Technology) によってFIPS (Federal Information Processing Standard) として公開された暗号学的ハッシュ関数のファミリーです。
- SHA-256: 256ビット（32バイト）のハッシュ値を生成します。主に32ビットワードで動作するように設計されています。
- SHA-512: 512ビット（64バイト）のハッシュ値を生成します。主に64ビットワードで動作するように設計されており、SHA-256よりも大きなデータブロックを効率的に処理できます。
これらのアルゴリズムは、入力データを固定サイズのブロックに分割し、各ブロックに対して一連の複雑なビット演算（ビットシフト、ローテート、XOR、AND、NOTなど）と加算を繰り返し適用することでハッシュ値を計算します。
3. ビット演算 (Bitwise Operations)
このコミットで変更されているコードは、ビット演算を多用しています。
- ビットシフト (
>>,<<): ビットを左右に移動させます。x >> nはxのビットを右にnビット移動させ、x << nはxのビットを左にnビット移動させます。 - ビットローテート (Circular Shift): ビットを左右に移動させますが、端からあふれたビットが反対側の端に戻ってきます。Go言語には直接的なローテート演算子はありませんが、
(x >> n) | (x << (WORD_SIZE - n))のようにビットシフトとOR演算を組み合わせて実現されます。SHA-256/512のアルゴリズムでは、このローテート演算が頻繁に利用されます。 - XOR (
^): 排他的論理和。対応するビットが異なる場合に1、同じ場合に0を返します。
4. Go言語の crypto パッケージ
Go言語の標準ライブラリには、暗号学的機能を提供する crypto パッケージ群が含まれています。crypto/sha256 と crypto/sha512 は、それぞれSHA-256とSHA-512ハッシュアルゴリズムの実装を提供します。これらのパッケージは、hash.Hash インターフェースを実装しており、Write メソッドでデータを入力し、Sum メソッドでハッシュ値を取得する一般的なパターンで利用されます。
ハッシュ計算の内部では、入力データを処理するために、block 関数のような低レベルの関数が使用されます。この block 関数は、ハッシュアルゴリズムのコアとなる圧縮関数を実装しており、大量のビット演算と配列アクセスを行います。
技術的詳細
SHA-256およびSHA-512のハッシュ計算プロセスでは、メッセージスケジュール配列 w が使用されます。この配列は、入力ブロックから派生したワードと、以前に計算されたワードに基づいて拡張されます。特に、w[i] の計算は、w[i-2]、w[i-15]、w[i-7]、w[i-16] といった以前のワードに依存します。
変更前のコードでは、w[i-2] や w[i-15] の値が、t1 や t2 の計算において複数回直接参照されていました。例えば、SHA-256の t1 の計算では w[i-2] が3回、SHA-512の t1 の計算では w[i-2] が3回、それぞれ異なるビットシフトやローテート演算のオペランドとして使用されていました。
// 変更前 (sha256block.goの例)
t1 := (w[i-2]>>17 | w[i-2]<<(32-17)) ^ (w[i-2]>>19 | w[i-2]<<(32-19)) ^ (w[i-2] >> 10)
このコードでは、w[i-2] の値がメモリから3回読み込まれる可能性があります（コンパイラの最適化によっては1回にまとめられることもありますが、保証されません）。配列要素へのアクセスは、レジスタやキャッシュからのアクセスに比べてコストが高い操作です。
このコミットでは、この冗長なメモリアクセスを排除するために、w[i-2] と w[i-15] の値をそれぞれ一時変数 v1 と v2 にキャッシュするように変更されました。
// 変更後 (sha256block.goの例)
v1 := w[i-2]
t1 := (v1>>17 | v1<<(32-17)) ^ (v1>>19 | v1<<(32-19)) ^ (v1 >> 10)
これにより、w[i-2] の値は一度だけメモリから読み込まれ、その後の計算ではレジスタに格納された v1 の値が使用されます。レジスタへのアクセスはCPUにとって最も高速な操作であるため、これにより計算の効率が向上します。同様の最適化が w[i-15] と t2 の計算にも適用されています。
この最適化は、特にループ内で頻繁に実行されるコードパスにおいて、CPUのパイプライン効率を改善し、メモリアクセスのレイテンシを削減することで、全体的な実行速度を向上させます。ベンチマーク結果が示すように、この小さな変更がSHA-256とSHA-512の両方で約1.3倍の速度向上をもたらしました。
コアとなるコードの変更箇所
src/pkg/crypto/sha256/sha256block.go
--- a/src/pkg/crypto/sha256/sha256block.go
+++ b/src/pkg/crypto/sha256/sha256block.go
@@ -86,10 +86,10 @@ func block(dig *digest, p []byte) {
w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])
}
for i := 16; i < 64; i++ {
- t1 := (w[i-2]>>17 | w[i-2]<<(32-17)) ^ (w[i-2]>>19 | w[i-2]<<(32-19)) ^ (w[i-2] >> 10)
-
- t2 := (w[i-15]>>7 | w[i-15]<<(32-7)) ^ (w[i-15]>>18 | w[i-15]<<(32-18)) ^ (w[i-15] >> 3)
-
+ v1 := w[i-2]
+ t1 := (v1>>17 | v1<<(32-17)) ^ (v1>>19 | v1<<(32-19)) ^ (v1 >> 10)
+ v2 := w[i-15]
+ t2 := (v2>>7 | v2<<(32-7)) ^ (v2>>18 | v2<<(32-18)) ^ (v2 >> 3)
w[i] = t1 + w[i-7] + t2 + w[i-16]
}
src/pkg/crypto/sha512/sha512block.go
--- a/src/pkg/crypto/sha512/sha512block.go
+++ b/src/pkg/crypto/sha512/sha512block.go
@@ -101,9 +101,10 @@ func block(dig *digest, p []byte) {
uint64(p[j+4])<<24 | uint64(p[j+5])<<16 | uint64(p[j+6])<<8 | uint64(p[j+7])
}
for i := 16; i < 80; i++ {
- t1 := (w[i-2]>>19 | w[i-2]<<(64-19)) ^ (w[i-2]>>61 | w[i-2]<<(64-61)) ^ (w[i-2] >> 6)
-
- t2 := (w[i-15]>>1 | w[i-15]<<(64-1)) ^ (w[i-15]>>8 | w[i-15]<<(64-8)) ^ (w[i-15] >> 7)
+ v1 := w[i-2]
+ t1 := (v1>>19 | v1<<(64-19)) ^ (v1>>61 | v1<<(64-61)) ^ (v1 >> 6)
+ v2 := w[i-15]
+ t2 := (v2>>1 | v2<<(64-1)) ^ (v2>>8 | v2<<(64-8)) ^ (v2 >> 7)
w[i] = t1 + w[i-7] + t2 + w[i-16]
}
コアとなるコードの解説
上記の変更箇所は、SHA-256およびSHA-512のメッセージスケジュール配列 w の拡張部分、具体的には for i := 16; i < ...; i++ ループ内にあります。このループでは、w[i] の値が、以前の w の値（w[i-2], w[i-15], w[i-7], w[i-16]）と、ビット演算によって計算される t1 および t2 という中間値に基づいて計算されます。
変更の核心は、t1 と t2 の計算式において、w[i-2] と w[i-15] の値をそれぞれ新しい一時変数 v1 と v2 に代入してから使用するようにした点です。
-
変更前:
t1 := (w[i-2]>>17 | w[i-2]<<(32-17)) ^ (w[i-2]>>19 | w[i-2]<<(32-19)) ^ (w[i-2] >> 10) t2 := (w[i-15]>>7 | w[i-15]<<(32-7)) ^ (w[i-15]>>18 | w[i-15]<<(32-18)) ^ (w[i-15] >> 3)この形式では、
w[i-2]がt1の計算式内で3回、w[i-15]がt2の計算式内で3回、それぞれ配列から直接参照されています。 -
変更後:
v1 := w[i-2] // w[i-2] の値を一時変数 v1 にキャッシュ t1 := (v1>>17 | v1<<(32-17)) ^ (v1>>19 | v1<<(32-19)) ^ (v1 >> 10) v2 := w[i-15] // w[i-15] の値を一時変数 v2 にキャッシュ t2 := (v2>>7 | v2<<(32-7)) ^ (v2>>18 | v2<<(32-18)) ^ (v2 >> 3)この変更により、
w[i-2]の値は一度だけv1に読み込まれ、その後のt1の計算ではv1が使用されます。同様に、w[i-15]の値は一度だけv2に読み込まれ、その後のt2の計算ではv2が使用されます。
この最適化は、コンパイラが必ずしもこのような共通部分式除去（Common Subexpression Elimination）を自動的に行わない場合に特に有効です。配列要素へのアクセスは、ポインタのデリファレンスやキャッシュの考慮が必要なため、単純な変数へのアクセスよりもコストがかかることがあります。一時変数にキャッシュすることで、CPUは値をレジスタに保持しやすくなり、繰り返し同じメモリアドレスにアクセスするオーバーヘッドを削減できます。結果として、CPUの実行ユニットがより効率的に動作し、ハッシュ計算の全体的な速度が向上します。
関連リンク
- Go Code Review: https://golang.org/cl/6584071
参考にした情報源リンク
- SHA-256 - Wikipedia: https://ja.wikipedia.org/wiki/SHA-256
- SHA-512 - Wikipedia: https://ja.wikipedia.org/wiki/SHA-512
- Go言語のcryptoパッケージ: https://pkg.go.dev/crypto
- Go言語のビット演算: https://go.dev/ref/spec#Arithmetic_operators (Go言語の仕様書における演算子に関する記述)
- Common Subexpression Elimination - Wikipedia: https://en.wikipedia.org/wiki/Common_subexpression_elimination