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

このコミットは、Go言語の image/jpeg パッケージ内のテストファイル dct_test.go におけるパフォーマンス改善を目的としています。具体的には、離散コサイン変換（DCT）および逆離散コサイン変換（IDCT）のテスト関数 slowFDCT と slowIDCT において、繰り返し計算されるコサイン値をグローバル配列にキャッシュすることで、テストの実行速度を向上させています。特にARMアーキテクチャ上でのテストが非常に遅かった問題に対処しています。

コミット

commit 2abaaefa729502740002fc9a87c012ea7d1a3e64
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Oct 18 21:28:04 2012 +0200

    image/jpeg: make TestDCT faster.
    
    The value of cosines are cached in a global array
    instead of being recomputed each time.
    The test was terribly slow on arm.
    
    R=golang-dev, dave, nigeltao
    CC=golang-dev
    https://golang.org/cl/6733046

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

https://github.com/golang/go/commit/2abaaefa729502740002fc9a87c012ea7d1a3e64

元コミット内容

image/jpeg: make TestDCT faster. The value of cosines are cached in a global array instead of being recomputed each time. The test was terribly slow on arm.

変更の背景

この変更の主な背景は、Go言語の image/jpeg パッケージに含まれるDCT（離散コサイン変換）およびIDCT（逆離散コサイン変換）のテストが、特にARMアーキテクチャ上で非常に遅かったという問題です。これらのテストは、JPEG画像のエンコード・デコード処理の核心部分であるDCT/IDCTの正確性を検証するために重要ですが、テストの実行に時間がかかりすぎると開発効率が低下します。

遅さの原因は、テスト関数 slowFDCT および slowIDCT の内部で、コサイン（math.Cos）の計算がループ内で繰り返し行われていたことにあります。三角関数、特にコサインの計算は一般的にCPU負荷の高い操作であり、これを何度も実行するとパフォーマンスに大きな影響を与えます。ARMプロセッサのような一部のアーキテクチャでは、浮動小数点演算、特に超越関数（math.Cosなど）の計算がx86などの他のアーキテクチャと比較して相対的に遅い場合があり、これが問題の顕在化につながったと考えられます。

このコミットは、このパフォーマンスボトルネックを解消し、テストスイート全体の実行時間を短縮することを目的としています。

前提知識の解説

1. JPEG画像圧縮とDCT/IDCT

JPEG（Joint Photographic Experts Group）は、静止画像の非可逆圧縮方式です。JPEG圧縮の主要なステップの一つに、**離散コサイン変換（Discrete Cosine Transform, DCT）**があります。

• DCT（離散コサイン変換）: 画像データを周波数領域に変換する数学的な操作です。人間の目は低周波数成分（画像の滑らかな変化）には敏感ですが、高周波数成分（細かいディテールやノイズ）には比較的鈍感です。DCTは、画像ブロック（通常は8x8ピクセル）を空間領域から周波数領域に変換し、各周波数成分の「強さ」を表す係数（DCT係数）を生成します。これにより、高周波数成分の情報を間引いたり、量子化したりすることで、視覚的な品質を大きく損なうことなくデータ量を削減できます。
• IDCT（逆離散コサイン変換）: 圧縮されたDCT係数を元の空間領域の画像データに戻す操作です。デコード時に使用されます。

DCTとIDCTは、コサイン関数を用いた複雑な行列演算を含みます。

2. math.Cos 関数とパフォーマンス

math.Cos は、Go言語の標準ライブラリ math パッケージに含まれるコサイン関数です。これは浮動小数点数を受け取り、そのコサイン値を返します。内部的には、テイラー展開やCORDICアルゴリズムなどの数値計算手法を用いてコサイン値を近似計算します。これらの計算は、単純な加算や乗算に比べて多くのCPUサイクルを必要とします。

3. キャッシュの概念

キャッシュとは、頻繁にアクセスされるデータを高速な記憶領域（キャッシュメモリ）に一時的に保存し、次回のアクセス時に計算や取得をやり直すのではなく、キャッシュから直接読み出すことで処理速度を向上させる技術です。

このコミットでは、コサインの計算結果をグローバルな配列（cosines）に保存し、再利用することで、math.Cos の呼び出し回数を減らしています。これは、計算結果をキャッシュする典型的な例です。

4. Go言語の init 関数

Go言語には、init 関数という特別な関数があります。

• init 関数は、パッケージがインポートされた際に、main 関数が実行されるよりも前に自動的に実行されます。
• 各パッケージは複数の init 関数を持つことができ、それらは定義された順序で実行されます。
• init 関数は、プログラムの起動時に必要な初期化処理（例: グローバル変数の設定、データベース接続の確立、設定ファイルの読み込みなど）を行うのに適しています。

このコミットでは、init 関数を利用して、プログラムの起動時に一度だけ必要なコサイン値を事前に計算し、cosines 配列に格納しています。

技術的詳細

このコミットは、image/jpeg パッケージの dct_test.go ファイル内の slowFDCT および slowIDCT 関数におけるパフォーマンスボトルネックを解消するために、コサイン値の事前計算とキャッシュという最適化手法を導入しています。

1. 問題の特定: slowFDCT と slowIDCT は、DCTおよびIDCTの「遅い」実装（テスト目的のため、最適化されていない直接的な実装）です。これらの関数は、ネストされたループ内で math.Cos 関数を繰り返し呼び出していました。具体的には、math.Cos(math.Pi*float64((2*x+1)*u)/16) や math.Cos(math.Pi*float64((2*y+1)*v)/16) のような形式でコサイン値が計算されていました。これらの引数は、ループのイテレーションごとに変化しますが、その変化のパターンは予測可能であり、取りうる値の範囲も限られています。

2. 最適化の戦略: コサイン関数の計算はCPU負荷が高いため、同じ引数で何度も計算するのを避けることがパフォーマンス向上の鍵となります。そこで、以下の戦略が採用されました。

   • グローバル配列 cosines の導入: var cosines [32]float64 というグローバル配列が宣言されました。この配列は、cos(π/2 * k/8) の形式で計算されるコサイン値を格納するために使用されます。配列のサイズが32であるのは、((2*x+1)*u)%32 や ((2*y+1)*v)%32 の計算結果が0から31の範囲に収まるためです。
   • init 関数による事前計算: プログラムの起動時に一度だけ実行される init 関数内で、cosines 配列の全ての要素が事前に計算され、格納されます。for k := range cosines { cosines[k] = math.Cos(math.Pi * float64(k) / 16) } というループにより、必要なコサイン値が全て計算されます。
   • ルックアップテーブルとしての利用: slowFDCT と slowIDCT 関数内では、math.Cos の直接的な呼び出しを、事前に計算された cosines 配列からのルックアップに置き換えます。例えば、math.Cos(math.Pi*float64((2*x+1)*u)/16) は cosines[((2*x+1)*u)%32] に変更されます。ここで、((2*x+1)*u)%32 は、元のコサイン関数の引数 (π * float64((2*x+1)*u) / 16) に対応する k の値を計算し、そのインデックスで cosines 配列から値を取得しています。モジュロ演算子 %32 を使用しているのは、math.Pi * float64(k) / 16 の k が (2*x+1)*u や (2*y+1)*v の値に対応し、これらの値が32の倍数で周期性を持つためです。これにより、配列の範囲内に収まるようにインデックスを調整しています。

3. パフォーマンスへの影響: この変更により、slowFDCT と slowIDCT の実行中に高コストな math.Cos の呼び出しが大幅に削減されます。代わりに、配列のインデックス計算とメモリアクセスという、より高速な操作に置き換えられます。これにより、特に浮動小数点演算が遅いARMアーキテクチャ上で、テストの実行速度が劇的に向上します。

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

変更は src/pkg/image/jpeg/dct_test.go ファイルに集中しています。

--- a/src/pkg/image/jpeg/dct_test.go
+++ b/src/pkg/image/jpeg/dct_test.go
@@ -112,6 +112,14 @@ func alpha(i int) float64 {
 	return math.Sqrt2
 }
 
+var cosines [32]float64 // cosines[k] = cos(π/2 * k/8)
+
+func init() {
+	for k := range cosines {
+		cosines[k] = math.Cos(math.Pi * float64(k) / 16)
+	}
+}
+
 // slowFDCT performs the 8*8 2-dimensional forward discrete cosine transform:
 //
 //
@@ -129,8 +137,8 @@ func slowFDCT(b *block) {
 			for y := 0; y < 8; y++ {
 				for x := 0; x < 8; x++ {
 					sum += alpha(u) * alpha(v) * float64(b[8*y+x]) *
-						math.Cos(math.Pi*float64((2*x+1)*u)/16) *
-						math.Cos(math.Pi*float64((2*y+1)*v)/16)
+						cosines[((2*x+1)*u)%32] *
+						cosines[((2*y+1)*v)%32]
 				}
 			}
 			dst[8*v+u] = sum / 8
@@ -159,8 +167,8 @@ func slowIDCT(b *block) {
 			for v := 0; v < 8; v++ {
 				for u := 0; u < 8; u++ {
 					sum += alpha(u) * alpha(v) * float64(b[8*v+u]) *
-						math.Cos(math.Pi*float64((2*x+1)*u)/16) *
-						math.Cos(math.Pi*float64((2*y+1)*v)/16)
+						cosines[((2*x+1)*u)%32] *
+						cosines[((2*y+1)*v)%32]
 				}
 			}
 			dst[8*y+x] = sum / 8

コアとなるコードの解説

1. var cosines [32]float64:

   • cosines という名前のグローバル変数として、float64 型の要素を32個持つ配列が宣言されています。
   • この配列は、DCT/IDCT計算で頻繁に必要となるコサイン値を事前に格納するためのキャッシュとして機能します。
   • コメント // cosines[k] = cos(π/2 * k/8) は、この配列に格納される値の数学的な意味を示しています。これは cos(π * k / 16) と等価です。

2. func init():

   • Go言語の特別な init 関数です。このパッケージがインポートされる際に、main 関数が実行されるよりも前に自動的に一度だけ実行されます。
   • この init 関数内で、cosines 配列の全ての要素が初期化されます。
   • for k := range cosines { ... } ループは、配列のインデックス k を0から31まで順に処理します。
   • cosines[k] = math.Cos(math.Pi * float64(k) / 16): 各インデックス k に対して、対応するコサイン値 cos(π * k / 16) を計算し、cosines[k] に格納しています。これにより、プログラムの実行開始時に必要なコサイン値が全てメモリ上に準備されます。

3. slowFDCT および slowIDCT 関数内の変更:

   • 変更前は、math.Cos(math.Pi*float64((2*x+1)*u)/16) や math.Cos(math.Pi*float64((2*y+1)*v)/16) のように、ループ内で math.Cos 関数が直接呼び出されていました。
   • 変更後は、これらの math.Cos の呼び出しが、cosines[((2*x+1)*u)%32] や cosines[((2*y+1)*v)%32] という形式の配列ルックアップに置き換えられています。
   • ((2*x+1)*u)%32 および ((2*y+1)*v)%32 は、元のコサイン関数の引数 (π * float64(arg) / 16) における arg の値に対応するインデックスを計算しています。このインデックスは、cosines 配列の範囲（0-31）に収まるようにモジュロ演算子 %32 を使用して調整されています。
   • これにより、実行時に高コストなコサイン計算を繰り返し行う代わりに、事前に計算された値を高速に参照できるようになり、テストの実行速度が大幅に向上します。

関連リンク

• Go言語の image/jpeg パッケージのドキュメント: https://pkg.go.dev/image/jpeg
• Go言語の math パッケージのドキュメント: https://pkg.go.dev/math
• Go言語の init 関数に関する公式ドキュメント（Effective Goより）: https://go.dev/doc/effective_go#init

参考にした情報源リンク

• 離散コサイン変換 (DCT) - Wikipedia: https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%B3%E3%82%B5%E3%82%A4%E3%83%B3%E5%A4%89%E6%8F%9B
• JPEG - Wikipedia: https://ja.wikipedia.org/wiki/JPEG
• キャッシュ (コンピュータ) - Wikipedia: https://ja.wikipedia.org/wiki/%E3%82%AD%E3%83%A3%E3%83%83%E3%82%B7%E3%83%A5_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)
• Go言語の init 関数に関する解説記事（例: Qiitaなど）: (具体的なURLは省略しますが、Go init 関数 で検索すると多数見つかります)
• 浮動小数点演算のパフォーマンスに関する一般的な情報（例: 各種CPUアーキテクチャの特性に関する技術記事）