Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 13126] ファイルの概要

このコミットは、Go言語の標準ライブラリ crypto/md5 パッケージにおけるMD5ハッシュ計算のパフォーマンスを大幅に向上させることを目的としています。具体的には、MD5アルゴリズムのコアとなるブロック処理の内部ループを最適化し、全体で約3倍の高速化を実現しています。この最適化は、ループアンローリングとコンパイラがより効率的なコードを生成できるようにするための変更の組み合わせによって達成されています。

コミット

commit 15436da232d83674b1e58efd6310ca38310b2dc4
Author: Russ Cox <rsc@golang.org>
Date:   Tue May 22 13:53:27 2012 -0400

    crypto/md5: faster inner loop, 3x faster overall

    The speedup is a combination of unrolling/specializing
    the actual code and also making the compiler generate better code.

    Go 1.0.1 (size: 1239 code + 320 data = 1559 total)
    md5.BenchmarkHash1K   1000000      7178 ns/op    142.64 MB/s
    md5.BenchmarkHash8K    200000     56834 ns/op    144.14 MB/s

    Partial unroll  (size: 1115 code + 256 data = 1371 total)
    md5.BenchmarkHash1K   5000000      2513 ns/op    407.37 MB/s
    md5.BenchmarkHash8K    500000     19406 ns/op    422.13 MB/s

    Complete unroll  (size: 1900 code + 0 data = 1900 code)
    md5.BenchmarkHash1K   5000000      2442 ns/op    419.18 MB/s
    md5.BenchmarkHash8K    500000     18957 ns/op    432.13 MB/s

    Comparing Go 1.0.1 and the complete unroll (this CL):

    benchmark               old MB/s     new MB/s  speedup
    md5.BenchmarkHash1K       142.64       419.18    2.94x
    md5.BenchmarkHash8K       144.14       432.13    3.00x

    On the same machine, 'openssl speed md5' reports 441 MB/s
    and 531 MB/s for our two cases, so this CL is at 90% and 80% of
    those speeds, which is at least in the right ballpark.
    OpenSSL is using carefully engineered assembly, so we are
    unlikely to catch up completely.

    Measurements on a Mid-2010 MacPro5,1.

    R=golang-dev, bradfitz, agl
    CC=golang-dev
    https://golang.org/cl/6220046

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/15436da232d83674b1e58efd6310ca38310b2dc4

元コミット内容

このコミットの元々の内容は、crypto/md5 パッケージの内部ループを高速化し、全体で3倍の性能向上を目指すものです。具体的には、コードのアンローリングと特殊化、そしてコンパイラがより良いコードを生成できるようにする変更を組み合わせることで、この高速化を実現しています。ベンチマーク結果として、Go 1.0.1と比較して、1KBおよび8KBのハッシュ計算において、それぞれ約2.94倍と3.00倍の速度向上が示されています。また、OpenSSLのMD5速度と比較しても、約80%〜90%の性能に達しており、アセンブリコードを使用するOpenSSLに迫る性能を実現していることが強調されています。

変更の背景

MD5ハッシュアルゴリズムは、データの整合性チェックやデジタル署名など、様々な場面で利用される重要な暗号学的ハッシュ関数です。Go言語の標準ライブラリとして提供される crypto/md5 パッケージは、これらの用途において高い性能が求められます。

このコミットが行われた2012年当時、Go言語はまだ比較的新しい言語であり、その性能は常に改善の対象でした。特に、暗号関連の処理は計算負荷が高く、CPUの性能を最大限に引き出すための最適化が重要視されていました。MD5のブロック処理は、ハッシュ計算の大部分を占めるため、この部分の効率化は全体の性能に直結します。

既存のMD5実装では、ブロック処理の内部ループが一般的なループ構造で記述されており、コンパイラによる最適化の余地がありました。このコミットは、ループアンローリングや、特定のアーキテクチャ（x86/amd64）でのデータアクセス最適化といった低レベルな手法を導入することで、MD5計算のボトルネックを解消し、Go言語の暗号ライブラリ全体の性能向上に貢献することを目的としています。

前提知識の解説

MD5 (Message-Digest Algorithm 5)

MD5は、128ビット（16バイト）のハッシュ値を生成する暗号学的ハッシュ関数です。任意の長さの入力データから、固定長の短いハッシュ値を生成します。このハッシュ値は、入力データが少しでも変更されると大きく変化するという特性を持ち、データの改ざん検出などに利用されます。MD5は現在、衝突攻撃（異なる入力から同じハッシュ値が生成されること）に対して脆弱であることが知られており、セキュリティが厳しく求められる場面ではSHA-256などのより強力なハッシュ関数が推奨されています。しかし、ファイルの整合性チェックなど、セキュリティ要件が比較的低い場面では依然として広く利用されています。

MD5アルゴリズムは、入力データを512ビット（64バイト）のブロックに分割し、各ブロックに対して一連の複雑なビット演算と加算を繰り返すことでハッシュ値を計算します。このブロック処理がMD5計算の「内側のループ」にあたります。

ループアンローリング (Loop Unrolling)

ループアンローリングは、プログラムの最適化手法の一つです。ループの反復回数を減らすために、ループ本体のコードを複数回コピーして展開します。例えば、10回繰り返すループがあった場合、ループ本体を2回コピーして5回繰り返すように変更することで、ループのオーバーヘッド（ループ変数のインクリメント、条件チェック、ジャンプ命令など）を削減し、命令キャッシュの効率を向上させることができます。

このコミットでは、MD5のブロック処理における16回の反復を完全にアンロールしています。これにより、ループ構造が完全に排除され、各ステップが個別の命令として記述されるため、コンパイラはより広範な最適化（レジスタ割り当ての最適化、命令スケジューリングなど）を行うことが可能になります。

unsafe パッケージ (Go言語)

Go言語の unsafe パッケージは、Goの型安全性をバイパスするための機能を提供します。通常、Goは厳格な型システムを持ち、ポインタ演算や型変換には制限があります。しかし、unsafe パッケージを使用することで、C言語のように任意のメモリ位置を指すポインタを操作したり、異なる型の間で直接メモリを共有したりすることが可能になります。

このコミットでは、unsafe.Pointer を使用して []byte 型の入力データを *[16]uint32 型に直接キャストしています。これは、MD5アルゴリズムが32ビットワードで動作するため、バイト配列から32ビット整数への変換を効率的に行うためのものです。通常、この変換はバイト単位のシフトとOR演算を繰り返すことで行われますが、unsafe.Pointer を使うことで、メモリ上のバイト列を直接32ビット整数の配列として解釈できるため、変換のオーバーヘッドを大幅に削減できます。

unsafe パッケージの使用は強力な最適化を可能にする一方で、Goの型安全性を損なうため、メモリ破壊や未定義動作を引き起こすリスクがあります。そのため、unsafe パッケージは慎重に使用し、その使用が正当化されるようなパフォーマンスがクリティカルな場面に限定されるべきです。

Goのベンチマーク

Go言語には、標準でベンチマークテストを記述・実行するための testing パッケージが用意されています。go test -bench=. コマンドを実行することで、ベンチマーク関数（Benchmark プレフィックスを持つ関数）が実行され、処理時間や1秒あたりの操作数、メモリ割り当てなどの性能指標が計測されます。このコミットでは、md5.BenchmarkHash1K と md5.BenchmarkHash8K というベンチマークが追加されており、MD5ハッシュ計算の性能改善を定量的に評価するために利用されています。

技術的詳細

このコミットの技術的詳細は、主に以下の2点に集約されます。

  1. MD5ブロック処理の完全なループアンローリングと定数化: MD5アルゴリズムのコアであるブロック処理は、4つのラウンドから構成され、各ラウンドで16回のステップが実行されます。元の実装では、これらのステップはループ内で処理されていました。このコミットでは、src/pkg/crypto/md5/gen.go という新しいGoプログラムを導入し、このプログラムが md5block.go を生成するように変更されました。 gen.go は text/template パッケージを利用して、MD5の各ステップを個別のGoのステートメントとして展開します。これにより、ループのオーバーヘッドが完全に排除され、MD5のラウンド関数内で使用されるシフト量や定数（table 配列の値）が、実行時にルックアップされるのではなく、コンパイル時にコードに直接埋め込まれるようになりました。これにより、CPUの命令キャッシュの効率が向上し、分岐予測の失敗も減少するため、実行速度が向上します。

  2. x86/amd64アーキテクチャにおける unsafe.Pointer を用いたデータ変換の最適化: MD5アルゴリズムは32ビットワードで動作しますが、入力データはバイト配列 ([]byte) として与えられます。通常、バイト配列から32ビット整数への変換は、バイト単位のシフトとOR演算を繰り返すことで行われます。

    X[i&15] = uint32(p[j]) | uint32(p[j+1])<<8 | uint32(p[j+2])<<16 | uint32(p[j+3])<<24

    しかし、x86およびamd64アーキテクチャでは、メモリ上のバイト列を直接32ビット整数として読み込むことが可能です。このコミットでは、md5block.go の _Block 関数内で、runtime.GOARCH == "amd64" || runtime.GOARCH == "386" という条件チェックを追加し、これらのアーキテクチャの場合に unsafe.Pointer を使用して入力バイト配列 p の先頭アドレスを *[16]uint32 型のポインタに直接キャストしています。

    X = (*[16]uint32)(unsafe.Pointer(&p[0]))

    これにより、バイト配列から32ビット整数への変換処理が不要になり、メモリコピーやビット操作のオーバーヘッドが削減され、特に大量のデータを処理する際に顕著なパフォーマンス向上をもたらします。コミットメッセージにも「1.3倍高速になる」と記載されており、この最適化の重要性が示されています。

これらの変更により、Goコンパイラはより最適化された機械語コードを生成できるようになり、結果としてMD5ハッシュ計算の実行速度が大幅に向上しました。

コアとなるコードの変更箇所

このコミットにおけるコアとなるコードの変更は、主に以下の3つのファイルにわたります。

  1. src/pkg/crypto/md5/gen.go (新規追加): このファイルは、MD5ブロック処理のアンロールされたコードを生成するためのGoプログラムです。text/template パッケージを使用して、MD5の各ラウンドの計算ステップをハードコードされた定数とシフト値で展開します。これにより、md5block.go が手動で記述するのではなく、自動生成されるようになります。

  2. src/pkg/crypto/md5/md5_test.go (変更): MD5ハッシュ計算の性能を測定するためのベンチマーク関数 BenchmarkHash1K と BenchmarkHash8K が追加されました。これらのベンチマークは、1KBと8KBのデータブロックに対するMD5計算速度を計測し、最適化の効果を定量的に評価するために使用されます。

  3. src/pkg/crypto/md5/md5block.go (変更): MD5ブロック処理の実際のロジックが記述されているファイルです。

    • 以前はグローバル変数として定義されていた table および shift 配列が削除されました。これらの値は gen.go によって生成されるコードに直接埋め込まれるため不要になります。
    • _Block 関数の内部が大幅に変更されました。
      • 入力バイト配列 p を uint32 の配列として扱うための X 変数の宣言が変更され、x86/amd64アーキテクチャでは unsafe.Pointer を用いて直接キャストするロジックが追加されました。
      • MD5の各ラウンド（Round 1, Round 2, Round 3, Round 4）のループが完全にアンロールされ、各ステップの計算が個別のステートメントとして記述されています。これにより、ループのオーバーヘッドが排除され、コンパイラによる最適化の機会が増大します。

コアとなるコードの解説

src/pkg/crypto/md5/gen.go の役割

gen.go は、md5block.go の中核部分を生成するメタプログラミングツールです。このプログラムは、MD5アルゴリズムの数学的な定数（Table1〜Table4）とシフト量（Shift1〜Shift4）を定義し、これらを text/template を使ってGoのソースコードに埋め込みます。

特に注目すべきは、{{if .Full}} と {{else}} ブロックです。

  • {{if .Full}} ブロックは、-full フラグが指定された場合に、MD5の各ラウンドの16ステップを完全にアンロールしたコードを生成します。例えば、Round 1の最初のステップは以下のように展開されます。 
    a += (((c ^ d) & b) ^ d) + X[0] + 3614090360
a = a<<7 | a>>(32-7) + b
    ここで、3614090360 は Table1 の最初の値 0xd76aa478 の10進数表現、7 は Shift1 の最初の値です。このように、ループ変数のインクリメントや配列のインデックス参照が不要になり、コンパイラはこれらの定数値を直接利用して効率的な機械語を生成できます。
  • {{else}} ブロックは、-full フラグがない場合に、部分的にアンロールされた（4xアンロール）コードを生成します。このコミットでは最終的に完全アンロールが採用されていますが、開発過程で様々なアンロール戦略が試されたことが伺えます。

src/pkg/crypto/md5/md5block.go の _Block 関数

_Block 関数は、MD5ハッシュ計算の主要な部分であり、512ビット（64バイト）のデータブロックを処理します。

  1. 初期状態の保存:

    aa, bb, cc, dd := a, b, c, d

    これは、現在のハッシュ状態（a, b, c, d）を一時変数に保存しています。MD5のブロック処理では、各ブロックの処理後に初期状態を最終結果に加算するため、この保存が必要です。

  2. 入力データの変換最適化:

    var X *[16]uint32
var xbuf [16]uint32
if runtime.GOARCH == "amd64" || runtime.GOARCH == "386" {
    X = (*[16]uint32)(unsafe.Pointer(&p[0]))
} else {
    X = &xbuf
    j := 0
    for i := 0; i < 16; i++ {
        X[i&15] = uint32(p[j]) | uint32(p[j+1])<<8 | uint32(p[j+2])<<16 | uint32(p[j+3])<<24
        j += 4
    }
}

    この部分が、x86/amd64アーキテクチャでのパフォーマンス向上に大きく貢献しています。

    • runtime.GOARCH をチェックし、実行環境が amd64 または 386 (x86) の場合、unsafe.Pointer を使用して入力バイトスライス p の先頭アドレスを直接 *[16]uint32 型のポインタ X にキャストします。これにより、バイト列を32ビット整数として直接アクセスできるようになり、バイトごとの変換処理が不要になります。
    • それ以外のアーキテクチャの場合（例えばARMなど）、xbuf という一時的な [16]uint32 配列に、バイト列を通常のバイト操作で32ビット整数に変換して格納します。これは、アーキテクチャによってはアラインメントの問題やエンディアンの問題があるため、安全なフォールバックとして機能します。

  3. MD5ラウンドのアンロールされた実装: md5block.go の最も大きな変更点は、MD5の4つのラウンドが、それぞれ16ステップの計算を明示的に記述したコードブロックに置き換えられていることです。例えば、Round 1の最初の数ステップは以下のようになります（gen.go によって生成されるコードの抜粋）。

    a += (((c ^ d) & b) ^ d) + X[0] + 3614090360
a = a<<7 | a>>(32-7) + b

d += (((b ^ c) & a) ^ c) + X[1] + 3905402710
d = d<<12 | d>>(32-12) + a

c += (((a ^ b) & d) ^ b) + X[2] + 606105819
c = c<<17 | c>>(32-17) + d

b += (((d ^ a) & c) ^ a) + X[3] + 3250441966
b = b<<22 | b>>(32-22) + c
// ... 続く12ステップ

    各行はMD5アルゴリズムの特定のステップに対応しており、a, b, c, d のレジスタ値が更新され、ビットシフトと加算が行われます。X[i] は入力ブロックの32ビットワード、数値定数はMD5のテーブル値です。このアンロールにより、ループ制御のオーバーヘッドがなくなり、コンパイラは各ステップを独立した命令として最適化できます。また、変数 a, b, c, d のローテーション（a, b, c, d = d, a, b, c）も、各ステップで明示的に変数を入れ替えることで、コンパイラがレジスタ割り当てをより効率的に行えるようになっています。

  4. 最終状態の更新:

    a += aa
b += bb
c += cc
d += dd

    各ブロックの処理が完了した後、初期状態 (aa, bb, cc, dd) を現在のハッシュ状態に加算し、最終的なハッシュ状態を更新します。

これらの変更により、MD5のブロック処理は、Go言語で記述されたコードとしては非常に効率的なものとなり、アセンブリ言語で最適化された実装に匹敵する性能を達成しています。

関連リンク

参考にした情報源リンク