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

このコミットは、Go言語の標準ライブラリ math/big パッケージ内の Int.Bit メソッドに対する最適化を導入しています。具体的には、Int.Bit(0)、つまり数値の最下位ビット（0番目のビット）を取得する際の共通ケースを高速化することを目的としています。この最適化により、特に数値が偶数か奇数かを判定するような頻繁に発生する操作のパフォーマンスが向上します。

コミット

• コミットハッシュ: 008c62b2cd728db744dcef53f1226cb1e43ba617
• 作者: Robert Griesemer gri@golang.org
• コミット日時: 2012年6月12日 火曜日 09:36:35 -0700

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

https://github.com/golang/go/commit/008c62b2cd728db744dcef53f1226cb1e43ba617

元コミット内容

math/big: optimize common case of Int.Bit(0)

R=golang-dev, dsymonds, rsc
CC=golang-dev
https://golang.org/cl/6306069

変更の背景

math/big パッケージは、Go言語で任意精度整数を扱うための機能を提供します。Int.Bit(i) メソッドは、指定されたインデックス i のビットの値を返します。このメソッドは、特に i=0 の場合、つまり数値が偶数か奇数かを判定するために最下位ビットをチェックする際に頻繁に呼び出されることが想定されます。

元の実装では、Int.Bit(0) の呼び出しも一般的なビット取得ロジックに従っていました。しかし、最下位ビットの取得は、数値の内部表現の最初のワード（最下位のワード）に直接アクセスすることで、より効率的に行うことができます。このコミットは、この特定の共通ケースを検出し、より直接的で高速なパスを提供することで、パフォーマンスのボトルネックを解消しようとしています。

前提知識の解説

math/big パッケージ

math/big パッケージは、Go言語で任意精度の数値演算を可能にするためのパッケージです。標準のGoの組み込み型（int, int64 など）は固定のビット幅を持ちますが、math/big の型（Int, Float, Rat）は、メモリが許す限り任意の大きさの数値を表現できます。これは、暗号化、科学計算、金融アプリケーションなど、非常に大きな整数や高精度な浮動小数点数が必要な場合に不可欠です。

Int 型は、符号と、数値の絶対値を表す Word 型のスライス（abs フィールド）で構成されます。Word は通常、プラットフォームのネイティブなワードサイズ（32ビットまたは64ビット）に対応する符号なし整数型です。数値の絶対値は、この Word のスライスをリトルエンディアン形式（最下位のワードがスライスの先頭に来る）で格納することで表現されます。

ビット演算と最下位ビット

ビット演算は、数値をビット列として扱い、個々のビットに対して論理演算を行うことです。

• ビットインデックス: 通常、ビットは右から左へ0から始まるインデックスで数えられます。0番目のビットは最下位ビット（Least Significant Bit, LSB）と呼ばれ、数値の偶奇を決定します。
• x >> i: 数値 x を i ビット右にシフトします。これにより、i 番目のビットが最下位ビットの位置に移動します。
• & 1: ビット列と1（バイナリで ...001）とのビットごとのAND演算を行います。これにより、最下位ビット以外のすべてのビットが0になり、最下位ビットの値（0または1）のみが残ります。

したがって、Int.Bit(i) の元の実装が (x>>i)&1 のロジックに従っていたのは、一般的なビット取得の標準的な方法です。

偶数/奇数判定

整数が偶数か奇数かを判定する最も一般的な方法は、その最下位ビットをチェックすることです。

• 最下位ビットが 0 の場合、その数値は偶数です。
• 最下位ビットが 1 の場合、その数値は奇数です。

このため、Int.Bit(0) は math/big.Int 型の偶奇判定に直接利用できるため、非常に頻繁に呼び出されることが予想されます。

技術的詳細

この最適化は、Int.Bit(0) の呼び出しが、math/big.Int の内部表現の特性を利用して、より効率的に処理できるという事実に基づいています。

math/big.Int の絶対値は、x.abs という Word 型のスライスに格納されています。このスライスは、数値の各「ワード」を保持しており、x.abs[0] は常に最下位のワード（Least Significant Word）を表します。最下位ビットは、この最下位のワードの最下位ビットに他なりません。

したがって、Int.Bit(0) の場合、以下の条件をチェックすることで、直接かつ高速に結果を得ることができます。

1. if i == 0: まず、要求されたビットインデックスが0であるかを確認します。これが最適化の対象となる共通ケースです。
2. if len(x.abs) > 0: 次に、数値がゼロでないことを確認します。x.abs スライスの長さが0の場合、その数値は0であり、0の0番目のビットは0です。スライスが空でない場合、少なくとも1つのワードが存在し、その最下位ワードにアクセスできます。
3. return uint(x.abs[0] & 1): x.abs[0] は最下位のワードです。このワードと 1 とのビットごとのAND演算 (& 1) を行うことで、そのワードの最下位ビットの値（0または1）を直接抽出できます。この結果は uint 型にキャストされて返されます。
   • x.abs[0] & 1 は、x が正の数であろうと負の数であろうと、その絶対値の最下位ビットを正しく返します。なぜなら、Bit メソッドは (x>>i)&1 と定義されており、これは符号に関わらず絶対値のビットを返すためです。コメント // bit 0 is same for -x がこの点を補足しています。

この最適化により、一般的なビットシフト操作や、より複雑な任意精度数値のビット操作ロジックを迂回し、直接メモリにアクセスして最下位ビットを取得できるため、大幅なパフォーマンス向上が期待できます。

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

diff --git a/src/pkg/math/big/int.go b/src/pkg/math/big/int.go
index ce308bd24f..276f56708a 100644
--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -697,6 +697,13 @@ func (z *Int) Rsh(x *Int, n uint) *Int {
 // Bit returns the value of the i'th bit of x. That is, it
 // returns (x>>i)&1. The bit index i must be >= 0.
 func (x *Int) Bit(i int) uint {
+	if i == 0 {
+		// optimization for common case: odd/even test of x
+		if len(x.abs) > 0 {
+			return uint(x.abs[0] & 1) // bit 0 is same for -x
+		}
+		return 0
+	}
 	if i < 0 {
 		panic("negative bit index")
 	}

コアとなるコードの解説

追加されたコードブロックは Int.Bit(i) メソッドの冒頭に挿入されています。

	if i == 0 {
		// optimization for common case: odd/even test of x
		if len(x.abs) > 0 {
			return uint(x.abs[0] & 1) // bit 0 is same for -x
		}
		return 0
	}

1. if i == 0 { ... }:

   • これは、この最適化が適用される条件です。引数 i が 0 である場合、つまり最下位ビットの取得が要求された場合にのみ、以下の最適化されたロジックが実行されます。
   • コメント // optimization for common case: odd/even test of x は、この最適化が偶数/奇数判定のような一般的なユースケースをターゲットにしていることを明確に示しています。

2. if len(x.abs) > 0 { ... }:

   • x.abs は math/big.Int の絶対値を構成する Word のスライスです。
   • len(x.abs) が 0 の場合、それは数値が 0 であることを意味します。0 の最下位ビットは 0 なので、この場合は直接 0 を返します。
   • len(x.abs) > 0 の場合、数値は 0 ではないため、x.abs[0]（最下位のワード）にアクセスしてビットを抽出できます。

3. return uint(x.abs[0] & 1):

   • x.abs[0] は、Int 型の数値の絶対値の最下位ワードです。
   • & 1 はビットごとのAND演算で、x.abs[0] の最下位ビットのみを抽出します。例えば、Word が ...xxxxxx1 であれば 1 を、...xxxxxx0 であれば 0 を返します。
   • uint(...) は、結果を uint 型にキャストしています。Bit メソッドの戻り値の型が uint であるためです。
   • コメント // bit 0 is same for -x は、負の数に対してもこのロジックが正しく機能することを保証しています。Bit メソッドの定義 (x>>i)&1 は、数値の絶対値のビットを返すため、符号は関係ありません。

この変更により、Int.Bit(0) の呼び出しは、複雑なビットシフトやループ処理を伴う汎用的なビット取得ロジックをスキップし、直接的な配列アクセスと単一のビット演算で完了するようになります。これにより、特に頻繁に Int.Bit(0) が呼び出されるアプリケーションにおいて、顕著なパフォーマンス改善が期待できます。

関連リンク

• Go CL 6306069: https://golang.org/cl/6306069

参考にした情報源リンク

• Go math/big パッケージのドキュメント: https://pkg.go.dev/math/big
• Go math/big のソースコード (int.go): https://github.com/golang/go/blob/master/src/math/big/int.go
• ビット演算に関する一般的な情報 (例: Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97
• 偶数と奇数に関する一般的な情報 (例: Wikipedia): https://ja.wikipedia.org/wiki/%E5%81%B6%E6%95%B0%E3%81%A8%E5%A5%87%E6%95%B0

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

このコミットは、Go言語の標準ライブラリ math/big パッケージ内の Int.Bit メソッドに対する最適化を導入しています。具体的には、Int.Bit(0)、つまり数値の最下位ビット（0番目のビット）を取得する際の共通ケースを高速化することを目的としています。この最適化により、特に数値が偶数か奇数かを判定するような頻繁に発生する操作のパフォーマンスが向上します。

コミット

• コミットハッシュ: 008c62b2cd728db744dcef53f1226cb1e43ba617
• 作者: Robert Griesemer gri@golang.org
• コミット日時: 2012年6月12日 火曜日 09:36:35 -0700

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

https://github.com/golang/go/commit/008c62b2cd728db744dcef53f1226cb1e43ba617

元コミット内容

math/big: optimize common case of Int.Bit(0)

R=golang-dev, dsymonds, rsc
CC=golang-dev
https://golang.org/cl/6306069

変更の背景

math/big パッケージは、Go言語で任意精度整数を扱うための機能を提供します。Int.Bit(i) メソッドは、指定されたインデックス i のビットの値を返します。このメソッドは、特に i=0 の場合、つまり数値が偶数か奇数かを判定するために最下位ビットをチェックする際に頻繁に呼び出されることが想定されます。

元の実装では、Int.Bit(0) の呼び出しも一般的なビット取得ロジックに従っていました。しかし、最下位ビットの取得は、数値の内部表現の最初のワード（最下位のワード）に直接アクセスすることで、より効率的に行うことができます。このコミットは、この特定の共通ケースを検出し、より直接的で高速なパスを提供することで、パフォーマンスのボトルネックを解消しようとしています。

前提知識の解説

math/big パッケージ

math/big パッケージは、Go言語で任意精度の数値演算を可能にするためのパッケージです。標準のGoの組み込み型（int, int64 など）は固定のビット幅を持ちますが、math/big の型（Int, Float, Rat）は、メモリが許す限り任意の大きさの数値を表現できます。これは、暗号化、科学計算、金融アプリケーションなど、非常に大きな整数や高精度な浮動小数点数が必要な場合に不可欠です。

Int 型は、符号と、数値の絶対値を表す Word 型のスライス（abs フィールド）で構成されます。Word は通常、プラットフォームのネイティブなワードサイズ（32ビットまたは64ビット）に対応する符号なし整数型です。数値の絶対値は、この Word のスライスをリトルエンディアン形式（最下位のワードがスライスの先頭に来る）で格納することで表現されます。

ビット演算と最下位ビット

ビット演算は、数値をビット列として扱い、個々のビットに対して論理演算を行うことです。

• ビットインデックス: 通常、ビットは右から左へ0から始まるインデックスで数えられます。0番目のビットは最下位ビット（Least Significant Bit, LSB）と呼ばれ、数値の偶奇を決定します。
• x >> i: 数値 x を i ビット右にシフトします。これにより、i 番目のビットが最下位ビットの位置に移動します。
• & 1: ビット列と1（バイナリで ...001）とのビットごとのAND演算を行います。これにより、最下位ビット以外のすべてのビットが0になり、最下位ビットの値（0または1）のみが残ります。

したがって、Int.Bit(i) の元の実装が (x>>i)&1 のロジックに従っていたのは、一般的なビット取得の標準的な方法です。

偶数/奇数判定

整数が偶数か奇数かを判定する最も一般的な方法は、その最下位ビットをチェックすることです。

• 最下位ビットが 0 の場合、その数値は偶数です。
• 最下位ビットが 1 の場合、その数値は奇数です。

このため、Int.Bit(0) は math/big.Int 型の偶奇判定に直接利用できるため、非常に頻繁に呼び出されることが予想されます。

技術的詳細

この最適化は、Int.Bit(0) の呼び出しが、math/big.Int の内部表現の特性を利用して、より効率的に処理できるという事実に基づいています。

math/big.Int の絶対値は、x.abs という Word 型のスライスに格納されています。このスライスは、数値の各「ワード」を保持しており、x.abs[0] は常に最下位のワード（Least Significant Word）を表します。最下位ビットは、この最下位のワードの最下位ビットに他なりません。

したがって、Int.Bit(0) の場合、以下の条件をチェックすることで、直接かつ高速に結果を得ることができます。

1. if i == 0: まず、要求されたビットインデックスが0であるかを確認します。これが最適化の対象となる共通ケースです。
2. if len(x.abs) > 0: 次に、数値がゼロでないことを確認します。x.abs スライスの長さが0の場合、その数値は0であり、0の0番目のビットは0です。スライスが空でない場合、少なくとも1つのワードが存在し、その最下位ワードにアクセスできます。
3. return uint(x.abs[0] & 1): x.abs[0] は最下位のワードです。このワードと 1 とのビットごとのAND演算 (& 1) を行うことで、そのワードの最下位ビットの値（0または1）を直接抽出できます。この結果は uint 型にキャストされて返されます。
   • x.abs[0] & 1 は、x が正の数であろうと負の数であろうと、その絶対値の最下位ビットを正しく返します。なぜなら、Bit メソッドは (x>>i)&1 と定義されており、これは符号に関わらず絶対値のビットを返すためです。コメント // bit 0 is same for -x がこの点を補足しています。

この最適化により、一般的なビットシフト操作や、より複雑な任意精度数値のビット操作ロジックを迂回し、直接メモリにアクセスして最下位ビットを取得できるため、大幅なパフォーマンス向上が期待できます。

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

diff --git a/src/pkg/math/big/int.go b/src/pkg/math/big/int.go
index ce308bd24f..276f56708a 100644
--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -697,6 +697,13 @@ func (z *Int) Rsh(x *Int, n uint) *Int {
 // Bit returns the value of the i'th bit of x. That is, it
 // returns (x>>i)&1. The bit index i must be >= 0.
 func (x *Int) Bit(i int) uint {
+	if i == 0 {
+		// optimization for common case: odd/even test of x
+		if len(x.abs) > 0 {
+			return uint(x.abs[0] & 1) // bit 0 is same for -x
+		}
+		return 0
+	}
 	if i < 0 {
 		panic("negative bit index")
 	}

コアとなるコードの解説

追加されたコードブロックは Int.Bit(i) メソッドの冒頭に挿入されています。

	if i == 0 {
		// optimization for common case: odd/even test of x
		if len(x.abs) > 0 {
			return uint(x.abs[0] & 1) // bit 0 is same for -x
		}
		return 0
	}

1. if i == 0 { ... }:

   • これは、この最適化が適用される条件です。引数 i が 0 である場合、つまり最下位ビットの取得が要求された場合にのみ、以下の最適化されたロジックが実行されます。
   • コメント // optimization for common case: odd/even test of x は、この最適化が偶数/奇数判定のような一般的なユースケースをターゲットにしていることを明確に示しています。

2. if len(x.abs) > 0 { ... }:

   • x.abs は math/big.Int の絶対値を構成する Word のスライスです。
   • len(x.abs) が 0 の場合、それは数値が 0 であることを意味します。0 の最下位ビットは 0 なので、この場合は直接 0 を返します。
   • len(x.abs) > 0 の場合、数値は 0 ではないため、x.abs[0]（最下位のワード）にアクセスしてビットを抽出できます。

3. return uint(x.abs[0] & 1):

   • x.abs[0] は、Int 型の数値の絶対値の最下位ワードです。
   • & 1 はビットごとのAND演算で、x.abs[0] の最下位ビットのみを抽出します。例えば、Word が ...xxxxxx1 であれば 1 を、...xxxxxx0 であれば 0 を返します。
   • uint(...) は、結果を uint 型にキャストしています。Bit メソッドの戻り値の型が uint であるためです。
   • コメント // bit 0 is same for -x は、負の数に対してもこのロジックが正しく機能することを保証しています。Bit メソッドの定義 (x>>i)&1 は、数値の絶対値のビットを返すため、符号は関係ありません。

この変更により、Int.Bit(0) の呼び出しは、複雑なビットシフトやループ処理を伴う汎用的なビット取得ロジックをスキップし、直接的な配列アクセスと単一のビット演算で完了するようになります。これにより、特に頻繁に Int.Bit(0) が呼び出されるアプリケーションにおいて、顕著なパフォーマンス改善が期待できます。

関連リンク

• Go CL 6306069: https://golang.org/cl/6306069

参考にした情報源リンク

• Go math/big パッケージのドキュメント: https://pkg.go.dev/math/big
• Go math/big のソースコード (int.go): https://github.com/golang/go/blob/master/src/math/big/int.go
• ビット演算に関する一般的な情報 (例: Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97
• 偶数と奇数に関する一般的な情報 (例: Wikipedia): https://ja.wikipedia.org/wiki/%E5%81%B6%E6%95%B0%E3%81%A8%E5%A5%87%E6%95%B0