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

このコミットは、Go言語のmath/bigパッケージにおけるアセンブリコードの微調整に関するものです。具体的には、arith_amd64.sファイル内のaddVV、subVV、addVW、subVWといった多倍長整数演算のコアとなる関数において、ループ処理とキャリーフラグの扱いを最適化し、わずかながらパフォーマンスを向上させています。

コミット

commit 3bd8684facfadb57ba649cae6b067e3a3ecb1208
Author: Robert Griesemer <gri@golang.org>
Date:   Fri Aug 24 10:51:39 2012 -0700

    math/big: minor tweaks to assembly code (slightly better performance)
    
    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   -0.82%
    BenchmarkAddVV_2              8            8   -3.46%
    BenchmarkAddVV_3             10            9   -4.81%
    BenchmarkAddVV_4              9            9   -1.89%
    BenchmarkAddVV_5             11           10   -5.22%
    BenchmarkAddVV_1e1           17           18   +4.05%
    BenchmarkAddVV_1e2          117          115   -1.71%
    BenchmarkAddVV_1e3         1095         1090   -0.46%
    BenchmarkAddVV_1e4        13149        12679   -3.57%
    BenchmarkAddVV_1e5       135133       129482   -4.18%
    BenchmarkAddVW_1              6            6   -1.14%
    BenchmarkAddVW_2              7            7   +3.78%
    BenchmarkAddVW_3              8            8   +0.12%
    BenchmarkAddVW_4              8            8   -6.52%
    BenchmarkAddVW_5              9            8   -3.70%
    BenchmarkAddVW_1e1           14           13   -4.29%
    BenchmarkAddVW_1e2           97           96   -1.33%
    BenchmarkAddVW_1e3          953          940   -1.36%
    BenchmarkAddVW_1e4         9776         9527   -2.55%
    BenchmarkAddVW_1e5       102396        97738   -4.55%
    
    benchmark              old MB/s     new MB/s  speedup
    BenchmarkAddVV_1        8702.84      8774.56    1.01x
    BenchmarkAddVV_2       14739.60     15277.82    1.04x
    BenchmarkAddVV_3       18375.37     19398.16    1.06x
    BenchmarkAddVV_4       26935.44     27464.68    1.02x
    BenchmarkAddVV_5       27754.04     29423.30    1.06x
    BenchmarkAddVV_1e1     37050.89     35629.72    0.96x
    BenchmarkAddVV_1e2     54289.15     55533.24    1.02x
    BenchmarkAddVV_1e3     58428.83     58682.53    1.00x
    BenchmarkAddVV_1e4     48670.55     50475.99    1.04x
    BenchmarkAddVV_1e5     47360.54     49427.66    1.04x
    BenchmarkAddVW_1       10397.27     10502.23    1.01x
    BenchmarkAddVW_2       17279.03     16654.13    0.96x
    BenchmarkAddVW_3       23858.39     23825.89    1.00x
    BenchmarkAddVW_4       29799.42     31895.06    1.07x
    BenchmarkAddVW_5       34781.83     36105.11    1.04x
    BenchmarkAddVW_1e1     45629.88     47597.42    1.04x
    BenchmarkAddVW_1e2     65341.93     66240.04    1.01x
    BenchmarkAddVW_1e3     67153.67     68069.83    1.01x
    BenchmarkAddVW_1e4     65464.60     67173.83    1.03x
    BenchmarkAddVW_1e5     62501.88     65480.66    1.05x
    
    R=iant
    CC=golang-dev
    https://golang.org/cl/6484056

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

https://github.com/golang/go/commit/3bd8684facfadb57ba649cae6b067e3a3ecb1208

このコミットは、Go言語の標準ライブラリであるmath/bigパッケージ内のアセンブリコードに対して、細かな調整（"minor tweaks"）を行うことで、わずかながらパフォーマンスを向上させることを目的としています。具体的には、addVV（多倍長整数同士の加算）、subVV（多倍長整数同士の減算）、addVW（多倍長整数と単一ワードの加算）、subVW（多倍長整数と単一ワードの減算）といった関数が対象です。

コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されており、多くのケースで処理時間（ns/op）が減少し、処理速度（MB/s）が向上していることが示されています。特に、大規模な数値（1e4や1e5のサフィックスが付くベンチマーク）に対する操作で顕著な改善が見られます。

変更の背景

math/bigパッケージは、Go言語で任意精度の算術演算を可能にするための重要なライブラリです。このようなライブラリでは、非常に大きな数値を扱うため、基本的な加算、減算、乗算などの操作が、CPUのワードサイズ（64ビットシステムでは64ビット）を超える複数のワード（big.Word型）に分割されて処理されます。これらの低レベルな演算は、パフォーマンスに直結するため、Go言語では多くの場合、プラットフォーム固有のアセンブリ言語で実装されています。

このコミットの背景には、math/bigパッケージの性能をさらに最適化し、多倍長整数演算の効率を高めるという継続的な取り組みがあります。アセンブリコードレベルでの最適化は、コンパイラが生成するコードでは達成が難しい、特定のCPUアーキテクチャの特性（パイプライン、キャッシュ、命令セットなど）を最大限に活用するために行われます。

ベンチマーク結果が示すように、この変更は全体的なパフォーマンス向上に寄与しており、特に大きな数値の計算においてその効果が期待されます。これは、科学技術計算、暗号通貨、セキュリティなど、高精度な数値計算が求められるアプリケーションにとって重要です。

前提知識の解説

このコミットの変更内容を理解するためには、以下の知識が役立ちます。

多倍長整数演算 (Arbitrary-Precision Arithmetic): 通常のプログラミング言語の組み込み整数型（例: int64）は、固定されたビット幅（例: 64ビット）で数値を表現します。しかし、これでは表現できる数値の範囲に限界があります。多倍長整数演算は、この制限を取り払い、メモリが許す限り任意の大きさの整数を扱うことを可能にします。これは、数値を複数の「ワード」（通常はCPUのレジスタサイズに合わせた単位、Goのmath/bigではbig.Word）の配列として表現し、各ワードに対して算術演算を行い、キャリー（繰り上がり）やボロー（借り）を適切に処理することで実現されます。
アセンブリ言語 (Assembly Language): アセンブリ言語は、CPUが直接実行できる機械語（バイナリコード）と1対1に対応する低レベルなプログラミング言語です。特定のCPUアーキテクチャ（この場合はAMD64、すなわちx86-64）の命令セットを直接操作するため、非常に高速なコードを記述できますが、その分、CPUの内部動作やレジスタ、フラグなどの詳細な知識が必要です。
x86-64 アセンブリの基本:
- レジスタ: R8, R9, R10, R11, R12, R13, R14, CX, DI, SI などが使用されています。これらは汎用レジスタであり、データの格納やアドレス計算に用いられます。
- メモリ参照: 0(R8)(SI*8) のような表記は、R8レジスタの値に SI * 8 を加算したアドレスにあるメモリの内容を参照することを意味します。これは配列の要素にアクセスする際によく使われます（SIはインデックス、8はbig.Wordが8バイトであることを示唆）。
- フラグレジスタ (FLAGS Register): CPUは演算結果に応じて様々なフラグを設定します。このコミットで特に重要なのはキャリーフラグ (CF: Carry Flag) です。
  - キャリーフラグ (CF): 加算で最上位ビットからの繰り上がりが発生した場合、または減算で借りが発生した場合にセットされます。多倍長整数演算では、このキャリーフラグを次のワードの演算に引き継ぐことが不可欠です。
- 命令:
  - MOVQ: 64ビットの値を移動します。
  - ADDQ: 64ビットの加算を行います。
  - SUBQ: 64ビットの減算を行います。
  - ADCQ (Add with Carry): キャリーフラグの値を加算に含めます。多倍長整数の加算で、前のワードからの繰り上がりを現在のワードに加えるために使用されます。
  - SBBQ (Subtract with Borrow): キャリーフラグの値を減算に含めます（キャリーフラグがセットされていると、借りが発生したとみなしてさらに1を引きます）。多倍長整数の減算で、前のワードからの借り入れを現在のワードに反映するために使用されます。
  - RCRQ (Rotate through Carry Right): オペランドを右に1ビット回転させ、最下位ビットをキャリーフラグに、キャリーフラグを最上位ビットに移動させます。このコミットでは、RCRQ $1, CX は、CXレジスタの最下位ビットをキャリーフラグに移動させ、同時にキャリーフラグの値をCXの最上位ビットに移動させます。これにより、CXレジスタとキャリーフラグの間で値を交換するような効果が得られます。特に、CXレジスタに保存されたキャリー値をキャリーフラグに「復元」するために使われます。
  - RCLQ (Rotate through Carry Left): オペランドを左に1ビット回転させ、最上位ビットをキャリーフラグに、キャリーフラグを最下位ビットに移動させます。RCLQ $1, CX は、CXレジスタの最上位ビットをキャリーフラグに移動させ、同時にキャリーフラグの値をCXの最下位ビットに移動させます。これにより、演算によって新しく生成されたキャリーフラグの値をCXレジスタに「保存」するために使われます。
  - CMPQ: 2つのオペランドを比較し、フラグを設定します。
  - JMP, JL, JGE, JLE: 条件付きまたは無条件のジャンプ命令です。ループ制御や条件分岐に使用されます。
  - ANDQ: ビット単位のAND演算を行います。ANDQ $1, CX は、CXレジスタの最下位ビット以外の全てを0にし、CXが0か1（キャリーの有無）を示すようにします。
ループアンローリング (Loop Unrolling): ループアンローリングは、ループの反復回数を減らすために、ループ本体のコードを複数回（このコミットでは4回）複製する最適化手法です。これにより、ループのオーバーヘッド（カウンタの更新、条件チェック、ジャンプ命令など）が削減され、命令キャッシュの効率が向上し、CPUのパイプラインをより効率的に利用できるようになります。

技術的詳細

このコミットの技術的詳細は、主にsrc/pkg/math/big/arith_amd64.sファイル内のアセンブリコードの変更に集約されます。変更は、多倍長整数演算におけるループ処理とキャリーフラグの伝播メカニズムを改善することに焦点を当てています。

1. ループ条件の変更

変更前は、アンロールされたループ（U1, U2, U3, U4）に入る前に、CMPQ DI, $4 と JL V1 のように、残りの要素数DIがアンロールサイズ（4）以上であるかをチェックしていました。

変更後は、SUBQ $4, DI を先に実行し、その結果が負になるかどうかでジャンプを判断しています。

-	CMPQ DI, $4
-	JL V1			// if n < 4 goto V1
+	SUBQ $4, DI		// n -= 4
+	JL V1			// if n < 0 goto V1

この変更は、ループの開始条件をより効率的に処理するためのものです。SUBQ命令はDIから4を減算し、その結果に基づいてフラグを設定します。JL（Jump if Less）命令は、結果が負の場合にジャンプします。これにより、DIが4未満の場合にアンロールループをスキップし、残りの要素を処理する単一ワードループ（L1など）に直接移行します。このパターンは、分岐予測の精度向上や、命令の依存関係を減らすことでパイプラインの効率を高める可能性があります。

また、アンロールループの終了条件も同様に、CMPQ DI, $4 と JGE U1 から、JGE U1 のみ（DIが0以上であればループを継続）に変更されています。

アンロールループを抜けた後の残りの要素を処理する部分（V1など）では、ADDQ $4, DI を実行してDIの値を元に戻し、残りの要素数を正しく計算しています。

2. キャリーフラグ (CF) の扱い

多倍長整数演算では、各ワードの加算/減算の結果生じるキャリー（繰り上がり）またはボロー（借り）を、次のワードの演算に正確に伝播させることが極めて重要です。x86-64アーキテクチャでは、ADCQ（Add with Carry）やSBBQ（Subtract with Borrow）命令がこのためにキャリーフラグ（CF）を利用します。

このコミットでは、CXレジスタとキャリーフラグの間でキャリー値をやり取りするRCRQとRCLQ命令の配置が変更されています。

変更前:

	RCRQ $1, CX		// restore CF
	MOVQ 0(R8)(SI*8), R11
	ADCQ 0(R9)(SI*8), R11
	RCLQ $1, CX		// save CF

ここでは、RCRQ $1, CXでCXからキャリーフラグを復元した後、オペランドをメモリからレジスタにロードし、ADCQで加算を行い、最後にRCLQ $1, CXで新しいキャリーフラグをCXに保存しています。

変更後:

	RCRQ $1, CX		// CF = c
	MOVQ 0(R8)(SI*8), R11
	ADCQ 0(R9)(SI*8), R11
	RCLQ $1, CX		// c = CF

変更後も基本的なロジックは同じですが、RCRQ $1, CXのコメントが// CF = cに、RCLQ $1, CXのコメントが// c = CFに変更されており、より明確にキャリーフラグとCXレジスタ間の役割が示されています。

addVWとsubVW関数では、ADCQ $0, RxxやSBBQ $0, Rxxといった命令が使われています。これらは、単一ワードとの加算/減算において、キャリーフラグを伝播させるために、0を加算/減算することでキャリーフラグのみを結果に反映させるテクニックです。これらの関数でも、RCLQ $1, CXとANDQ $1, CXの順序が変更され、キャリーフラグの保存とCXレジスタへの反映がより効率的に行われるようになっています。

これらの変更は、命令の並び替えや、CPUのパイプライン処理における依存関係の解消、あるいは特定のCPUアーキテクチャにおける命令のレイテンシやスループットの改善を狙ったものと考えられます。アセンブリレベルの最適化は非常に細かく、わずかな命令の順序変更でもパフォーマンスに影響を与えることがあります。

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

変更はsrc/pkg/math/big/arith_amd64.sファイルに集中しています。このファイルは、Go言語のmath/bigパッケージがAMD64アーキテクチャ上で多倍長整数演算を行う際に使用するアセンブリコードを含んでいます。

具体的には、以下の4つの関数の実装が変更されています。

TEXT ·addVV(SB),7,$0 (多倍長整数同士の加算)
TEXT ·subVV(SB),7,$0 (多倍長整数同士の減算)
TEXT ·addVW(SB),7,$0 (多倍長整数と単一ワードの加算)
TEXT ·subVW(SB),7,$0 (多倍長整数と単一ワードの減算)

各関数において、主に以下の部分が変更されています。

ループ開始前の条件分岐: CMPQ DI, $4 と JL V1 の代わりに SUBQ $4, DI と JL V1 を使用。
アンロールループ内のキャリーフラグ操作: RCRQ $1, CX と RCLQ $1, CX の配置とコメントの変更。
アンロールループ後の残りの要素処理: ADDQ $4, DI を追加してDIを調整。
単一ワードループ内のキャリーフラグ操作: RCLQ $1, CX と ANDQ $1, CX の順序変更（addVW, subVW）。

コアとなるコードの解説

ここでは、addVV関数の変更を例に、コアとなるコードの変更点を詳しく解説します。他の関数も同様のパターンで変更されています。

`addVV`関数の変更点

addVV関数は、2つの多倍長整数xとyをワード単位で加算し、結果をzに格納します。同時に、繰り上がり（キャリー）を返します。

変更前後の比較（抜粋）:

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -32,45 +32,44 @@ TEXT ·addVV(SB),7,$0
 	MOVQ z+0(FP), R10
 
 	MOVQ $0, CX		// c = 0
-	MOVQ $0, SI	     // i = 0
+	MOVQ $0, SI		// i = 0
 
 	// uncomment the next line to disable the unrolled loop
 	// JMP V1
 	
-	CMPQ DI, $4
-	JL V1			// if n < 4 goto V1
+	SUBQ $4, DI		// n -= 4
+	JL V1			// if n < 0 goto V1
 
-U1:	// n >= 4
+U1:	// n >= 0
 	// regular loop body unrolled 4x
+\tRCRQ $1, CX		// CF = c
 	MOVQ 0(R8)(SI*8), R11
 	MOVQ 8(R8)(SI*8), R12
 	MOVQ 16(R8)(SI*8), R13
 	MOVQ 24(R8)(SI*8), R14
-\tRCRQ $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
-\tRCLQ $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)
+\tRCLQ $1, CX		// c = CF
 
 	ADDQ $4, SI		// i += 4
 	SUBQ $4, DI		// n -= 4
-	CMPQ DI, $4
-	JGE U1			// if n >= 4 goto U1
+	JGE U1			// if n >= 0 goto U1
 
-V1:	CMPQ DI, $0
+V1:	ADDQ $4, DI		// n += 4
 	JLE E1			// if n <= 0 goto E1
 
 L1:	// n > 0
+\tRCRQ $1, CX		// CF = c
 	MOVQ 0(R8)(SI*8), R11
-\tRCRQ $1, CX		// restore CF
 	ADCQ 0(R9)(SI*8), R11
-\tRCLQ $1, CX		// save CF
 	MOVQ R11, 0(R10)(SI*8)
+\tRCLQ $1, CX		// c = CF
 
 	ADDQ $1, SI		// i++
 	SUBQ $1, DI		// n--

ループ初期化と条件分岐の変更:
- 変更前: CMPQ DI, $4 と JL V1 は、DI（残りのワード数）が4未満の場合にアンロールループをスキップし、V1（残りのワードを1つずつ処理するループ）へジャンプします。
- 変更後: SUBQ $4, DI と JL V1 は、まずDIから4を減算します。もしDIが負になった場合（つまり元のDIが4未満だった場合）、V1へジャンプします。この変更により、CMPQ命令が不要になり、命令数が削減されます。また、SUBQ命令はフラグを設定するため、その後のJL命令に直接利用できます。
アンロールループ (U1) 内のキャリーフラグ処理:
- 変更前: RCRQ $1, CX がMOVQ命令の後にありました。これは、CXレジスタに保存されたキャリーフラグを復元し、その後のADCQ命令で使用できるようにします。
- 変更後: RCRQ $1, CX がMOVQ命令の前に移動しました。この変更は、CPUの命令パイプラインの効率を向上させる可能性があります。ADCQ命令はキャリーフラグを必要とするため、その前にキャリーフラグが確実に設定されていることが重要です。この再配置は、命令の依存関係を最適化し、プロセッサがより効率的に命令を実行できるようにする可能性があります。
- RCLQ $1, CX も同様に、新しいキャリーフラグをCXレジスタに保存する役割を担いますが、その位置は変わっていません。コメントがより明確に// c = CFと変更されています。
ループ終了条件の変更:
- 変更前: CMPQ DI, $4 と JGE U1 は、DIが4以上の場合にアンロールループを継続します。
- 変更後: JGE U1 のみになりました。これは、ループ開始時にDIから4を減算しているため、DIが0以上であればループを継続するという意味になります。これにより、ループの条件チェックが簡素化されます。
残りの要素を処理するループ (L1) の変更:
- V1ラベルの直後にADDQ $4, DIが追加されました。これは、アンロールループに入る前にDIから減算した4を元に戻し、残りのワード数を正しく計算するためです。
- L1ループ内でも、RCRQ $1, CXがMOVQ命令の前に移動し、RCLQ $1, CXのコメントが変更されています。これはアンロールループと同様の最適化です。

これらの変更は、命令の実行順序を微調整し、分岐予測の効率を高め、CPUのパイプラインをよりスムーズに流れるようにすることで、全体的な実行速度を向上させることを目的としています。アセンブリレベルの最適化は、このような細かな変更が積み重なることで、最終的なパフォーマンスに大きな影響を与えることがあります。

参考にした情報源リンク

x86-64 Instruction Set Reference (Intel/AMDの公式ドキュメント):
- Intel® 64 and IA-32 Architectures Software Developer’s Manuals: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
- AMD64 Architecture Programmer’s Manuals: https://developer.amd.com/resources/developer-guides-manuals/
Go言語のベンチマークに関する情報: https://go.dev/doc/articles/go_benchmarking.html
多倍長整数演算の概念に関する一般的な情報源（例: Wikipediaなど）
アセンブリ言語の最適化に関する一般的な情報源（例: コンピュータアーキテクチャの教科書など）
Goのコードレビューシステム (Gerrit) の変更リスト: https://golang.org/cl/6484056 (コミットメッセージに記載されているリンク)

comemo