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

このコミットは、Go言語の標準ライブラリ math/big パッケージにおける、多倍長整数（big.Int）の乗算アルゴリズムであるKaratsuba法の性能評価と調整に関する改善を含んでいます。具体的には、Karatsuba法の適用閾値（threshold）を決定するためのキャリブレーションコードの改良と、乗算ベンチマークの精度向上を目的としています。

コミット

commit cc1890cbe3053953a5967474c8fad5005aba4165
Author: Robert Griesemer <gri@golang.org>
Date:   Mon Jun 4 09:48:27 2012 -0700

    math/big: improved karatsuba calibration code, better mul benchmark
    
    An attempt to profit from CL 6176043 (fix to superpolinomial
    runtime of karatsuba multiplication) and determine a better
    karatsuba threshold. The result indicates that 32 is still
    a reasonable value. Left the threshold as is (== 32), but
    made some minor changes to the calibrate code which are
    worthwhile saving (use of existing benchmarking code for
    better results, better use of package time).
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/6260062

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

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

このコミットの目的は、math/big パッケージにおけるKaratsuba乗算のキャリブレーションコードを改善し、より良い乗算ベンチマークを提供することです。以前の変更（CL 6176043）でKaratsuba乗算の「超多項式（superpolinomial）」ランタイムの修正が行われたことを受け、より適切なKaratsuba閾値を決定しようと試みました。その結果、閾値32が依然として妥当な値であることが示されました。閾値自体は変更されませんでしたが、既存のベンチマークコードをより有効活用し、time パッケージを適切に使用することで、キャリブレーションコードに価値のある小さな変更が加えられました。

変更の背景

多倍長整数（big.Int）の乗算は、非常に大きな数値を扱う際に計算コストが高くなる処理です。Go言語の math/big パッケージでは、この乗算を効率的に行うためにKaratsuba乗算アルゴリズムが採用されています。

Karatsuba乗算は、ある程度の桁数以上の数値の乗算において、古典的な筆算アルゴリズムよりも高速ですが、小さな桁数の数値にはオーバーヘッドが大きいため、古典的な方法の方が速い場合があります。この切り替わる境界となるのが「Karatsuba閾値」です。この閾値は、システムのアーキテクチャやGoのランタイムの特性によって最適な値が異なる可能性があり、性能に直結するため、適切に設定される必要があります。

このコミットの背景には、以前のコミット（CL 6176043）でKaratsuba乗算の「超多項式ランタイム」に関する修正が行われたことがあります。この修正により、Karatsuba乗算の挙動が改善されたため、改めて最適な閾値を再評価する必要が生じました。コミットメッセージにある「superpolinomial runtime」とは、アルゴリズムの計算量が期待される多項式時間よりも悪化するような挙動を指している可能性があります。この修正によってKaratsuba乗算の性能特性が安定したため、より正確な閾値のキャリブレーションが可能になったと考えられます。

前提知識の解説

1. 多倍長整数 (Arbitrary-Precision Integers)

通常のプログラミング言語で扱える整数型（例: int64）には表現できる数値の範囲に限界があります。多倍長整数は、この制限を超えて、メモリが許す限り任意の桁数の整数を扱うことができるデータ型です。Go言語では math/big パッケージがこれを提供し、暗号学、科学計算、金融計算など、非常に大きな数値を正確に扱う必要がある場面で利用されます。

2. Karatsuba乗算アルゴリズム

Karatsuba乗算は、1960年にアナトリー・カラツバによって発見された、2つのn桁の数を乗算するための高速なアルゴリズムです。古典的な筆算による乗算がO(n^2)の計算量であるのに対し、Karatsuba法はO(n^log2(3))、約O(n^1.585)の計算量で実行されます。これは、大きな数の乗算において大幅な高速化をもたらします。

基本的なアイデアは、2つのn桁の数を半分に分割し、再帰的に乗算を行うことで、乗算の回数を減らすというものです。例えば、2つの2n桁の数 x と y を x = x1*B^n + x0、y = y1*B^n + y0 と表現した場合、古典的な乗算では x*y = x1*y1*B^(2n) + (x1*y0 + x0*y1)*B^n + x0*y0 となり、4回のn桁の乗算が必要になります。Karatsuba法では、z2 = x1*y1、z0 = x0*y0、z1 = (x1+x0)*(y1+y0) - z2 - z0 とすることで、3回のn桁の乗算で結果を得ることができます。

3. Karatsuba閾値 (Karatsuba Threshold)

Karatsuba乗算は、再帰的な性質を持つため、非常に小さな数の乗算にまで適用すると、再帰呼び出しのオーバーヘッドが大きくなり、古典的な乗算よりも遅くなることがあります。そのため、ある一定の桁数（またはワード数）以下の数値の乗算には古典的なアルゴリズムを使い、それ以上の桁数の場合にKaratsuba法に切り替えるという戦略が取られます。この切り替わる桁数が「Karatsuba閾値」です。この閾値は、実際のシステム上でのベンチマークによって最適な値が決定されます。

4. Go言語のベンチマーク (`testing` パッケージ)

Go言語には、標準ライブラリとしてベンチマークを記述・実行するための testing パッケージが用意されています。

BenchmarkXxx(b *testing.B) 関数: ベンチマーク関数は Benchmark で始まり、*testing.B 型の引数を取ります。
b.N: ベンチマーク関数内でループを回す回数を示します。testing フレームワークが自動的に調整し、統計的に有意な結果が得られるように十分な回数実行します。
b.NsPerOp(): ベンチマーク結果から、1回の操作あたりのナノ秒（ns）を返します。これは性能評価の主要な指標となります。
testing.Benchmark(f func(b *testing.B)): この関数は、指定されたベンチマーク関数 f を実行し、その結果（testing.BenchmarkResult）を返します。これにより、プログラム内で動的にベンチマークを実行し、その結果を利用することが可能になります。

5. `time` パッケージ

Go言語の time パッケージは、時間に関する機能を提供します。

time.Now(): 現在の時刻を返します。
time.Duration: 時間の長さを表す型です。ナノ秒単位で表現されます。
Sub(t Time): 2つの Time オブジェクトの差を Duration として返します。

これらの知識が、コミット内容の理解に不可欠です。

技術的詳細

このコミットの技術的な変更点は、主に src/pkg/math/big/calibrate_test.go と src/pkg/math/big/nat_test.go の2つのファイルにわたります。

`calibrate_test.go` の変更点

このファイルは、Karatsuba乗算の最適な閾値を決定するためのキャリブレーションロジックを含んでいます。

measure 関数の削除と measureKaratsuba の導入:
- 以前の measure 関数は、単純に与えられた関数 f を N 回実行し、その合計時間を計測して平均を算出していました。これは一般的な時間計測には使えますが、Goのベンチマークフレームワークが提供する詳細な統計情報（特に NsPerOp）を利用していませんでした。
- 新しく導入された measureKaratsuba 関数は、testing.Benchmark 関数を内部で呼び出すように変更されました。これにより、Goのベンチマークフレームワークが提供するより堅牢で正確なベンチマーク結果（NsPerOp()）を直接利用できるようになりました。
- measureKaratsuba は、一時的に karatsubaThreshold グローバル変数を設定し、ベンチマークを実行した後で元の値に戻すことで、特定の閾値でのKaratsuba乗算の性能を測定できるようにしています。
ベンチマーク対象の変更:
- measureKaratsuba 関数内で BenchmarkMul(b) を呼び出す karatsubaLoad 関数が導入されました。これにより、calibrate_test.go から nat_test.go に定義されている実際の乗算ベンチマーク関数を呼び出すことが可能になり、より現実的なワークロードでの性能評価が行えるようになりました。
- 以前は benchmarkMulLoad という関数を直接呼び出していましたが、これは nat_test.go から削除され、より汎用的な BenchmarkMul に置き換えられました。
キャリブレーションロジックの改善:
- 閾値の探索範囲が n から th に変更され、初期値が 8 から 4 に、ループの終了条件が th < 128 に変更されました。これにより、より広範囲で効率的な閾値の探索が可能になります。
- 出力フォーマットが fmt.Printf("n = %3d ...") から fmt.Printf("th = %3d ...") に変更され、より明確になりました。
- ブレークイーブンポイント（Karatsubaが古典的な乗算より速くなる点）と収穫逓減点（Karatsubaの性能向上が鈍化する点）の検出ロジックは維持されていますが、閾値の変数名が n から th に変更されています。
- 両方の閾値が検出された後の追加測定回数が 20 から 10 に減らされました。これは、testing.Benchmark の精度向上により、少ない試行回数で十分な結果が得られるようになったためと考えられます。

`nat_test.go` の変更点

このファイルは、多倍長整数の基本的な操作（nat 型）に関するテストとベンチマークを含んでいます。

ベンチマークデータの生成方法の変更:
- 以前は init() 関数内で固定サイズの mulArg を作成し、_M（最大値）で埋めていました。
- 新しい実装では、rndNat(n int) nat 関数が導入され、math/rand パッケージを使用してランダムな多倍長整数を生成するようになりました。これにより、より多様な入力データでのベンチマークが可能になり、現実的な性能評価に近づきました。
- mulx と muly というグローバル変数が導入され、ベンチマークの入力として使用されるランダムな多倍長整数が格納されます。これらの変数は、ベンチマークの各イテレーションで同じ入力を使用することで、結果の再現性と比較可能性を保証します。
benchmarkMulLoad 関数の削除:
- この関数は、calibrate_test.go から呼び出されていた特定のワークロードをシミュレートするものでしたが、calibrate_test.go が BenchmarkMul を直接呼び出すように変更されたため、不要となり削除されました。
BenchmarkMul 関数の簡素化:
- 以前の BenchmarkMul は、内部で benchmarkMulLoad() を呼び出すだけでした。
- 新しい BenchmarkMul は、z.mul(mulx, muly) を直接呼び出すように変更されました。これにより、mulx と muly というランダムに生成された固定の大きな数値を乗算する、より直接的で標準的なベンチマークになりました。b.N 回のループ内でこの乗算を実行することで、Karatsuba乗算の実際の性能が測定されます。

これらの変更により、Karatsuba閾値のキャリブレーションプロセスがより正確で信頼性の高いものになり、math/big パッケージの性能最適化に貢献しています。

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

`src/pkg/math/big/calibrate_test.go`

--- a/src/pkg/math/big/calibrate_test.go
+++ b/src/pkg/math/big/calibrate_test.go
@@ -21,15 +21,17 @@ import (
 
 var calibrate = flag.Bool("calibrate", false, "run calibration test")
 
-// measure returns the time to run f
-// func measure(f func()) time.Duration {
-// 	const N = 100
-// 	start := time.Now()
-// 	for i := N; i > 0; i-- {
-// 		f()
-// 	}
-// 	stop := time.Now()
-// 	return stop.Sub(start) / N
-// }
+func karatsubaLoad(b *testing.B) {
+	BenchmarkMul(b)
+}
+
+// measureKaratsuba returns the time to run a Karatsuba-relevant benchmark
+// given Karatsuba threshold th.
+func measureKaratsuba(th int) time.Duration {
+	th, karatsubaThreshold = karatsubaThreshold, th
+	res := testing.Benchmark(karatsubaLoad)
+	karatsubaThreshold = th
+	return time.Duration(res.NsPerOp())
 }
 
 func computeThresholds() {
@@ -37,35 +39,33 @@ func computeThresholds() {
 	fmt.Printf("(run repeatedly for good results)\\n")
 
 	// determine Tk, the work load execution time using basic multiplication
-	karatsubaThreshold = 1e9 // disable karatsuba
-	Tb := measure(benchmarkMulLoad)
-	fmt.Printf("Tb = %dns\\n", Tb)
+	Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled
+	fmt.Printf("Tb = %10s\\n", Tb)
 
 	// thresholds
-	n := 8 // any lower values for the threshold lead to very slow multiplies
+	th := 4
 	th1 := -1
 	th2 := -1
 
 	var deltaOld time.Duration
-	for count := -1; count != 0; count-- {
+	for count := -1; count != 0 && th < 128; count-- {
 		// determine Tk, the work load execution time using Karatsuba multiplication
-		karatsubaThreshold = n // enable karatsuba
-		Tk := measure(benchmarkMulLoad)
+		Tk := measureKaratsuba(th)
 
 		// improvement over Tb
 		delta := (Tb - Tk) * 100 / Tb
 
-		fmt.Printf("n = %3d  Tk = %8dns  %4d%%", n, Tk, delta)
+		fmt.Printf("th = %3d  Tk = %10s  %4d%%", th, Tk, delta)
 
 		// determine break-even point
 		if Tk < Tb && th1 < 0 {
-			th1 = n
+			th1 = th
 			fmt.Print("  break-even point")
 		}
 
 		// determine diminishing return
 		if 0 < delta && delta < deltaOld && th2 < 0 {
-			th2 = n
+			th2 = th
 			fmt.Print("  diminishing return")
 		}
 		deltaOld = delta
@@ -74,10 +74,10 @@ func computeThresholds() {
 
 		// trigger counter
 		if th1 >= 0 && th2 >= 0 && count < 0 {
-			count = 20 // this many extra measurements after we got both thresholds
+			count = 10 // this many extra measurements after we got both thresholds
 		}
 
-		n++
+		th++
 	}
 }

`src/pkg/math/big/nat_test.go`

--- a/src/pkg/math/big/nat_test.go
+++ b/src/pkg/math/big/nat_test.go
@@ -6,6 +6,7 @@ package big
 
 import (
 	"io"
+	"math/rand"
 	"strings"
 	"testing"
 )
@@ -135,26 +136,22 @@ func TestMulRangeN(t *testing.T) {
 	}
 }
 
-var mulArg, mulTmp nat
+var rnd = rand.New(rand.NewSource(0x43de683f473542af))
+var mulx = rndNat(1e4)
+var muly = rndNat(1e4)
 
-func init() {
-	const n = 1000
-	mulArg = make(nat, n)
+func rndNat(n int) nat {
+	x := make(nat, n)
 	for i := 0; i < n; i++ {
-		mulArg[i] = _M
-	}
+		x[i] = Word(rnd.Int63()<<1 + rnd.Int63n(2))
+	}
+	return x
 }
 
-func benchmarkMulLoad() {
-	for j := 1; j <= 10; j++ {
-		x := mulArg[0 : j*100]
-		mulTmp.mul(x, x)
-	}
-}
-
 func BenchmarkMul(b *testing.B) {
 	for i := 0; i < b.N; i++ {
-		benchmarkMulLoad()
+		var z nat
+		z.mul(mulx, muly)
 	}
 }

コアとなるコードの解説

`src/pkg/math/big/calibrate_test.go`

measure 関数の削除と measureKaratsuba の追加:
- 古い measure 関数はコメントアウトされ、代わりに measureKaratsuba 関数が導入されました。
- measureKaratsuba は、testing.Benchmark を利用して、より正確なベンチマーク結果（res.NsPerOp()）を取得します。これは、Goのベンチマークフレームワークが提供する統計的な信頼性を活用するものです。
- karatsubaThreshold グローバル変数を一時的に設定し、ベンチマーク実行後に元に戻すことで、特定の閾値でのKaratsuba乗算の性能を測定できるようにしています。
karatsubaLoad 関数の追加:
- この関数は *testing.B を引数に取り、BenchmarkMul(b) を呼び出します。これは、calibrate_test.go から nat_test.go に定義されている実際の乗算ベンチマークを呼び出すためのラッパーとして機能します。
computeThresholds 関数の変更:
- Tb := measureKaratsuba(1e9): Karatsuba乗算を無効化（閾値を非常に大きな値に設定）した状態での基本乗算の時間を測定します。
- th := 4: 閾値の探索開始点が n=8 から th=4 に変更されました。
- for count := -1; count != 0 && th < 128; count--: 閾値の探索ループの条件が変更され、th が 128 に達するまで探索を続けます。
- Tk := measureKaratsuba(th): 各閾値 th におけるKaratsuba乗算の時間を測定します。
- fmt.Printf("th = %3d ..."): 出力メッセージが n から th に変更され、より分かりやすくなりました。
- th1 = th と th2 = th: ブレークイーブンポイントと収穫逓減点の検出において、閾値の変数名が n から th に変更されました。
- count = 10: 両方の閾値が検出された後の追加測定回数が 20 から 10 に減らされました。これは、testing.Benchmark の精度向上により、少ない試行回数で十分な結果が得られるようになったためと考えられます。

`src/pkg/math/big/nat_test.go`

math/rand のインポート: ランダムな数値を生成するために math/rand パッケージがインポートされました。
rnd 変数の追加: rand.New(rand.NewSource(0x43de683f473542af)) を使用して、固定シードの乱数ジェネレータが初期化されます。これにより、ベンチマークの再現性が保証されます。
rndNat(n int) nat 関数の追加:
- 指定されたワード数 n のランダムな多倍長整数 nat を生成するヘルパー関数です。
- rnd.Int63()<<1 + rnd.Int63n(2) を使用して、各ワードにランダムな64ビット値を設定します。これにより、より現実的なランダムな入力データが生成されます。
mulx と muly グローバル変数の追加:
- rndNat(1e4) を使用して、それぞれ10,000ワードのランダムな多倍長整数が生成され、mulx と muly に格納されます。これらが BenchmarkMul の入力として使用されます。
mulArg, mulTmp, init() 関数の削除:
- 以前の固定データ生成ロジックと関連する変数が削除されました。
benchmarkMulLoad() 関数の削除:
- この関数は calibrate_test.go から呼び出されていた特定のワークロードをシミュレートするものでしたが、新しいキャリブレーションロジックでは不要になったため削除されました。
BenchmarkMul(b *testing.B) 関数の変更:
- for i := 0; i < b.N; i++ { ... } ループ内で、var z nat; z.mul(mulx, muly) が実行されます。
- これにより、mulx と muly という固定の大きなランダムな数値を b.N 回乗算する、より直接的で標準的なベンチマークになりました。このベンチマークは、Karatsuba乗算の実際の性能を測定するために使用されます。

これらの変更により、Karatsuba閾値のキャリブレーションがより正確かつ効率的に行えるようになり、math/big パッケージの多倍長整数乗算の性能最適化に貢献しています。

参考にした情報源リンク

Go Gerrit Change-ID 6260062: https://golang.org/cl/6260062 (コミットメッセージに記載されているCLへのリンク)
Go Gerrit Change-ID 6176043: https://golang.org/cl/6176043 (コミットメッセージに記載されている、以前のKaratsuba修正に関するCLへのリンク)
Go言語のベンチマークに関する公式ドキュメントやブログ記事: Go言語のベンチマークの書き方や実行方法に関する一般的な情報源。
多倍長整数ライブラリの実装に関する一般的な情報: Karatsuba法や他の乗算アルゴリズムに関するコンピュータサイエンスの教科書やオンラインリソース。

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. 多倍長整数 (Arbitrary-Precision Integers)

2. Karatsuba乗算アルゴリズム

3. Karatsuba閾値 (Karatsuba Threshold)

4. Go言語のベンチマーク (`testing` パッケージ)

5. `time` パッケージ

技術的詳細

`calibrate_test.go` の変更点

`nat_test.go` の変更点

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

`src/pkg/math/big/calibrate_test.go`

`src/pkg/math/big/nat_test.go`

コアとなるコードの解説

`src/pkg/math/big/calibrate_test.go`

`src/pkg/math/big/nat_test.go`

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo