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

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

このコミットは、Go言語の math/big パッケージにおけるコアな算術関数（AddVV, AddVW, AddMulVVW）のパフォーマンスベースラインを確立するために、ベンチマークテストを追加するものです。これにより、将来的な最適化や変更がこれらの関数のパフォーマンスに与える影響を定量的に評価できるようになります。

コミット

commit 053b448d6104a9a005697a9d0360c4402cdcbc30
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Aug 23 15:56:14 2012 -0700

    math/big: added benchmarks to establish baseline for core functions
    
    BenchmarkAddVV_1          500000000        7.24 ns/op     8844.11 MB/s
    BenchmarkAddVV_2          100000000       10.4 ns/op     12290.41 MB/s
    BenchmarkAddVV_3          100000000       10.7 ns/op     17966.58 MB/s
    BenchmarkAddVV_4          100000000       12.3 ns/op     20848.67 MB/s
    BenchmarkAddVV_5          100000000       14.5 ns/op     21993.82 MB/s
    BenchmarkAddVV_1e1        100000000       24.0 ns/op     26720.65 MB/s
    BenchmarkAddVV_1e2         10000000      246 ns/op       26014.58 MB/s
    BenchmarkAddVV_1e3          1000000     2416 ns/op       26485.06 MB/s
    BenchmarkAddVV_1e4           100000    23874 ns/op       26806.36 MB/s
    BenchmarkAddVV_1e5            10000   241155 ns/op       26538.87 MB/s
    BenchmarkAddVW_1          500000000        6.12 ns/op    10461.91 MB/s
    BenchmarkAddVW_2          200000000       11.0 ns/op     11596.63 MB/s
    BenchmarkAddVW_3          200000000        8.97 ns/op    21409.82 MB/s
    BenchmarkAddVW_4          100000000       10.8 ns/op     23696.72 MB/s
    BenchmarkAddVW_5          100000000       12.5 ns/op     25524.88 MB/s
    BenchmarkAddVW_1e1        100000000       21.5 ns/op     29786.32 MB/s
    BenchmarkAddVW_1e2         10000000      168 ns/op       37925.36 MB/s
    BenchmarkAddVW_1e3          1000000     1658 ns/op       38579.15 MB/s
    BenchmarkAddVW_1e4           100000    16492 ns/op       38805.85 MB/s
    BenchmarkAddVW_1e5            10000   172155 ns/op       37175.69 MB/s
    BenchmarkAddMulVVW_1      100000000       12.9 ns/op      4968.49 MB/s
    BenchmarkAddMulVVW_2      100000000       15.5 ns/op      8279.42 MB/s
    BenchmarkAddMulVVW_3      100000000       13.4 ns/op     14340.53 MB/s
    BenchmarkAddMulVVW_4      100000000       15.8 ns/op     16194.94 MB/s
    BenchmarkAddMulVVW_5      100000000       18.9 ns/op     16906.61 MB/s
    BenchmarkAddMulVVW_1e1     50000000       32.3 ns/op     19838.35 MB/s
    BenchmarkAddMulVVW_1e2     10000000      285 ns/op       22427.28 MB/s
    BenchmarkAddMulVVW_1e3      1000000     2777 ns/op       23040.42 MB/s
    BenchmarkAddMulVVW_1e4       100000    27901 ns/op       22938.01 MB/s
    BenchmarkAddMulVVW_1e5        10000   281087 ns/op       22768.73 MB/s
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6478055

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

https://github.com/golang/go/commit/053b448d6104a9a005697a9d0360c4402cdcbc30

元コミット内容

math/big パッケージのコア関数に対してベンチマークを追加し、パフォーマンスのベースラインを確立する。

変更の背景

math/big パッケージは、任意精度の整数演算を提供するGo言語の重要なライブラリです。このような低レベルの算術演算は、暗号化、科学計算、金融アプリケーションなど、多くの分野でパフォーマンスが非常に重要になります。

このコミットが行われた2012年当時、Go言語はまだ比較的新しい言語であり、標準ライブラリの最適化は継続的なプロセスでした。math/big パッケージのコア関数は、その性質上、非常に頻繁に呼び出され、全体のパフォーマンスに大きな影響を与えます。

ベンチマークを追加する主な目的は以下の通りです。

  1. パフォーマンスのベースライン確立: 現在の関数のパフォーマンスを数値として記録し、将来の変更（アルゴリズムの改善、コンパイラの最適化など）がパフォーマンスにどのような影響を与えるかを比較するための基準とします。
  2. リグレッションの検出: パフォーマンスが意図せず低下する「パフォーマンスリグレッション」を早期に検出し、修正するためのメカニズムを提供します。
  3. 最適化の指針: どの関数やどの入力サイズでパフォーマンスのボトルネックが存在するかを特定し、最適化の努力を集中すべき領域を明確にします。
  4. 品質保証: パッケージの安定性と効率性を保証する一環として、継続的なパフォーマンス監視を可能にします。

コミットメッセージに含まれるベンチマーク結果は、様々な入力サイズ（1ワードから10万ワードまで）における AddVV (Vector-Vector加算), AddVW (Vector-Word加算), AddMulVVW (Vector-Vector-Word乗算加算) の操作にかかる時間（ns/op）とスループット（MB/s）を示しており、これがこのコミットによって確立された初期のベースラインデータとなります。

前提知識の解説

Go言語の math/big パッケージ

math/big パッケージは、Go言語で任意精度の算術演算を行うための機能を提供します。これは、標準の int や int64 型では表現できない非常に大きな整数や、浮動小数点数を扱う必要がある場合に利用されます。

  • Word 型: math/big パッケージの基本的な構成要素です。これは uint のエイリアスであり、システムのワードサイズ（通常は32ビットまたは64ビット）に対応する符号なし整数を表します。大きな整数は、この Word 型の配列として内部的に表現されます。
  • nat 型: []Word のエイリアスであり、Word のスライス（配列）として表現される自然数（非負整数）です。例えば、nat 型の変数は [Word, Word, Word] のように、複数のワードを連結して大きな数を表現します。
  • コア算術関数: math/big パッケージには、AddVV (2つの nat 型の数を加算), AddVW ( nat 型の数と Word 型の数を加算), AddMulVVW ( nat 型の数に Word 型の数を乗算し、別の nat 型の数を加算) など、任意精度演算の基盤となる低レベルの算術関数が多数存在します。これらの関数は通常、アセンブリ言語で最適化されており、非常に高速な実行が求められます。

Go言語のベンチマークテスト (testing パッケージ)

Go言語には、標準ライブラリの testing パッケージにベンチマークテストの機能が組み込まれています。

  • ベンチマーク関数: func BenchmarkXxx(b *testing.B) というシグネチャを持つ関数として定義されます。
  • *testing.B: ベンチマーク実行を制御するための構造体です。
    • b.N: ベンチマーク関数が実行されるイテレーション回数です。Goのテストフレームワークが自動的に調整し、統計的に有意な結果が得られるように十分な回数実行します。
    • b.ResetTimer(): タイマーをリセットします。セットアップコードの実行時間を測定から除外するために使用されます。
    • b.SetBytes(n int64): 1回の操作で処理されるバイト数を設定します。これにより、ベンチマーク結果に「MB/s」（メガバイト/秒）のようなスループットのメトリクスが表示されるようになります。これは、データ処理の効率を評価する上で非常に有用です。
  • 実行方法: go test -bench=. コマンドで実行します。

再現可能な乱数生成

ベンチマークテストでは、入力データが毎回同じであること（再現性）が非常に重要です。異なる入力データで実行すると、結果がばらつき、比較が困難になります。Goの math/rand パッケージでは、rand.NewSource(seed) を使用してシード値を固定することで、再現可能な乱数シーケンスを生成できます。これにより、ベンチマークの実行ごとに同じ入力データが生成され、結果の信頼性が向上します。

技術的詳細

このコミットでは、src/pkg/math/big/arith_test.go に以下の主要な変更が加えられました。

  1. math/rand パッケージのインポート: ベンチマーク用のランダムな入力データを生成するために math/rand がインポートされました。
  2. 再現可能な乱数ジェネレータの初期化: 
    var rnd = rand.New(rand.NewSource(0))
    rand.NewSource(0) を使用して、シード値が 0 に固定された新しい乱数ジェネレータ rnd が作成されました。これにより、ベンチマークの実行ごとに同じ乱数シーケンスが生成され、結果の再現性が保証されます。
  3. ランダムな Word の生成関数 rndW(): 
    func rndW() Word {
    return Word(rnd.Int63()<<1 | rnd.Int63n(2))
}
    この関数は、Word 型のランダムな値を生成します。rnd.Int63() は63ビットのランダムな符号なし整数を返します。<<1 | rnd.Int63n(2) は、最下位ビットをランダムに設定することで、64ビットの Word を完全に埋めることを意図しています（Word が64ビットの場合）。
  4. ランダムな []Word (nat) の生成関数 rndV(n int): 
    func rndV(n int) []Word {
    v := make([]Word, n)
    for i := range v {
        v[i] = rndW()
    }
    return v
}
    この関数は、指定された長さ n の Word スライス（つまり nat 型の数）を生成し、各要素を rndW() で初期化します。
  5. 汎用ベンチマークヘルパー関数:
    • benchmarkFunVV(b *testing.B, f funVV, n int): addVV のような funVV 型の関数をベンチマークするためのヘルパー。
    • benchmarkFunVW(b *testing.B, f funVW, n int): addVW のような funVW 型の関数をベンチマークするためのヘルパー。
    • benchmarkAddMulVVW(b *testing.B, n int): addMulVVW をベンチマークするためのヘルパー。 これらのヘルパー関数は、共通のベンチマークロジック（ランダムな入力の生成、タイマーのリセット、b.SetBytes の呼び出し、ループ内での関数呼び出し）をカプセル化しています。 特に b.SetBytes(int64(n * _W)) は重要です。ここで _W は Word 型のビット数（通常は32または64）を表す定数です。n * _W は、n 個の Word が処理されることを示し、これによりベンチマーク結果に「MB/s」のスループットが表示されるようになります。
  6. 具体的なベンチマーク関数: BenchmarkAddVV_1 から BenchmarkAddVV_1e5、BenchmarkAddVW_1 から BenchmarkAddVW_1e5、BenchmarkAddMulVVW_1 から BenchmarkAddMulVVW_1e5 といった形式で、各コア関数に対して様々な入力サイズ（1ワード、2ワード、...、5ワード、10ワード、100ワード、1000ワード、1万ワード、10万ワード）のベンチマーク関数が追加されました。これにより、入力サイズがパフォーマンスに与える影響を詳細に分析できます。

src/pkg/math/big/nat_test.go では、既存の rndNat 関数が arith_test.go で定義された新しい rndV 関数を使用するように変更され、乱数生成のロジックが一元化されました。また、nat_test.go から math/rand のインポートと関連するグローバル変数が削除されました。これはコードの重複を避け、依存関係を整理する良いリファクタリングです。

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

src/pkg/math/big/arith_test.go

--- a/src/pkg/math/big/arith_test.go
+++ b/src/pkg/math/big/arith_test.go
@@ -4,7 +4,10 @@
 
 package big
 
-import "testing"
+import (
+	"math/rand"
+	"testing"
+)
 
 type funWW func(x, y, c Word) (z1, z0 Word)
 type argWW struct {
@@ -100,6 +103,43 @@ func TestFunVV(t *testing.T) {
 	}
 }
 
+// Always the same seed for reproducible results.
+var rnd = rand.New(rand.NewSource(0))
+
+func rndW() Word {
+	return Word(rnd.Int63()<<1 | rnd.Int63n(2))
+}
+
+func rndV(n int) []Word {
+	v := make([]Word, n)
+	for i := range v {
+		v[i] = rndW()
+	}
+	return v
+}
+
+func benchmarkFunVV(b *testing.B, f funVV, n int) {
+	x := rndV(n)
+	y := rndV(n)
+	z := make([]Word, n)
+	b.SetBytes(int64(n * _W))
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		f(z, x, y)
+	}
+}
+
+func BenchmarkAddVV_1(b *testing.B)   { benchmarkFunVV(b, addVV, 1) }
+func BenchmarkAddVV_2(b *testing.B)   { benchmarkFunVV(b, addVV, 2) }
+func BenchmarkAddVV_3(b *testing.B)   { benchmarkFunVV(b, addVV, 3) }
+func BenchmarkAddVV_4(b *testing.B)   { benchmarkFunVV(b, addVV, 4) }
+func BenchmarkAddVV_5(b *testing.B)   { benchmarkFunVV(b, addVV, 5) }
+func BenchmarkAddVV_1e1(b *testing.B) { benchmarkFunVV(b, addVV, 1e1) }
+func BenchmarkAddVV_1e2(b *testing.B) { benchmarkFunVV(b, addVV, 1e2) }
+func BenchmarkAddVV_1e3(b *testing.B) { benchmarkFunVV(b, addVV, 1e3) }
+func BenchmarkAddVV_1e4(b *testing.B) { benchmarkFunVV(b, addVV, 1e4) }
+func BenchmarkAddVV_1e5(b *testing.B) { benchmarkFunVV(b, addVV, 1e5) }
+
 type funVW func(z, x []Word, y Word) (c Word)
 type argVW struct {
  z, x nat
@@ -210,6 +250,28 @@ func TestFunVW(t *testing.T) {
 	}
 }
 
+func benchmarkFunVW(b *testing.B, f funVW, n int) {
+	x := rndV(n)
+	y := rndW()
+	z := make([]Word, n)
+	b.SetBytes(int64(n * _W))
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		f(z, x, y)
+	}
+}
+
+func BenchmarkAddVW_1(b *testing.B)   { benchmarkFunVW(b, addVW, 1) }
+func BenchmarkAddVW_2(b *testing.B)   { benchmarkFunVW(b, addVW, 2) }
+func BenchmarkAddVW_3(b *testing.B)   { benchmarkFunVW(b, addVW, 3) }
+func BenchmarkAddVW_4(b *testing.B)   { benchmarkFunVW(b, addVW, 4) }
+func BenchmarkAddVW_5(b *testing.B)   { benchmarkFunVW(b, addVW, 5) }
+func BenchmarkAddVW_1e1(b *testing.B) { benchmarkFunVW(b, addVW, 1e1) }
+func BenchmarkAddVW_1e2(b *testing.B) { benchmarkFunVW(b, addVW, 1e2) }
+func BenchmarkAddVW_1e3(b *testing.B) { benchmarkFunVW(b, addVW, 1e3) }
+func BenchmarkAddVW_1e4(b *testing.B) { benchmarkFunVW(b, addVW, 1e4) }
+func BenchmarkAddVW_1e5(b *testing.B) { benchmarkFunVW(b, addVW, 1e5) }
+
 type funVWW func(z, x []Word, y, r Word) (c Word)
 type argVWW struct {
  z, x nat
@@ -334,6 +396,28 @@ func TestMulAddWWW(t *testing.T) {
 	}
 }
 
+func benchmarkAddMulVVW(b *testing.B, n int) {
+	x := rndV(n)
+	y := rndW()
+	z := make([]Word, n)
+	b.SetBytes(int64(n * _W))
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		addMulVVW(z, x, y)
+	}
+}
+
+func BenchmarkAddMulVVW_1(b *testing.B)   { benchmarkAddMulVVW(b, 1) }
+func BenchmarkAddMulVVW_2(b *testing.B)   { benchmarkAddMulVVW(b, 2) }
+func BenchmarkAddMulVVW_3(b *testing.B)   { benchmarkAddMulVVW(b, 3) }
+func BenchmarkAddMulVVW_4(b *testing.B)   { benchmarkAddMulVVW(b, 4) }
+func BenchmarkAddMulVVW_5(b *testing.B)   { benchmarkAddMulVVW(b, 5) }
+func BenchmarkAddMulVVW_1e1(b *testing.B) { benchmarkAddMulVVW(b, 1e1) }
+func BenchmarkAddMulVVW_1e2(b *testing.B) { benchmarkAddMulVVW(b, 1e2) }
+func BenchmarkAddMulVVW_1e3(b *testing.B) { benchmarkAddMulVVW(b, 1e3) }
+func BenchmarkAddMulVVW_1e4(b *testing.B) { benchmarkAddMulVVW(b, 1e4) }
+func BenchmarkAddMulVVW_1e5(b *testing.B) { benchmarkAddMulVVW(b, 1e5) }
+
 func testWordBitLen(t *testing.T, fname string, f func(Word) int) {
  for i := 0; i <= _W; i++ {
  x := Word(1) << uint(i-1) // i == 0 => x == 0

src/pkg/math/big/nat_test.go

--- a/src/pkg/math/big/nat_test.go
+++ b/src/pkg/math/big/nat_test.go
@@ -6,7 +6,6 @@ package big
 
 import (
 	"io"
-	"math/rand"
 	"runtime"
 	"strings"
 	"testing"
@@ -192,19 +191,14 @@ func TestMulUnbalanced(t *testing.T) {
 	}
 }
 
-var rnd = rand.New(rand.NewSource(0x43de683f473542af))\n-var mulx = rndNat(1e4)\n-var muly = rndNat(1e4)\n-\n func rndNat(n int) nat {\n-\tx := make(nat, n)\n-\tfor i := 0; i < n; i++ {\n-\t\tx[i] = Word(rnd.Int63()<<1 + rnd.Int63n(2))\n-\t}\n-\treturn x.norm()\n+\treturn nat(rndV(n)).norm()\n }\
 
 func BenchmarkMul(b *testing.B) {\n+\tmulx := rndNat(1e4)\n+\tmuly := rndNat(1e4)\n+\tb.ResetTimer()\n \tfor i := 0; i < b.N; i++ {\n \t\tvar z nat\n \t\tz.mul(mulx, muly)\n```

## コアとなるコードの解説

### `src/pkg/math/big/arith_test.go` の変更点

*   **`import ("math/rand", "testing")`**: `testing` パッケージはGoの標準ベンチマーク機能を提供し、`math/rand` はベンチマークの入力データを生成するために使用されます。
*   **`var rnd = rand.New(rand.NewSource(0))`**: ベンチマークの再現性を確保するために、固定シード（0）で初期化された乱数ジェネレータ `rnd` が導入されました。これにより、ベンチマークを複数回実行しても常に同じ入力データが生成され、結果の比較が容易になります。
*   **`rndW() Word`**: 1つの `Word` 型のランダムな値を生成します。`rnd.Int63()` は63ビットの乱数を生成し、`<<1 | rnd.Int63n(2)` は最下位ビットをランダムに設定することで、`Word` 型の全ビットをランダムに埋めることを意図しています。
*   **`rndV(n int) []Word`**: 指定された長さ `n` の `Word` スライス（`nat` 型の数）を生成し、各要素を `rndW()` で初期化します。これにより、様々なサイズの大きな整数をベンチマークの入力として使用できます。
*   **`benchmarkFunVV`, `benchmarkFunVW`, `benchmarkAddMulVVW`**: これらは、それぞれの算術関数（`addVV`, `addVW`, `addMulVVW`）のベンチマークを実行するための汎用ヘルパー関数です。
    *   これらの関数は、`rndV` や `rndW` を使ってランダムな入力データを生成します。
    *   `b.SetBytes(int64(n * _W))` は、1回の操作で処理されるバイト数をGoのベンチマークフレームワークに伝えます。`n` はワード数、`_W` は1ワードあたりのビット数（通常は32または64）です。これにより、ベンチマーク結果に「MB/s」というスループットのメトリクスが表示され、関数のデータ処理効率を評価できます。
    *   `b.ResetTimer()` は、入力データの生成などのセットアップにかかる時間をベンチマークの測定から除外するために、タイマーをリセットします。
    *   `for i := 0; i < b.N; i++` ループ内で、対象の算術関数が `b.N` 回実行されます。`b.N` はベンチマークフレームワークによって自動的に調整され、統計的に有意な結果が得られるように十分な回数実行されます。
*   **`BenchmarkAddVV_N`, `BenchmarkAddVW_N`, `BenchmarkAddMulVVW_N`**: これらは、Goのベンチマークフレームワークによって自動的に検出・実行される実際のベンチマーク関数です。それぞれが対応するヘルパー関数を呼び出し、異なる入力サイズ（1, 2, 3, 4, 5, 10, 100, 1000, 10000, 100000ワード）でコア算術関数のパフォーマンスを測定します。これにより、入力サイズが大きくなるにつれてパフォーマンスがどのように変化するかを詳細に分析できます。

### `src/pkg/math/big/nat_test.go` の変更点

*   **`math/rand` のインポートとグローバル変数の削除**: `arith_test.go` に乱数生成ロジックが一元化されたため、`nat_test.go` から重複する `math/rand` のインポートと、グローバルな `rnd`, `mulx`, `muly` 変数が削除されました。これにより、コードの重複が解消され、保守性が向上します。
*   **`rndNat` 関数の変更**: 以前は `nat_test.go` 独自の乱数生成ロジックを持っていましたが、`arith_test.go` で定義された `rndV` 関数を呼び出すように変更されました。`return nat(rndV(n)).norm()` は、`rndV` で生成された `[]Word` を `nat` 型にキャストし、`norm()` メソッドで正規化（先行ゼロの除去など）を行っています。
*   **`BenchmarkMul` 関数の変更**: `mulx` と `muly` の初期化がベンチマークループの外に移動し、`b.ResetTimer()` の後に実行されるようになりました。これにより、これらの初期化にかかる時間がベンチマークの測定から除外され、より正確な乗算処理自体のパフォーマンスが測定されます。

これらの変更により、`math/big` パッケージのコア算術関数のパフォーマンスを体系的に測定し、将来の最適化や変更の影響を評価するための強固な基盤が確立されました。

## 関連リンク

*   [GitHub上でのコミットページ](https://github.com/golang/go/commit/053b448d6104a9a005697a9d0360c4402cdcbc30)
*   [Go Code Review 6478055](https://golang.org/cl/6478055) (Goのコードレビューシステムにおけるこの変更のページ)

## 参考にした情報源リンク

*   Go言語の `testing` パッケージに関する公式ドキュメント: [https://pkg.go.dev/testing](https://pkg.go.dev/testing)
*   Go言語の `math/big` パッケージに関する公式ドキュメント: [https://pkg.go.dev/math/big](https://pkg.go.dev/math/big)
*   Go言語の `math/rand` パッケージに関する公式ドキュメント: [https://pkg.go.dev/math/rand](https://pkg.go.dev/math/rand)
*   Go言語のベンチマークに関するブログ記事やチュートリアル (一般的な知識として参照)