[インデックス 13686] ファイルの概要
このコミットは、Go言語の標準ライブラリである math/big パッケージ内の、任意精度演算におけるベクトル加算・減算ルーチン (addVV, subVV, addVW, subVW) のパフォーマンスを向上させるための変更です。具体的には、arith_amd64.s というアセンブリ言語ファイルにおいて、これらの関数の実装にループアンローリングを導入することで、処理速度の改善を図っています。
コミット
commit 35422bc11f8de6d086f382f5f636b1e0a96f895e
Author: Robert Griesemer <gri@golang.org>
Date: Fri Aug 24 09:20:44 2012 -0700
math/big: faster (add|sub)V(V|W) routines
Benchmarks run on 3.06GHz Intel Core 2 Duo,
4GB 800MHz DDR2 SDRAM ("iMac").
benchmark old ns/op new ns/op delta
BenchmarkAddVV_1 6 6 +2.75%
BenchmarkAddVV_2 9 7 -19.71%
BenchmarkAddVV_3 9 9 +2.25%
BenchmarkAddVV_4 10 8 -20.46%
BenchmarkAddVV_5 12 10 -19.53%
BenchmarkAddVV_1e1 23 15 -32.48%
BenchmarkAddVV_1e2 213 107 -49.77%
BenchmarkAddVV_1e3 2088 993 -52.44%
BenchmarkAddVV_1e4 20874 12027 -42.38%
BenchmarkAddVV_1e5 209858 121480 -42.11%
BenchmarkAddVW_1 5 5 +0.90%
BenchmarkAddVW_2 11 11 -3.51%
BenchmarkAddVW_3 7 7 -0.27%
BenchmarkAddVW_4 8 7 -6.32%
BenchmarkAddVW_5 9 8 -10.89%
BenchmarkAddVW_1e1 17 12 -26.01%
BenchmarkAddVW_1e2 155 89 -42.32%
BenchmarkAddVW_1e3 1479 873 -40.97%
BenchmarkAddVW_1e4 13838 8764 -36.67%
BenchmarkAddVW_1e5 147353 89560 -39.22%
benchmark old MB/s new MB/s speedup
BenchmarkAddVV_1 9765.57 9508.55 0.97x
BenchmarkAddVV_2 13077.63 16284.97 1.25x
BenchmarkAddVV_3 20599.58 20156.67 0.98x
BenchmarkAddVV_4 23591.58 29516.02 1.25x
BenchmarkAddVV_5 24920.95 31194.10 1.25x
BenchmarkAddVV_1e1 27393.76 40621.71 1.48x
BenchmarkAddVV_1e2 29911.96 59592.99 1.99x
BenchmarkAddVV_1e3 30650.73 64429.84 2.10x
BenchmarkAddVV_1e4 30660.09 53213.08 1.74x
BenchmarkAddVV_1e5 30496.74 52683.46 1.73x
BenchmarkAddVW_1 11503.39 11405.98 0.99x
BenchmarkAddVW_2 11203.56 11586.92 1.03x
BenchmarkAddVW_3 26173.45 26224.75 1.00x
BenchmarkAddVW_4 30560.30 32621.94 1.07x
BenchmarkAddVW_5 33183.81 37269.94 1.12x
BenchmarkAddVW_1e1 36991.75 50098.53 1.35x
BenchmarkAddVW_1e2 41087.14 71549.93 1.74x
BenchmarkAddVW_1e3 43266.42 73279.83 1.69x
BenchmarkAddVW_1e4 46246.74 73021.97 1.58x
BenchmarkAddVW_1e5 43433.00 71459.96 1.65x
Benchmarks run on 2.8GHz Quad-Code Intel Xeon,
4GB 800MHz DDR2 FB-DIMM ("PowerMac").
benchmark old ns/op new ns/op delta
BenchmarkAddVV_1 7 7 +2.51%
BenchmarkAddVV_2 8 8 +3.70%
BenchmarkAddVV_3 10 10 +4.00%
BenchmarkAddVV_4 11 9 -19.49%
BenchmarkAddVV_5 14 11 -18.44%
BenchmarkAddVV_1e1 23 17 -27.00%
BenchmarkAddVV_1e2 234 117 -50.00%
BenchmarkAddVV_1e3 2284 1095 -52.06%
BenchmarkAddVV_1e4 22906 13149 -42.60%
BenchmarkAddVV_1e5 229860 135133 -41.21%
BenchmarkAddVW_1 6 6 +1.15%
BenchmarkAddVW_2 7 7 +1.37%
BenchmarkAddVW_3 7 8 +1.00%
BenchmarkAddVW_4 9 8 -6.93%
BenchmarkAddVW_5 10 9 -13.21%
BenchmarkAddVW_1e1 18 14 -24.32%
BenchmarkAddVW_1e2 170 97 -42.41%
BenchmarkAddVW_1e3 1619 953 -41.14%
BenchmarkAddVW_1e4 15142 9776 -35.44%
BenchmarkAddVW_1e5 160835 102396 -36.33%
benchmark old MB/s new MB/s speedup
BenchmarkAddVV_1 8928.95 8702.84 0.97x
BenchmarkAddVV_2 15298.84 14739.60 0.96x
BenchmarkAddVV_3 19116.52 18375.37 0.96x
BenchmarkAddVV_4 21644.30 26935.44 1.24x
BenchmarkAddVV_5 22771.64 27754.04 1.22x
BenchmarkAddVV_1e1 27017.62 37050.89 1.37x
BenchmarkAddVV_1e2 27326.09 54289.15 1.99x
BenchmarkAddVV_1e3 28016.84 58428.83 2.09x
BenchmarkAddVV_1e4 27939.38 48670.55 1.74x
BenchmarkAddVV_1e5 27843.00 47360.54 1.70x
BenchmarkAddVW_1 10510.97 10397.27 0.99x
BenchmarkAddVW_2 17499.71 17279.03 0.99x
BenchmarkAddVW_3 24093.93 23858.39 0.99x
BenchmarkAddVW_4 27733.08 29799.42 1.07x
BenchmarkAddVW_5 30267.17 34781.83 1.15x
BenchmarkAddVW_1e1 34566.78 45629.88 1.32x
BenchmarkAddVW_1e2 37521.89 65341.93 1.74x
BenchmarkAddVW_1e3 39513.18 67153.67 1.70x
BenchmarkAddVW_1e4 42263.80 65464.60 1.55x
BenchmarkAddVW_1e5 39792.21 62501.88 1.57x
R=iant, remyoudompheng, nightlyone, minux.ma
CC=golang-dev
https://golang.org/cl/6482062
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/35422bc11f8de6d086f382f5f636b1e0a96f895e
元コミット内容
math/big: faster (add|sub)V(V|W) routines
このコミットは、math/big パッケージ内の addVV, subVV, addVW, subVW といった任意精度演算の基盤となるルーチンの高速化を目的としています。ベンチマーク結果が示されており、特に大きな数値（1e2、1e3、1e4、1e5といった接尾辞が付いているもの）に対する演算で大幅な性能向上が見られます。
変更の背景
Go言語の math/big パッケージは、標準の整数型や浮動小数点型では表現できない非常に大きな数値や高精度な計算を扱うために設計されています。このような任意精度演算では、基本的な加算や減算といった操作が頻繁に行われるため、これらの基盤となるルーチンの性能はパッケージ全体のパフォーマンスに直結します。
元の実装では、これらのルーチンはシンプルなループ構造で記述されていましたが、CPUのパイプライン処理やキャッシュ効率を最大限に引き出すためには、より低レベルな最適化が必要でした。特に、ループの各イテレーションで発生するオーバーヘッド（ループカウンタの更新、条件分岐など）は、処理するデータ量が少ない場合には無視できるかもしれませんが、データ量が増えるにつれて顕著なボトルネックとなります。
このコミットの背景には、このようなパフォーマンス上の課題を解決し、math/big パッケージの任意精度演算をより高速化するという明確な目的がありました。アセンブリ言語による実装は、Goコンパイラが生成するコードよりもさらに細かくCPUのレジスタや命令を制御できるため、このような低レベルな最適化に適しています。
前提知識の解説
1. math/big パッケージ
Go言語の math/big パッケージは、任意精度（arbitrary-precision）の数値演算を提供するライブラリです。これは、int や float64 といった組み込み型では扱えない、非常に大きな整数（Int型）、有理数（Rat型）、浮動小数点数（Float型）を扱うことができます。科学技術計算、暗号化、金融アプリケーションなど、高い精度や大きな数値範囲が要求される場面で利用されます。
math/big パッケージの内部では、これらの大きな数値は Word 型の配列（スライス）として表現されます。Word 型は通常、システムのワードサイズ（32ビットまたは64ビット）に対応する符号なし整数型です。例えば、64ビットシステムでは uint64 が Word 型として使われます。これにより、大きな数値を複数の Word に分割して格納し、各 Word に対して基本的な算術演算を行うことで、任意精度の計算を実現しています。
2. addVV, subVV, addVW, subVW 関数
これらの関数は、math/big パッケージにおける任意精度演算の基盤となるアセンブリルーチンです。
addVV(z, x, y []Word) (c Word): 2つのWordスライスxとyを要素ごとに加算し、結果をzに格納します。cはキャリー（繰り上がり）ビットを返します。これは、多倍長整数の加算において、下位の桁からの繰り上がりを上位の桁に伝播させるために重要です。subVV(z, x, y []Word) (c Word): 2つのWordスライスxからyを要素ごとに減算し、結果をzに格納します。cはボロー（借り入れ）ビットを返します。これは、多倍長整数の減算において、上位の桁からの借り入れを下位の桁に伝播させるために重要です。addVW(z, x []Word, y Word) (c Word):Wordスライスxの各要素に単一のWord値yを加算し、結果をzに格納します。cはキャリービットを返します。subVW(z, x []Word, y Word) (c Word):Wordスライスxの各要素から単一のWord値yを減算し、結果をzに格納します。cはボロービットを返します。
これらの関数は、math/big パッケージの Int 型や Float 型の加算・減算メソッドの内部で呼び出され、実際の数値演算の大部分を担っています。
3. アセンブリ言語とパフォーマンス最適化
アセンブリ言語は、特定のCPUアーキテクチャ（この場合はAMD64、つまりx86-64）の命令セットに直接対応する低レベルなプログラミング言語です。Go言語のような高水準言語で書かれたコードは、コンパイラによって機械語に変換されますが、アセンブリ言語を使用することで、プログラマはCPUのレジスタ、メモリ、命令の実行順序などをより細かく制御できます。
これにより、以下のような最適化が可能になります。
- レジスタの効率的な利用: メモリへのアクセスはCPUレジスタへのアクセスよりもはるかに遅いため、頻繁にアクセスするデータをレジスタに保持することでパフォーマンスを向上させます。
- 命令の選択と順序付け: 特定のCPU命令（例:
ADCQ(Add with Carry),SBBQ(Subtract with Borrow)）は、高水準言語では直接表現しにくいが、算術演算の効率を大幅に向上させることができます。また、命令の実行順序を最適化することで、パイプラインストールを減らすことができます。 - ループアンローリング (Loop Unrolling): ループの各イテレーションで発生するオーバーヘッド（ループカウンタの更新、条件分岐、ジャンプ命令など）を削減するための最適化手法です。ループ本体を複数回コピーして展開することで、ループの実行回数を減らし、これらのオーバーヘッドを相対的に小さくします。これにより、CPUの命令フェッチやデコードの効率が向上し、パイプラインがよりスムーズに動作するようになります。
4. AMD64 (x86-64) アセンブリの基本命令
このコミットで使われている主要なAMD64アセンブリ命令について簡単に説明します。
MOVQ(Move Quadword): 64ビットの値をレジスタ間、またはレジスタとメモリ間で移動します。ADDQ(Add Quadword): 64ビットの加算を行います。ADCQ(Add with Carry Quadword): キャリーフラグ（CF）を考慮して64ビットの加算を行います。多倍長整数演算で繰り上がりを伝播させる際に不可欠です。SUBQ(Subtract Quadword): 64ビットの減算を行います。SBBQ(Subtract with Borrow Quadword): ボローフラグ（CF）を考慮して64ビットの減算を行います。多倍長整数演算で借り入れを伝播させる際に不可欠です。RCLQ $1, reg(Rotate Left through Carry Quadword): レジスタの内容を左に1ビット回転させ、キャリーフラグを最下位ビットに、最上位ビットをキャリーフラグに移動させます。ADCQ/SBBQの後にキャリー/ボローフラグの状態をレジスタに保存するために使われます。RCRQ $1, reg(Rotate Right through Carry Quadword): レジスタの内容を右に1ビット回転させ、キャリーフラグを最上位ビットに、最下位ビットをキャリーフラグに移動させます。ADCQ/SBBQの前にキャリー/ボローフラグの状態をレジスタから復元するために使われます。ANDQ(Logical AND Quadword): ビットごとの論理AND演算を行います。RCLQの後にキャリーフラグの状態を0または1に正規化するために使われます。CMPQ(Compare Quadword): 2つの64ビット値を比較し、フラグレジスタ（特にZF, CF, SFなど）を設定します。JMP(Jump): 無条件ジャンプ。JL(Jump Less): 比較結果が「より小さい」場合にジャンプ。JGE(Jump Greater or Equal): 比較結果が「より大きいか等しい」場合にジャンプ。JLE(Jump Less or Equal): 比較結果が「より小さいか等しい」場合にジャンプ。JG(Jump Greater): 比較結果が「より大きい」場合にジャンプ。RET(Return): サブルーチンから戻ります。TEXT: Goのアセンブリ構文で関数を定義するためのディレクティブ。
5. Goのアセンブリ構文
Go言語は、Plan 9アセンブラの構文を使用しています。これは一般的なIntel構文やAT&T構文とは異なる点があります。
- レジスタ名:
AX,BX,CX,DX,SI,DI,BP,SP,R8～R15など。 - オペランドの順序:
MOVQ src, dstのように、ソースが先、デスティネーションが後です。 - メモリ参照:
offset(base)(index*scale)の形式で、offset + base + index * scaleのアドレスを示します。例えば0(R8)(SI*8)はR8 + SI * 8のアドレスにあるメモリを参照します。これは、Word型が8バイト（64ビット）であるため、インデックスSIに8を掛けてオフセットを計算していることを意味します。 - フレームポインタ (FP): 関数引数やローカル変数へのアクセスに使われます。
x+16(FP)のように、フレームポインタからのオフセットで引数にアクセスします。
技術的詳細
このコミットの主要な技術的変更点は、addVV, subVV, addVW, subVW の各アセンブリルーチンにループアンローリングを適用したことです。
ループアンローリングの適用
元のコードでは、これらの関数はシンプルなループで実装されていました。例えば addVV の場合、各 Word を1つずつ処理していました。
L1: MOVQ (R8)(BX*8), AX
RCRQ $1, DX
ADCQ (R9)(BX*8), AX
RCLQ $1, DX
MOVQ AX, (R10)(BX*8)
ADDL $1, BX // i++
E1: CMPQ BX, R11 // i < n
JL L1
このループは、各イテレーションで以下のオーバーヘッドを伴います。
ADDL $1, BX: ループカウンタBXのインクリメントCMPQ BX, R11: ループ条件の比較JL L1: 条件付きジャンプ
これらの命令は、実際の加算・減算処理とは直接関係なく、ループの制御のために必要です。データ量が少ない場合は問題になりませんが、データ量が増えるにつれて、これらのオーバーヘッドが全体の実行時間に占める割合が大きくなります。
新しい実装では、このループを4回アンロールしています。つまり、ループ本体の処理を4回分まとめて記述し、ループの実行回数を1/4に削減しています。
例えば、addVV の新しい実装では、U1 ラベルで始まるブロックが4回分の処理をまとめて行っています。
U1: // n >= 4
// regular loop body unrolled 4x
MOVQ 0(R8)(SI*8), R11
MOVQ 8(R8)(SI*8), R12
MOVQ 16(R8)(SI*8), R13
MOVQ 24(R8)(SI*8), R14
RCRQ $1, CX // restore CF
ADCQ 0(R9)(SI*8), R11
ADCQ 8(R9)(SI*8), R12
ADCQ 16(R9)(SI*8), R13
ADCQ 24(R9)(SI*8), R14
RCLQ $1, CX // save CF
MOVQ R11, 0(R10)(SI*8)
MOVQ R12, 8(R10)(SI*8)
MOVQ R13, 16(R10)(SI*8)
MOVQ R14, 24(R10)(SI*8)
ADDQ $4, SI // i += 4
SUBQ $4, DI // n -= 4
CMPQ DI, $4
JGE U1 // if n >= 4 goto U1
このアンロールされたループでは、一度のイテレーションで4つの Word を処理するため、ループ制御のための命令（ADDQ $4, SI, SUBQ $4, DI, CMPQ DI, $4, JGE U1）の実行頻度が1/4になります。これにより、CPUの命令フェッチ、デコード、実行パイプラインがより効率的に利用され、全体的なスループットが向上します。
キャリー/ボローフラグの扱い
多倍長整数演算では、各ワード間のキャリー（繰り上がり）やボロー（借り入れ）の伝播が重要です。AMD64の ADCQ (Add with Carry) や SBBQ (Subtract with Borrow) 命令は、CPUのキャリーフラグ（CF）を利用してこの伝播を自動的に処理します。
アンロールされたループでは、4つの ADCQ または SBBQ 命令が連続して実行されます。この際、最初の演算のキャリー/ボローフラグが次の演算に自動的に引き継がれるため、明示的にフラグを保存・復元する必要があるのは、4つの演算ブロックの最初と最後だけです。
RCRQ $1, CX: 演算ブロックの開始時に、前回の演算で保存されたキャリー/ボローの状態をキャリーフラグに復元します。RCLQ $1, CX: 演算ブロックの終了時に、最後の演算で設定されたキャリー/ボローの状態をCXレジスタに保存します。ANDQ $1, CXは、CXレジスタに保存されたキャリー/ボローの状態を0または1に正規化するために使用されます。
処理フロー
各関数は、まず入力のワード数 n をチェックします。
nが4未満の場合、アンロールされていない通常のループ（V1、V2、V3、V4ラベルから始まる）にジャンプします。これは、データ量が少ない場合にアンローリングのオーバーヘッドがメリットを上回る可能性があるためです。nが4以上の場合、アンロールされたループ（U1、U2、U3、U4ラベルから始まる）を実行します。このループは、nが4未満になるまで4ワードずつ処理を進めます。- アンロールされたループが終了した後、残りのワード（0〜3ワード）は通常のループで処理されます。
- 全てのワードの処理が完了した後、最終的なキャリー/ボロービットが返されます。
このハイブリッドアプローチにより、様々なサイズの入力に対して最適なパフォーマンスが期待できます。
ベンチマーク結果の分析
コミットメッセージには、2つの異なるシステム（iMacとPowerMac）でのベンチマーク結果が示されています。
ns/op(nanoseconds per operation): 1回の操作にかかる時間を示します。値が小さいほど高速です。MB/s(megabytes per second): 1秒あたりに処理できるデータ量を示します。値が大きいほど高速です。delta:ns/opの変化率。負の値は高速化、正の値は低速化を示します。speedup:MB/sの改善率。1より大きい値は高速化を示します。
結果を見ると、特に BenchmarkAddVV_1e2、BenchmarkAddVV_1e3、BenchmarkAddVV_1e4、BenchmarkAddVV_1e5 のように、処理するワード数が多いベンチマークで ns/op が大幅に減少（約40%〜50%の改善）し、MB/s が約1.7倍〜2.1倍に向上していることがわかります。これは、ループアンローリングが大きなデータセットに対して特に効果的であることを明確に示しています。
一方で、_1、_2、_3 のように処理するワード数が少ないベンチマークでは、ns/op の改善が小さいか、場合によってはわずかに悪化しているものもあります。これは、アンローリングによるコードサイズの増加や、アンロールされたループに入る前の条件分岐のオーバーヘッドが、少ないデータ量では相対的に大きくなるためと考えられます。しかし、全体としては、math/big パッケージが扱うような大きな数値演算において、この最適化が非常に有効であることが示されています。
コアとなるコードの変更箇所
変更は src/pkg/math/big/arith_amd64.s ファイルに集中しています。
func addVV(z, x, y []Word) (c Word)
- 元のシンプルなループが削除され、4回アンロールされたループ (
U1) と、残りの要素を処理するための通常のループ (V1,L1) に置き換えられました。 - ループカウンタとインデックスのレジスタ割り当てが変更されました (
BX->SI,R11->DI)。 - キャリーフラグの保存と復元に
RCRQとRCLQが使用され、CXレジスタがキャリービットの保持に使用されています。
func subVV(z, x, y []Word) (c Word)
addVVと同様に、4回アンロールされたループ (U2) と通常のループ (V2,L2) に置き換えられました。- 加算命令 (
ADCQ) が減算命令 (SBBQ) に変更されています。
func addVW(z, x []Word, y Word) (c Word)
addVVと同様に、4回アンロールされたループ (U3) と通常のループ (V3,L3) に置き換えられました。- 単一の
Word値yを各要素に加算するロジックが、アンロールされた形式で実装されています。キャリーの伝播はADCQ $0, Regを用いて行われます。
func subVW(z, x []Word, y Word) (c Word)
addVWと同様に、4回アンロールされたループ (U4) と通常のループ (V4,L4) に置き換えられました。- 減算命令 (
SUBQ,SBBQ) が使用されています。
コアとなるコードの解説
各関数の変更は、基本的に同じパターンに従っています。ここでは addVV を例に、変更されたアセンブリコードの主要部分を解説します。
TEXT ·addVV(SB),7,$0
MOVL n+8(FP), DI // n (要素数) を DI レジスタにロード
MOVQ x+16(FP), R8 // x スライスのデータポインタを R8 にロード
MOVQ y+32(FP), R9 // y スライスのデータポインタを R9 にロード
MOVQ z+0(FP), R10 // z スライスのデータポインタを R10 にロード
MOVQ $0, CX // c (キャリー) を 0 に初期化
MOVQ $0, SI // i (インデックス) を 0 に初期化
// uncomment the next line to disable the unrolled loop
// JMP V1
CMPQ DI, $4 // n と 4 を比較
JL V1 // n < 4 なら V1 (通常のループ) へジャンプ
U1: // n >= 4
// regular loop body unrolled 4x
MOVQ 0(R8)(SI*8), R11 // x[i] を R11 にロード
MOVQ 8(R8)(SI*8), R12 // x[i+1] を R12 にロード
MOVQ 16(R8)(SI*8), R13 // x[i+2] を R13 にロード
MOVQ 24(R8)(SI*8), R14 // x[i+3] を R14 にロード
RCRQ $1, CX // CX に保存されたキャリーをキャリーフラグに復元
ADCQ 0(R9)(SI*8), R11 // R11 += y[i] + CF
ADCQ 8(R9)(SI*8), R12 // R12 += y[i+1] + CF
ADCQ 16(R9)(SI*8), R13 // R13 += y[i+2] + CF
ADCQ 24(R9)(SI*8), R14 // R14 += y[i+3] + CF
RCLQ $1, CX // 最後の ADCQ で設定されたキャリーフラグを CX に保存
MOVQ R11, 0(R10)(SI*8) // R11 を z[i] にストア
MOVQ R12, 8(R10)(SI*8) // R12 を z[i+1] にストア
MOVQ R13, 16(R10)(SI*8) // R13 を z[i+2] にストア
MOVQ R14, 24(R10)(SI*8) // R14 を z[i+3] にストア
ADDQ $4, SI // i を 4 増やす
SUBQ $4, DI // n を 4 減らす
CMPQ DI, $4 // 残りの n と 4 を比較
JGE U1 // n >= 4 なら U1 へジャンプ (ループ継続)
V1: CMPQ DI, $0 // 残りの n と 0 を比較
JLE E1 // n <= 0 なら E1 (終了) へジャンプ
L1: // n > 0
MOVQ 0(R8)(SI*8), R11 // x[i] を R11 にロード
RCRQ $1, CX // CX に保存されたキャリーをキャリーフラグに復元
ADCQ 0(R9)(SI*8), R11 // R11 += y[i] + CF
RCLQ $1, CX // 最後の ADCQ で設定されたキャリーフラグを CX に保存
MOVQ R11, 0(R10)(SI*8) // R11 を z[i] にストア
ADDQ $1, SI // i を 1 増やす
SUBQ $1, DI // n を 1 減らす
JG L1 // n > 0 なら L1 へジャンプ (ループ継続)
E1: MOVQ CX, c+48(FP) // 最終的なキャリーを戻り値 c にストア
RET // 関数から戻る
主要なポイント:
- レジスタの役割:
DI: 残りの要素数nを保持。R8:xスライスのデータポインタ。R9:yスライスのデータポインタ。R10:zスライスのデータポインタ。CX: キャリービットを保持。SI: 現在のインデックスiを保持。R11,R12,R13,R14: アンロールされたループ内で一時的にワード値を保持するための汎用レジスタ。
- ループアンローリングの分岐:
CMPQ DI, $4とJL V1によって、要素数が少ない場合は通常のループに分岐し、オーバーヘッドを避けています。 - アンロールされたループ (
U1):MOVQ命令で4つのワードを一度にレジスタにロードします。RCRQ $1, CXで前回のキャリーを復元し、ADCQ命令で連続して4つの加算を行います。ADCQはキャリーフラグを自動的に伝播させるため、各ADCQの間にRCRQ/RCLQは不要です。RCLQ $1, CXで最後の加算結果のキャリーをCXに保存します。MOVQ命令で4つの結果ワードを一度にメモリにストアします。ADDQ $4, SIとSUBQ $4, DIでインデックスとカウンタを4ずつ更新し、ループのオーバーヘッドを削減します。
- 通常のループ (
L1): アンロールされたループで処理しきれなかった残りの要素（0〜3個）を1つずつ処理します。ここでもRCRQ/RCLQを使ってキャリーを伝播させています。 - 戻り値: 最終的なキャリービットが
CXレジスタからc+48(FP)(戻り値cのメモリ位置) にストアされ、関数が終了します。
subVV, addVW, subVW も同様の構造を持ち、それぞれ ADCQ の代わりに SBBQ を使用したり、単一の Word 値を扱うためのロジックが組み込まれています。特に addVW と subVW では、ADCQ $0, Reg や SBBQ $0, Reg を用いて、単一のキャリー/ボローを複数のワードに伝播させるテクニックが使われています。これは、Reg += 0 + CF や Reg -= 0 + CF と同じ効果を持ち、キャリー/ボローフラグの状態だけを次の演算に引き継ぐために利用されます。
関連リンク
- Go言語の
math/bigパッケージのドキュメント: https://pkg.go.dev/math/big - Go言語のアセンブリについて: https://go.dev/doc/asm
- Go言語のソースコードリポジトリ: https://github.com/golang/go
参考にした情報源リンク
- Go言語の
math/bigパッケージのソースコード (arith_amd64.s): https://github.com/golang/go/blob/master/src/math/big/arith_amd64.s - Go言語の
math/bigパッケージのソースコード (arith.go): https://github.com/golang/go/blob/master/src/math/big/arith.go (アセンブリルーチンがGoコードからどのように呼び出されているかを確認できます) - ループアンローリングに関する一般的な情報:
- Wikipedia: https://en.wikipedia.org/wiki/Loop_unrolling
- x86-64 アセンブリ命令セットリファレンス (Intel Software Developer's Manualsなど)
- Go言語のベンチマークに関するドキュメント: https://go.dev/doc/articles/go_benchmarking