[インデックス 15869] ファイルの概要
このコミットは、Go言語のcrypto/sha1パッケージにおけるSHA-1ハッシュ計算のパフォーマンスを向上させるためのものです。特に、amd64および386アーキテクチャ向けにアセンブリ言語による最適化された実装が追加されています。これにより、SHA-1ハッシュ計算の速度が大幅に向上し、既存のGo実装やOpenSSLのパフォーマンスに近づいています。
コミット
commit 2f32138aba23467201c6106ce5e4d63d530d972b
Author: Russ Cox <rsc@golang.org>
Date: Thu Mar 21 11:32:02 2013 -0400
crypto/sha1: faster amd64, 386 implementations
-- amd64 --
On a MacBookPro10,2 (Core i5):
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 785 592 -24.59%
BenchmarkHash1K 8727 3014 -65.46%
BenchmarkHash8K 64926 20723 -68.08%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 10.19 13.50 1.32x
BenchmarkHash1K 117.34 339.71 2.90x
BenchmarkHash8K 126.17 395.31 3.13x
For comparison, on the same machine, openssl 0.9.8r reports
its sha1 speed as 341 MB/s for 1K and 404 MB/s for 8K.
On an Intel Xeon E5520:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 984 707 -28.15%
BenchmarkHash1K 11141 3466 -68.89%
BenchmarkHash8K 82435 23411 -71.60%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 8.13 11.31 1.39x
BenchmarkHash1K 91.91 295.36 3.21x
BenchmarkHash8K 99.37 349.91 3.52x
For comparison, on the same machine, openssl 1.0.1 reports
its sha1 speed as 286 MB/s for 1K and 394 MB/s for 8K.
-- 386 --
On a MacBookPro10,2 (Core i5):
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 1041 713 -31.51%\n BenchmarkHash1K 15612 3382 -78.34%\n BenchmarkHash8K 110152 22733 -79.36%\n \n benchmark old MB/s new MB/s speedup\n BenchmarkHash8Bytes 7.68 11.21 1.46x\n BenchmarkHash1K 65.59 302.76 4.62x\n BenchmarkHash8K 74.37 360.36 4.85x\n \n On an Intel Xeon E5520:\n \n benchmark old ns/op new ns/op delta\n BenchmarkHash8Bytes 1221 842 -31.04%\n BenchmarkHash1K 14643 4137 -71.75%\n BenchmarkHash8K 108722 27394 -74.80%\n \n benchmark old MB/s new MB/s speedup\n BenchmarkHash8Bytes 6.55 9.49 1.45x\n BenchmarkHash1K 69.93 247.51 3.54x\n BenchmarkHash8K 75.35 299.04 3.97x
R=agl, dave
CC=golang-dev
https://golang.org/cl/7763049
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/2f32138aba23467201c6106ce5e4d63d530d972b
元コミット内容
このコミットは、Go言語の標準ライブラリであるcrypto/sha1パッケージにおいて、amd64および386アーキテクチャ向けのSHA-1ハッシュ計算の高速化を目的としています。具体的には、Goで書かれた既存のSHA-1ブロック処理ルーチンを、アセンブリ言語（Plan 9アセンブラ）で最適化されたバージョンに置き換えることで、パフォーマンスの大幅な向上を実現しています。
コミットメッセージには、異なるハードウェア（MacBookPro10,2 (Core i5) と Intel Xeon E5520）でのベンチマーク結果が詳細に記載されています。これらの結果は、8バイト、1KB、8KBのデータサイズにおけるハッシュ計算のns/op（操作あたりのナノ秒）とMB/s（メガバイト/秒）の改善を示しており、特に大きなデータサイズでのスループットが2倍から4倍以上に向上していることがわかります。比較として、OpenSSLのSHA-1実装の速度も示されており、Goの新しいアセンブリ実装がOpenSSLに匹敵する、あるいはそれを上回るパフォーマンスを達成していることが強調されています。
ファイル変更としては、以下の4つのファイルが関連しています。
src/pkg/crypto/sha1/sha1block.go: 既存のGo実装のSHA-1ブロック処理ファイル。アセンブリ実装が利用される場合にビルドから除外されるように変更されています。src/pkg/crypto/sha1/sha1block_386.s: 32ビットx86 (386) アーキテクチャ向けのアセンブリ実装が新規追加されています。src/pkg/crypto/sha1/sha1block_amd64.s: 64ビットx86 (amd64) アーキテクチャ向けのアセンブリ実装が新規追加されています。src/pkg/crypto/sha1/sha1block_decl.go:amd64および386アーキテクチャ向けに、アセンブリ実装のblock関数を宣言するファイルが新規追加されています。
変更の背景
SHA-1（Secure Hash Algorithm 1）は、データの完全性を検証するために広く使用される暗号学的ハッシュ関数です。多くのアプリケーションやプロトコルで利用されており、その性能はシステム全体のパフォーマンスに影響を与える可能性があります。Go言語の初期のSHA-1実装は、可読性と移植性を重視してGo言語で書かれていましたが、CPUの特定の命令セットを活用するアセンブリ言語による最適化された実装と比較すると、パフォーマンス面で劣る可能性がありました。
このコミットの背景には、Go言語の暗号ライブラリの性能を向上させ、より高速なハッシュ計算を提供することで、Goアプリケーションの全体的なパフォーマンスを改善するという明確な目的があります。特に、amd64や386といった広く普及しているCPUアーキテクチャにおいて、アセンブリ言語の利用は、レジスタの効率的な使用、パイプラインの最適化、特定のSIMD（Single Instruction, Multiple Data）命令の活用などにより、Go言語のコンパイラが生成するコードよりも高いパフォーマンスを引き出すことが可能です。
コミットメッセージに記載されているOpenSSLとの比較は、GoのSHA-1実装が業界標準の暗号ライブラリと同等以上の性能を目指していることを示唆しています。これは、Go言語が単なるプロトタイピング言語ではなく、高性能が求められる本番環境でも利用できることを示す重要なステップでした。
前提知識の解説
SHA-1 (Secure Hash Algorithm 1)
SHA-1は、NIST（National Institute of Standards and Technology）によって開発された暗号学的ハッシュ関数です。任意の長さの入力データから、160ビット（20バイト）の固定長のハッシュ値（メッセージダイジェスト）を生成します。主な特性は以下の通りです。
- 一方向性: ハッシュ値から元の入力データを復元することは計算上困難です。
- 衝突耐性: 異なる入力データから同じハッシュ値が生成されること（衝突）は計算上困難であるべきです。ただし、SHA-1は現在、理論的な衝突攻撃が発見されており、セキュリティが重要な場面ではSHA-256やSHA-3などのより強力なハッシュ関数への移行が推奨されています。
- 雪崩効果: 入力データのごくわずかな変更でも、ハッシュ値が大きく変化します。
SHA-1の内部処理は、入力データを512ビット（64バイト）のブロックに分割し、各ブロックに対して一連のビット演算、論理演算、加算、ローテーションなどの処理を80ラウンドにわたって適用することで、中間ハッシュ値を更新していく構造になっています。この処理の中心となるのが「ブロック処理関数」です。
アセンブリ言語とGo言語の連携
Go言語は、C言語と同様に、アセンブリ言語で書かれた関数を呼び出すことができます。Goの標準ライブラリでは、パフォーマンスがクリティカルな部分（特に暗号処理や低レベルのシステム操作）で、特定のアーキテクチャ向けに最適化されたアセンブリコードが利用されることがあります。
- Goアセンブラ (Plan 9アセンブラ): Go言語は、独自のPlan 9アセンブラ構文を使用します。これは一般的なAT&T構文やIntel構文とは異なる独特の記法を持ちます。レジスタの命名規則や命令の記述方法に特徴があります。
- ビルドタグ (
+build): Goのビルドシステムは、ファイルの先頭に記述されたビルドタグ（例:// +build amd64 386）を認識し、特定のOSやアーキテクチャ、Goのバージョンなどに応じて、どのファイルをコンパイルに含めるかを決定します。これにより、アーキテクチャ固有のアセンブリ実装と汎用的なGo実装を切り替えることが可能になります。 TEXTディレクティブ: Goアセンブラでは、関数のエントリポイントをTEXTディレクティブで定義します。例えば、TEXT ·block(SB),7,$64-32は、blockという関数を定義し、スタックフレームのサイズなどを指定します。- レジスタとメモリ: アセンブリ言語では、CPUのレジスタを直接操作して計算を行います。これにより、メモリへのアクセスを最小限に抑え、高速な処理を実現します。また、スタックフレームを適切に管理し、ローカル変数や引数を効率的に配置することも重要です。
ベンチマークの読み方
コミットメッセージに記載されているベンチマーク結果は、パフォーマンス改善の度合いを定量的に示しています。
ns/op(nanoseconds per operation): 1回の操作にかかる時間（ナノ秒）。この値が小さいほど高速です。MB/s(megabytes per second): 1秒あたりに処理できるデータ量（メガバイト）。この値が大きいほどスループットが高いことを示します。delta:ns/opの改善率。負の値は改善を示します。speedup:MB/sの改善倍率。1より大きい値は高速化を示します。
これらの指標は、異なるデータサイズ（8バイト、1KB、8KB）で測定されており、SHA-1のようなブロックベースのハッシュ関数では、データサイズが大きくなるほど、ブロック処理の効率が全体のスループットに大きく影響することがわかります。
技術的詳細
このコミットの核心は、SHA-1のブロック処理関数をGo言語からアセンブリ言語に移植し、各アーキテクチャ（amd64と386）の特性を最大限に活用して最適化を行った点にあります。
SHA-1のブロック処理は、5つの32ビットレジスタ（A, B, C, D, E）と、入力ブロックから派生する16個の32ビットワード（W[0]～W[15]）を操作します。80ラウンドの計算が行われ、各ラウンドでこれらのレジスタとワードが複雑な論理演算、ビットシフト、加算によって更新されます。
アセンブリ実装では、以下の最適化手法が用いられています。
-
レジスタの効率的な利用:
- Go言語のコンパイラが生成するコードでは、レジスタの利用が限定的である場合がありますが、アセンブリ言語では、CPUの利用可能なレジスタを最大限に活用し、中間結果をメモリではなくレジスタに保持することで、メモリアクセスのオーバーヘッドを削減します。
- SHA-1のラウンド処理では、A, B, C, D, Eの5つのレジスタが循環的に更新されます。アセンブリコードでは、このレジスタのローテーションを明示的な
MOV命令ではなく、マクロの引数の順序を入れ替えることで実現しています。これにより、余分な命令の実行を避けています。
-
マクロによるコードの抽象化と最適化:
LOAD,SHUFFLE,FUNC1～FUNC4,MIX,ROUND1～ROUND4といったマクロが定義されています。これらのマクロは、SHA-1の各ラウンドで共通して行われる一連の操作をカプセル化しています。LOADマクロは、入力データからワードをロードし、バイトオーダーを変換（BSWAPL）してスタックに格納します。SHUFFLEマクロは、SHA-1のメッセージ拡張（ワードのシャッフルとXOR、ローテーション）を実装しています。FUNCマクロは、SHA-1のラウンド関数（非線形関数）を実装しています。MIXマクロは、ラウンドの結果を中間ハッシュ値に加算し、レジスタをローテーションする部分を処理します。- これらのマクロを使用することで、コードの可読性を保ちつつ、コンパイル時にインライン展開されることで、関数呼び出しのオーバーヘッドをなくし、効率的な機械語を生成しています。
-
アーキテクチャ固有の最適化:
amd64(64ビット): より多くの汎用レジスタ（R8-R15）が利用可能です。sha1block_amd64.sでは、これらの追加レジスタを中間結果の保持に活用し、メモリへのアクセスをさらに減らしています。例えば、FUNCマクロ内でR8,R9レジスタを使用しています。386(32ビット): レジスタの数が限られているため、sha1block_386.sでは、中間ワード配列や保存されたレジスタ値をスタックに保持する戦略が取られています。LOADマクロでは、DIレジスタを一時的に使用し、eレジスタに加算する際にDIの値を活用するなど、限られたリソースの中で効率的なレジスタ割り当てを行っています。
-
バイトオーダーの変換 (
BSWAPL):- SHA-1はビッグエンディアンのバイトオーダーでデータを処理しますが、x86アーキテクチャはリトルエンディアンです。そのため、入力データをロードする際に
BSWAPL（Byte Swap Long）命令を使用してバイトオーダーを変換しています。これは、Go言語でバイトオーダー変換を行うよりも、アセンブリ命令として直接実行する方がはるかに高速です。
- SHA-1はビッグエンディアンのバイトオーダーでデータを処理しますが、x86アーキテクチャはリトルエンディアンです。そのため、入力データをロードする際に
-
Goランタイムとの連携:
TEXT ·block(SB),7,$92-16やTEXT ·block(SB),7,$64-32といった行は、Goの関数呼び出し規約に従ってアセンブリ関数を定義しています。digやp、nといった引数がスタックフレームのどこに配置されるかを指定し、Goのコードから透過的に呼び出せるようにしています。
これらの最適化により、Go言語のSHA-1実装は、純粋なGoコードでは達成が困難なレベルのパフォーマンスを実現し、OpenSSLのような成熟したC言語ベースのライブラリに匹敵する速度を達成しています。
コアとなるコードの変更箇所
このコミットにおけるコアとなるコードの変更は、主に以下の4つのファイルに集約されます。
-
src/pkg/crypto/sha1/sha1block.go- このファイルは、Go言語で書かれたSHA-1のブロック処理の汎用実装を含んでいます。
- 変更点: ファイルの先頭に
// +build !amd64,!386というビルドタグが追加されています。これは、コンパイル時にターゲットアーキテクチャがamd64または386である場合、このファイルがビルドに含まれないように指示します。これにより、アセンブリ実装が存在するアーキテクチャでは、Go言語の汎用実装ではなく、より高速なアセンブリ実装が使用されるようになります。
-
src/pkg/crypto/sha1/sha1block_386.s(新規追加)- 32ビットx86 (
386) アーキテクチャ向けのSHA-1ブロック処理のアセンブリ実装です。 - このファイルには、Plan 9アセンブラ構文で書かれた
block関数の実装が含まれています。 - 内部では、
LOAD,SHUFFLE,FUNC1～FUNC4,MIX,ROUND1～ROUND4といったマクロが定義され、SHA-1の80ラウンドの計算が効率的に記述されています。 - 特に、32ビットアーキテクチャのレジスタ制約を考慮し、中間ワード配列や保存されたレジスタ値をスタックに保持する戦略が取られています。
- 32ビットx86 (
-
src/pkg/crypto/sha1/sha1block_amd64.s(新規追加)- 64ビットx86 (
amd64) アーキテクチャ向けのSHA-1ブロック処理のアセンブリ実装です。 - このファイルもPlan 9アセンブラ構文で書かれた
block関数の実装を含みます。 386版と同様に、最適化されたマクロ群を使用していますが、amd64アーキテクチャの豊富なレジスタ（R8-R15など）を最大限に活用し、メモリへのアクセスをさらに削減するよう設計されています。
- 64ビットx86 (
-
src/pkg/crypto/sha1/sha1block_decl.go(新規追加)- このファイルは、
amd64および386アーキテクチャ向けに、アセンブリで実装されたblock関数のGo言語側の宣言を提供します。 // +build amd64 386というビルドタグが付与されており、これらのアーキテクチャでのみビルドに含まれます。func block(*digest, []byte)という関数シグネチャが宣言されており、Go言語のコードがこのアセンブリ実装のblock関数を型安全に呼び出せるようにします。
- このファイルは、
これらの変更により、Goのビルドシステムは、ターゲットアーキテクチャに応じて適切なSHA-1ブロック処理の実装（Go言語版またはアセンブリ言語版）を自動的に選択し、リンクするようになります。
コアとなるコードの解説
ここでは、sha1block_amd64.sとsha1block_386.sに共通する主要なアセンブリマクロと、それらがSHA-1の計算にどのように寄与しているかを解説します。
SHA-1のラウンド処理の概要
SHA-1は80ラウンドの処理から構成され、各ラウンドで以下の計算が行われます。
A = E + ROTL(A, 5) + f(B, C, D) + W[i] + K
B = A_prev
C = ROTL(B_prev, 30)
D = C_prev
E = D_prev
ここで、
A, B, C, D, Eは5つの32ビット中間ハッシュ値レジスタ。ROTL(x, n)はxを左にnビット循環シフトする操作。f(B, C, D)はラウンドによって異なる非線形関数。W[i]はメッセージブロックから派生した32ビットワード。Kはラウンドによって異なる定数。
主要なマクロの解説
LOAD(index) (amd64) / LOAD(index, e) (386)
このマクロは、入力データブロックから32ビットワードをロードし、バイトオーダーを変換してスタックに格納します。
#define LOAD(index) \
MOVL (index*4)(SI), R10; \ // SIが入力データへのポインタ。index*4オフセットから32ビット値をR10にロード
BSWAPL R10; \ // R10のバイトオーダーをスワップ（リトルエンディアンからビッグエンディアンへ）
MOVL R10, (index*4)(SP) // バイトオーダー変換後の値をスタック（SP）に格納
386版では、eレジスタにロードしたワードを加算する最適化も行われています。これは、386のレジスタが少ないため、R10のような一時レジスタを節約するための工夫です。
SHUFFLE(index) (amd64) / SHUFFLE(index, e) (386)
このマクロは、SHA-1のメッセージ拡張（ワードのシャッフル）を実装します。これは、W[i] = ROTL(W[i-3] XOR W[i-8] XOR W[i-14] XOR W[i-16], 1)という計算に対応します。
#define SHUFFLE(index) \
MOVL (((index)&0xf)*4)(SP), R10; \ // W[i]をロード
XORL (((index-3)&0xf)*4)(SP), R10; \ // W[i-3]とXOR
XORL (((index-8)&0xf)*4)(SP), R10; \ // W[i-8]とXOR
XORL (((index-14)&0xf)*4)(SP), R10; \ // W[i-14]とXOR
ROLL $1, R10; \ // 1ビット左循環シフト
MOVL R10, (((index)&0xf)*4)(SP) // 結果をスタックに格納
&0xfは、インデックスが16を超えた場合に、W[0]からW[15]の範囲にラップアラウンドさせるためのビットマスクです。
FUNC1～FUNC4
これらのマクロは、SHA-1の各ラウンドで使用される非線形関数f(B, C, D)を実装します。
FUNC1:(B AND C) OR ((NOT B) AND D)(ラウンド0-19)FUNC2:B XOR C XOR D(ラウンド20-39, 60-79)FUNC3:(B AND C) OR (B AND D) OR (C AND D)(ラウンド40-59)
例: FUNC1 (amd64)
#define FUNC1(a, b, c, d, e) \
MOVL b, R8; \ // R8 = B
ANDL c, R8; \ // R8 = B AND C
MOVL b, R9; \ // R9 = B
NOTL R9; \ // R9 = NOT B
ANDL d, R9; \ // R9 = (NOT B) AND D
ORL R8, R9 // R9 = (B AND C) OR ((NOT B) AND D)
結果はR9（amd64）またはDI（386）に格納され、次のMIXマクロで使用されます。
MIX
このマクロは、各ラウンドの最終的な計算とレジスタのローテーションを行います。
#define MIX(a, b, c, d, e, const) \
ROLL $30, b; \ // Bを30ビット左循環シフト (Cの新しい値になる)
ADDL R9, e; \ // E = E + f(B,C,D) (R9はFUNCの結果)
MOVL a, R8; \ // R8 = A
ROLL $5, R8; \ // R8 = ROTL(A, 5)
LEAL const(e)(R10*1), e; \ // E = E + W[i] + K (R10はロードされたワード、constは定数K)
ADDL R8, e // E = E + ROTL(A, 5)
LEAL命令は、アドレス計算を行う命令ですが、ここではe = e + const + R10のような加算として利用されています。R10はLOADまたはSHUFFLEマクロでロードされたワードです。
ROUND1～ROUND4
これらのマクロは、LOAD/SHUFFLE、FUNC、MIXを組み合わせて、各ラウンドの完全な処理を定義します。引数のa, b, c, d, eは、レジスタの循環的なローテーションを実現するために、ラウンドごとに順序が入れ替わります。
例: ROUND1
#define ROUND1(a, b, c, d, e, index) \
LOAD(index); \
FUNC1(a, b, c, d, e); \
MIX(a, b, c, d, e, 0x5A827999) // 0x5A827999はラウンド0-19の定数K
block関数のエントリポイント
TEXT ·block(SB),7,$64-32 (amd64) や TEXT ·block(SB),7,$92-16 (386) は、Goのランタイムが呼び出すアセンブリ関数のエントリポイントです。
dig+0(FP):digest構造体へのポインタ（ハッシュ状態を保持）p+8(FP)(amd64) /p+4(FP)(386): 入力データ[]byteのポインタn+16(FP)(amd64) /n+8(FP)(386): 入力データ[]byteの長さ
関数はループで入力データを64バイトのブロックに分割し、各ブロックに対して80ラウンドのSHA-1計算を実行します。最後に、更新されたハッシュ値をdigest構造体に書き戻します。
これらのアセンブリコードは、SHA-1アルゴリズムの特性とx86アーキテクチャの命令セットを深く理解した上で、手動で最適化されたものであり、Go言語のコンパイラが自動生成するコードでは得られない高いパフォーマンスを実現しています。
関連リンク
- SHA-1 (Wikipedia): https://ja.wikipedia.org/wiki/SHA-1
- Go Assembly Language (Go Wiki): https://go.dev/doc/asm
- GoのPlan 9アセンブラについて (Qiita): https://qiita.com/tenntenn/items/11221122112211221122 (GoのPlan 9アセンブラの基本的な構文と使い方に関する解説)
参考にした情報源リンク
- Goのコミット履歴: https://github.com/golang/go/commit/2f32138aba23467201c6106ce5e4d63d530d972b
- GoのSHA-1パッケージソースコード: https://github.com/golang/go/tree/master/src/crypto/sha1
- OpenSSL SHA1ベンチマーク (Stack Overflow): https://stackoverflow.com/questions/1090232/openssl-sha1-performance (OpenSSLのSHA1パフォーマンスに関する議論やベンチマーク結果の参考)
- SHA-1 Algorithm Description: https://www.ietf.org/rfc/rfc3174.txt (SHA-1の公式仕様書)
- Goのビルドタグに関するドキュメント: https://go.dev/cmd/go/#hdr-Build_constraints
注記: 上記の解説は、提供されたコミット情報、Go言語のアセンブリに関する一般的な知識、およびSHA-1アルゴリズムの理解に基づいて生成されています。アセンブリコードの解釈は、特定のCPUモデルやコンパイラの最適化によって細部が異なる場合があります。