[インデックス 17970] ファイルの概要
このコミットは、Go言語のcrypto/sha1パッケージにおけるSHA-1ハッシュアルゴリズムの実装に関するパフォーマンス最適化を目的としています。具体的には、SHA-1アルゴリズム内で使用される関数の一つであるFUNC1の計算式を、より効率的な代替形式に変更することで、全体的なハッシュ計算速度を向上させています。
コミット
commit 107d18299cb6e222ec26f86a28a4454dc1eb8888
Author: Nick Craig-Wood <nick@craig-wood.com>
Date: Thu Dec 12 11:26:36 2013 -0800
crypto/sha1: Optimise FUNC1 with alternate formulation
According to Wikipedia: http://en.wikipedia.org/wiki/SHA-1
there is an alternate formulation for the FUNC1 transform,
namely
f1 = d xor (b and (c xor d))
instead of
f1 = (b and c) or ((not b) and d)
This reduces the instruction count of FUNC1 from 6 to 4 and
makes about 5% speed improvement on amd64 and suprisingly 17%
on 386.
amd64 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 506 499 -1.38%
BenchmarkHash1K 3099 2961 -4.45%
BenchmarkHash8K 22292 21243 -4.71%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 15.80 16.00 1.01x
BenchmarkHash1K 330.40 345.82 1.05x
BenchmarkHash8K 367.48 385.63 1.05x
i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz:
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 647 615 -4.95%
BenchmarkHash1K 3673 3161 -13.94%
BenchmarkHash8K 26141 22374 -14.41%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 12.35 13.01 1.05x
BenchmarkHash1K 278.74 323.94 1.16x
BenchmarkHash8K 313.37 366.13 1.17x
The improvements on an Intel(R) Core(TM) i7-4770K CPU @
3.50GHz were almost identical.
R=golang-dev, r, hanwen
CC=golang-dev, rsc
https://golang.org/cl/19910043
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/107d18299cb6e222ec26f86a28a4454dc1eb8888
元コミット内容
crypto/sha1: FUNC1を代替の定式化で最適化
Wikipediaによると、SHA-1の変換関数FUNC1には代替の定式化が存在します。
元の形式: f1 = (b and c) or ((not b) and d)
代替形式: f1 = d xor (b and (c xor d))
この変更により、FUNC1の命令数が6から4に削減され、amd64アーキテクチャで約5%、386アーキテクチャでは驚くべきことに17%の速度向上が見られました。
ベンチマーク結果（amd64 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz）:
BenchmarkHash8Bytes: 1.38%高速化BenchmarkHash1K: 4.45%高速化BenchmarkHash8K: 4.71%高速化- スループットも向上（1.01x〜1.05x）
ベンチマーク結果（i386 Intel(R) Core(TM) i7 CPU Q 820 @ 1.73GHz）:
BenchmarkHash8Bytes: 4.95%高速化BenchmarkHash1K: 13.94%高速化BenchmarkHash8K: 14.41%高速化- スループットも大幅に向上（1.05x〜1.17x）
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHzでの改善もほぼ同様でした。
変更の背景
このコミットの主な背景は、SHA-1ハッシュアルゴリズムのパフォーマンスを向上させることです。SHA-1は、データの完全性検証やデジタル署名など、様々なセキュリティ関連の用途で広く利用される暗号学的ハッシュ関数です。そのため、その計算速度は、システム全体のパフォーマンスに直接影響を与えます。
SHA-1アルゴリズムは、内部で複数の論理関数（FUNC1からFUNC4）を繰り返し適用してハッシュ値を計算します。これらの関数は、ビット単位のAND、OR、XOR、NOTといった基本的な論理演算を組み合わせたものです。コミットメッセージにあるように、FUNC1の既存の実装が、より効率的な代替形式に置き換えられる可能性があることが発見されました。この代替形式は、論理的に等価でありながら、CPUが実行するアセンブリ命令の数を削減できるため、計算コストを低減できます。
特に、Go言語のcrypto/sha1パッケージは、GoプログラムがSHA-1ハッシュを生成する際に利用される標準ライブラリの一部です。このパッケージのパフォーマンス改善は、Go言語を使用する多くのアプリケーションに恩恵をもたらします。ベンチマーク結果が示すように、特に386アーキテクチャ（32ビットシステム）での改善が顕著であり、これはリソースが限られた環境や古いシステムでのパフォーマンス向上に寄与します。
前提知識の解説
SHA-1 (Secure Hash Algorithm 1)
SHA-1は、アメリカ国家安全保障局（NSA）によって設計された暗号学的ハッシュ関数です。任意の長さの入力データから、160ビット（20バイト）の固定長のハッシュ値（メッセージダイジェスト）を生成します。このハッシュ値は、入力データが少しでも変更されると大きく変化するという特性（雪崩効果）を持ち、データの改ざん検出に利用されます。
SHA-1の基本的な処理は、入力メッセージを512ビット（64バイト）のブロックに分割し、各ブロックに対して圧縮関数を適用していくことで行われます。圧縮関数は、80ラウンドの処理から構成され、各ラウンドでビット単位の論理演算とビットシフト、加算が行われます。
SHA-1のラウンド関数とFUNC1
SHA-1の80ラウンドは、大きく4つのフェーズに分けられ、それぞれのフェーズで異なる論理関数が使用されます。
- ラウンド 0-19:
FUNC1(B, C, D) = (B AND C) OR ((NOT B) AND D) - ラウンド 20-39:
FUNC2(B, C, D) = B XOR C XOR D - ラウンド 40-59:
FUNC3(B, C, D) = (B AND C) OR (B AND D) OR (C AND D) - ラウンド 60-79:
FUNC4(B, C, D) = B XOR C XOR D
このコミットで最適化の対象となっているのは、最初の20ラウンドで使用されるFUNC1です。この関数は、3つの入力変数B, C, Dに対してビット単位のAND、OR、NOT演算を組み合わせて結果を生成します。
論理演算の等価性
論理演算には、同じ結果をもたらす複数の表現方法が存在します。例えば、ブール代数の法則（ド・モルガンの法則、分配法則など）を利用することで、ある論理式を別の論理式に変換できます。このコミットでは、FUNC1の元の形式と代替形式が論理的に等価であることが重要です。
- 元の形式:
(B AND C) OR ((NOT B) AND D) - 代替形式:
D XOR (B AND (C XOR D))
これらの式が等価であることは、真理値表を作成するか、ブール代数の法則を適用することで証明できます。この等価性を利用することで、計算結果を変えずに、より少ないCPU命令で同じ処理を実行することが可能になります。
アセンブリ言語とパフォーマンス最適化
Go言語の標準ライブラリには、パフォーマンスが重要な部分でアセンブリ言語が使用されることがあります。特に、暗号化アルゴリズムのような計算負荷の高い処理では、C言語やGo言語で書かれたコードよりも、特定アーキテクチャ向けに最適化されたアセンブリコードの方が高速に動作する場合があります。
アセンブリ言語では、CPUのレジスタ操作や命令実行を直接制御できるため、コンパイラが生成するコードよりも効率的なコードを書くことが可能です。このコミットでは、sha1block_386.s（32ビットIntel/AMDアーキテクチャ向け）とsha1block_amd64.s（64ビットIntel/AMDアーキテクチャ向け）というアセンブリファイルが変更されています。これらのファイルは、SHA-1のブロック処理の中核部分をアセンブリで実装しており、FUNC1の最適化が直接的にパフォーマンスに影響を与えます。
命令数の削減は、CPUのサイクル数を減らし、結果として処理時間を短縮します。特に、SHA-1のように同じ関数が何十回も繰り返し呼び出されるアルゴリズムでは、わずかな命令数の削減でも全体として大きなパフォーマンス向上につながります。
技術的詳細
このコミットの核心は、SHA-1アルゴリズムの内部で使用されるFUNC1関数の論理式を、より効率的な形式に置き換えることです。
元のFUNC1の論理式:
f1 = (b AND c) OR ((NOT b) AND d)
この式は、ブール代数における「条件付き選択」のような振る舞いをします。もしbが真（1）ならばcを、bが偽（0）ならばdを選択する、というように解釈できます。
代替のFUNC1の論理式:
f1 = d XOR (b AND (c XOR d))
この代替形式は、WikipediaのSHA-1のページで言及されているものです。この式が元の式と論理的に等価であることは、真理値表で確認できます。
| b | c | d | (b AND c) | (NOT b) | ((NOT b) AND d) | (b AND c) OR ((NOT b) AND d) (元の f1) | (c XOR d) | (b AND (c XOR d)) | d XOR (b AND (c XOR d)) (代替の f1) |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
真理値表から、両方のf1の列が完全に一致していることがわかります。これにより、両方の式が論理的に等価であることが証明されます。
この論理式の変更がパフォーマンスに与える影響は、アセンブリ命令レベルで現れます。
元の実装（擬似アセンブリ）:
MOVL b, SI(SI = b)ANDL c, SI(SI = b AND c)MOVL b, DI(DI = b)NOTL DI(DI = NOT b)ANDL d, DI(DI = (NOT b) AND d)ORL SI, DI(DI = (b AND c) OR ((NOT b) AND d)) 合計6命令
新しい実装（擬似アセンブリ）:
MOVL d, DI(DI = d)XORL c, DI(DI = c XOR d)ANDL b, DI(DI = b AND (c XOR d))XORL d, DI(DI = d XOR (b AND (c XOR d))) 合計4命令
命令数が6から4に削減されることで、CPUの実行サイクルが減少し、結果としてSHA-1ハッシュ計算の速度が向上します。特に、SHA-1の圧縮関数は80ラウンドあり、そのうち20ラウンドでFUNC1が使用されるため、この小さな最適化が全体として大きな影響を与えます。
ベンチマーク結果は、この最適化が特に32ビットシステム（i386）で顕著な効果をもたらしたことを示しています。これは、32ビットアーキテクチャではレジスタの数が限られている、あるいは特定の命令のレイテンシが異なるなどの要因が影響している可能性があります。64ビットアーキテクチャ（amd64）でも改善が見られ、この変更が幅広い環境で有効であることが確認されました。
コアとなるコードの変更箇所
変更は、Go言語のcrypto/sha1パッケージ内のアセンブリファイルに集中しています。具体的には、32ビットアーキテクチャ向けのsrc/pkg/crypto/sha1/sha1block_386.sと、64ビットアーキテクチャ向けのsrc/pkg/crypto/sha1/sha1block_amd64.sの2つのファイルです。
これらのファイルは、SHA-1のブロック処理（特に圧縮関数）をアセンブリ言語で実装しており、パフォーマンスが非常に重要な部分です。変更は、FUNC1マクロの定義部分にあります。
src/pkg/crypto/sha1/sha1block_386.sの変更
--- a/src/pkg/crypto/sha1/sha1block_386.s
+++ b/src/pkg/crypto/sha1/sha1block_386.s
@@ -46,12 +46,10 @@
ADDL DI, e
#define FUNC1(a, b, c, d, e) \
- MOVL b, SI; \
- ANDL c, SI; \
- MOVL b, DI; \
- NOTL DI; \
- ANDL d, DI; \
- ORL SI, DI
+ MOVL d, DI; \
+ XORL c, DI; \
+ ANDL b, DI; \
+ XORL d, DI
#define FUNC2(a, b, c, d, e) \
MOVL b, DI; \
src/pkg/crypto/sha1/sha1block_amd64.sの変更
--- a/src/pkg/crypto/sha1/sha1block_amd64.s
+++ b/src/pkg/crypto/sha1/sha1block_amd64.s
@@ -34,12 +34,10 @@
MOVL R10, (((index)&0xf)*4)(SP)
#define FUNC1(a, b, c, d, e) \
- MOVL b, R8; \
- ANDL c, R8; \
- MOVL b, R9; \
- NOTL R9; \
- ANDL d, R9; \
- ORL R8, R9
+ MOVL d, R9; \
+ XORL c, R9; \
+ ANDL b, R9; \
+ XORL d, R9
#define FUNC2(a, b, c, d, e) \
MOVL b, R9; \
コアとなるコードの解説
両方のアセンブリファイルにおいて、FUNC1マクロの定義が変更されています。このマクロは、SHA-1のメインループ内で繰り返し呼び出され、b, c, dという3つの入力レジスタ（または変数）に対してビット演算を実行し、結果を生成します。
変更前 (sha1block_386.sの例)
#define FUNC1(a, b, c, d, e) \
MOVL b, SI; \ // SI = b
ANDL c, SI; \ // SI = b AND c
MOVL b, DI; \ // DI = b
NOTL DI; \ // DI = NOT b
ANDL d, DI; \ // DI = (NOT b) AND d
ORL SI, DI // DI = (b AND c) OR ((NOT b) AND d)
このコードは、元の論理式 (b AND c) OR ((NOT b) AND d) を直接アセンブリ命令に変換しています。
MOVL b, SI; ANDL c, SI;でb AND cを計算し、結果をSIレジスタに格納。MOVL b, DI; NOTL DI; ANDL d, DI;で(NOT b) AND dを計算し、結果をDIレジスタに格納。- 最後に
ORL SI, DIで両方の結果をOR演算し、最終的なFUNC1の結果をDIレジスタに格納しています。 合計6つの命令が使用されています。
変更後 (sha1block_386.sの例)
#define FUNC1(a, b, c, d, e) \
MOVL d, DI; \ // DI = d
XORL c, DI; \ // DI = c XOR d
ANDL b, DI; \ // DI = b AND (c XOR d)
XORL d, DI // DI = d XOR (b AND (c XOR d))
この新しいコードは、代替の論理式 d XOR (b AND (c XOR d)) をアセンブリ命令に変換しています。
MOVL d, DI; XORL c, DI;でc XOR dを計算し、結果をDIレジスタに格納。ANDL b, DI;でb AND (c XOR d)を計算し、結果をDIレジスタに格納。- 最後に
XORL d, DIでdと現在のDIの内容をXOR演算し、最終的なFUNC1の結果をDIレジスタに格納しています。 合計4つの命令で同じ論理演算が実現されています。
レジスタの使用
sha1block_386.sでは、SIとDIレジスタが一時的な計算に使用されています。sha1block_amd64.sでは、R8とR9レジスタが同様の目的で使用されています。これは、amd64アーキテクチャがより多くの汎用レジスタを持つためです。
どちらのアーキテクチャでも、命令数が削減され、より効率的なコードが生成されています。この変更は、SHA-1の計算ボトルネックの一つを解消し、特にCPUバウンドなアプリケーションにおいて顕著なパフォーマンス向上をもたらします。
関連リンク
- GitHubコミットページ: https://github.com/golang/go/commit/107d18299cb6e222ec26f86a28a4454dc1eb8888
- Go CL (Change List): https://golang.org/cl/19910043
- Wikipedia - SHA-1: http://en.wikipedia.org/wiki/SHA-1 (特に「Comparison of functions」セクションで異なる論理関数形式が言及されています)
参考にした情報源リンク
- 上記の「関連リンク」セクションに記載されたGitHubコミットページ、Go CL、WikipediaのSHA-1ページ。
- SHA-1アルゴリズムに関する一般的な知識。
- アセンブリ言語（x86/x64）の基本的な命令セットに関する知識。
- ブール代数と論理演算の等価性に関する知識。
- Go言語の標準ライブラリにおけるアセンブリコードの利用に関する一般的な理解。