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

このコミットは、Go言語のmath/bigパッケージにおけるbitLen関数のパフォーマンスを大幅に改善することを目的としています。具体的には、x86-64、386、およびARMアーキテクチャ向けに、この関数のアセンブリ言語実装を追加することで、既存のGo言語による汎用実装と比較して約2倍の高速化を実現しています。これにより、多倍長整数演算の基盤となるビット長計算が効率化され、math/bigパッケージ全体の性能向上に寄与します。

コミット

commit 316f81bb1dfca9f109bf3edf77f4da5821d0ec99
Author: David G. Andersen <dave.andersen@gmail.com>
Date:   Wed Jan 25 15:04:16 2012 -0800

    math/big:  assembly versions of bitLen for x86-64, 386, and ARM.
    
    Roughly 2x speedup for the internal bitLen function in arith.go.  Added TestWordBitLen test.
    
    Performance differences against the new version of
    bitLen generic:
    
    x86-64 Macbook pro (current tip):
    
    benchmark                old ns/op    new ns/op    delta
    big.BenchmarkBitLen0             6            4  -37.40%
    big.BenchmarkBitLen1             6            2  -51.79%
    big.BenchmarkBitLen2             6            2  -65.04%
    big.BenchmarkBitLen3             6            2  -66.10%
    big.BenchmarkBitLen4             6            2  -60.96%
    big.BenchmarkBitLen5             6            2  -55.80%
    big.BenchmarkBitLen8             6            2  -56.19%
    big.BenchmarkBitLen9             6            2  -64.73%
    big.BenchmarkBitLen16            7            2  -68.84%
    big.BenchmarkBitLen17            6            2  -67.11%
    big.BenchmarkBitLen31            7            2  -61.57%
    
    386 Intel Atom (current tip):
    benchmark                old ns/op    new ns/op    delta
    big.BenchmarkBitLen0            23           20  -13.04%
    big.BenchmarkBitLen1            23           20  -14.77%
    big.BenchmarkBitLen2            24           20  -19.28%
    big.BenchmarkBitLen3            25           20  -21.57%
    big.BenchmarkBitLen4            24           20  -16.94%
    big.BenchmarkBitLen5            25           20  -20.78%
    big.BenchmarkBitLen8            24           20  -19.28%
    big.BenchmarkBitLen9            25           20  -20.47%
    big.BenchmarkBitLen16           26           20  -23.37%
    big.BenchmarkBitLen17           26           20  -25.09%
    big.BenchmarkBitLen31           32           20  -35.51%
    
    ARM v5 SheevaPlug, previous weekly patched with bitLen:
    benchmark                old ns/op    new ns/op    delta
    big.BenchmarkBitLen0            50           29  -41.73%
    big.BenchmarkBitLen1            51           29  -42.75%
    big.BenchmarkBitLen2            59           29  -50.08%
    big.BenchmarkBitLen3            60           29  -50.75%
    big.BenchmarkBitLen4            59           29  -50.08%
    big.BenchmarkBitLen5            60           29  -50.75%
    big.BenchmarkBitLen8            59           29  -50.08%
    big.BenchmarkBitLen9            60           29  -50.75%
    big.BenchmarkBitLen16           69           29  -57.35%
    big.BenchmarkBitLen17           70           29  -57.89%
    big.BenchmarkBitLen31           95           29  -69.07%
    
    R=golang-dev, minux.ma, gri
    CC=golang-dev
    https://golang.org/cl/5574054

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

https://github.com/golang/go/commit/316f81bb1dfca9f109bf3edf77f4da5821d0ec99

元コミット内容

math/big: x86-64、386、およびARM向けbitLenのアセンブリバージョン。

arith.go内の内部関数bitLenが約2倍高速化されました。TestWordBitLenテストが追加されました。

新しいbitLen汎用バージョンに対するパフォーマンス比較：

x86-64 Macbook Pro (現在のtip):

ベンチマーク	old ns/op	new ns/op	delta
`big.BenchmarkBitLen0`	6	4	-37.40%
`big.BenchmarkBitLen1`	6	2	-51.79%
`big.BenchmarkBitLen2`	6	2	-65.04%
`big.BenchmarkBitLen3`	6	2	-66.10%
`big.BenchmarkBitLen4`	6	2	-60.96%
`big.BenchmarkBitLen5`	6	2	-55.80%
`big.BenchmarkBitLen8`	6	2	-56.19%
`big.BenchmarkBitLen9`	6	2	-64.73%
`big.BenchmarkBitLen16`	7	2	-68.84%
`big.BenchmarkBitLen17`	6	2	-67.11%
`big.BenchmarkBitLen31`	7	2	-61.57%

386 Intel Atom (現在のtip):

ベンチマーク	old ns/op	new ns/op	delta
`big.BenchmarkBitLen0`	23	20	-13.04%
`big.BenchmarkBitLen1`	23	20	-14.77%
`big.BenchmarkBitLen2`	24	20	-19.28%
`big.BenchmarkBitLen3`	25	20	-21.57%
`big.BenchmarkBitLen4`	24	20	-16.94%
`big.BenchmarkBitLen5`	25	20	-20.78%
`big.BenchmarkBitLen8`	24	20	-19.28%
`big.BenchmarkBitLen9`	25	20	-20.47%
`big.BenchmarkBitLen16`	26	20	-23.37%
`big.BenchmarkBitLen17`	26	20	-25.09%
`big.BenchmarkBitLen31`	32	20	-35.51%

ARM v5 SheevaPlug (bitLenで以前にパッチ適用済み):

ベンチマーク	old ns/op	new ns/op	delta
`big.BenchmarkBitLen0`	50	29	-41.73%
`big.BenchmarkBitLen1`	51	29	-42.75%
`big.BenchmarkBitLen2`	59	29	-50.08%
`big.BenchmarkBitLen3`	60	29	-50.75%
`big.BenchmarkBitLen4`	59	29	-50.08%
`big.BenchmarkBitLen5`	60	29	-50.75%
`big.BenchmarkBitLen8`	59	29	-50.08%
`big.BenchmarkBitLen9`	60	29	-50.75%
`big.BenchmarkBitLen16`	69	29	-57.35%
`big.BenchmarkBitLen17`	70	29	-57.89%
`big.BenchmarkBitLen31`	95	29	-69.07%

R=golang-dev, minux.ma, gri CC=golang-dev https://golang.org/cl/5574054

変更の背景

Go言語のmath/bigパッケージは、任意精度の整数および浮動小数点数演算を提供します。これらの演算の多くは、数値のビット長（最上位ビットの位置）を効率的に計算する能力に依存しています。bitLen関数は、このビット長を計算する基本的なユーティリティ関数であり、math/bigパッケージ内の様々な算術演算（例: 乗算、除算、シフト操作）で内部的に頻繁に呼び出されます。

従来のbitLen関数の実装は、Go言語で記述された汎用的なものでした。しかし、ビット長計算はCPUの特定の命令セット（例: ビットスキャン命令や先行ゼロカウント命令）を利用することで、非常に高速に実行できることが知られています。汎用的なGoコードでは、これらの低レベルなCPU命令を直接利用することが難しく、ループや条件分岐を多用するため、アセンブリ言語による実装と比較して性能が劣る傾向がありました。

math/bigパッケージの性能は、Go言語で大規模な数値計算を行うアプリケーションにとって非常に重要です。特に、暗号通貨、科学計算、暗号化などの分野では、多倍長整数演算が頻繁に行われるため、その基盤となるbitLen関数のボトルネックは全体のパフォーマンスに大きな影響を与えます。

このコミットは、この性能ボトルネックを解消し、math/bigパッケージの全体的な実行速度を向上させることを目的としています。特定のアーキテクチャ向けに最適化されたアセンブリ実装を提供することで、Go言語のポータビリティを維持しつつ、性能が要求される部分で最大限の効率を引き出すというGo言語の設計哲学に沿った変更と言えます。

前提知識の解説

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

Go言語の標準ライブラリであるmath/bigパッケージは、Goの組み込み型（int, int64など）では表現できない非常に大きな整数や高精度な浮動小数点数を扱うための機能を提供します。これは、暗号学、科学計算、金融アプリケーションなど、任意精度の数値が必要とされる場面で不可欠です。

math/bigパッケージの内部では、これらの大きな数値はWord型のスライス（配列）として表現されます。Word型は、基盤となるCPUアーキテクチャのワードサイズ（例: 32ビットまたは64ビット）に合わせた符号なし整数型です。例えば、64ビットシステムではuint64、32ビットシステムではuint32に相当します。多倍長整数は、このWord型の要素を複数連結することで表現されます。

2. ビット長 (Bit Length)

数値のビット長とは、その数値を表現するために必要な最小のビット数を指します。より厳密には、数値の最上位ビット（Most Significant Bit, MSB）の位置に1を加えたものです。例えば：

0 のビット長は 0
1 (バイナリ: 1) のビット長は 1
2 (バイナリ: 10) のビット長は 2
7 (バイナリ: 111) のビット長は 3
8 (バイナリ: 1000) のビット長は 4

これは、log2(x+1)を切り上げた値に相当します。bitLen関数は、math/bigパッケージ内で、数値の正規化、シフト操作、メモリ割り当ての最適化など、様々な算術演算の効率的な実装に利用されます。

3. アセンブリ言語による最適化

Go言語は通常、Goコンパイラによって機械語にコンパイルされますが、性能が極めて重要な一部の関数では、Go言語のコードではなく、直接アセンブリ言語で実装されることがあります。これは、アセンブリ言語がCPUの特定の命令を直接利用できるため、Go言語では表現しにくい低レベルな最適化や、コンパイラが自動的に生成できないような効率的なコードを記述できるためです。

ビット長計算のような操作は、多くの現代のCPUがそのための専用命令を持っています。これらの命令は、数サイクルで結果を返すことができ、ソフトウェアでループを使ってビットを数えるよりもはるかに高速です。

4. 特定のCPU命令

このコミットで利用されている主要なCPU命令は以下の通りです。

BSR (Bit Scan Reverse) - x86/x86-64アーキテクチャ: BSR命令は、オペランドの最上位ビット（MSB）の位置を検索し、そのインデックスをデスティネーションレジスタに格納します。例えば、32ビット値0x00008000（15番目のビットがセットされている）に対してBSRを実行すると、結果は15になります。この命令は、ビット長を効率的に計算するために非常に適しています。入力が0の場合、結果は未定義となるため、通常は事前に0チェックが必要です。
CLZ (Count Leading Zeros) - ARMアーキテクチャ: CLZ命令は、オペランドの最上位ビットより上位にある連続するゼロの数をカウントします。例えば、32ビット値0x00008000に対してCLZを実行すると、結果は16（先頭から16個のゼロ）になります。ビット長は、ワードサイズ（例: 32または64）からCLZの結果を引くことで計算できます。例えば、32ビットワードの場合、bitLen = 32 - CLZ(x)となります（ただし、xが0の場合は別途処理が必要）。

これらの命令は、ビット操作を非常に効率的に行うことができ、汎用的なGoコードでのビットシフトやループによる実装と比較して、大幅な性能向上をもたらします。

技術的詳細

このコミットの核心は、math/bigパッケージのbitLen関数を、各アーキテクチャの専用命令を利用したアセンブリ言語で再実装した点にあります。

汎用Go実装 (`bitLen_g`)

変更前、またはアセンブリ実装が利用できない環境では、bitLen関数はarith.go内で以下のようなGoコードで実装されていました（コミットによってbitLen_gにリネームされています）。

// Length of x in bits.
func bitLen_g(x Word) (n int) {
	for ; x >= 0x8000; x >>= 16 {
		n += 16
	}
	// ... (残りのビットを処理するロジック)
}

このコードは、Word型の値xを16ビットずつ右シフトしながら、セットされているビットの数を数えるという基本的なループ処理を行っていました。これはポータブルですが、各シフトと加算の操作がCPUサイクルを消費し、特に大きなWord値に対しては非効率的でした。

アセンブリ実装 (`bitLen`)

コミットでは、以下の3つのアーキテクチャ向けにbitLenのアセンブリ実装が追加されました。

x86-64 (arith_amd64.s): x86-64アーキテクチャでは、BSRQ (Bit Scan Reverse Quadword) 命令が使用されます。これは64ビットオペランドに対してBSRを実行します。
```
TEXT ·bitLen(SB),7,$0
	BSRQ x+0(FP), AX  // xの最上位ビットの位置をAXに格納
	JZ Z1             // AXが0ならZ1へジャンプ (xが0の場合)
	INCQ AX           // 結果に1を加える (0-indexedから1-indexedへ)
	MOVQ AX, n+8(FP)  // 結果を戻り値nに格納
	RET
Z1:	MOVQ $0, n+8(FP)  // xが0の場合、ビット長は0
	RET
```
BSRQは、オペランドの最上位ビットの0から始まるインデックスを返します。例えば、0x8000000000000000 (64ビットの最上位ビットのみがセット) の場合、BSRQは63を返します。ビット長は、このインデックスに1を加えた値（この場合は64）となるため、INCQ AXでインクリメントしています。入力が0の場合、BSRQはデスティネーションレジスタを未定義にし、ZF (Zero Flag) をセットします。そのため、JZ Z1で0の場合の特殊処理を行っています。
386 (arith_386.s): 386アーキテクチャ（32ビットx86）では、BSRL (Bit Scan Reverse Long) 命令が使用されます。これは32ビットオペランドに対してBSRを実行します。
```
TEXT ·bitLen(SB),7,$0
	BSRL x+0(FP), AX  // xの最上位ビットの位置をAXに格納
	JZ Z1             // AXが0ならZ1へジャンプ (xが0の場合)
	INCL AX           // 結果に1を加える
	MOVL AX, n+4(FP)  // 結果を戻り値nに格納
	RET
Z1:	MOVL $0, n+4(FP)  // xが0の場合、ビット長は0
	RET
```
基本的なロジックはx86-64版と同じですが、レジスタとオペランドのサイズが32ビット（Lサフィックス）になっています。
ARM (arith_arm.s): ARMアーキテクチャでは、CLZ (Count Leading Zeros) 命令が使用されます。
```
TEXT ·bitLen(SB),7,$0
	MOVW	x+0(FP), R0       // xをR0レジスタにロード
	WORD	$0xe16f0f10 // CLZ R0, R0  (R0の先行ゼロをカウントし、R0に格納)
	MOVW	$32, R1           // 32をR1にロード (32ビットワードサイズ)
	SUB.S	R0, R1            // R1からR0を引く (32 - CLZ(x))
	MOVW	R1, n+4(FP)       // 結果を戻り値nに格納
	RET
```
ARMのCLZ命令は、オペランドの最上位ビットより上位にある連続するゼロの数を返します。例えば、32ビット値の場合、CLZ(0x80000000)は0を、CLZ(0x00000001)は31を返します。ビット長は、ワードサイズ（この場合は32）からCLZの結果を引くことで得られます。例えば、0x80000000のビット長は32 - 0 = 32、0x00000001のビット長は32 - 31 = 1となります。この実装では、入力が0の場合の特殊処理は明示的に記述されていませんが、GoのWord型が符号なし整数であること、およびCLZ命令の動作（通常、0に対してはワードサイズを返すか、未定義動作となる）を考慮すると、Goのランタイムやコンパイラが適切に処理するか、あるいはbitLenが0以外の入力に対してのみ呼び出されることを前提としている可能性があります。

パフォーマンス向上

コミットメッセージに記載されているベンチマーク結果は、アセンブリ実装による大幅な性能向上を明確に示しています。

x86-64: ほとんどのケースで50%以上の高速化、最大で約69%の高速化（約3倍の速度向上）を達成しています。これは、BSRQ命令が非常に効率的であることを示しています。
386: 約13%から35%の高速化が見られます。x86-64ほど劇的ではありませんが、それでも顕著な改善です。
ARM: 約41%から69%の高速化を達成しており、x86-64と同様に大きな改善が見られます。CLZ命令の効率性がここでも確認できます。

これらの性能向上は、math/bigパッケージを利用するアプリケーション全体の実行速度に直接的な利益をもたらします。

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

このコミットでは、以下のファイルが変更されています。

src/pkg/math/big/arith.go:
- 既存のGo言語で書かれたbitLen関数がbitLen_gにリネームされました。これは、アセンブリ実装のbitLenと区別するためです。
src/pkg/math/big/arith_386.s:
- 32ビットx86アーキテクチャ（386）向けに、bitLen関数のアセンブリ実装が追加されました。BSRL命令を使用します。
src/pkg/math/big/arith_amd64.s:
- 64ビットx86アーキテクチャ（x86-64）向けに、bitLen関数のアセンブリ実装が追加されました。BSRQ命令を使用します。
src/pkg/math/big/arith_arm.s:
- ARMアーキテクチャ向けに、bitLen関数のアセンブリ実装が追加されました。CLZ命令を使用します。
src/pkg/math/big/arith_decl.go:
- bitLen関数のGo言語での宣言が追加されました。これにより、Goコードからアセンブリ実装のbitLenを呼び出すことができるようになります。
src/pkg/math/big/arith_test.go:
- TestWordBitLenという新しいテスト関数が追加されました。これは、bitLen関数の正確性を検証するためのものです。特に、すべての可能なビット長（0からワードサイズまで）に対して、関数が正しい結果を返すことを確認します。

コアとなるコードの解説

`src/pkg/math/big/arith.go` の変更

--- a/src/pkg/math/big/arith.go
+++ b/src/pkg/math/big/arith.go
@@ -79,7 +79,7 @@ func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
 }
 
 // Length of x in bits.
-func bitLen(x Word) (n int) {
+func bitLen_g(x Word) (n int) {
 	for ; x >= 0x8000; x >>= 16 {
 		n += 16
 	}

bitLen関数がbitLen_gにリネームされています。これは、Goコンパイラがアーキテクチャ固有のアセンブリ実装（bitLen）を優先的に選択し、それがない場合にのみこの汎用Go実装（bitLen_g）にフォールバックするためのGoのメカニズムです。

`src/pkg/math/big/arith_386.s` の追加

--- a/src/pkg/math/big/arith_386.s
+++ b/src/pkg/math/big/arith_386.s
@@ -263,3 +263,14 @@ E7:	SUBL $1, BX		// i--
 
 	MOVL DX, r+32(FP)
 	RET
+
+// func bitLen(x Word) (n int)
+TEXT ·bitLen(SB),7,$0
+	BSRL x+0(FP), AX
+	JZ Z1
+	INCL AX
+	MOVL AX, n+4(FP)
+	RET
+
+Z1:	MOVL $0, n+4(FP)
+	RET

TEXT ·bitLen(SB),7,$0 は、bitLenという名前の関数を定義しています。x+0(FP)は引数xを、n+4(FP)は戻り値nをスタックフレームポインタ（FP）からのオフセットで参照しています。

BSRL x+0(FP), AX: 引数xの最上位ビットのインデックスをAXレジスタに格納します。
JZ Z1: xが0の場合（BSRLがゼロフラグをセットする）、Z1ラベルにジャンプします。
INCL AX: BSRLは0から始まるインデックスを返すため、ビット長（1から始まる）を得るためにAXをインクリメントします。
MOVL AX, n+4(FP): 計算されたビット長を戻り値nに格納します。
Z1: MOVL $0, n+4(FP): xが0の場合、ビット長は0として設定されます。

`src/pkg/math/big/arith_amd64.s` の追加

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -261,3 +261,14 @@ E7:	SUBL $1, BX		// i--
 
 	MOVQ DX, r+48(FP)
 	RET
+
+// func bitLen(x Word) (n int)
+TEXT ·bitLen(SB),7,$0
+	BSRQ x+0(FP), AX
+	JZ Z1
+	INCQ AX
+	MOVQ AX, n+8(FP)
+	RET
+
+Z1:	MOVQ $0, n+8(FP)
+	RET

386版とほぼ同じロジックですが、64ビットアーキテクチャに対応するため、命令がBSRQ（Quadword）、レジスタがAX（64ビット）、オフセットがn+8(FP)（64ビットワード）に変更されています。

`src/pkg/math/big/arith_arm.s` の追加

--- a/src/pkg/math/big/arith_arm.s
+++ b/src/pkg/math/big/arith_arm.s
@@ -310,3 +310,12 @@ TEXT ·mulWW(SB),7,$0
 	MOVW	R4, z1+8(FP)
 	MOVW	R3, z0+12(FP)
 	RET
+
+// func bitLen(x Word) (n int)
+TEXT ·bitLen(SB),7,$0
+	MOVW	x+0(FP), R0
+	WORD	$0xe16f0f10 // CLZ R0, R0  (count leading zeros)
+	MOVW	$32, R1
+	SUB.S	R0, R1
+	MOVW	R1, n+4(FP)
+	RET

MOVW x+0(FP), R0: 引数xをR0レジスタにロードします。
WORD $0xe16f0f10 // CLZ R0, R0: これはARMのCLZ命令の機械語表現です。CLZ R0, R0はR0の先行ゼロの数をカウントし、その結果を再びR0に格納します。
MOVW $32, R1: 32ビットワードサイズを表す定数32をR1レジスタにロードします。
SUB.S R0, R1: R1（32）からR0（CLZの結果）を引きます。これにより、ビット長が計算されます（例: 32 - CLZ(x)）。
MOVW R1, n+4(FP): 計算されたビット長を戻り値nに格納します。

`src/pkg/math/big/arith_decl.go` の変更

--- a/src/pkg/math/big/arith_decl.go
+++ b/src/pkg/math/big/arith_decl.go
@@ -16,3 +16,4 @@ func shrVU(z, x []Word, s uint) (c Word)
 func mulAddVWW(z, x []Word, y, r Word) (c Word)
 func addMulVVW(z, x []Word, y Word) (c Word)
 func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
+func bitLen(x Word) (n int)

func bitLen(x Word) (n int)という関数宣言が追加されています。これにより、Goコンパイラは、このシグネチャを持つ関数が外部（この場合はアセンブリファイル）で定義されていることを認識し、GoコードからbitLenを呼び出す際にアセンブリ実装にリンクします。

`src/pkg/math/big/arith_test.go` の追加

--- a/src/pkg/math/big/arith_test.go
+++ b/src/pkg/math/big/arith_test.go
@@ -334,6 +334,29 @@ func TestMulAddWWW(t *testing.T) {
 	}
 }
 
+func TestWordBitLen(t *testing.T) {
+	// Test every possible output of bitLen with the high bit set
+	// and then with all bits below max set
+	z := bitLen(0)
+	if z != 0 {
+		t.Errorf("0 got %d want 0", z)
+	}
+	x := Word(1) // Will be ...00010000...
+	y := Word(1) // Will be ...00011111...
+	for i := 1; i <= _W; i++ {
+		z = bitLen(x)
+		if z != i {
+			t.Errorf("%x got %d want %d", x, z, i)
+		}
+		z = bitLen(y)
+		if z != i {
+			t.Errorf("%x got %d want %d", y, z, i)
+		}
+		x <<= 1
+		y = (y << 1) | 0x1
+	}
+}
+
 // runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1.
 func benchmarkBitLenN(b *testing.B, nbits uint) {
 	testword := Word((uint64(1) << nbits) - 1)

TestWordBitLen関数は、bitLen関数の正確性を検証するための単体テストです。

bitLen(0)が0を返すことを確認します。
xは1から始まり、各ループで左シフトされ、1, 10, 100, ... となり、最上位ビットのみがセットされた値のビット長をテストします。
yは1から始まり、各ループで左シフトされ0x1がORされ、1, 11, 111, ... となり、すべてのビットがセットされた値のビット長をテストします。
_WはWord型のビット幅（32または64）を表す定数で、Word型のすべての可能なビット長を網羅的にテストします。

このテストの追加は、アセンブリ実装の正確性を保証するために非常に重要です。

参考にした情報源リンク

Go math/big package documentation: https://pkg.go.dev/math/big
Intel 64 and IA-32 Architectures Software Developer's Manuals (for BSR instruction): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
ARM Architecture Reference Manuals (for CLZ instruction): https://developer.arm.com/documentation/ddi0487/latest/
Go Assembly Language (Plan 9 style): https://go.dev/doc/asm
Bit Scan Reverse (BSR) instruction: https://www.felixcloutier.com/x86/bsr
Count Leading Zeros (CLZ) instruction: https://developer.arm.com/documentation/dui0489/c/arm-and-thumb-instructions/clz

comemo