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

このコミットは、Go言語の初期の標準ライブラリの一部である src/lib/bignum.go ファイルに対する変更です。このファイルは、Go言語における多倍長整数（任意精度整数）の演算を扱うための基盤を提供していました。具体的には、Natural 型（非負の整数を表す）に対する加算、減算、乗算、ビット論理演算（AND, OR, XOR）、シフト演算などの基本的な算術操作の実装が含まれています。

コミット

このコミットは、多倍長整数演算ライブラリにおけるパフォーマンスと正確性の改善を目的としています。主な変更点は以下の通りです。

Natural.And() メソッドにおけるバグの修正。
非効率な関数分割（"non-beneficial factorization"）の削除。これにより、操作あたりの配列スライスの生成回数が大幅に削減されました。
コード行数の削減。
benchhil ベンチマークにおいて、実行時間が約2%短縮されるというパフォーマンス改善が達成されました。

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

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

元コミット内容

commit ab0d2582b475751ef0f81adff13e616067250b1b
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Dec 18 09:55:33 2008 -0800

    - fixed a bug in Natural.And()
    - removed some non-beneficial factorization and reduced number of array slices per
      operations significantly
    - reduced line count
    - benchhil benchmark time reduced by ~2%
    
    R=r
    DELTA=313  (106 added, 163 deleted, 44 changed)
    OCL=21473
    CL=21497

変更の背景

このコミットが行われた2008年12月は、Go言語がまだ一般に公開される前の開発初期段階でした。当時のGo言語の設計者たちは、言語のパフォーマンスと効率性を極限まで高めることに注力していました。

このコミットの背景には、以下の課題があったと考えられます。

Natural.And() のバグ: 多倍長整数のビット論理積 (AND) 演算に、計算結果の正確性に影響を与えるバグが存在していました。これは、正確な数値計算を保証するライブラリにとって致命的な問題であり、修正が急務でした。
パフォーマンスのボトルネック:
- 非効率な関数分割 (Factorization): コードベースには、多倍長整数演算の内部処理を細かく分割した低レベル関数が多数存在していました。これらの関数は、それぞれが小さなタスクを実行するように設計されていましたが、頻繁な関数呼び出しはオーバーヘッドとなり、全体的なパフォーマンスを低下させていました。特に、ループ内でこれらの関数が繰り返し呼び出される場合、その影響は顕著になります。
- 過剰な配列スライス生成: Go言語のスライスは強力な機能ですが、頻繁に新しいスライスを作成したり、既存のスライスから小さなサブスライスを生成したりする操作は、メモリ割り当てとガベージコレクションの負荷を増大させ、パフォーマンスの低下につながります。特に、多倍長整数のように大きなデータ構造を扱う場合、この問題はより深刻になります。
コードの複雑性: 細かく分割された関数と、それらを連携させるためのスライス操作は、コードの可読性や保守性を損なう可能性がありました。

これらの課題に対処し、Go言語の多倍長整数ライブラリの堅牢性と効率性を向上させることが、このコミットの主要な動機となりました。特に、benchhil ベンチマークでの2%の改善は、当時のGo言語開発チームがパフォーマンス最適化にどれほど注力していたかを示しています。

前提知識の解説

多倍長整数 (BigNum/Arbitrary-Precision Arithmetic)

多倍長整数とは、コンピュータの標準的なデータ型（例: 32ビット整数、64ビット整数）で表現できる範囲を超える、任意の大きさの整数を扱うためのデータ構造とアルゴリズムの総称です。

内部表現: 通常、多倍長整数は、コンピュータのワードサイズ（例: 64ビット）に収まる「桁（Digit）」の配列として表現されます。例えば、10進数の大きな数を扱う場合、各配列要素が10000（10の4乗）を表すような形で格納されることがあります。Go言語の bignum.go では、Digit 型がこの基本単位を表し、Natural 型が []Digit（Digitのスライス）として定義されています。
算術演算: 加算、減算、乗算、除算、ビット演算などの基本的な算術操作は、これらの桁の配列に対して、小学校で習う筆算のように、下位の桁から順に処理を行い、繰り上がりや繰り下がりを適切に処理することで実現されます。例えば、加算では、各桁を足し合わせ、桁あふれが発生した場合は次の上位の桁に繰り上げます。

Go言語の初期の設計思想

Go言語は、Googleで開発されたプログラミング言語で、2009年に一般公開されました。その設計目標の一つに「効率性」があります。これは、コンパイル速度、実行速度、メモリ使用量の全てにおいて効率的であることを目指していました。

このコミットが行われた2008年は、Go言語がまだ内部開発段階であり、言語仕様や標準ライブラリの設計が活発に行われていました。当時の開発者たちは、C++のようなシステムプログラミング言語のパフォーマンスと、PythonやJavaScriptのようなスクリプト言語の生産性を両立させることを目指していました。そのため、細部にわたるパフォーマンス最適化が頻繁に行われていました。

配列スライス (Array Slices)

Go言語のスライスは、配列の一部を参照する軽量なデータ構造です。スライスは、基盤となる配列へのポインタ、長さ、容量の3つの要素で構成されます。

利点: スライスは、動的なサイズの配列のような振る舞いを可能にし、メモリ効率の良いデータ操作を提供します。
パフォーマンスへの影響: しかし、スライスを頻繁に作成したり、既存のスライスから新しいスライスを生成したりする操作は、内部的に新しいスライスヘッダの作成や、場合によっては基盤となる配列のコピー（容量が足りない場合）を伴うため、オーバーヘッドが発生します。特に、小さなスライスを大量に生成し、それがすぐに不要になるようなパターンは、ガベージコレクションの負荷を増大させ、パフォーマンスのボトルネックとなる可能性があります。

ビット演算 (Bitwise Operations)

ビット演算は、数値をビット列として扱い、個々のビットに対して論理演算（AND, OR, XOR, NOT）やシフト演算（左シフト, 右シフト）を行う操作です。

AND (&): 両方のビットが1の場合にのみ結果が1になります。
OR (|): どちらか一方または両方のビットが1の場合に結果が1になります。
XOR (^): どちらか一方のビットのみが1の場合に結果が1になります（排他的論理和）。
シフト演算: ビット列を左右に移動させます。左シフトは乗算、右シフトは除算に相当することが多いです。

多倍長整数においては、これらのビット演算は、各桁（Digit）に対して個別に適用され、必要に応じて桁間の繰り上がりや繰り下がりを考慮しながら処理されます。

`Natural.And()`

Natural.And() は、2つの多倍長整数 x と y のビットごとの論理積（AND）を計算し、その結果を新しい多倍長整数として返すメソッドです。例えば、x = 10 (1010_2) と y = 6 (0110_2) の場合、x.And(y) は 2 (0010_2) を返します。この操作は、特定のビットマスクを適用したり、共通のビットが立っている部分を抽出したりする際に使用されます。

技術的詳細

このコミットの技術的詳細は、主にパフォーマンス最適化とコードの簡素化に焦点を当てています。

`Natural.And()` のバグ修正

コミットメッセージには「fixed a bug in Natural.And()」とありますが、具体的なバグの内容は示されていません。しかし、差分を見ると、And 関数（低レベルのDigit配列に対するAND演算）が削除され、Natural.And メソッド内で直接ループ処理が行われるように変更されています。

変更前:

func (x *Natural) And(y *Natural) *Natural {
	// ...
	z := new(Natural, n);
	And(z[0 : m], x[0 : m], y); // 低レベルのAnd関数を呼び出し
	Or1(z[m : n], x[m : n], 0); // 低レベルのOr1関数を呼び出し
	return Normalize(z);
}

変更後:

func (x *Natural) And(y *Natural) *Natural {
	// ...
	z := new(Natural, m); // 結果のサイズがmになるように変更
	for i := 0; i < m; i++ {
		z[i] = x[i] & y[i]; // 直接ビットAND演算
	}
	// upper bits are 0 (上位ビットは0になるため、Or1の呼び出しが不要に)
	return Normalize(z);
}

この変更により、And 関数と Or1 関数への呼び出しが削除され、Natural.And メソッド内で直接ビットごとのAND演算が行われるようになりました。これにより、関数呼び出しのオーバーヘッドが削減されるだけでなく、Or1 を使って上位ビットを0で埋めるという冗長な処理が不要になったことで、バグが修正されたか、あるいはバグが発生しにくい、より直接的な実装になったと考えられます。特に、And 演算の性質上、結果の長さは短い方のオペランドの長さに等しくなるため、z[m:n] の部分を Or1 で処理する必要がなくなったことが重要です。

非効率な因数分解の削除と配列スライスの削減

このコミットの最も大きな変更点は、src/lib/bignum.go の冒頭部分に定義されていた、Digit 型のスライスに対する低レベルな算術演算関数（Add1, Add, Sub1, Sub, Mul, Shl, Shr, And1, And, Or1, Or, Xor1, Xor など）が多数削除されたことです。

これらの関数は、例えば Add(z, x, y *[]Digit) のように、結果を格納するスライス z とオペランドのスライス x, y を引数として受け取っていました。Natural 型のメソッド（例: (x *Natural) Add(y *Natural) *Natural）は、これらの低レベル関数を呼び出す際に、x[0:m] のように部分的なスライスを生成して渡していました。

変更前（概念図）:

Natural.Add()
  -> Add(z[0:m], x[0:m], y)  // スライス生成と関数呼び出し
  -> Add1(z[m:n], x[m:n], c) // スライス生成と関数呼び出し

変更後（概念図）:

Natural.Add()
  -> for i < m { ... } // ループ内で直接要素にアクセス
  -> for i < n { ... } // ループ内で直接要素にアクセス

この変更により、以下の効果が得られました。

関数呼び出しのオーバーヘッド削減: 低レベル関数への頻繁な呼び出しが不要になり、関数呼び出しに伴うスタックフレームの生成や引数のコピーといったオーバーヘッドが削減されました。
配列スライス生成の削減: 各操作で部分的なスライスを生成して渡す必要がなくなったため、スライスヘッダの作成や、場合によっては基盤となる配列のコピーといったコストが削減されました。これにより、メモリ割り当ての回数が減り、ガベージコレクションの頻度と負荷が軽減されます。
コンパイラ最適化の機会増加: コードがインライン化されたことで、コンパイラがより広範なコンテキストで最適化（例: レジスタ割り当ての最適化、不要なロード/ストアの削除）を行う機会が増加しました。

`Mul11` 関数の再利用

多くの低レベル関数が削除された中で、Mul11(x, y Digit) (Digit, Digit) 関数は残され、Natural.Mul メソッド内で直接呼び出されるようになりました。Mul11 は、2つの単一桁（Digit）を乗算し、その結果を2つの桁（繰り上がりと結果）として返す関数です。これは多倍長整数乗算の基本的なビルディングブロックであり、非常に頻繁に呼び出されるため、その効率性が重要です。

この関数が削除されずに残されたのは、その粒度が適切であり、これ以上細かく分割してもメリットがない、あるいはインライン化してもコンパイラが同等の最適化を行うと判断されたためと考えられます。

`Copy` 関数の導入

Natural.Or および Natural.Xor メソッドでは、変更前は Or1(z[m : n], x[m : n], 0) のように、残りの部分をゼロでOR演算することでコピーしていました。このコミットでは、新しく Copy(z, x *[]Digit) 関数が導入され、より直接的にスライスをコピーするようになりました。

変更前 (Natural.Or の一部):

	Or1(z[m : n], x[m : n], 0); // 0とのORでコピー

変更後 (Natural.Or の一部):

	Copy(z[m : n], x[m : n]); // Copy関数で直接コピー

これは、セマンティクスをより明確にし、不要なビット演算を避けるための改善です。

正規化 (Normalize) の変更

Natural.Add および Natural.Sub メソッドでは、変更前は最後に Normalize(z) を呼び出して結果を正規化していました。変更後、Add メソッドでは z[0 : i] のように結果のスライス長をループ内で動的に調整するようになり、Sub メソッドではループの最後に不要な先行ゼロを削除する処理が追加されました。

これにより、Normalize 関数への呼び出しが不要になり、結果のサイズ調整がより効率的に行われるようになりました。

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

主な変更は src/lib/bignum.go ファイルに集中しています。

低レベル算術関数の削除:
- Add1, Add, Sub1, Sub, Mul, Shl, Shr, And1, And, Or1, Or, Xor1, Xor といった、Digit スライスを直接操作する関数がファイル冒頭から削除されました。これらは約170行にわたるコードでした。
Natural 型メソッドへのロジックのインライン化:
- func (x *Natural) Add(y *Natural) *Natural
- func (x *Natural) Sub(y *Natural) *Natural
- func (x *Natural) Mul(y *Natural) *Natural
- func (x *Natural) Shl(s uint) *Natural
- func (x *Natural) Shr(s uint) *Natural
- func (x *Natural) And(y *Natural) *Natural
- func (x *Natural) Or(y *Natural) *Natural
- func (x *Natural) Xor(y *Natural) *Natural これらのメソッド内で、以前は低レベル関数に委譲していた処理が、直接ループを使って実装されるようになりました。これにより、関数呼び出しとスライス生成が削減されています。
Mul11, Shl, Shr 関数の移動:
- Mul11, Shl, Shr 関数は削除されず、Natural 型のメソッドの定義に近い位置に移動されました。これは、これらの関数が引き続き有用な低レベルプリミティブとして機能するためです。
Copy 関数の追加:
- func Copy(z, x *[]Digit) という新しい関数が追加され、スライスの内容を直接コピーするために使用されます。
Natural.ToString メソッドの変更:
- Or1(t, x, 0) によるコピーが Copy(t, x) に変更されました。

コアとなるコードの解説

ここでは、Natural.Add メソッドの変更を例にとり、どのようにロジックがインライン化され、効率化が図られたかを詳細に解説します。

`Natural.Add` メソッドの変更

変更前:

func (x *Natural) Add(y *Natural) *Natural {
	n := len(x);
	m := len(y);
	if n < m {
		return y.Add(x);
	}

	z := new(Natural, n + 1);
	c := Add(z[0 : m], x[0 : m], y); // 低レベルのAdd関数を呼び出し
	z[n] = Add1(z[m : n], x[m : n], c); // 低レベルのAdd1関数を呼び出し

	return Normalize(z); // 正規化
}

このコードでは、x と y の短い方の長さ m までを Add 関数で処理し、残りの x の部分を Add1 関数（単一桁の加算）で処理しています。Add と Add1 はそれぞれ Digit スライスを引数にとるため、x[0:m], z[0:m], z[m:n], x[m:n] といったスライスが生成され、関数呼び出しが行われていました。

変更後:

func (x *Natural) Add(y *Natural) *Natural {
	n := len(x);
	m := len(y);
	if n < m {
		return y.Add(x);
	}

	c := Digit(0); // 繰り上がり (carry)
	z := new(Natural, n + 1); // 結果を格納するスライス

	i := 0;
	// 短い方のオペランドの長さまで加算
	for i < m {
		t := c + x[i] + y[i]; // 現在の桁と繰り上がり、yの桁を加算
		c, z[i] = t>>W, t&M; // 繰り上がりと結果の桁を計算
		i++;
	}
	// 長い方のオペランドの残りの部分を加算（繰り上がりがある場合）
	for i < n {
		t := c + x[i]; // 現在の桁と繰り上がりを加算
		c, z[i] = t>>W, t&M; // 繰り上がりと結果の桁を計算
		i++;
	}
	// 最後の繰り上がりを処理
	if c != 0 {
		z[i] = c;
		i++;
	}

	return z[0 : i]; // 結果のスライスを適切な長さに調整して返す
}

変更後のコードでは、Add および Add1 関数への呼び出しが完全に削除され、そのロジックが Natural.Add メソッドの内部に直接インライン化されています。

ループによる直接アクセス: for i < m と for i < n の2つのループにより、x[i], y[i], z[i] の各要素に直接アクセスして加算処理を行っています。これにより、スライスの生成や関数呼び出しのオーバーヘッドがなくなります。
繰り上がり (carry) の直接管理: c 変数で繰り上がりを直接管理し、各桁の計算結果 t から次の繰り上がりと現在の桁の値を計算しています。
動的な結果サイズ調整: 最後に return z[0 : i] とすることで、結果の多倍長整数の実際の長さに合わせてスライスを調整しています。これにより、以前の Normalize 関数による後処理が不要になりました。

この変更は、Go言語の初期の設計思想である「シンプルさ」と「効率性」を体現しています。コードはより直接的になり、関数呼び出しのオーバーヘッドとメモリ割り当てが削減され、結果としてパフォーマンスが向上しました。

参考にした情報源リンク

Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
Go言語の初期の設計に関する議論（Go言語のメーリングリストアーカイブなど、一般公開されている情報源があれば参照） (具体的なURLは、当時のメーリングリストのアーカイブを検索する必要がありますが、一般にはアクセスが難しい場合があります。)
多倍長整数演算に関する一般的な情報源（例: Wikipedia, 計算機科学の教科書） https://ja.wikipedia.org/wiki/%E5%A4%9A%E5%80%8D%E9%95%B7%E6%95%B4%E6%95%B0
Go言語のスライスに関するドキュメント: https://go.dev/blog/slices-intro https://go.dev/blog/go-slices-usage-and-internals
Go言語のパフォーマンス最適化に関する一般的な情報: https://go.dev/doc/effective_go#performance https://go.dev/blog/go-performance-tips-2011 (これらの記事はコミット当時のものではありませんが、Go言語のパフォーマンスに関する一般的な考え方を理解するのに役立ちます。)```markdown