[インデックス 10393] math/big: nat{}からnat(nil)への置換によるパフォーマンス最適化

コミット

commit f5cf0a486ecded2e5200b53973cc53c74d1f25aa
Author: Robert Griesemer <gri@golang.org>
Date:   Mon Nov 14 13:35:22 2011 -0800

    math/big: replace nat{} -> nat(nil)
    
    No need for creating a new nat each time.
    Per Roger Peppe's suggestion; assuming
    nat(nil) produces better code than nat{}.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/5375092

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

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

元コミット内容

このコミットは、Go言語のmath/bigパッケージ内で、nat{}の使用をnat(nil)に置き換える最適化を行いました。Robert Griesemer氏により2011年11月14日に実装され、Roger Peppe氏の提案に基づいています。

変更対象となったファイルは以下の通りです：

src/pkg/math/big/int.go (30行の変更)
src/pkg/math/big/nat.go (10行の変更)
src/pkg/math/big/nat_test.go (26行の変更)
src/pkg/math/big/rat.go (14行の変更)

合計40行の追加、40行の削除という対称的な変更でした。

変更の背景

2011年当時、Go言語のmath/bigパッケージでは、一時的な自然数（natural number）のスライスを作成する際にnat{}という記法が使われていました。しかし、Roger Peppe氏の提案により、nat(nil)の方がより効率的なコードを生成することが指摘されました。

この変更は、パフォーマンスの向上を目的としており、特に大きな数値を扱う演算において、不要なメモリ割り当てを削減することが期待されました。

前提知識の解説

natとは

natは、Go言語のmath/bigパッケージにおいて、自然数（非負整数）を表現するためのスライス型です。定義は以下の通りです：

type nat []Word

ここでWordは、システムアーキテクチャに応じたワード長（通常は32ビットまたは64ビット）の符号なし整数です。

nilスライスと空スライスの違い

Go言語において、スライスにはnilスライスと空スライスという2つの"空"の状態があります：

nilスライス: var s []int または []int(nil)
- 長さ：0
- 容量：0
- 基底配列：nil
空スライス: []int{} または make([]int, 0)
- 長さ：0
- 容量：0（または指定された容量）
- 基底配列：存在する（長さ0だが割り当て済み）

パフォーマンス上の違い

nilスライスと空スライスの主な違いは以下の通りです：

メモリ割り当て：
- nilスライス：基底配列の割り当てなし
- 空スライス：基底配列の割り当てあり（長さ0でも）
append操作：
- nilスライス：最初のappendで新しい配列を割り当て
- 空スライス：容量がある場合は配列を再利用
コンパイラ最適化：
- nilスライス：より効率的な機械語コードを生成
- 空スライス：不要な初期化コードが生成される場合がある

技術的詳細

nat{}からnat(nil)への変更理由

メモリ効率の向上：
- nat{}は空の基底配列を持つスライスを作成
- nat(nil)は基底配列を持たないnilスライスを作成
- 一時的な演算において、不要なメモリ割り当てを削減
コンパイラ最適化：
- nat(nil)はより効率的な機械語コードを生成
- 型変換のオーバーヘッドが削減される
ガベージコレクション効率：
- 不要な小さなオブジェクトの生成を避けることで、GC負荷を軽減

変更パターンの分析

このコミットで変更されたパターンは、主に以下の用途で使用されていました：

一時的な演算結果の保存：

// 変更前
t := nat{}.sub(z.abs, natOne)
// 変更後
t := nat(nil).sub(z.abs, natOne)

除算操作でのクォータント・レマインダー：

// 変更前
q, r := nat{}.div(nat{}, z.a.abs, z.b)
// 変更後
q, r := nat(nil).div(nat(nil), z.a.abs, z.b)

テストコードでの初期化：

// 変更前
z := nat{}.set(a.z)
// 変更後
z := nat(nil).set(a.z)

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

主要な変更箇所を以下に示します：

int.goでの変更

// Rem関数での変更
func (z *Int) Rem(x, y *Int) *Int {
-    _, z.abs = nat{}.div(z.abs, x.abs, y.abs)
+    _, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
     z.neg = len(z.abs) > 0 && x.neg
     return z
}

// Bit関数での変更
func (z *Int) Bit(i int) uint {
     if i < 0 {
         panic("negative bit index")
     }
     if z.neg {
-        t := nat{}.sub(z.abs, natOne)
+        t := nat(nil).sub(z.abs, natOne)
         return t.bit(uint(i)) ^ 1
     }
     // ...
}

nat.goでの変更

// mulRange関数での変更
func (z nat) mulRange(a, b uint64) nat {
     // ...
     case a+1 == b:
-        return z.mul(nat{}.setUint64(a), nat{}.setUint64(b))
+        return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b))
     }
     m := (a + b) / 2
-    return z.mul(nat{}.mulRange(a, m), nat{}.mulRange(m+1, b))
+    return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
}

// string関数での変更
func (x nat) string(charset string) string {
     // ...
     // preserve x, create local copy for use in repeated divisions
-    q := nat{}.set(x)
+    q := nat(nil).set(x)
     // ...
}

rat.goでの変更

// SetFrac関数での変更
func (z *Rat) SetFrac(a, b *Int) *Rat {
     // ...
     if &z.a == b || alias(z.a.abs, babs) {
-        babs = nat{}.set(babs) // make a copy
+        babs = nat(nil).set(babs) // make a copy
     }
     // ...
}

// FloatString関数での変更
func (z *Rat) FloatString(prec int) string {
     // ...
-    q, r := nat{}.div(nat{}, z.a.abs, z.b)
+    q, r := nat(nil).div(nat(nil), z.a.abs, z.b)
     // ...
}

コアとなるコードの解説

1. 除算操作の最適化

// 変更前
_, z.abs = nat{}.div(z.abs, x.abs, y.abs)
// 変更後
_, z.abs = nat(nil).div(z.abs, x.abs, y.abs)

この変更により、除算操作において一時的なnatインスタンスの作成が最適化されます。nat{}は空の基底配列を持つスライスを作成しますが、nat(nil)はnilスライスを作成するため、不要なメモリ割り当てが削減されます。

2. ビット演算の最適化

// 変更前
t := nat{}.sub(z.abs, natOne)
// 変更後
t := nat(nil).sub(z.abs, natOne)

ビット演算において、負の数の2の補数表現を計算する際に使用される一時変数tの初期化が最適化されます。

3. 乗算範囲計算の最適化

// 変更前
return z.mul(nat{}.setUint64(a), nat{}.setUint64(b))
// 変更後
return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b))

階乗計算や範囲乗算において、中間結果を保存するためのnatインスタンスの作成が最適化されます。

4. 文字列変換の最適化

// 変更前
q := nat{}.set(x)
// 変更後
q := nat(nil).set(x)

大きな数値を文字列に変換する際に、元の値を保持するためのコピーの作成が最適化されます。

パフォーマンスへの影響

この変更により、以下の効果が期待されます：

メモリ使用量の削減：不要な小さなオブジェクトの生成を避けることで、総メモリ使用量が削減されます。
割り当て頻度の削減：ガベージコレクションの負荷が軽減され、全体的なパフォーマンスが向上します。
コンパイラ最適化の向上：より効率的な機械語コードの生成により、実行時間が短縮されます。

comemo