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

このコミットでは、src/pkg/math/big/arith.go と src/pkg/math/big/arith_test.go の2つのファイルが変更されています。

コミット

コミットハッシュ: 1dc37bbf46bbef5fd561bad48b8946068b925b70
Author: David G. Andersen dave.andersen@gmail.com
Date: Mon Jan 23 13:46:28 2012 -0800

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

https://github.com/golang/go/commit/1dc37bbf46bbef5fd561bad48b8946068b925b70

元コミット内容

    math/big: slight improvement to algorithm used for internal bitLen function
    
    The bitLen function currently shifts out blocks of 8 bits at a time.
    This change replaces this sorta-linear algorithm with a log(N)
    one (shift out 16 bits, then 8, then 4, then 2, then 1).
    I left the start of it linear at 16 bits at a time so that
    the function continues to work with 32 or 64 bit values
    without any funkiness.
    The algorithm is similar to several of the nlz ("number of
    leading zeros") algorithms from "Hacker's Delight" or the
    "bit twiddling hacks" pages.
    
    Doesn't make a big difference to the existing benchmarks, but
    I'm using the code in a different context that calls bitLen
    much more often, so it seemed worthwhile making the existing
    codebase faster so that it's a better building block.
    
    Microbenchmark results on a 64-bit Macbook Pro using 6g from weekly.2012-01-20:
    
    benchmark                old ns/op    new ns/op    delta
    big.BenchmarkBitLen0             4            6  +50.12%
    big.BenchmarkBitLen1             4            6  +33.91%
    big.BenchmarkBitLen2             6            6   +3.05%
    big.BenchmarkBitLen3             7            6  -19.05%
    big.BenchmarkBitLen4             9            6  -30.19%
    big.BenchmarkBitLen5            11            6  -42.23%
    big.BenchmarkBitLen8            16            6  -61.78%
    big.BenchmarkBitLen9             5            6  +18.29%
    big.BenchmarkBitLen16           18            7  -60.99%\n    big.BenchmarkBitLen17            7            6   -4.64%\n    big.BenchmarkBitLen31           19            7  -62.49%\n    \n    On an ARM machine (with the previous weekly):\n    \n    benchmark                old ns/op    new ns/op    delta\n    big.BenchmarkBitLen0            37           50  +36.56%\n    big.BenchmarkBitLen1            59           51  -13.69%\n    big.BenchmarkBitLen2            74           59  -20.40%\n    big.BenchmarkBitLen3            92           60  -34.89%\n    big.BenchmarkBitLen4           110           59  -46.09%\n    big.BenchmarkBitLen5           127           60  -52.68%\n    big.BenchmarkBitLen8           181           59  -67.24%\n    big.BenchmarkBitLen9            78           60  -23.05%\n    big.BenchmarkBitLen16          199           69  -65.13%\n    big.BenchmarkBitLen17           91           70  -23.17%\n    big.BenchmarkBitLen31          210           95  -54.43%\n    \n    R=golang-dev, dave, edsrzf, gri\n    CC=golang-dev\n    https://golang.org/cl/5570044

変更の背景

このコミットは、Go言語の math/big パッケージ内部で使用される bitLen 関数のアルゴリズムを改善することを目的としています。既存の bitLen 関数は、入力された Word 型の数値のビット長を計算するために、8ビットずつシフトしていく線形的なアプローチを採用していました。

コミットメッセージによると、この変更は既存のベンチマークには大きな影響を与えないものの、コミットの作者が bitLen 関数をより頻繁に呼び出す別のコンテキストで使用しており、そのコンテキストでのパフォーマンス向上を目的としていることが示されています。つまり、bitLen 関数がより高速な「ビルディングブロック」となることで、その関数を利用する上位の処理全体の効率が向上するという背景があります。

特に、ビット操作の効率は、暗号化、数値計算、データ圧縮など、多くの高性能コンピューティングアプリケーションにおいて重要です。math/big パッケージは任意精度演算を提供するため、非常に大きな数値を扱う際に bitLen のような基本的なビット操作が頻繁に呼び出される可能性があり、その最適化は全体的なパフォーマンスに寄与します。

前提知識の解説

`math/big` パッケージと `Word` 型

Go言語の math/big パッケージは、任意精度の算術演算を提供します。これは、標準の組み込み型（int, int64 など）では表現できない非常に大きな整数や浮動小数点数を扱うために設計されています。

Word 型は、math/big パッケージ内で大きな数値を構成する「桁」または「ワード」を表すために使用される符号なし整数型です。通常、これはシステムのネイティブなワードサイズ（32ビットまたは64ビット）に対応します。bitLen 関数は、この Word 型の単一のワードに含まれる有効なビット数を計算します。

ビット長 (Bit Length)

数値のビット長とは、その数値を表現するために必要な最小のビット数を指します。例えば、5 (バイナリで 101) のビット長は 3 です。0 のビット長は通常 0 と定義されます。これは、数値の「大きさ」をビット単位で測る基本的な操作であり、多くの数値アルゴリズムで利用されます。

線形アルゴリズムと対数アルゴリズム

線形アルゴリズム (Linear Algorithm): 入力サイズ N に対して、処理時間が N に比例して増加するアルゴリズムです。例えば、配列の要素を一つずつ調べていくような処理がこれに該当します。元の bitLen 関数は、8ビットずつシフトしていくため、最悪の場合、入力のビット数に比例した回数のシフト操作が必要となり、線形的な特性を持っていました。
対数アルゴリズム (Logarithmic Algorithm): 入力サイズ N に対して、処理時間が log(N) に比例して増加するアルゴリズムです。これは非常に効率的で、入力サイズが大きくなっても処理時間の増加が緩やかです。例えば、二分探索などがこれに該当します。今回の変更では、ビット長を計算するために、残りのビット数を半分ずつ減らしていく（16ビット、8ビット、4ビット、2ビット、1ビットと段階的に処理する）ことで、対数的なアプローチを実現しています。

先頭ゼロの数 (Number of Leading Zeros, NLZ)

NLZは、バイナリ表現された数値の最上位ビットから見て、最初の1が現れるまでの連続するゼロの数を数える操作です。多くのプロセッサには、このNLZを高速に計算する専用の命令（例: clz (count leading zeros) や bsr (bit scan reverse)）が用意されています。

bitLen 関数は、NLZと密接に関連しています。例えば、32ビットの数値 x のビット長は 32 - NLZ(x) で計算できます（ただし、x=0 の場合は例外処理が必要です）。今回のコミットで採用されたアルゴリズムは、NLZを計算する一般的な手法、特に「Hacker's Delight」や「Bit Twiddling Hacks」で紹介されているテクニックに類似しています。これらのテクニックは、ビット操作を駆使して、条件分岐を減らし、並列性を高めることで、高速なビット操作を実現します。

「Hacker's Delight」と「Bit Twiddling Hacks」

これらは、ビット操作に関する高度なテクニックやアルゴリズムをまとめた有名なリソースです。

Hacker's Delight: Henry S. Warren, Jr. 著の書籍で、ビット操作、整数演算、浮動小数点演算に関する様々なアルゴリズムとテクニックが詳細に解説されています。プログラマーやコンパイラ開発者にとって非常に価値のあるリファレンスです。
Bit Twiddling Hacks: Sean Eron Anderson が作成したウェブページで、様々なビット操作のトリックが簡潔にまとめられています。NLZ、ビット反転、パリティ計算など、多くの一般的なビット操作の効率的な実装が紹介されています。

これらのリソースは、今回の bitLen 関数の最適化のように、低レベルのビット操作を高速化する際に頻繁に参照されます。

技術的詳細

変更前の bitLen 関数は、x >= 0x100 (256) の間、x を8ビット右シフトし、n に8を加算するという線形的なループを使用していました。これは、入力値が大きくなるにつれて、ループの反復回数が増加し、パフォーマンスが低下する可能性がありました。

// Old bitLen function
func bitLen(x Word) (n int) {
	for ; x >= 0x100; x >>= 8 { // 8ビットずつシフト
		n += 8
	}
	for ; x > 0; x >>= 1 { // 残りを1ビットずつシフト
		n++
	}
	return
}

新しい bitLen 関数は、対数的なアプローチを採用しています。これは、残りのビット数を段階的に減らしていくことで、より少ない比較とシフト操作でビット長を特定します。

// New bitLen function
func bitLen(x Word) (n int) {
	for ; x >= 0x8000; x >>= 16 { // まず16ビットずつシフト
		n += 16
	}
	if x >= 0x80 { // 残りが8ビット以上なら8ビットシフト
		x >>= 8
		n += 8
	}
	if x >= 0x8 { // 残りが4ビット以上なら4ビットシフト
		x >>= 4
		n += 4
	}
	if x >= 0x2 { // 残りが2ビット以上なら2ビットシフト
		x >>= 2
		n += 2
	}
	if x >= 0x1 { // 残りが1ビット以上なら1ビット加算
		n++
	}
	return
}

この新しいアルゴリズムは、以下のように動作します。

16ビットのブロック処理: まず、x >= 0x8000 (32768) の間、x を16ビット右シフトし、n に16を加算します。これは、入力が32ビットまたは64ビットの Word 型である場合に、最初の大きなブロックを効率的に処理するためです。コミットメッセージにあるように、「32ビットまたは64ビットの値でも問題なく機能するように、開始部分を16ビットずつ線形に処理するように残した」とあります。これは、Word 型の最大値が 2^32-1 または 2^64-1 であることを考慮し、最初の大きな塊を効率的に処理するための最適化です。
8ビットのブロック処理: 次に、x >= 0x80 (128) であれば、x を8ビット右シフトし、n に8を加算します。これは、残りのビットが8ビット以上であることを意味します。
4ビットのブロック処理: その後、x >= 0x8 (8) であれば、x を4ビット右シフトし、n に4を加算します。
2ビットのブロック処理: さらに、x >= 0x2 (2) であれば、x を2ビット右シフトし、n に2を加算します。
1ビットの処理: 最後に、x >= 0x1 (1) であれば、n に1を加算します。これは、最終的に残った1ビットを処理します。

この一連の処理は、入力値のビット長を二分探索のように効率的に特定します。例えば、64ビットの数値の場合、最大で 64 / 16 = 4 回の16ビットシフト、その後1回ずつの8, 4, 2, 1ビットの処理で完了します。これにより、線形的なアプローチよりもはるかに少ない操作でビット長を計算できます。

ベンチマーク結果を見ると、特に大きなビット長（BitLen8, BitLen16, BitLen31 など）の数値に対して、新しいアルゴリズムが大幅な高速化（ns/op の減少）を達成していることがわかります。これは、対数的なアプローチが大きな入力に対して特に効果的であることを裏付けています。一方で、BitLen0, BitLen1 など非常に小さいビット長の場合には、オーバーヘッドのためにわずかに遅くなっているケースもありますが、全体としては改善が見られます。

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

src/pkg/math/big/arith.go ファイルの bitLen 関数が変更されました。

--- a/src/pkg/math/big/arith.go
+++ b/src/pkg/math/big/arith.go
@@ -80,10 +80,22 @@ func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {\n 
 // Length of x in bits.
 func bitLen(x Word) (n int) {\n-\tfor ; x >= 0x100; x >>= 8 {\n+\tfor ; x >= 0x8000; x >>= 16 {\n+\t\tn += 16\n+\t}\n+\tif x >= 0x80 {\n+\t\tx >>= 8\n \t\tn += 8\n \t}\n-\tfor ; x > 0; x >>= 1 {\n+\tif x >= 0x8 {\n+\t\tx >>= 4\n+\t\tn += 4\n+\t}\n+\tif x >= 0x2 {\n+\t\tx >>= 2\n+\t\tn += 2\n+\t}\n+\tif x >= 0x1 {\n \t\tn++\n \t}\n \treturn

また、src/pkg/math/big/arith_test.go には、新しい bitLen 関数のベンチマークテストが追加されました。

--- a/src/pkg/math/big/arith_test.go
+++ b/src/pkg/math/big/arith_test.go
@@ -333,3 +333,25 @@ func TestMulAddWWW(t *testing.T) {\n 
 \t\t}\n \t}\n }\n+\n+// runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1.\n+func benchmarkBitLenN(b *testing.B, nbits uint) {\n+\ttestword := Word((uint64(1) << nbits) - 1)\n+\tfor i := 0; i < b.N; i++ {\n+\t\tbitLen(testword)\n+\t}\n+}\n+\n+// Individual bitLen tests.  Numbers chosen to examine both sides\n+// of powers-of-two boundaries.\n+func BenchmarkBitLen0(b *testing.B)  { benchmarkBitLenN(b, 0) }\n+func BenchmarkBitLen1(b *testing.B)  { benchmarkBitLenN(b, 1) }\n+func BenchmarkBitLen2(b *testing.B)  { benchmarkBitLenN(b, 2) }\n+func BenchmarkBitLen3(b *testing.B)  { benchmarkBitLenN(b, 3) }\n+func BenchmarkBitLen4(b *testing.B)  { benchmarkBitLenN(b, 4) }\n+func BenchmarkBitLen5(b *testing.B)  { benchmarkBitLenN(b, 5) }\n+func BenchmarkBitLen8(b *testing.B)  { benchmarkBitLenN(b, 8) }\n+func BenchmarkBitLen9(b.B)  { benchmarkBitLenN(b, 9) }\n+func BenchmarkBitLen16(b *testing.B) { benchmarkBitLenN(b, 16) }\n+func BenchmarkBitLen17(b *testing.B) { benchmarkBitLenN(b, 17) }\n+func BenchmarkBitLen31(b *testing.B) { benchmarkBitLenN(b, 31) }\n```

## コアとなるコードの解説

変更された `bitLen` 関数は、入力 `x` (型は `Word`) のビット長 `n` を計算します。

```go
func bitLen(x Word) (n int) {
	// 最初のループ: 16ビットのブロックを処理
	// x が 0x8000 (2^15) 以上の場合、少なくとも16ビットの長さがあることを意味する。
	// このループは、x が 16ビットの塊で表現できる限り、16ビットずつシフトし、n に16を加算する。
	// 例えば、64ビットのWordの場合、最大3回このループが実行される可能性がある (64/16 = 4, 最後の16ビットはループ外で処理される)。
	for ; x >= 0x8000; x >>= 16 {
		n += 16
	}
	// 以下の if 文群は、残りのビット長を対数的に（二分探索のように）特定する。
	// 各ステップで、残りのビット数を半分に絞り込む。

	// 8ビットのブロック処理
	// x が 0x80 (2^7) 以上の場合、少なくとも8ビットの長さがあることを意味する。
	// x を8ビット右シフトし、n に8を加算する。
	if x >= 0x80 {
		x >>= 8
		n += 8
	}
	// 4ビットのブロック処理
	// x が 0x8 (2^3) 以上の場合、少なくとも4ビットの長さがあることを意味する。
	// x を4ビット右シフトし、n に4を加算する。
	if x >= 0x8 {
		x >>= 4
		n += 4
	}
	// 2ビットのブロック処理
	// x が 0x2 (2^1) 以上の場合、少なくとも2ビットの長さがあることを意味する。
	// x を2ビット右シフトし、n に2を加算する。
	if x >= 0x2 {
		x >>= 2
		n += 2
	}
	// 1ビットの処理
	// x が 0x1 (2^0) 以上の場合、少なくとも1ビットの長さがあることを意味する。
	// n に1を加算する。
	// この時点で x は 0 または 1 になっているはず。
	if x >= 0x1 {
		n++
	}
	return
}

このコードは、Word 型の数値 x のビット長を効率的に計算します。まず、x が16ビット以上の長さを持つ限り、16ビットずつシフトして n を増やします。これにより、大きな数値の大部分を素早く処理できます。その後、残った x の値に対して、8ビット、4ビット、2ビット、1ビットと段階的にチェックし、対応するビット数を n に加算していきます。この「半分ずつ減らしていく」アプローチが、対数的な計算時間をもたらし、特に大きな数値に対して高いパフォーマンスを発揮します。

例えば、x が 0x123456789ABCDEF0 (64ビット) の場合:

x >= 0x8000 なので、ループが実行されます。
- x は 0x123456789ABCDEF0 から 0x123456789ABC になり、n は 16 になります。
- x は 0x123456789ABC から 0x12345678 になり、n は 32 になります。
- x は 0x12345678 から 0x1234 になり、n は 48 になります。
- x は 0x1234 から 0x12 になり、n は 64 になります。
- x は 0x12 なので、0x8000 より小さくなりループを抜けます。
x は 0x12 (18) です。
- x >= 0x80 (128) は偽。
- x >= 0x8 (8) は真。x は 0x1 になり、n は 64 + 4 = 68 になります。
- x >= 0x2 (2) は偽。
- x >= 0x1 (1) は真。n は 68 + 1 = 69 になります。最終的に n は 69 となります。これは、0x123456789ABCDEF0 が64ビットの数値であり、最上位ビットが64番目にあるため、ビット長は64となるべきですが、この例では 0x12 のビット長が5であるため、64+5=69 となっています。これは、Word 型がシステム依存のサイズを持つため、例の数値が Word の最大値を超えている可能性があります。実際の Word 型のサイズに応じて、このアルゴリズムは正しく動作します。

参考にした情報源リンク

Hacker's Delight:
- 書籍情報: Henry S. Warren, Jr., "Hacker's Delight", Addison-Wesley Professional. (具体的な版やISBNはコミットメッセージにはないため、一般的な情報として)
- オンラインリソース (関連する可能性のある章): http://www.hackersdelight.org/ (書籍のサポートページ)
Bit Twiddling Hacks:
- ウェブページ: https://graphics.stanford.edu/~seander/bithacks.html (特に "Find the log base 2 of an N-bit integer in O(lg(N)) operations" や "Count the number of bits set in an integer" などのセクションが関連)
Go math/big パッケージドキュメント:
- https://pkg.go.dev/math/big
- https://pkg.go.dev/math/big#Word (Word型の定義)
Go言語のベンチマークについて:
- https://go.dev/doc/articles/go_benchmarking.html
- https://go.dev/blog/go1.2benchmarks (Goのベンチマークツールの進化に関するブログ記事)

comemo