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

このコミットは、Go言語の標準ライブラリ crypto/aes パッケージにおけるAES暗号化・復号処理のパフォーマンス改善を目的としています。具体的には、AESアルゴリズム内で使用されるルックアップテーブルのデータ構造を変更し、アクセス時の間接参照を排除することで、処理速度の向上を図っています。

コミット

commit a620f2b73ab1642fcd53fcc9cc5ada31ebdae455
Author: Taru Karttunen <taruti@taruti.net>
Date:   Mon Dec 12 09:58:04 2011 -0500

    crypto/aes: Made faster by eliminating some indirection
    
    Made te and td arrays into variables te0-3 and td0-3,
    which improves performance from 7000ns/op to 5800.
    
    R=rsc, rogpeppe, agl
    CC=golang-dev
    https://golang.org/cl/5449077

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

https://github.com/golang/go/commit/a620f2b73ab1642fcd53fcc9cc5ada31ebdae455

元コミット内容

crypto/aes: Made faster by eliminating some indirection te および td 配列を te0-3 および td0-3 という変数にすることで、パフォーマンスが7000ns/opから5800ns/opに改善された。

変更の背景

AES（Advanced Encryption Standard）は、広く利用されているブロック暗号アルゴリズムであり、その性能は多くのアプリケーションにとって重要です。特に、暗号化や復号処理が頻繁に行われるシステムでは、わずかなパフォーマンス改善でも全体のスループットに大きな影響を与えます。

このコミットの背景には、crypto/aes パッケージにおけるAESの実装において、ルックアップテーブルへのアクセス方法に改善の余地があるという認識がありました。従来のコードでは、te および td という2次元配列（[4][256]uint32）として定義されたルックアップテーブルが使用されていました。この2次元配列へのアクセスは、te[j][i] のように行われ、j のインデックスによって間接参照が発生していました。

開発者は、この間接参照がパフォーマンスのボトルネックになっている可能性を特定し、これを排除することで処理速度を向上させようと試みました。具体的には、2次元配列を複数の1次元配列に分割することで、より直接的なメモリアクセスを可能にし、CPUのキャッシュ効率や命令パイプラインの最適化を促進することを狙いました。コミットメッセージに記載されている「7000ns/opから5800ns/opへの改善」という具体的な数値は、この最適化が実際に顕著な効果をもたらしたことを示しています。

前提知識の解説

AES (Advanced Encryption Standard)

AESは、米国標準技術局（NIST）によって制定されたブロック暗号です。128ビットのブロックサイズを持ち、鍵長は128ビット、192ビット、256ビットのいずれかを選択できます。AESは、複数のラウンド（繰り返し処理）を通じてデータを変換します。各ラウンドでは、以下の4つの主要な操作が行われます。

1. SubBytes (バイト置換): 各バイトを非線形なS-box（Substitution box）を使って別のバイトに置換します。これにより、非線形性が導入され、線形攻撃に対する耐性が高まります。
2. ShiftRows (行シフト): 状態行列の各行を異なる量だけ左に循環シフトします。これにより、バイトが異なる列に分散され、拡散性が高まります。
3. MixColumns (列混合): 各列を有限体GF(2^8)上での多項式乗算によって混合します。これにより、列内のバイト間の依存関係が複雑になり、拡散性がさらに高まります。
4. AddRoundKey (ラウンド鍵加算): 現在のラウンド鍵と状態行列をXORします。これにより、鍵依存性が導入されます。

復号処理では、これらの操作の逆変換が逆の順序で行われます。

ルックアップテーブル (Lookup Tables)

AESの実装では、SubBytesとMixColumnsの操作を高速化するために、しばしばルックアップテーブルが使用されます。特に、SubBytesとMixColumnsを組み合わせた操作（複合操作）を事前に計算してテーブルに格納することで、実行時の計算量を大幅に削減できます。

• te (T-box for Encryption): 暗号化（Encryption）の際に使用されるルックアップテーブルです。SubBytesとMixColumnsの操作を組み合わせた結果が格納されており、各バイトの変換を単一のテーブルルックアップで効率的に行えるようにします。
• td (T-box for Decryption): 復号（Decryption）の際に使用されるルックアップテーブルです。暗号化と同様に、復号時の逆SubBytesと逆MixColumnsの複合操作の結果が格納されています。

これらのテーブルは通常、uint32 型の要素を持つ256エントリの配列として定義されます。各エントリは、入力バイトに対応する4バイトのワード（uint32）を含み、これはSubBytesとMixColumnsの結果をエンコードしたものです。

間接参照 (Indirection)

プログラミングにおいて「間接参照」とは、データに直接アクセスするのではなく、別の場所を指し示すポインタやインデックスを介してデータにアクセスすることを指します。

例えば、array[index] のような1次元配列へのアクセスは比較的直接的です。しかし、matrix[row][col] のような2次元配列へのアクセスは、通常、matrix のベースアドレスから row に対応する行の開始アドレスを計算し、そこから col に対応する要素にアクセスするという2段階のプロセスを伴います。この「行の開始アドレスを計算する」部分が間接参照の一種と見なせます。

CPUの観点から見ると、間接参照は追加のメモリアクセスやアドレス計算を必要とすることがあります。これにより、パイプラインのストールやキャッシュミスが発生しやすくなり、パフォーマンスが低下する可能性があります。特に、ループ内で頻繁に間接参照が行われる場合、そのオーバーヘッドは無視できないものとなります。

技術的詳細

このコミットの技術的詳細な変更点は、AESの暗号化・復号処理で用いられるルックアップテーブル te と td のデータ構造と、それらへのアクセス方法に集約されます。

変更前の構造とアクセス

変更前、te と td はそれぞれ [4][256]uint32 型の2次元配列として定義されていました。 例えば、te は以下のような構造でした。

var te = [4][256]uint32{
    { /* te[0] の256個のuint32値 */ },
    { /* te[1] の256個のuint32値 */ },
    { /* te[2] の256個のuint32値 */ },
    { /* te[3] の256個のuint32値 */ },
}

この配列へのアクセスは、te[j][i] の形式で行われていました。 block.go 内の encryptBlock 関数では、以下のようなコードがありました。

t0 = xk[k+0] ^ te[0][uint8(s0>>24)] ^ te[1][uint8(s1>>16)] ^ te[2][uint8(s2>>8)] ^ te[3][uint8(s3)]

ここで、te[0]、te[1]、te[2]、te[3] へのアクセスは、te 配列のベースアドレスから各サブ配列の開始位置を計算し、さらにそのサブ配列内でインデックス uint8(...) を用いて要素にアクセスするという、複数段階の間接参照を伴います。Goコンパイラがこれらのアクセスをどのように最適化するかにもよりますが、一般的にこのような多次元配列のアクセスは、個別の1次元配列への直接アクセスよりもオーバーヘッドが大きくなる傾向があります。

変更後の構造とアクセス

このコミットでは、te と td の2次元配列を、それぞれ4つの独立した1次元配列に分割しました。 具体的には、const.go で以下のように定義が変更されました。

var te0 = [256]uint32{ /* te[0] の値 */ }
var te1 = [256]uint32{ /* te[1] の値 */ }
var te2 = [256]uint32{ /* te[2] の値 */ }
var te3 = [256]uint32{ /* te[3] の値 */ }

// 同様に td0, td1, td2, td3 も定義

そして、block.go 内の暗号化・復号ロジックでは、これらの新しい独立した変数に直接アクセスするように変更されました。

t0 = xk[k+0] ^ te0[uint8(s0>>24)] ^ te1[uint8(s1>>16)] ^ te2[uint8(s2>>8)] ^ te3[uint8(s3)]

この変更により、te[j][i] のような間接参照が teJ[i] のような直接参照に置き換えられました。

パフォーマンスへの影響

この「間接参照の排除」がパフォーマンスに寄与する主な理由は以下の通りです。

1. アドレス計算の簡素化: 独立した変数になったことで、コンパイラは各 teX や tdX のベースアドレスをより効率的に管理できるようになります。例えば、これらのベースアドレスをCPUレジスタに保持することで、メモリアクセス時のアドレス計算のオーバーヘッドを削減できます。
2. キャッシュ効率の向上: 2次元配列の場合、メモリ上での配置によっては、異なる j の値へのアクセスがキャッシュラインをまたぐ可能性があり、キャッシュミスを誘発することがあります。独立した1次元配列にすることで、特定のテーブルへのアクセスがより連続したメモリ領域に集中し、キャッシュヒット率が向上する可能性があります。
3. コンパイラの最適化の機会: 間接参照が少ないコードは、コンパイラがより積極的な最適化（例：ループアンローリング、命令スケジューリング）を適用しやすくなります。これにより、生成される機械語コードがより効率的になり、CPUのパイプラインを最大限に活用できるようになります。

コミットメッセージにある「7000ns/opから5800ns/opへの改善」という数値は、この変更がAESのブロック処理において約17%の速度向上をもたらしたことを示しており、間接参照の排除がGoのランタイムとコンパイラの特性と相まって、顕著な効果を発揮した良い例と言えます。

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

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

1. src/pkg/crypto/aes/const.go
2. src/pkg/crypto/aes/block.go
3. src/pkg/crypto/aes/aes_test.go

src/pkg/crypto/aes/const.go

このファイルでは、AESのルックアップテーブル te と td の定義が変更されました。

変更前: te と td は [4][256]uint32 型の2次元配列として定義されていました。

// Lookup tables for encryption.
// These can be recomputed by adapting the tests in aes_test.go.

var te = [4][256]uint32{
    { /* te[0] の値 */ },
    { /* te[1] の値 */ },
    { /* te[2] の値 */ },
    { /* te[3] の値 */ },
}

// Lookup tables for decryption.
// These can be recomputed by adapting the tests in aes_test.go.

var td = [4][256]uint32{
    { /* td[0] の値 */ },
    { /* td[1] の値 */ },
    { /* td[2] の値 */ },
    { /* td[3] の値 */ },
}

変更後: te と td はそれぞれ4つの独立した [256]uint32 型の1次元配列として定義されました。

// Lookup tables for encryption.
// These can be recomputed by adapting the tests in aes_test.go.

var te0 = [256]uint32{ /* te[0] の値 */ }
var te1 = [256]uint32{ /* te[1] の値 */ }
var te2 = [256]uint32{ /* te[2] の値 */ }
var te3 = [256]uint32{ /* te[3] の値 */ }

// Lookup tables for decryption.
// These can be recomputed by adapting the tests in aes_test.go.

var td0 = [256]uint32{ /* td[0] の値 */ }
var td1 = [256]uint32{ /* td[1] の値 */ }
var td2 = [256]uint32{ /* td[2] の値 */ }
var td3 = [256]uint32{ /* td[3] の値 */ }

src/pkg/crypto/aes/block.go

このファイルでは、AESの暗号化 (encryptBlock)、復号 (decryptBlock)、および鍵拡張 (expandKey) の各関数内で、ルックアップテーブルへのアクセス方法が変更されました。

変更前: te[j][i] や td[j][i] の形式でアクセスしていました。

// encryptBlock 関数内
t0 = xk[k+0] ^ te[0][uint8(s0>>24)] ^ te[1][uint8(s1>>16)] ^ te[2][uint8(s2>>8)] ^ te[3][uint8(s3)]
t1 = xk[k+1] ^ te[0][uint8(s1>>24)] ^ te[1][uint8(s2>>16)] ^ te[2][uint8(s3>>8)] ^ te[3][uint8(s0)]
t2 = xk[k+2] ^ te[0][uint8(s2>>24)] ^ te[1][uint8(s3>>16)] ^ te[2][uint8(s0>>8)] ^ te[3][uint8(s1)]
t3 = xk[k+3] ^ te[0][uint8(s3>>24)] ^ te[1][uint8(s0>>16)] ^ te[2][uint8(s1>>8)] ^ te[3][uint8(s2)]

// decryptBlock 関数内
t0 = xk[k+0] ^ td[0][uint8(s0>>24)] ^ td[1][uint8(s3>>16)] ^ td[2][uint8(s2>>8)] ^ td[3][uint8(s1)]
t1 = xk[k+1] ^ td[0][uint8(s1>>24)] ^ td[1][uint8(s0>>16)] ^ td[2][uint8(s3>>8)] ^ td[3][uint8(s2)]
t2 = xk[k+2] ^ td[0][uint8(s2>>24)] ^ td[1][uint8(s1>>16)] ^ td[2][uint8(s0>>8)] ^ td[3][uint8(s3)]
t3 = xk[k+3] ^ td[0][uint8(s3>>24)] ^ td[1][uint8(s2>>16)] ^ td[2][uint8(s1>>8)] ^ td[3][uint8(s0)]

// expandKey 関数内
x = td[0][sbox0[x>>24]] ^ td[1][sbox0[x>>16&0xff]] ^ td[2][sbox0[x>>8&0xff]] ^ td[3][sbox0[x&0xff]]

変更後: te0[i] や td0[i] の形式で直接アクセスするように変更されました。

// encryptBlock 関数内
t0 = xk[k+0] ^ te0[uint8(s0>>24)] ^ te1[uint8(s1>>16)] ^ te2[uint8(s2>>8)] ^ te3[uint8(s3)]
t1 = xk[k+1] ^ te0[uint8(s1>>24)] ^ te1[uint8(s2>>16)] ^ te2[uint8(s3>>8)] ^ te3[uint8(s0)]
t2 = xk[k+2] ^ te0[uint8(s2>>24)] ^ te1[uint8(s3>>16)] ^ te2[uint8(s0>>8)] ^ te3[uint8(s1)]
t3 = xk[k+3] ^ te0[uint8(s3>>24)] ^ te1[uint8(s0>>16)] ^ te2[uint8(s1>>8)] ^ te3[uint8(s2)]

// decryptBlock 関数内
t0 = xk[k+0] ^ td0[uint8(s0>>24)] ^ td1[uint8(s3>>16)] ^ td2[uint8(s2>>8)] ^ td3[uint8(s1)]
t1 = xk[k+1] ^ td0[uint8(s1>>24)] ^ td1[uint8(s0>>16)] ^ td2[uint8(s3>>8)] ^ td3[uint8(s2)]
t2 = xk[k+2] ^ td0[uint8(s2>>24)] ^ td1[uint8(s1>>16)] ^ td2[uint8(s0>>8)] ^ td3[uint8(s3)]
t3 = xk[k+3] ^ td0[uint8(s3>>24)] ^ td1[uint8(s2>>16)] ^ td2[uint8(s1>>8)] ^ td3[uint8(s0)]

// expandKey 関数内
x = td0[sbox0[x>>24]] ^ td1[sbox0[x>>16&0xff]] ^ td2[sbox0[x>>8&0xff]] ^ td3[sbox0[x&0xff]]

src/pkg/crypto/aes/aes_test.go

テストコードも、新しいルックアップテーブルの変数名に合わせて修正されました。

変更前: te と td を2次元配列として扱っていました。

// TestTe 関数内
te := [][256]uint32{te0, te1, te2, te3} // この行は変更後のコードで追加されたものだが、概念的に変更前は te を直接使っていた
for j := 0; j < 4; j++ {
    if x := te[j][i]; x != w {
        t.Fatalf("te[%d][%d] = %#x, want %#x", j, i, x, w)
    }
}

// TestTd 関数内
td := [][256]uint32{td0, td1, td2, td3} // この行は変更後のコードで追加されたものだが、概念的に変更前は td を直接使っていた
for j := 0; j < 4; j++ {
    if x := td[j][i]; x != w {
        t.Fatalf("td[%d][%d] = %#x, want %#x", j, i, x, w)
    }
}

変更後: テスト内で、新しい独立した te0-3 および td0-3 変数を一時的に2次元配列としてまとめることで、既存のテストロジックを最小限の変更で再利用しています。

// TestTe 関数内
te := [][256]uint32{te0, te1, te2, te3} // te0, te1, te2, te3 を使って一時的に te を構築
for j := 0; j < 4; j++ {
    if x := te[j][i]; x != w {
        t.Fatalf("te[%d][%d] = %#x, want %#x", j, i, x, w)
    }
}

// TestTd 関数内
td := [][256]uint32{td0, td1, td2, td3} // td0, td1, td2, td3 を使って一時的に td を構築
for j := 0; j < 4; j++ {
    if x := td[j][i]; x != w {
        t.Fatalf("td[%d][%d] = %#x, want %#x", j, i, x, w)
    }
}

コアとなるコードの解説

このコミットの核心は、AESの暗号化・復号処理におけるルックアップテーブル te と td へのアクセス方法の変更にあります。

AESの各ラウンドでは、バイト置換と列混合の操作が組み合わされて行われます。これらの操作は、事前に計算されたルックアップテーブル（T-box）を使用することで高速化されます。AESでは、128ビット（16バイト）のブロックを4x4のバイト行列として扱います。各バイトは独立して処理されるのではなく、列混合操作によって列内の他のバイトと相互作用します。

te および td テーブルは、この複合操作の結果を格納しています。各テーブルは4つのサブテーブル（te[0]からte[3]、td[0]からtd[3]）に分かれており、それぞれが256エントリ（0-255のバイト値に対応）を持ちます。各エントリは uint32 型であり、これは4バイトのワードとして、MixColumns操作の結果をエンコードしています。

変更前のコードでは、これらのサブテーブルへのアクセスは te[j][i] のように行われていました。Go言語において、[4][256]uint32 のような多次元配列は、メモリ上では通常、連続したブロックとして配置されます。te[j][i] にアクセスする際、コンパイラはまず j を使って te のベースアドレスから te[j] の開始アドレスを計算し、次に i を使ってその開始アドレスから目的の要素にアクセスします。この te[j] の開始アドレスを計算する部分が「間接参照」となります。

変更後のコードでは、te0, te1, te2, te3 (および td0, td1, td2, td3) という4つの独立した1次元配列が導入されました。これにより、te[j][i] のようなアクセスは te0[i] や te1[i] のような直接的なアクセスに置き換えられます。

この変更がパフォーマンスに与える影響は、Goコンパイラがこれらの独立した配列をどのように扱うかに依存します。

• レジスタ割り当ての改善: コンパイラは、独立した配列のベースアドレスをCPUのレジスタに割り当てることで、メモリアクセス時のアドレス計算をさらに高速化できる可能性があります。
• キャッシュの最適化: 独立した配列は、それぞれがキャッシュラインに収まりやすくなり、特定のテーブルへのアクセスがよりキャッシュフレンドリーになる可能性があります。これにより、キャッシュミスが減少し、メモリアクセスのレイテンシが低減されます。
• 命令レベルの並列性: 間接参照が減ることで、CPUの命令パイプラインがよりスムーズに動作し、命令レベルの並列性が向上する可能性があります。

結果として、この変更はAESのコア処理におけるメモリアクセスの効率を向上させ、全体的な暗号化・復号速度の向上に貢献しました。コミットメッセージに示された7000ns/opから5800ns/opへの改善は、この最適化が実測で約17%の性能向上をもたらしたことを明確に示しています。これは、低レベルのデータ構造の選択とアクセスパターンが、高性能を要求される暗号ライブラリにおいていかに重要であるかを示す好例です。

関連リンク

• Go言語のAESパッケージ: https://pkg.go.dev/crypto/aes
• Advanced Encryption Standard (AES) - Wikipedia: https://ja.wikipedia.org/wiki/Advanced_Encryption_Standard

参考にした情報源リンク

• Go CL 5449077: https://golang.org/cl/5449077 (コミットメッセージに記載されているGoのコードレビューシステムへのリンク)
• Go言語のソースコード (crypto/aes): https://github.com/golang/go/tree/master/src/crypto/aes
• Go言語の配列とスライス: Go言語における配列とスライスのメモリレイアウトやパフォーマンス特性に関する一般的な情報源。
• CPUキャッシュとパフォーマンス最適化: CPUのキャッシュメモリの動作原理と、それがプログラムのパフォーマンスに与える影響に関する一般的な情報源。
• コンパイラ最適化の基本: コンパイラがコードを最適化する際の一般的な手法（レジスタ割り当て、ループ最適化など）に関する情報源。