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

このコミットは、Go言語のmath/randパッケージのテストコードにおいて、math.Pow関数を単なる二乗計算に使用している箇所を修正し、より効率的なx * xに置き換えるものです。これにより、特にソフトウェア浮動小数点演算を使用するARMアーキテクチャ上でのテスト実行速度が大幅に改善されました。

コミット

commit 1a0a09dafecddf2b63befda53aa5e54d74ce19e1
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Wed Jul 4 00:38:01 2012 +0200

    math/rand: avoid use of math.Pow in tests.
    
    The use of math.Pow for mere squaring can be extremely
    slow on soft-float ARM. Even on systems with hardware
    floating-point, a speedup in test duration is observed.
    
    On amd64
    Before: ok      math/rand       2.009s
    After:  ok      math/rand       0.340s
    
    Fixes #3740.
    
    R=dave, golang-dev, r, r
    CC=golang-dev
    https://golang.org/cl/6348061

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

https://github.com/golang/go/commit/1a0a09dafecddf2b63befda53aa5e54d74ce19e1

元コミット内容

math/randパッケージのテストにおいて、math.Pow関数を二乗計算のために使用するのを避ける変更です。math.Powを単なる二乗計算に使うと、特にソフトウェア浮動小数点演算を使用するARMアーキテクチャ上で非常に遅くなることが判明しました。ハードウェア浮動小数点演算を持つシステムでも、テスト実行時間の短縮が確認されています。

amd64環境でのテスト時間比較：

• 変更前: ok math/rand 2.009s
• 変更後: ok math/rand 0.340s

これはIssue #3740を修正するものです。

変更の背景

この変更の主な背景は、math.Pow関数が特定の環境、特にソフトウェア浮動小数点演算を使用するARMプロセッサ上で、単なる二乗（x^2）の計算に非常に非効率的であったことです。math.Pow(x, 2)は、より汎用的なx^yの計算を行うために設計されており、内部的には対数や指数関数（exp(y * log(x))）を用いることが多いため、単純な乗算であるx * xよりもはるかに多くの計算コストがかかります。

Go言語のテストスイートは、様々なアーキテクチャや環境で実行されるため、このようなパフォーマンスボトルネックはテスト全体の実行時間に大きな影響を与えます。コミットメッセージに示されているように、amd64環境ですらテスト時間が2秒から0.34秒へと大幅に短縮されており、これはテストのCI/CDパイプラインの効率化にも寄与します。

この問題はGoのIssue #3740として報告されており、このコミットはその解決策として実装されました。

前提知識の解説

浮動小数点演算 (Floating-Point Arithmetic)

コンピュータが実数を近似的に表現・計算する方法です。通常、IEEE 754標準に従って表現されます。浮動小数点演算は、整数演算に比べて複雑で、計算コストが高くなる傾向があります。

ソフトウェア浮動小数点演算 (Soft-Float) と ハードウェア浮動小数点演算 (Hard-Float)

• ハードウェア浮動小数点演算 (Hard-Float): CPU内に浮動小数点演算ユニット (FPU) が搭載されており、浮動小数点計算をハードウェアで高速に実行します。現代のほとんどのデスクトップPCやサーバー、高性能なモバイルプロセッサはこれに該当します。
• ソフトウェア浮動小数点演算 (Soft-Float): CPUにFPUが搭載されていないか、FPUが非常に低機能な場合、浮動小数点計算はソフトウェア（CPUの汎用レジスタと命令セットを使ってエミュレート）で行われます。これはハードウェアによる計算に比べて非常に遅く、計算コストが劇的に増加します。組み込みシステムや古いARMプロセッサなどで見られます。

math.Pow関数

Go言語のmathパッケージに含まれる関数で、Pow(x, y)はxのy乗を計算します。数学的にはx^yを意味します。内部的には、y * log(x)を計算し、その結果を指数関数expに渡すといった、より複雑なアルゴリズムを使用することが一般的です。このため、yが整数、特に2のような小さな整数の場合でも、単純な乗算よりもはるかに多くのCPUサイクルを消費します。

標準偏差 (Standard Deviation) の計算

統計学における標準偏差は、データセットのばらつきの度合いを示す指標です。一般的に以下の式で計算されます。

$$ \sigma = \sqrt{\frac{1}{N} \sum_{i=1}^{N} (x_i - \mu)^2} $$

ここで、

• $\sigma$ は標準偏差
• $N$ はデータ点の数
• $x_i$ は各データ点
• $\mu$ はデータの平均 ($\frac{1}{N} \sum_{i=1}^{N} x_i$)

この式は「平均からの偏差の二乗の平均の平方根」と解釈できます。 しかし、計算の安定性や効率性を考慮して、以下の等価な式もよく用いられます。

$$ \sigma = \sqrt{\frac{1}{N} \sum_{i=1}^{N} x_i^2 - \mu^2} $$

この式は「二乗の平均から平均の二乗を引いた値の平方根」と解釈でき、データ点の二乗和と合計を一度に計算できるため、ループを一度で済ませることができ、計算効率が良い場合があります。特に、平均からの偏差を毎回計算する必要がないため、浮動小数点演算の誤差蓄積を抑える効果も期待できます。

技術的詳細

このコミットの技術的な核心は、math.Pow(x, 2)という形式の計算をx * xに置き換えることで、計算コストを大幅に削減した点にあります。

math.Powは、任意の浮動小数点数yに対してx^yを計算するための汎用的な関数です。これは通常、exp(y * log(x))のような数学的変換を利用して実装されます。log（自然対数）やexp（指数関数）の計算は、テイラー展開などの級数計算や、専用のハードウェア命令（FPUがある場合）を必要とし、非常に多くのCPUサイクルを消費します。

一方、x * xは単純な浮動小数点乗算であり、CPUのFPUが利用できる場合は単一の命令で実行できることがほとんどです。FPUがない場合でも、ソフトウェアエミュレーションによる乗算は、logやexpの計算に比べてはるかに高速です。

src/pkg/math/rand/rand_test.go内のgetStatsResults関数は、乱数サンプルの統計的特性（平均と標準偏差）を計算するために使用されていました。この関数内で標準偏差を計算する際に、math.Pow(samples[i]-res.mean, 2)という形で偏差の二乗を求めていました。

変更後のコードでは、標準偏差の計算式を、二乗の平均から平均の二乗を引く形式に変更しています。具体的には、squaresum/float64(len(samples)) - res.mean*res.meanという計算を行っています。 この変更により、各サンプルについてsamples[i]-res.meanを計算し、その結果をmath.Powに渡すという二段階の処理が不要になり、代わりにsamples[i] * samples[i]という単純な乗算をループ内で一度行うだけでよくなりました。これにより、計算の複雑さが大幅に軽減され、特にFPUが非効率な環境でのパフォーマンスが劇的に向上しました。

amd64環境でのテスト時間短縮（2.009秒から0.340秒）は、この最適化がハードウェア浮動小数点演算が利用可能な環境でも顕著な効果をもたらすことを示しています。これは、math.Powの内部的なオーバーヘッドが、たとえハードウェアで実行されても、単純な乗算に比べて無視できないほど大きいことを意味します。

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

変更はsrc/pkg/math/rand/rand_test.goファイル内のgetStatsResults関数に集中しています。

--- a/src/pkg/math/rand/rand_test.go
+++ b/src/pkg/math/rand/rand_test.go
@@ -57,16 +57,13 @@ func (this *statsResults) checkSimilarDistribution(expected *statsResults) error
 
 func getStatsResults(samples []float64) *statsResults {
 	res := new(statsResults)
-	var sum float64
-	for i := range samples {
-		sum += samples[i]
+	var sum, squaresum float64
+	for _, s := range samples {
+		sum += s
+		squaresum += s * s
 	}
 	res.mean = sum / float64(len(samples))
-	var devsum float64
-	for i := range samples {
-		devsum += math.Pow(samples[i]-res.mean, 2)
-	}\n-\tres.stddev = math.Sqrt(devsum / float64(len(samples)))\n+\tres.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean)\n 	return res
 }
 

コアとなるコードの解説

変更前のコード

func getStatsResults(samples []float64) *statsResults {
	res := new(statsResults)
	var sum float64
	for i := range samples {
		sum += samples[i]
	}
	res.mean = sum / float64(len(samples))
	var devsum float64
	for i := range samples {
		devsum += math.Pow(samples[i]-res.mean, 2) // ここで math.Pow を使用
	}
	res.stddev = math.Sqrt(devsum / float64(len(samples)))
	return res
}

変更前は、getStatsResults関数内で標準偏差を計算するために、まずサンプルの合計sumを計算して平均res.meanを求めます。その後、別のループで各サンプルと平均との差の二乗をmath.Powを使って計算し、その合計devsumを求めていました。最後にdevsumをサンプル数で割って平方根を取ることで標準偏差を算出していました。この二重ループとmath.Powの使用がパフォーマンスのボトルネックとなっていました。

変更後のコード

func getStatsResults(samples []float64) *statsResults {
	res := new(statsResults)
	var sum, squaresum float64 // squaresum を追加
	for _, s := range samples { // ループを一つに集約
		sum += s
		squaresum += s * s // 各サンプルの二乗和を計算
	}
	res.mean = sum / float64(len(samples))
	// 標準偏差の計算式を変更
	res.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean)
	return res
}

変更後では、sumに加えてsquaresum（各サンプルの二乗の合計）を保持する変数が追加されました。そして、単一のループ内で、サンプルの合計sumと、各サンプルの二乗の合計squaresumを同時に計算するように変更されています。

標準偏差の計算式は、以下の統計的恒等式に基づいています。 $$ \text{Variance} = E[X^2] - (E[X])^2 $$ ここで、$E[X]$は期待値（平均）、$E[X^2]$は二乗の期待値（二乗の平均）です。 したがって、標準偏差は次のようになります。 $$ \sigma = \sqrt{E[X^2] - (E[X])^2} = \sqrt{\frac{\sum x_i^2}{N} - \left(\frac{\sum x_i}{N}\right)^2} $$ この式をコードに適用すると、squaresum/float64(len(samples))が$E[X^2]$に相当し、res.mean*res.meanが$(E[X])^2$に相当します。

この変更により、math.Powの呼び出しが完全に削除され、ループの回数も実質的に一度に集約されたため、計算効率が大幅に向上しました。特に、x * xはmath.Pow(x, 2)よりもはるかに高速な操作であるため、この最適化がパフォーマンスに大きな影響を与えました。

関連リンク

• Go Issue #3740: https://code.google.com/p/go/issues/detail?id=3740 (古いGoのIssueトラッカーのリンクですが、現在はGitHubに移行しています)
• Go CL 6348061: https://golang.org/cl/6348061 (GoのコードレビューシステムGerritの変更リストへのリンク)

参考にした情報源リンク

• IEEE 754: 浮動小数点数の標準に関する情報
• 標準偏差の計算式: 統計学の教科書やオンラインリソース（例: Wikipediaの「標準偏差」の項目）
• ARMアーキテクチャにおける浮動小数点演算: ARMの公式ドキュメントや関連する技術記事