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

コミット

コミット: c7cf56bec994c6888be89c7c8f8a1911fb266ca8
作成者: Robert Griesemer gri@golang.org
日付: 2011年10月18日 12:40:41 -0700
メッセージ: big: handle aliasing correctly for Rat.SetFrac.

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

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

元コミット内容

このコミットは、Go言語のmath/bigパッケージにおけるRat.SetFracメソッドのエイリアシング問題を修正したものです。具体的には、Issue #2379を解決し、2つのファイルを変更しています：

src/pkg/big/rat.go - メインのロジック修正（8行追加、2行削除）
src/pkg/big/rat_test.go - テストケースの追加（40行追加）

変更の背景

エイリアシング問題の発生

Go 1.0リリース前の2011年、big.RatのSetFracメソッドにおいて、メモリエイリアシングが原因で予期しない動作が発生する問題が発見されました。この問題は、以下のような状況で発生していました：

レシーバー自身のフィールドを引数として使用する場合：

x := big.NewRat(2, 3)
x.SetFrac(x.Denom(), x.Num())  // 有理数を逆数に変換

同じIntオブジェクトを分子と分母に使用する場合：
```
n := big.NewInt(7)
x.SetFrac(n, n)  // 7/7 = 1
```

問題の具体的な症状

修正前のコードでは、x.SetFrac(x.Denom(), x.Num())を実行すると、期待される3/2ではなく1/1が出力されていました。これは、SetFrac内部での処理中に、引数として渡された値が同じメモリ領域を参照していたため、処理の途中で値が変更されてしまうことが原因でした。

Go言語における大整数の内部構造

Go言語のmath/bigパッケージでは、大整数や有理数を以下のような構造で表現しています：

Int型：符号フラグ（neg）と絶対値（abs）で構成
Rat型：分子（a）と分母（b）の2つのIntで構成
nat型：[]Wordスライスで多精度整数を表現

このような構造において、メモリの共有（エイリアシング）が発生すると、意図しない副作用が生じる可能性があります。

前提知識の解説

メモリエイリアシングとは

メモリエイリアシングとは、異なる変数や参照が同じメモリ領域を指している状態を指します。Go言語では、スライスやポインタによって容易にエイリアシングが発生する可能性があります。

Go言語のスライスとメモリ共有

Go言語のスライスは以下の構造を持ちます：

ptr：データへのポインタ
len：現在の長さ
cap：容量

複数のスライスが同じ基底配列を共有する場合、一方のスライスの変更がもう一方に影響を与える可能性があります。

big.Ratの内部構造

type Rat struct {
    a, b Int  // 分子と分母
}

type Int struct {
    neg bool  // 符号
    abs nat   // 絶対値
}

type nat []Word  // 多精度整数のスライス

エイリアシング検出の重要性

多精度演算ライブラリでは、以下の理由でエイリアシング検出が重要です：

パフォーマンス最適化：不要なメモリコピーを避けるため
正確性の保証：計算結果の整合性を保つため
メモリ効率：メモリ使用量を最小化するため

技術的詳細

修正前のコード

func (z *Rat) SetFrac(a, b *Int) *Rat {
    z.a.Set(a)
    z.a.neg = a.neg != b.neg
    z.b = z.b.set(b.abs)
    return z.norm()
}

修正後のコード

func (z *Rat) SetFrac(a, b *Int) *Rat {
    z.a.neg = a.neg != b.neg
    babs := b.abs
    if &z.a == b || alias(z.a.abs, babs) {
        babs = nat(nil).set(babs) // make a copy
    }
    z.a.abs = z.a.abs.set(a.abs)
    z.b = z.b.set(babs)
    return z.norm()
}

修正の詳細分析

1. エイリアシング検出ロジック

if &z.a == b || alias(z.a.abs, babs) {
    babs = nat(nil).set(babs) // make a copy
}

この条件では2つのケースをチェックしています：

&z.a == b：レシーバーの分子（z.a）と引数bが同じオブジェクトを参照しているか
alias(z.a.abs, babs)：レシーバーの分子の絶対値と引数bの絶対値が同じnatスライスを共有しているか

2. 安全なコピーの作成

エイリアシングが検出された場合、nat(nil).set(babs)により新しいnatスライスを作成し、元の値をコピーします。これにより、後続の処理で元の値が変更されることを防ぎます。

3. 処理順序の最適化

修正後のコードでは、以下の順序で処理を行います：

符号の設定：z.a.neg = a.neg != b.neg
エイリアシング検出とコピー作成
分子の設定：z.a.abs = z.a.abs.set(a.abs)
分母の設定：z.b = z.b.set(babs)
正規化：return z.norm()

 // SetFrac sets z to a/b and returns z.
 func (z *Rat) SetFrac(a, b *Int) *Rat {
-	z.a.Set(a)
 	z.a.neg = a.neg != b.neg
-	z.b = z.b.set(b.abs)
+	babs := b.abs
+	if &z.a == b || alias(z.a.abs, babs) {
+		babs = nat(nil).set(babs) // make a copy
+	}
+	z.a.abs = z.a.abs.set(a.abs)
+	z.b = z.b.set(babs)
 	return z.norm()
 }

テストケースの追加

func TestIssue2379(t *testing.T) {
    // 各種エイリアシングケースのテスト
    // 1) エイリアシングなし
    // 2) 分子のエイリアシング
    // 3) 分母のエイリアシング
    // 4) 分子と分母のエイリアシング
    // 5) 分子と分母が同じオブジェクト
}

コアとなるコードの解説

エイリアシング検出の仕組み

ポインタ比較：&z.a == b
- レシーバーの分子フィールドのアドレスと引数bのアドレスを直接比較
- これにより、同じIntオブジェクトかどうかを判定
nat スライスの比較：alias(z.a.abs, babs)
- より深いレベルでのメモリ共有を検出
- natスライスの基底配列が同じかどうかを判定

安全なコピー戦略

babs := b.abs
if /* エイリアシング検出 */ {
    babs = nat(nil).set(babs)  // コピーを作成
}

この戦略により：

通常のケースではコピーを作成せず、パフォーマンスを維持
エイリアシングが検出された場合のみコピーを作成し、安全性を確保

テストケースの網羅性

追加されたテストケースは以下の5つのシナリオをカバーしています：

エイリアシングなし：通常の使用ケース
分子のエイリアシング：x.SetFrac(NewInt(3), x.Num())
分母のエイリアシング：x.SetFrac(x.Denom(), NewInt(2))
分子と分母の相互エイリアシング：x.SetFrac(x.Denom(), x.Num())
同一オブジェクトの使用：x.SetFrac(n, n)

これらのテストケースにより、あらゆるエイリアシングパターンが正しく処理されることを保証しています。

comemo