[インデックス 15868] ファイルの概要
このコミットは、Go言語のcrypto/md5パッケージにおけるMD5ハッシュ計算のパフォーマンスを、amd64および386アーキテクチャ向けに最適化するものです。具体的には、これらのアーキテクチャに特化したアセンブリ言語実装を導入することで、特に大きなデータブロックに対するMD5計算速度を大幅に向上させています。
コミット
commit 25cbd534df4ff829dbcdb063330ce689bdbc48a9
Author: Russ Cox <rsc@golang.org>
Date: Thu Mar 21 11:26:00 2013 -0400
crypto/md5: faster amd64, 386 implementations
-- amd64 --
On a MacBookPro10,2 (Core i5):
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 471 524 +11.25%
BenchmarkHash1K 3018 2220 -26.44%
BenchmarkHash8K 20634 14604 -29.22%
BenchmarkHash8BytesUnaligned 468 523 +11.75%
BenchmarkHash1KUnaligned 3006 2212 -26.41%
BenchmarkHash8KUnaligned 20820 14652 -29.63%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 16.98 15.26 0.90x
BenchmarkHash1K 339.26 461.19 1.36x
BenchmarkHash8K 397.00 560.92 1.41x
BenchmarkHash8BytesUnaligned 17.08 15.27 0.89x
BenchmarkHash1KUnaligned 340.65 462.75 1.36x
BenchmarkHash8KUnaligned 393.45 559.08 1.42x
For comparison, on the same machine, openssl 0.9.8r reports
its md5 speed as 350 MB/s for 1K and 410 MB/s for 8K.
On an Intel Xeon E5520:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 565 607 +7.43%
BenchmarkHash1K 3753 2475 -34.05%
BenchmarkHash8K 25945 16250 -37.37%
BenchmarkHash8BytesUnaligned 559 594 +6.26%
BenchmarkHash1KUnaligned 3754 2474 -34.10%
BenchmarkHash8KUnaligned 26011 16359 -37.11%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 14.15 13.17 0.93x
BenchmarkHash1K 272.83 413.58 1.52x
BenchmarkHash8K 315.74 504.11 1.60x
BenchmarkHash8BytesUnaligned 14.31 13.46 0.94x
BenchmarkHash1KUnaligned 272.73 413.78 1.52x
BenchmarkHash8KUnaligned 314.93 500.73 1.59x
For comparison, on the same machine, openssl 1.0.1 reports
its md5 speed as 443 MB/s for 1K and 513 MB/s for 8K.
-- 386 --
On a MacBookPro10,2 (Core i5):
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 602 670 +11.30%
BenchmarkHash1K 4038 2549 -36.87%
BenchmarkHash8K 27879 16690 -40.13%
BenchmarkHash8BytesUnaligned 602 670 +11.30%
BenchmarkHash1KUnaligned 4025 2546 -36.75%
BenchmarkHash8KUnaligned 27844 16692 -40.05%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 13.28 11.93 0.90x
BenchmarkHash1K 253.58 401.69 1.58x
BenchmarkHash8K 293.83 490.81 1.67x
BenchmarkHash8BytesUnaligned 13.27 11.94 0.90x
BenchmarkHash1KUnaligned 254.40 402.05 1.58x
BenchmarkHash8KUnaligned 294.21 490.77 1.67x
On an Intel Xeon E5520:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 752 716 -4.79%
BenchmarkHash1K 5307 2799 -47.26%
BenchmarkHash8K 36993 18042 -51.23%
BenchmarkHash8BytesUnaligned 748 730 -2.41%
BenchmarkHash1KUnaligned 5301 2795 -47.27%
BenchmarkHash8KUnaligned 36983 18085 -51.10%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 10.64 11.16 1.05x
BenchmarkHash1K 192.93 365.80 1.90x
BenchmarkHash8K 221.44 454.03 2.05x
BenchmarkHash8BytesUnaligned 10.69 10.95 1.02x
BenchmarkHash1KUnaligned 193.15 366.36 1.90x
BenchmarkHash8KUnaligned 221.51 452.96 2.04x
R=agl
CC=golang-dev
https://golang.org/cl/7621049
---
src/pkg/crypto/md5/gen.go | 19 +++-
src/pkg/crypto/md5/md5block.go | 5 +
src/pkg/crypto/md5/md5block_386.s | 180 ++++++++++++++++++++++++++++++++++++\n src/pkg/crypto/md5/md5block_amd64.s | 177 +++++++++++++++++++++++++++++++++++\n src/pkg/crypto/md5/md5block_decl.go | 9 ++\n 5 files changed, 388 insertions(+), 2 deletions(-)\n
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/25cbd534df4ff829dbcdb063330ce689bdbc48a9
元コミット内容
このコミットは、Go言語の標準ライブラリであるcrypto/md5パッケージにおいて、amd64および386アーキテクチャ向けのMD5ハッシュ計算のパフォーマンスを向上させることを目的としています。ベンチマーク結果が詳細に示されており、特に1KBや8KBといった比較的大きなデータサイズでのハッシュ計算において、大幅な速度向上が達成されていることがわかります。例えば、Intel Xeon E5520環境での8KBデータのハッシュ計算では、amd64で約1.6倍、386で約2倍の速度向上が見られます。一方で、8バイトのような非常に小さなデータサイズでは、わずかに性能が低下する傾向も示されています。これは、アセンブリコードのセットアップコストが、非常に小さなデータ処理のオーバーヘッドを上回るためと考えられます。
変更の背景
MD5は広く利用されているハッシュアルゴリズムですが、その計算速度はアプリケーションのパフォーマンスに直結する重要な要素です。特に、大量のデータを処理するサーバーアプリケーションや、ファイル整合性チェックなど、MD5計算が頻繁に行われる場面では、わずかな速度向上でも全体のスループットに大きな影響を与えます。
Go言語は、その高いパフォーマンスと並行処理能力で知られていますが、特定の計算集約的な処理においては、C言語やアセンブリ言語で書かれた既存の最適化されたライブラリに劣る場合があります。MD5のような暗号学的ハッシュ関数は、ビット演算やシフト演算を多用する性質上、プロセッサのレジスタを効率的に利用し、パイプラインを最大限に活用するアセンブリ言語による最適化が非常に効果的です。
このコミットの背景には、Go言語のMD5実装が、同等のOpenSSLライブラリと比較して性能が劣るという課題があったと考えられます。ベンチマーク結果にはOpenSSLとの比較も含まれており、この最適化によってOpenSSLの性能に近づく、あるいは一部で上回ることを目指していることが示唆されます。
また、amd64と386という特定のアーキテクチャに焦点を当てているのは、これらがサーバーやデスクトップ環境で最も普及しているCPUアーキテクチャであるため、これらの環境での性能向上が最も広範なユーザーに利益をもたらすと判断されたためでしょう。
前提知識の解説
MD5 (Message-Digest Algorithm 5)
MD5は、128ビット（16バイト）のハッシュ値を生成する暗号学的ハッシュ関数です。入力データがわずかでも異なると、出力されるハッシュ値は大きく変化するという性質（雪崩効果）を持ちます。主にデータの完全性チェックやデジタル署名などに利用されてきましたが、2004年以降、衝突攻撃（異なる入力から同じハッシュ値が生成されること）の脆弱性が発見されたため、セキュリティが要求される場面での利用は推奨されていません。しかし、非暗号学的な用途（例：ファイルの重複チェック）では依然として広く使われています。
MD5の計算プロセスは、入力データを512ビット（64バイト）のブロックに分割し、各ブロックに対して一連の複雑なビット演算と加算を繰り返すことでハッシュ値を更新していきます。このプロセスは4つのラウンドから構成され、各ラウンドで異なる非線形関数（F, G, H, I）が使用されます。
アセンブリ言語
アセンブリ言語は、CPUが直接実行できる機械語と1対1に対応する低水準プログラミング言語です。C言語などの高水準言語と比較して、プロセッサのレジスタ、メモリ、命令セットを直接制御できるため、極めて高速で効率的なコードを記述することが可能です。しかし、特定のCPUアーキテクチャに依存し、可読性が低く、開発に手間がかかるという欠点があります。パフォーマンスが最優先される暗号処理、OSカーネル、デバイスドライバなどの分野で利用されます。
x86/amd64 アーキテクチャ
- x86 (386): Intel 80386プロセッサから始まる32ビット命令セットアーキテクチャの総称です。WindowsやLinuxなどの主要なOSで広く採用されてきました。
- amd64 (x86-64): AMDが開発し、後にIntelも採用した64ビット命令セットアーキテクチャです。x86の32ビット命令セットとの互換性を保ちつつ、64ビットのレジスタとアドレス空間を提供し、より大量のメモリを扱えるようになりました。現代のほとんどのデスクトップPCやサーバーで採用されています。
これらのアーキテクチャは、リトルエンディアン（Little-Endian）方式を採用しています。
エンディアンネス (Endianness)
エンディアンネスは、複数バイトで構成されるデータをメモリに格納する際のバイト順序を指します。
- リトルエンディアン (Little-Endian): 最下位バイト（Least Significant Byte, LSB）が最も小さいアドレスに格納されます。x86およびamd64アーキテクチャで採用されています。
- ビッグエンディアン (Big-Endian): 最上位バイト（Most Significant Byte, MSB）が最も小さいアドレスに格納されます。ネットワークプロトコルや一部のプロセッサ（例：PowerPC）で採用されています。
MD5は32ビットのワードをリトルエンディアンで処理するように設計されているため、リトルエンディアンのx86/amd64プロセッサでは、バイト順序の変換が不要となり、効率的な処理が可能です。
アラインメント (Alignment)
メモリのアラインメントとは、データがメモリ上で特定のバイト境界に配置されることを指します。例えば、4バイトの整数が4の倍数のアドレスに配置される場合、そのデータは4バイトアラインされていると言います。CPUはアラインされたデータへのアクセスを高速に行うことができますが、アラインされていないデータへのアクセスは、パフォーマンスが低下したり、場合によってはエラーになったりすることがあります。
コミットメッセージのベンチマーク結果にはUnalignedという項目があり、これは入力データがアラインされていない場合の性能を示しています。アセンブリによる最適化は、アラインされていないデータに対しても効率的に動作するように設計されていることが重要です。
ベンチマーク指標
- ns/op (nanoseconds per operation): 1回の操作にかかるナノ秒。値が小さいほど高速。
- MB/s (megabytes per second): 1秒あたりに処理できるメガバイト数。値が大きいほど高速。
- speedup: 速度向上率。
new MB/s / old MB/sで計算され、1より大きいほど高速化。 - delta: 性能変化率。
((new - old) / old) * 100%で計算され、負の値は高速化、正の値は低速化。
技術的詳細
このコミットの主要な技術的アプローチは、MD5のコア計算ロジックをGo言語のコードからアセンブリ言語（Goのアセンブリシンタックス）に移植することです。これにより、コンパイラによる最適化の限界を超え、プロセッサの特性を最大限に引き出すことが可能になります。
具体的には、以下の点が最適化のポイントとなります。
- レジスタの効率的な利用: アセンブリ言語では、MD5計算に必要な中間値をCPUのレジスタに保持し、メモリへのアクセスを最小限に抑えることができます。メモリアクセスはCPUのレジスタアクセスに比べてはるかに遅いため、これにより大幅な速度向上が期待できます。
- 命令レベルの並列性 (Instruction-Level Parallelism, ILP): 現代のCPUは、複数の命令を同時に実行できるスーパースケーラアーキテクチャを採用しています。アセンブリ言語では、命令の順序を慎重に調整することで、CPUの実行ユニットを最大限に活用し、パイプラインストール（処理の停滞）を減らすことができます。MD5の各ラウンドの計算は、独立した部分が少ないため、ILPを最大限に引き出すには熟練したアセンブリプログラミングが必要です。
- MD5のラウンド関数の最適化:
- MD5の各ラウンドで使用される非線形関数（F, G, H, I）は、ビット演算の組み合わせです。アセンブリでは、これらの関数を最も効率的な命令シーケンスで実装できます。例えば、
md5-amd64.htmlで言及されているように、F関数は((y XOR z) AND x) XOR z、G関数は(x AND z) OR (y AND NOT(z))といった形式が、特定のアーキテクチャで効率的であることが知られています。 - 特に、
ROUND1,ROUND2,ROUND3,ROUND4といったマクロが定義されており、これらがMD5の各ステップの計算をカプセル化しています。これらのマクロ内部では、XORL,LEAL,ANDL,ADDL,ROLLなどのx86/amd64命令が使用され、効率的なビット演算と加算、ローテート（循環シフト）が実現されています。
- MD5の各ラウンドで使用される非線形関数（F, G, H, I）は、ビット演算の組み合わせです。アセンブリでは、これらの関数を最も効率的な命令シーケンスで実装できます。例えば、
- データのアラインメントとリトルエンディアンの活用:
- x86/amd64アーキテクチャはリトルエンディアンであるため、MD5の入力データ（32ビットワード）をメモリから直接読み込む際にバイト順序の変換が不要です。アセンブリコードでは、この特性を最大限に活用し、メモリから直接
uint32としてデータを読み込むことで、余分な処理を省いています。 gen.goの変更点を見ると、unsafe.Pointerを使ってバイトスライスpを*[16]uint32にキャストしています。これは、pがMD5のブロックサイズ（64バイト）であり、その内容を16個のuint32の配列として直接扱うことを意図しています。この操作は、メモリのアラインメントが適切である場合にのみ安全かつ効率的です。littleEndian変数の導入により、実行時にシステムのエンディアンネスをチェックし、リトルエンディアンでない場合は通常のバイト操作にフォールバックするロジックが追加されています。これにより、アセンブリコードが特定のエンディアンネスに依存する問題を回避し、ポータビリティを確保しています。
- x86/amd64アーキテクチャはリトルエンディアンであるため、MD5の入力データ（32ビットワード）をメモリから直接読み込む際にバイト順序の変換が不要です。アセンブリコードでは、この特性を最大限に活用し、メモリから直接
- Goアセンブリシンタックス: Go言語は独自のPlan 9アセンブラシンタックスを使用しており、一般的なGAS (GNU Assembler) シンタックスとは異なります。このコミットで追加された
md5block_386.sとmd5block_amd64.sは、このGoアセンブリシンタックスで記述されています。
ベンチマーク結果を見ると、8バイトのような非常に小さなデータサイズでは性能がわずかに低下していますが、これはアセンブリコードの呼び出しやセットアップにかかるオーバーヘッドが、実際のMD5計算時間よりも大きくなるためと考えられます。しかし、1KBや8KBといった実用的なサイズのデータでは、アセンブリによる最適化の恩恵が大きく、大幅な速度向上が達成されています。これは、MD5がブロック単位で処理を行うため、ブロックサイズが大きくなるほどアセンブリによる最適化の効果が顕著になることを示しています。
コアとなるコードの変更箇所
このコミットでは、以下の5つのファイルが変更されています。
src/pkg/crypto/md5/gen.go:- MD5のブロック処理を行う
block関数のGo言語実装が含まれています。 amd64または386アーキテクチャの場合に、アセンブリ実装を利用するための条件分岐が追加されました。x86定数とlittleEndian変数が導入され、実行時のアーキテクチャとエンディアンネスをチェックするロジックが追加されました。md5block.goを生成するためのコメントが追加されています。
- MD5のブロック処理を行う
src/pkg/crypto/md5/md5block.go:gen.goから生成されるファイルで、Go言語によるMD5ブロック処理のフォールバック実装が含まれています。+build !amd64,!386というビルドタグが追加され、amd64および386以外のアーキテクチャでのみこのファイルがコンパイルされるように変更されました。これにより、特定のアーキテクチャではアセンブリ実装が優先されます。
src/pkg/crypto/md5/md5block_386.s:- 新規追加されたファイル。32ビットx86 (
386) アーキテクチャ向けのMD5ブロック処理のアセンブリ言語実装です。 ROUND1,ROUND2,ROUND3,ROUND4といったマクロが定義され、MD5の各ラウンドの計算ステップを効率的に実行するx86アセンブリ命令が含まれています。
- 新規追加されたファイル。32ビットx86 (
src/pkg/crypto/md5/md5block_amd64.s:- 新規追加されたファイル。64ビットx86 (
amd64) アーキテクチャ向けのMD5ブロック処理のアセンブリ言語実装です。 md5block_386.sと同様に、MD5の各ラウンドを最適化されたamd64アセンブリ命令で実装しています。レジスタの利用方法などが64ビットアーキテクチャ向けに調整されています。
- 新規追加されたファイル。64ビットx86 (
src/pkg/crypto/md5/md5block_decl.go:- 新規追加されたファイル。
amd64および386アーキテクチャ向けに、アセンブリで実装されたblock関数のGo言語側の宣言（シグネチャ）を提供します。 +build amd64 386というビルドタグが追加され、これらのアーキテクチャでのみこのファイルがコンパイルされるように指定されています。
- 新規追加されたファイル。
コアとなるコードの解説
src/pkg/crypto/md5/gen.go の変更点
// +build !amd64
package md5
import (
"runtime"
"unsafe"
)
// ... (既存コード) ...
const x86 = runtime.GOARCH == "amd64" || runtime.GOARCH == "386"
var littleEndian bool
func init() {
x := uint32(0x04030201)
y := [4]byte{0x1, 0x2, 0x3, 0x4}
littleEndian = *(*[4]byte)(unsafe.Pointer(&x)) == y
}
func block(dig *digest, p []byte) {
a := dig.s[0]
b := dig.s[1]
c := dig.s[2]
d := dig.s[3]
aa, bb, cc, dd := a, b, c, d
// This is a constant condition - it is not evaluated on each iteration.
if x86 { // 変更前: if runtime.GOARCH == "amd64" || runtime.GOARCH == "386" {
// MD5 was designed so that x86 processors can just iterate
// over the block data directly as uint32s, and we generate
// less code and run 1.3x faster if we take advantage of that.
// My apologies.
X = (*[16]uint32)(unsafe.Pointer(&p[0]))
} else if littleEndian && uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0 { // 変更前: else if uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0 {
X = (*[16]uint32)(unsafe.Pointer(&p[0]))
} else {
X = &xbuf
// ... (既存コード) ...
}
// ... (既存コード) ...
}
- ビルドタグの変更:
// +build !amd64が// +build !amd64,!386に変更され、md5block.goがamd64と386以外のアーキテクチャでコンパイルされるように制御されています。これにより、amd64と386ではアセンブリ実装が優先されます。 x86定数:runtime.GOARCH == "amd64" || runtime.GOARCH == "386"という条件をx86という定数にまとめることで、コードの可読性を向上させています。この条件はコンパイル時に評価されるため、実行時のオーバーヘッドはありません。littleEndian変数とinit関数:littleEndianは、現在のシステムがリトルエンディアンであるかどうかを示すブール変数です。init関数は、パッケージが初期化される際に一度だけ実行されます。この中で、uint32(0x04030201)という値を[4]byteにキャストし、そのバイト順序が{0x1, 0x2, 0x3, 0x4}と一致するかどうかをチェックすることで、システムのエンディアンネスを判定しています。これは、リトルエンディアンのシステムでは0x04030201がメモリ上で01 02 03 04と格納されるためです。
block関数の条件分岐:if x86 { ... }のブロックは、amd64または386アーキテクチャの場合に実行されます。この場合、入力バイトスライスpの先頭アドレスを直接*[16]uint32にキャストし、MD5の入力ブロックとして扱います。これは、x86系プロセッサがリトルエンディアンであり、MD5の入力形式と一致するため、バイト順序の変換が不要で高速に処理できるためです。else if littleEndian && uintptr(unsafe.Pointer(&p[0]))&(unsafe.Alignof(uint32(0))-1) == 0 { ... }のブロックは、システムがリトルエンディアンであり、かつ入力データがuint32の境界にアラインされている場合に実行されます。この場合も、直接*[16]uint32にキャストして処理します。- それ以外の場合（ビッグエンディアン、またはアラインされていない場合）は、
xbufというバッファにデータをコピーしてから処理を行うフォールバックロジックが実行されます。
src/pkg/crypto/md5/md5block_386.s および src/pkg/crypto/md5/md5block_amd64.s
これらのファイルは、MD5のコア計算ロジックをアセンブリ言語で実装しています。Goのアセンブリシンタックスは、Plan 9アセンブラに基づいています。
TEXT ·block(SB),7,$24-16(386) /TEXT ·block(SB),7,$0-32(amd64):TEXTは関数の開始を宣言します。·block(SB)は、md5パッケージのblock関数を指します。SBはスタティックベースレジスタで、グローバルシンボルを参照するために使われます。7はフラグで、ここではスタックフレームのサイズに関する情報を含みます。$24-16(386) や$0-32(amd64) は、スタックフレームのサイズと引数のサイズを示します。
- レジスタの利用:
MOVL(Move Long) やMOVQ(Move Quad) 命令を使って、MD5の内部状態変数（A, B, C, D）や入力データへのポインタをレジスタ（AX, BX, CX, DX, SI, DIなど）にロードしています。amd64版では、より多くの汎用レジスタ（R8, R9, R10, R12, R13, R14, R15など）が利用可能であるため、これらを効率的に活用して中間値を保持し、メモリへのアクセスをさらに減らしています。
ROUND1,ROUND2,ROUND3,ROUND4マクロ:- これらのマクロは、MD5の各ラウンドの1ステップを構成する一連のアセンブリ命令を定義しています。
- 例えば、
ROUND1マクロは、MD5のF関数（(b AND c) OR (NOT b AND d)）に相当するビット演算と、定数の加算、循環シフト（ROLL）、そして次のステップへの準備を行います。 XORL,ANDL,ORL,ADDL,ROLLなどの命令が、MD5のビット演算と加算、ローテートを直接CPUレベルで実行します。LEAL(Load Effective Address) 命令は、アドレス計算の結果をレジスタに格納する命令ですが、ここではアドレス計算の副作用を利用して、複数の加算やシフトを1つの命令で効率的に行うテクニックとして使われています。
- ループ処理:
loop:ラベルとCMPL/CMPQ、JB(Jump Below) 命令を使って、入力データブロックを64バイトずつ処理するループを実装しています。
- 結果の保存:
- ループが終了した後、最終的なMD5ハッシュの状態変数（A, B, C, D）をメモリ（
digポインタが指すdigest構造体）に書き戻し、RET命令で関数から戻ります。
- ループが終了した後、最終的なMD5ハッシュの状態変数（A, B, C, D）をメモリ（
src/pkg/crypto/md5/md5block_decl.go
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// +build amd64 386
package md5
func block(dig *digest, p []byte)
- ビルドタグ:
// +build amd64 386は、このファイルがamd64または386アーキテクチャでビルドされる場合にのみコンパイルされることを示します。 - 関数宣言:
func block(dig *digest, p []byte)は、アセンブリで実装されたblock関数のGo言語側の宣言です。これにより、Go言語のコードからこのアセンブリ関数を呼び出すことが可能になります。実際の関数本体は.sファイルに記述されているため、ここでは本体は持ちません。
これらの変更により、Go言語のMD5実装は、特定のCPUアーキテクチャの特性を最大限に活用し、大幅なパフォーマンス向上を実現しています。特に、大量のデータに対するハッシュ計算において、その効果は顕著です。