[インデックス 14428] ファイルの概要
このコミットは、Go言語の crypto/md5 パッケージにおけるMD5ハッシュ計算のパフォーマンス改善を目的としています。特に、入力データがメモリ上で適切にアラインされている場合に、uint32 型のロードを安全に利用することで書き込み処理を高速化し、さらにアラインされていない書き込みに対するテストとベンチマークを追加しています。これにより、MD5ハッシュ計算の効率が向上し、特に大きなデータブロックの処理において顕著な速度向上が見られます。
コミット
- コミットハッシュ:
38458ce3fea94ed9c89eb2dc78be9bc79b2b0c66 - 作者: Shenghou Ma minux.ma@gmail.com
- コミット日時: 2012年11月18日 (日) 02:23:34 +0800
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/38458ce3fea94ed9c89eb2dc78be9bc79b2b0c66
元コミット内容
crypto/md5: speed up aligned writes and test/bench unaligned writes
Write() can safely use uint32 loads when input is aligned.
Also add test and benchmarks for unaligned writes.
Benchmark result obtained by Dave Cheney on ARMv5TE @ 1.2GHz:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 4104 3417 -16.74%
BenchmarkHash1K 22061 11208 -49.20%
BenchmarkHash8K 146630 65148 -55.57%
BenchmarkHash8BytesUnaligned 4128 3436 -16.76%
BenchmarkHash1KUnaligned 22054 21473 -2.63%
BenchmarkHash8KUnaligned 146658 146909 +0.17%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 1.95 2.34 1.20x
BenchmarkHash1K 46.42 91.36 1.97x
BenchmarkHash8K 55.87 125.74 2.25x
BenchmarkHash8BytesUnaligned 1.94 2.33 1.20x
BenchmarkHash1KUnaligned 46.43 47.69 1.03x
BenchmarkHash8KUnaligned 55.76 55.76 1.00x
R=golang-dev, dave, bradfitz
CC=golang-dev
https://golang.org/cl/6782072
変更の背景
MD5ハッシュ計算は、データの整合性チェックやデジタル署名など、様々な場面で利用される重要な暗号学的ハッシュ関数です。Go言語の crypto/md5 パッケージは、これらの機能を提供しますが、パフォーマンスは常に重要な考慮事項です。特に、大量のデータを処理する場合、ハッシュ計算の効率がアプリケーション全体のパフォーマンスに大きく影響します。
このコミットの背景には、MD5ハッシュ計算の内部処理において、入力データのメモリ配置（アラインメント）がパフォーマンスに与える影響を最適化するという目的があります。多くのCPUアーキテクチャでは、特定のデータ型（例えば uint32 や uint64）をメモリから読み書きする際に、そのアドレスがデータ型のサイズ（またはその倍数）にアラインされていると、より高速に処理できます。アラインされていないアクセスは、パフォーマンスの低下や、場合によってはハードウェア例外を引き起こす可能性があります。
このコミット以前の crypto/md5 パッケージでは、入力データのアラインメントを考慮せずにバイト単位で処理を行っていた可能性があります。これにより、アラインメントの恩恵を受けられず、特に uint32 のようなワード単位での高速なロードが可能な状況でも、その最適化が適用されていませんでした。
また、アラインされていないデータに対する処理の堅牢性とパフォーマンスも重要です。現実世界のデータは必ずしも理想的なアラインメントで提供されるわけではないため、アラインされていない入力に対しても正しく、かつ合理的なパフォーマンスで動作することが求められます。
このコミットは、これらの課題に対処し、MD5ハッシュ計算の全体的なパフォーマンスを向上させるとともに、アラインメントに関する挙動をより明確にし、テストカバレッジを拡大することを目的としています。
前提知識の解説
MD5 (Message-Digest Algorithm 5)
MD5は、128ビット（16バイト）のハッシュ値を生成する暗号学的ハッシュ関数です。入力されたデータ（メッセージ）から、そのデータを代表する固定長の短い値を生成します。このハッシュ値は、データの改ざん検出やデジタル署名などに利用されます。MD5は現在、衝突耐性（異なる入力から同じハッシュ値が生成される可能性）の脆弱性が指摘されており、セキュリティが要求される場面ではSHA-256などのより強力なハッシュ関数が推奨されていますが、データの整合性チェックなど、一部の用途では依然として利用されています。
MD5の内部処理では、入力データを512ビット（64バイト）のブロックに分割し、各ブロックに対して一連のビット演算と加算を繰り返してハッシュ値を更新していきます。このブロック処理の効率が、MD5計算全体のパフォーマンスに直結します。
データアラインメント (Data Alignment)
データアラインメントとは、コンピュータのメモリ上でデータが配置される際のアドレスの制約のことです。多くのCPUアーキテクチャでは、特定のデータ型（例: 4バイトの int や uint32）は、そのデータ型のサイズ（この場合は4バイト）の倍数となるアドレスに配置されていると、CPUが効率的にアクセスできます。
- アラインされたアクセス: データのアドレスがそのデータ型のサイズ（またはその倍数）に合致している場合。CPUは一度のメモリアクセスでデータを読み書きできるため、高速です。
- アラインされていないアクセス (Unaligned Access): データのアドレスがそのデータ型のサイズに合致していない場合。CPUはデータを読み書きするために複数回のメモリアクセスを行ったり、特別なハードウェア処理を必要としたりするため、パフォーマンスが低下します。一部のアーキテクチャでは、アラインされていないアクセスがハードウェア例外を引き起こすこともあります。
例えば、4バイトの uint32 型のデータがアドレス 0x1000 に配置されていればアラインされていますが、アドレス 0x1001 に配置されている場合はアラインされていません。
Go言語の unsafe パッケージ
Go言語の unsafe パッケージは、Goの型安全性をバイパスして、低レベルのメモリ操作を可能にするためのパッケージです。通常、Goは厳格な型システムを持ち、ポインタ演算や型変換を制限することで安全性を保証しますが、unsafe パッケージを使用すると、C言語のようにメモリを直接操作できます。
unsafe.Pointer: 任意の型のポインタを保持できる汎用ポインタ型です。*T型からunsafe.Pointerへ、またunsafe.Pointerから*T型へ、そしてuintptr型との間で相互に変換できます。uintptr: 整数型であり、ポインタの値を保持できます。unsafe.Pointerとuintptrの間で変換することで、ポインタの値を整数として扱い、ポインタ演算（アドレスの加算・減算）を行うことができます。unsafe.Alignof(x): 式xのアラインメント要件を返します。これは、xがメモリ上で配置される際に要求されるバイト境界を示します。例えば、unsafe.Alignof(uint32(0))は通常4を返します。
unsafe パッケージは強力ですが、Goのメモリ安全性を損なう可能性があるため、慎重に使用する必要があります。主に、C言語との相互運用、システムプログラミング、またはパフォーマンスが極めて重要な場面での最適化に利用されます。
Go言語のベンチマーク (testing パッケージ)
Go言語の標準ライブラリ testing パッケージには、ベンチマークテストを記述するための機能が含まれています。ベンチマーク関数は BenchmarkXxx(*testing.B) というシグネチャを持ち、b.N 回の操作を実行するループを含みます。
b.SetBytes(n): ベンチマークが処理するバイト数を指定します。これにより、結果が「MB/s」（1秒あたりのメガバイト数）として表示されるようになります。b.ResetTimer(): ベンチマークの計測を開始します。セットアップコードの時間を計測から除外するために使用されます。b.N: ベンチマーク関数が実行される回数です。testingパッケージが自動的に調整し、統計的に有意な結果が得られるようにします。
このコミットでは、BenchmarkHash8BytesUnaligned のように、アラインされていない入力に対するベンチマークも追加されており、様々な条件下でのパフォーマンス特性を評価しています。
技術的詳細
このコミットの主要な技術的詳細は、MD5ハッシュ計算のコア部分である block 関数における入力データの処理方法の変更にあります。MD5の block 関数は、入力バイトスライス p を処理し、内部状態を更新します。MD5のアルゴリズムは32ビットワード（uint32）で動作するため、入力バイトスライスを効率的に32ビットワードとして読み込むことがパフォーマンス向上に繋がります。
変更前のコードでは、入力スライス p の先頭アドレスが uint32 のアラインメント要件を満たしているかどうかを明示的にチェックしていませんでした。代わりに、p の長さが _BlockSize (64バイト) と等しい場合にのみ、unsafe.Pointer を使用して p を *[16]uint32 型に直接キャストしていました。これは、p が _BlockSize の倍数で、かつそのアドレスが uint32 のアラインメント要件を満たしている場合にのみ安全な最適化でした。
このコミットでは、以下の重要な変更が加えられました。
-
アラインメントチェックの追加:
src/pkg/crypto/md5/gen.goおよびsrc/pkg/crypto/md5/md5block.goのblock関数において、入力スライスpの先頭アドレスがuint32のアラインメント要件を満たしているかどうかをuintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0という式でチェックするようになりました。unsafe.Pointer(&p[0]): バイトスライスpの最初の要素のアドレスをunsafe.Pointerに変換します。uintptr(...):unsafe.Pointerを整数型uintptrに変換し、アドレス値を数値として扱えるようにします。unsafe.Alignof(uint32(0)):uint32型のアラインメント要件（通常は4）を取得します。unsafe.Alignof(uint32(0))-1: アラインメント要件から1を引いた値（例: 4-1=3）は、アラインメントチェックのためのビットマスクとして機能します。&: ビットAND演算子です。アドレス値とビットマスクのビットANDを取ることで、アドレスがアラインメント要件の倍数であるかどうかをチェックします。結果が0であれば、アドレスはアラインされています。
-
アラインされた場合の
uint32ロードの適用: 上記のチェックにより、pの先頭アドレスがuint32のアラインメント要件を満たしていることが確認できた場合、X = (*[16]uint32)(unsafe.Pointer(&p[0]))という行が実行されます。これにより、入力バイトスライスpが直接uint32の配列として扱われ、CPUが効率的に32ビットワードをロードできるようになります。これは、バイト単位でデータを読み込むよりもはるかに高速です。 -
アラインされていない場合のフォールバック: もしアラインメントチェックが失敗した場合（つまり、入力がアラインされていない場合）、コードは
X = &xbufとj := 0のブロックにフォールバックします。このブロックでは、pのバイトデータをxbufという一時的な[16]uint32配列にバイト単位でコピーします。このコピー処理はアラインされたロードよりも遅いですが、アラインされていない入力に対しても正しく動作することを保証します。 -
ベンチマークの追加:
src/pkg/crypto/md5/md5_test.goに、アラインされていない入力に対するベンチマーク関数 (BenchmarkHash8BytesUnaligned,BenchmarkHash1KUnaligned,BenchmarkHash8KUnaligned) が追加されました。これにより、アラインメントがパフォーマンスに与える影響を定量的に評価できるようになり、最適化の効果を明確に示しています。 -
テストケースの拡張:
TestGolden関数内で、アラインされていない書き込みをテストするためのロジックが追加されました。これにより、md5.Writeがアラインされていない入力に対しても正しくハッシュ値を計算できることが保証されます。
これらの変更により、Goの crypto/md5 パッケージは、アラインされた入力に対しては最大限のパフォーマンスを発揮し、アラインされていない入力に対しても正しく、かつ合理的なパフォーマンスで動作するようになりました。ベンチマーク結果が示すように、特に大きなデータブロック（1KBや8KB）のアラインされたハッシュ計算において、大幅な速度向上が実現されています。
コアとなるコードの変更箇所
このコミットで変更された主要なファイルとコードスニペットは以下の通りです。
src/pkg/crypto/md5/gen.go および src/pkg/crypto/md5/md5block.go
これらのファイルは、MD5のコアとなる block 関数の実装を含んでいます。変更は両方のファイルで同一です。
--- a/src/pkg/crypto/md5/gen.go
+++ b/src/pkg/crypto/md5/gen.go
@@ -203,6 +203,8 @@ func block(dig *digest, p []byte) {
// less code and run 1.3x faster if we take advantage of that.\n \t\t\t// My apologies.\n \t\t\tX = (*[16]uint32)(unsafe.Pointer(&p[0]))
+\t\t} else if uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0 {
+\t\t\tX = (*[16]uint32)(unsafe.Pointer(&p[0]))
\t\t} else {
\t\t\tX = &xbuf
\t\t\tj := 0
src/pkg/crypto/md5/md5_test.go
このファイルには、MD5パッケージのテストとベンチマークが含まれています。
--- a/src/pkg/crypto/md5/md5_test.go
+++ b/src/pkg/crypto/md5/md5_test.go
@@ -9,6 +9,7 @@ import (
"fmt"
"io"
"testing"
+ "unsafe"
)
type md5Test struct {
@@ -54,13 +55,19 @@ func TestGolden(t *testing.T) {
for i := 0; i < len(golden); i++ {
g := golden[i]
c := md5.New()
- for j := 0; j < 3; j++ {
+ for j := 0; j < 3+4; j++ {
if j < 2 {
io.WriteString(c, g.in)
- } else {
+ } else if j == 2 {
io.WriteString(c, g.in[0:len(g.in)/2])
c.Sum(nil)
io.WriteString(c, g.in[len(g.in)/2:])
+ } else if j > 2 {
+ // test unaligned write
+ buf = buf[1:]
+ copy(buf, g.in)
+ c.Write(buf[:len(g.in)])
}
s := fmt.Sprintf("%x", c.Sum(nil))
if s != g.out {
@@ -80,11 +87,18 @@ func ExampleNew() {
}
var bench = md5.New()
-var buf = make([]byte, 8192)
+var buf = make([]byte, 8192+1)
+var sum = make([]byte, bench.Size())
-func benchmarkSize(b *testing.B, size int) {
+func benchmarkSize(b *testing.B, size int, unaligned bool) {
b.SetBytes(int64(size))
- sum := make([]byte, bench.Size())
+ buf := buf
+ if unaligned {
+ if uintptr(unsafe.Pointer(&buf[0]))&(unsafe.Alignof(uint32(0))-1) == 0 {
+ buf = buf[1:]
+ }
+ }
+ b.ResetTimer()
for i := 0; i < b.N; i++ {
bench.Reset()
bench.Write(buf[:size])
@@ -93,13 +107,25 @@ func benchmarkSize(b *testing.B, size int) {
}
func BenchmarkHash8Bytes(b *testing.B) {
- benchmarkSize(b, 8)
+ benchmarkSize(b, 8, false)
}
func BenchmarkHash1K(b *testing.B) {
- benchmarkSize(b, 1024)
+ benchmarkSize(b, 1024, false)
}
func BenchmarkHash8K(b *testing.B) {
- benchmarkSize(b, 8192)
+ benchmarkSize(b, 8192, false)
+}
+
+func BenchmarkHash8BytesUnaligned(b *testing.B) {
+ benchmarkSize(b, 8, true)
+}
+
+func BenchmarkHash1KUnaligned(b *testing.B) {
+ benchmarkSize(b, 1024, true)
+}
+
+func BenchmarkHash8KUnaligned(b *testing.B) {
+ benchmarkSize(b, 8192, true)
}
コアとなるコードの解説
src/pkg/crypto/md5/gen.go および src/pkg/crypto/md5/md5block.go の変更
これらのファイルにおける block 関数の変更は、MD5ハッシュ計算のパフォーマンス最適化の核心です。
// less code and run 1.3x faster if we take advantage of that.
// My apologies.
X = (*[16]uint32)(unsafe.Pointer(&p[0]))
} else if uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0 {
X = (*[16]uint32)(unsafe.Pointer(&p[0]))
} else {
X = &xbuf
j := 0
-
既存の最適化: 変更前のコードには、既に
pの長さが_BlockSize(64バイト) と等しい場合にunsafe.Pointerを使ってpを*[16]uint32に直接キャストする最適化がありました。これは、入力が64バイトブロックで、かつアラインされている場合に高速な処理を可能にするものでした。コメントにある "less code and run 1.3x faster" は、この最適化の重要性を示しています。 -
新しいアラインメントチェックと最適化:
else if uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0の行が追加されました。- これは、入力スライス
pの先頭アドレスがuint32のアラインメント要件（通常4バイト）を満たしているかどうかをチェックしています。 unsafe.Alignof(uint32(0))はuint32のアラインメント要件を返します。例えば、これが4であれば、unsafe.Alignof(uint32(0))-1は3（バイナリで0b11）になります。uintptr(unsafe.Pointer(&p[0]))はpの先頭アドレスを整数値として取得します。- このアドレス値と
(unsafe.Alignof(uint32(0))-1)のビットAND演算を行い、結果が0であれば、アドレスはuint32のアラインメント要件を満たしていることになります。例えば、アドレスが0x1000(アラインされている) であれば0x1000 & 0x3 = 0。アドレスが0x1001(アラインされていない) であれば0x1001 & 0x3 = 1となり、0以外になります。 - この条件が真の場合、つまり
pがuint32のアラインメント要件を満たしている場合、X = (*[16]uint32)(unsafe.Pointer(&p[0]))が実行されます。これにより、pのバイトデータが直接uint32の配列として扱われ、CPUが効率的に32ビットワードをロードできるようになります。これは、アラインされたデータに対する高速な処理を可能にします。
- これは、入力スライス
-
アラインされていない場合のフォールバック:
elseブロックは、入力がアラインされていない場合（または、既存のlen(p) == _BlockSizeの条件も満たさない場合）に実行されます。X = &xbufは、xbufという一時的な[16]uint32配列をMD5の内部処理で使用することを意味します。j := 0から始まる後続のコード（diffには含まれていませんが、元のコードには存在します）は、入力スライスpのバイトデータをxbufにバイト単位でコピーする処理を行います。このバイト単位のコピーは、アラインされたuint32ロードよりも遅いですが、アラインされていない入力に対しても正しく動作することを保証します。
この変更により、block 関数は入力データのアラインメント状態を動的に判断し、最適なデータアクセス方法を選択することで、パフォーマンスと堅牢性を両立させています。
src/pkg/crypto/md5/md5_test.go の変更
テストファイルでは、主にベンチマークとテストケースの拡張が行われています。
-
unsafeパッケージのインポート:import "unsafe"が追加され、アラインメント関連の操作が可能になりました。 -
TestGolden関数の変更:for j := 0; j < 3+4; j++ { if j < 2 { io.WriteString(c, g.in) } else if j == 2 { io.WriteString(c, g.in[0:len(g.in)/2]) c.Sum(nil) io.WriteString(c, g.in[len(g.in)/2:]) } else if j > 2 { // test unaligned write buf = buf[1:] copy(buf, g.in) c.Write(buf[:len(g.in)]) }ループの回数が
3から3+4に増え、j > 2の条件でアラインされていない書き込みをテストする新しいパスが追加されました。buf = buf[1:]:bufスライスの先頭を1バイトずらすことで、bufの先頭アドレスがアラインされていない状態を作り出します。copy(buf, g.in): 元の入力データをアラインされていないbufにコピーします。c.Write(buf[:len(g.in)]): アラインされていないデータを含むbufをmd5.Writeに渡してテストします。これにより、md5.Writeがアラインされていない入力に対しても正しく動作することが検証されます。
-
ベンチマーク関数の変更と追加:
var buf = make([]byte, 8192+1) // +1 for unaligned tests var sum = make([]byte, bench.Size()) func benchmarkSize(b *testing.B, size int, unaligned bool) { b.SetBytes(int64(size)) buf := buf if unaligned { if uintptr(unsafe.Pointer(&buf[0]))&(unsafe.Alignof(uint32(0))-1) == 0 { buf = buf[1:] } } b.ResetTimer() // ... (benchmarking loop) } func BenchmarkHash8Bytes(b *testing.B) { benchmarkSize(b, 8, false) } func BenchmarkHash1K(b *testing.B) { benchmarkSize(b, 1024, false) } func BenchmarkHash8K(b *testing.B) { benchmarkSize(b, 8192, false) } func BenchmarkHash8BytesUnaligned(b *testing.B) { benchmarkSize(b, 8, true) } func BenchmarkHash1KUnaligned(b *testing.B) { benchmarkSize(b, 1024, true) } func BenchmarkHash8KUnaligned(b *testing.B) { benchmarkSize(b, 8192, true) }var buf = make([]byte, 8192+1): ベンチマーク用のバッファサイズが1バイト増やされ、アラインされていないテストケースに対応できるようになりました。benchmarkSize関数にunalignedというブール型の引数が追加されました。if unalignedブロック内で、bufの先頭アドレスがuint32のアラインメント要件を満たしている場合に、buf = buf[1:]を実行して意図的にアラインされていない状態を作り出します。これにより、アラインされていない入力に対するベンチマークが可能になります。- 新しいベンチマーク関数 (
BenchmarkHash8BytesUnalignedなど) が追加され、アラインされた入力とアラインされていない入力の両方でパフォーマンスを測定できるようになりました。
これらのテストとベンチマークの追加により、MD5実装の堅牢性とパフォーマンス特性がより詳細に評価できるようになり、最適化の効果が明確に示されています。
関連リンク
- Go CL 6782072: https://golang.org/cl/6782072
参考にした情報源リンク
- Go言語の
unsafeパッケージ: - データアラインメントに関する一般的な情報:
- Go言語のベンチマーク:
- MD5アルゴリズムに関する一般的な情報:
- Dave Cheney氏のブログ (Go言語のパフォーマンスに関する記事が多い):
- https://dave.cheney.net/ (具体的な記事は特定できませんでしたが、ベンチマーク結果の提供者として言及されています)