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

このコミットは、Go言語の標準ライブラリである math/big パッケージ内の nat 型（自然数、すなわち非負の整数を表す型）の乗算処理 (mul 関数) におけるパフォーマンス改善を目的としています。具体的には、一時的なスライス（Goにおける動的配列）の再利用を促進することで、余分なメモリ割り当て（アロケーション）を回避し、乗算処理の効率を高めています。

コミット

commit 98ca655919622659598988f7ed420706858ad4c0
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Jul 12 14:12:50 2012 -0700

    math/big: minor performance tuning
    
    Reuse temporary slice to avoid extra allocations
    (originally done correctly by remyoudompheng@gmail.com
    in https://golang.org/cl/6345075/).
    
    benchmark           old ns/op    new ns/op    delta
    BenchmarkHilbert      6252790      6262304   +0.15%
    BenchmarkMul         45827438     45301002   -1.15%
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6346097

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

https://github.com/golang/go/commit/98ca655919622659598988f7ed420706858ad4c0

このコミットは、math/big パッケージの nat.go ファイルにおける mul 関数（乗算処理）の変更が主です。具体的には、t.mul() の結果を一時変数に代入せず、直接 addAt() に渡していた箇所を、一度 t に再代入してから addAt() に渡すように変更しています。これにより、t.mul() が内部で再利用可能なスライスを返す場合に、その再利用が適切に行われるようになります。

また、nat_test.go では、テストヘルパー関数 rndNat の戻り値に .norm() を適用する変更と、コメントの修正が行われています。

変更の背景

この変更の主な背景は、math/big パッケージにおける大規模な数値計算のパフォーマンス最適化です。特に、nat 型の乗算処理は、その性質上、多くのメモリ割り当てと解放を伴う可能性があります。Go言語では、ガベージコレクション（GC）がメモリ管理を行いますが、頻繁なメモリ割り当てはGCの負荷を増加させ、結果としてプログラム全体の実行速度を低下させる要因となります。

コミットメッセージに記載されているように、この変更は「一時的なスライスの再利用によって余分なアロケーションを避ける」ことを目的としています。これは、math/big パッケージのような数値計算ライブラリにおいて、計算効率を向上させるための一般的な最適化手法です。ベンチマーク結果 (BenchmarkMul で1.15%の改善) が示すように、この変更は乗算処理のパフォーマンスに明確な正の影響を与えています。

前提知識の解説

Go言語のスライスとメモリ割り当て

Go言語のスライスは、配列のセグメントを参照するデータ構造です。スライスは、基になる配列へのポインタ、長さ、容量の3つの要素で構成されます。スライスを操作する際、特にスライスの容量を超える要素を追加したり、新しいスライスを作成したりする場合、Goランタイムは新しい基になる配列を割り当て、既存の要素をコピーすることがあります。このメモリ割り当て（アロケーション）は、ヒープ領域で行われ、ガベージコレクタの対象となります。

頻繁なアロケーションは、以下の理由でパフォーマンスに影響を与えます。

アロケーション自体のコスト: メモリを確保する操作には時間がかかります。
ガベージコレクションの負荷: 割り当てられたメモリが不要になった場合、ガベージコレクタがそれを回収する必要があります。GCは一時的にプログラムの実行を停止させることがあり（ストップ・ザ・ワールド）、これがレイテンシの原因となります。

したがって、可能な限りメモリ割り当てを減らし、既存のメモリ領域を再利用することは、Goプログラムのパフォーマンス最適化において非常に重要な戦略となります。

`math/big` パッケージ

math/big パッケージは、Go言語で任意精度の算術演算（大きな整数、有理数、浮動小数点数）を扱うための標準ライブラリです。通常のGoの組み込み型（int, int64 など）では表現できない非常に大きな数値を扱う際に使用されます。

nat 型: math/big パッケージ内で、非負の整数（自然数）の内部表現として使用される型です。通常、Word 型（uint または uint64）のスライスとして実装され、各要素が数値の「桁」を表します。例えば、[]Word{0x1234, 0x5678} のように、複数のワードを連結して大きな数値を表現します。

大規模な数値の乗算アルゴリズム

大きな数値の乗算は、小学校で習う筆算の原理を拡張したアルゴリズム（例: カラツバ法、Toom-Cook法など）や、より高度なアルゴリズム（例: FFTベースのSchönhage-Strassenアルゴリズム）が用いられます。これらのアルゴリズムは、中間結果を格納するための一時的なメモリ領域を頻繁に必要とします。このコミットで変更された mul 関数も、このようなアルゴリズムの一部であり、中間結果を保持するスライスの効率的な管理がパフォーマンスに直結します。

技術的詳細

このコミットの技術的な核心は、Goのスライスが持つ「基になる配列」の概念と、関数の戻り値がその基になる配列を再利用する可能性を最大限に活用することにあります。

nat 型は []Word のエイリアス（またはそれに近い構造）であると推測されます。t.mul(x0, y1) のようなメソッド呼び出しでは、t は nat 型のレシーバであり、mul メソッドは nat 型の値を返します。

Goの慣習として、パフォーマンスが重要な関数では、引数として渡されたスライスの基になる配列を再利用して結果を返すことがあります。例えば、append 関数は、既存のスライスに要素を追加する際に、容量が足りなければ新しい配列を割り当てますが、容量が十分であれば既存の配列を拡張して使用します。同様に、t.mul() のような関数も、t が持つ基になる配列を再利用して乗算結果を格納し、その配列を参照する新しいスライスを返すように実装されている可能性があります。

変更前のコード addAt(z, t.mul(x0, y1), k) では、t.mul(x0, y1) の結果が一時的な匿名変数として生成され、それが直接 addAt 関数に渡されていました。この場合、t.mul() が t の基になる配列を再利用して結果を返したとしても、その結果が t に再代入されないため、次のイテレーションで t が使用される際には、古い t の基になる配列が使われ、t.mul() が再度新しい配列を割り当てる可能性がありました。

変更後のコード t = t.mul(x0, y1); addAt(z, t, k) では、t.mul() の結果が明示的に t に再代入されます。これにより、t.mul() が t の基になる配列を再利用して結果を返した場合、その再利用された配列が t の新しい基になる配列として設定されます。その結果、次の t.mul() の呼び出しでは、以前の計算で拡張された t の基になる配列をさらに再利用できる可能性が高まり、余分なメモリ割り当てが削減されます。

この最適化は、特にループ内で何度も t.mul() のような操作が行われる場合に、累積的なメモリ割り当ての削減と、それに伴うGC負荷の軽減に大きく貢献します。

nat_test.go の rndNat 関数における return x.norm() への変更は、生成される乱数 nat が常に正規化された状態であることを保証します。norm() メソッドは、nat の内部表現から先頭のゼロワードを取り除くなどして、その値を正規形に変換する役割を持つと考えられます。これにより、テストデータの整合性が保たれ、mul 関数などのテストがより正確に行われるようになります。これは直接的なパフォーマンス改善ではありませんが、テストの信頼性を高める上で重要です。

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

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

--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -438,8 +438,9 @@ func (z nat) mul(x, y nat) nat {
 
 	// add x0*y1*b
 	x0 := x0.norm()
-	y1 := y[k:] // y1 is normalized because y is
-	addAt(z, t.mul(x0, y1), k)
+	y1 := y[k:]       // y1 is normalized because y is
+	t = t.mul(x0, y1) // update t so we don't lose t's underlying array
+	addAt(z, t, k)
 
 	// add xi*y0<<i, xi*y1*b<<(i+k)
 	y0 := y0.norm()
@@ -449,8 +449,10 @@ func (z nat) mul(x, y nat) nat {
 			xi = xi[:k]
 		}
 		xi = xi.norm()
-		addAt(z, t.mul(xi, y0), i)
-		addAt(z, t.mul(xi, y1), i+k)
+		t = t.mul(xi, y0)
+		addAt(z, t, i)
+		t = t.mul(xi, y1)
+		addAt(z, t, i+k)
 	}
 }
 
@@ -1232,7 +1235,7 @@ func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
 // reuses the storage of z if possible.
 func (z nat) expNN(x, y, m nat) nat {
 	if alias(z, x) || alias(z, y) {
-		// We cannot allow in place modification of x or y.
+		// We cannot allow in-place modification of x or y.
 		z = nil
 	}

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

--- a/src/pkg/math/big/nat_test.go
+++ b/src/pkg/math/big/nat_test.go
@@ -179,7 +179,7 @@ func allocBytes(f func()) uint64 {
 
 // TestMulUnbalanced tests that multiplying numbers of different lengths
 // does not cause deep recursion and in turn allocate too much memory.
-// test case for issue 3807
+// Test case for issue 3807.
 func TestMulUnbalanced(t *testing.T) {
 	x := rndNat(50000)
 	y := rndNat(40)
@@ -201,7 +201,7 @@ func rndNat(n int) nat {
 	for i := 0; i < n; i++ {
 		x[i] = Word(rnd.Int63()<<1 + rnd.Int63n(2))
 	}
-	return x
+	return x.norm()
 }
 
 func BenchmarkMul(b *testing.B) {

コアとなるコードの解説

`src/pkg/math/big/nat.go` の `mul` 関数内の変更

mul 関数は、nat 型の大きな数値の乗算を行う関数です。この関数内で、中間結果を計算するために t.mul() メソッドが呼び出されています。

変更前:

addAt(z, t.mul(x0, y1), k)

この行では、t.mul(x0, y1) の結果が直接 addAt 関数に渡されています。もし t.mul が t の基になる配列を再利用して結果を返していたとしても、その結果は一時的な値として扱われ、t 自体は更新されません。次のループイテレーションで t が再び使用される際、t は以前の（更新されていない）基になる配列を参照しているため、t.mul は再度新しい配列を割り当てる可能性がありました。

変更後:

t = t.mul(x0, y1) // update t so we don't lose t's underlying array
addAt(z, t, k)

この変更により、t.mul(x0, y1) の結果が明示的に変数 t に再代入されます。これにより、t.mul が t の基になる配列を再利用して結果を返した場合、その再利用された配列が t の新しい基になる配列として設定されます。コメントにあるように、「t の基になる配列を失わないように更新する」ことで、後続の t.mul 呼び出しが、以前の計算で拡張された t の基になる配列をさらに再利用できるようになり、結果としてメモリ割り当ての回数が削減されます。

同様の変更が、mul 関数内の別の箇所でも行われています。

// 変更前
addAt(z, t.mul(xi, y0), i)
addAt(z, t.mul(xi, y1), i+k)

// 変更後
t = t.mul(xi, y0)
addAt(z, t, i)
t = t.mul(xi, y1)
addAt(z, t, i+k)

ここでも、t.mul の結果を t に再代入することで、一時的なスライスの再利用を促進し、メモリ割り当てを削減しています。

`src/pkg/math/big/nat.go` の `expNN` 関数内のコメント修正

これはパフォーマンスとは直接関係なく、単なるコメントのタイポ修正です。 in place が in-place に変更されています。

`src/pkg/math/big/nat_test.go` の `rndNat` 関数内の変更