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

このコミットは、Go言語の math/big パッケージにおける、多倍長整数演算のパフォーマンス改善を目的としています。特に、AMD64アーキテクチャ向けのアンロールされたアセンブリコードにおいて、キャリーフラグ (CF) の処理方法を最適化しています。具体的には、RCLQ と ANDQ 命令の組み合わせを SETCS 命令に置き換えることで、より効率的なキャリーフラグの取得を実現しています。

コミット

commit baf426f10fdcb3c11aa20d5034c05c5ba9b0c239
Author: Christopher Swenson <cswenson@google.com>
Date:   Tue Aug 28 09:29:45 2012 -0700

    math/big: Replace RCLQ + ANDQ with SETCS in unrolled arithmetic assembly.
    
    benchmark             old ns/op    new ns/op    delta
    BenchmarkAddVW_1              8            8   +0.60%
    BenchmarkAddVW_2             10            9   -8.64%
    BenchmarkAddVW_3             10           10   -4.63%
    BenchmarkAddVW_4             10           11   +3.67%
    BenchmarkAddVW_5             11           12   +5.98%
    BenchmarkAddVW_1e1           18           20   +6.38%
    BenchmarkAddVW_1e2          129          115  -10.85%
    BenchmarkAddVW_1e3         1270         1089  -14.25%
    BenchmarkAddVW_1e4        13376        12145   -9.20%
    BenchmarkAddVW_1e5       130392       125260   -3.94%
    
    benchmark              old MB/s     new MB/s  speedup
    BenchmarkAddVW_1        7709.10      7661.92    0.99x
    BenchmarkAddVW_2       12451.10     13604.00    1.09x
    BenchmarkAddVW_3       17727.81     18721.54    1.06x
    BenchmarkAddVW_4       23552.64     22708.81    0.96x
    BenchmarkAddVW_5       27411.40     25816.22    0.94x
    BenchmarkAddVW_1e1     34063.19     32023.06    0.94x
    BenchmarkAddVW_1e2     49529.97     55360.55    1.12x
    BenchmarkAddVW_1e3     50380.44     58764.18    1.17x
    BenchmarkAddVW_1e4     47843.59     52696.10    1.10x
    BenchmarkAddVW_1e5     49082.60     51093.66    1.04x
    
    R=gri, rsc, r
    CC=golang-dev
    https://golang.org/cl/6480063

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

https://github.com/golang/go/commit/baf426f10fdcb3c11aa20d5034c05c5ba9b0c239

元コミット内容

このコミットの元々の内容は、math/big パッケージのアンロールされた算術アセンブリにおいて、RCLQ と ANDQ 命令の組み合わせを SETCS 命令に置き換えるというものです。これは、キャリーフラグ (CF) の値をレジスタに格納する際の効率を改善することを目的としています。

ベンチマーク結果も示されており、特に大きなサイズのデータ (1e2 から 1e5) において、ns/op (操作あたりのナノ秒) が減少し、MB/s (メガバイト/秒) が増加していることから、パフォーマンスが向上していることがわかります。

変更の背景

多倍長整数演算では、通常のCPUレジスタに収まらない非常に大きな数値を扱います。このような演算は、複数のワード（CPUのネイティブなデータサイズ、例えば64ビット）に分割して処理されます。加算や減算のような基本的な算術演算を行う際、あるワードの演算結果が次のワードの演算に影響を与える「キャリー」（繰り上がり）や「ボロー」（借り入れ）が発生します。このキャリー/ボローは、CPUのフラグレジスタにある「キャリーフラグ (CF)」によって示されます。

従来のコードでは、このキャリーフラグの値を汎用レジスタに格納するために、RCLQ $1, CX (Rotate Carry Left Quadword) と ANDQ $1, CX (Logical AND Quadword) という2つの命令を使用していました。RCLQ $1, CX は CX レジスタの内容を1ビット左に回転させ、同時にキャリーフラグの値を CX の最下位ビットに移動させます。その後、ANDQ $1, CX で CX レジスタの他のビットをクリアし、キャリーフラグの値（0または1）のみを CX に残していました。

この2つの命令の組み合わせは、キャリーフラグの値をレジスタに取得する一般的な方法ですが、より効率的な SETCS 命令が存在します。SETCS 命令は、キャリーフラグがセットされている（1である）場合に指定されたレジスタの最下位バイトを1に、それ以外の場合に0に設定します。これにより、1つの命令でキャリーフラグの値を直接レジスタに格納できるため、命令数を減らし、実行サイクルを短縮できます。

この変更の背景には、math/big パッケージの性能を最大限に引き出すために、アセンブリレベルでの細かな最適化を追求するというGo言語開発チームの姿勢があります。特に、多倍長整数演算は暗号化、科学技術計算、金融アプリケーションなど、パフォーマンスが非常に重要となる分野で利用されるため、このような低レベルでの最適化が全体の性能に大きく寄与します。

前提知識の解説

1. Go言語の `math/big` パッケージ

math/big パッケージは、Go言語で任意精度の算術演算（多倍長整数、有理数、浮動小数点数）を可能にするための標準ライブラリです。通常のGoの数値型（int, int64, float64など）では表現できない非常に大きな数値や、高い精度が要求される計算に用いられます。このパッケージは、内部的に数値をワードの配列として表現し、その演算の多くはパフォーマンスのためにアセンブリ言語で実装されています。

2. アセンブリ言語とパフォーマンス最適化

アセンブリ言語は、CPUが直接実行できる機械語命令を人間が読める形式で記述したものです。Go言語のような高水準言語で書かれたコードは、コンパイラによってアセンブリ言語に変換され、最終的に機械語になります。 math/big パッケージのように、極めて高いパフォーマンスが要求される部分では、コンパイラによる自動生成コードよりも、プログラマが手動で最適化したアセンブリコードの方が高速になることがあります。これは、プログラマが特定のCPUアーキテクチャの特性（レジスタの使い方、命令のレイテンシ、パイプライン処理など）を最大限に活用できるためです。

3. AMD64アーキテクチャ

AMD64（またはx86-64）は、現在のパーソナルコンピュータやサーバーで広く使われている64ビットのCPUアーキテクチャです。このアーキテクチャには、汎用レジスタ（RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8～R15など）と、演算結果の状態を示すフラグレジスタ（RFLAGS）があります。

4. CPUフラグレジスタとキャリーフラグ (CF)

RFLAGS レジスタは、CPUが実行した算術演算や論理演算の結果に関する様々な状態を示すビット（フラグ）の集合です。その中でも特に重要なのが「キャリーフラグ (CF)」です。

キャリーフラグ (CF): 加算命令（ADD, ADCなど）で最上位ビットからの繰り上がりが発生した場合、または減算命令（SUB, SBBなど）で借り入れが発生した場合にセット（1）されます。多倍長整数演算では、このキャリーフラグを次のワードの演算に引き継ぐために利用します。

5. アセンブリ命令の解説

RCLQ $1, CX (Rotate Carry Left Quadword):
- RCL 命令は、指定されたレジスタ（ここでは CX）の内容を、キャリーフラグを含めて左に回転させる命令です。
- $1 は回転させるビット数を指定します。
- この命令は、CX の最上位ビットをキャリーフラグに移動させ、同時にキャリーフラグの値を CX の最下位ビットに移動させます。
- 元のキャリーフラグの値を CX レジスタの最下位ビットにコピーするために使われていました。
ANDQ $1, CX (Logical AND Quadword):
- AND 命令は、ビットごとの論理積を計算します。
- $1 と論理積を取ることで、CX レジスタの最下位ビット以外のすべてのビットを0にクリアします。
- RCLQ の後にこの命令を使うことで、CX レジスタにはキャリーフラグの値（0または1）のみが残るようにしていました。
SETCS CX (Set Byte if Carry):
- SETcc 命令群の一つで、条件コード（cc）に基づいて指定されたレジスタの最下位バイトをセット（1）またはクリア（0）します。
- CS は "Carry Set" の略で、キャリーフラグ (CF) がセットされている（1である）場合に、CX レジスタの最下位バイトを1に設定し、それ以外の場合は0に設定します。
- この命令は、キャリーフラグの値を直接レジスタに格納する、より効率的な方法です。
MOVQ $0, CX (Move Quadword Immediate to Register):
- 即値 0 を CX レジスタに移動させます。
- アセンブラによっては、MOVQ $0, reg は XORQ reg, reg に最適化されることがあります。
- XORQ reg, reg は、レジスタをゼロクリアするだけでなく、キャリーフラグ (CF) を含むいくつかのフラグをクリアする副作用があります。
XORQ reg, reg (Exclusive OR Quadword):
- 指定されたレジスタ自身との排他的論理和を取ることで、レジスタの内容をゼロクリアします。
- この命令は、キャリーフラグ (CF) を含むいくつかのフラグをクリアします。

6. アンロールされたアセンブリ (Unrolled Assembly)

ループアンローリング（Loop Unrolling）は、ループの反復回数を減らすために、ループ本体のコードを複数回コピーして展開する最適化手法です。例えば、4回繰り返すループがある場合、ループ本体を4回記述し、ループ制御のオーバーヘッド（カウンタのインクリメント、条件チェック、ジャンプなど）を削減します。

math/big パッケージでは、多倍長整数演算の際に、複数のワードを一度に処理するためにこの手法が用いられています。これにより、ループのオーバーヘッドが減少し、CPUのパイプライン効率が向上し、全体的な実行速度が向上します。このコミットで変更されているコードも、U3, U4 といったラベルが見られることから、アンロールされたループの一部であることがわかります。

技術的詳細

このコミットの核心は、AMD64アセンブリにおけるキャリーフラグ (CF) の取得方法の最適化です。

従来のコードでは、キャリーフラグの値を CX レジスタに格納するために、以下の2つの命令を使用していました。

RCLQ $1, CX: CX レジスタとキャリーフラグを結合して左に1ビット回転させます。これにより、元のキャリーフラグの値が CX の最下位ビットに移動します。
ANDQ $1, CX: CX レジスタの最下位ビット以外のすべてのビットをクリアし、CX にはキャリーフラグの値（0または1）のみが残るようにします。

この2命令の組み合わせは機能的には正しいですが、より効率的な SETCS 命令が存在します。SETCS 命令は、キャリーフラグがセットされている（1である）場合に指定されたレジスタの最下位バイトを1に、それ以外の場合に0に設定します。これにより、1つの命令で同じ目的を達成できます。

しかし、SETCS 命令は指定されたレジスタの最下位バイトのみを操作し、残りのバイトは変更しません。そのため、SETCS を使用する前に、対象のレジスタ（ここでは CX）をゼロクリアしておく必要があります。もしゼロクリアせずに SETCS を使用すると、CX レジスタの他のバイトにゴミデータが残ってしまい、予期せぬ結果を招く可能性があります。

このコミットでは、このゼロクリアのために新しいマクロ ZERO_CX を導入しています。

#define ZERO_CX BYTE $0x48; \
		BYTE $0xc7; \
		BYTE $0xc1; \
		BYTE $0x00; \
		BYTE $0x00; \
		BYTE $0x00; \
		BYTE $0x00

このマクロは、MOVQ $0, CX 命令の機械語バイト列を直接記述したものです。Goのアセンブラ（Plan 9アセンブラ）では、MOVQ $0, reg は通常 XORQ reg, reg に最適化されます。XORQ reg, reg はレジスタをゼロクリアするだけでなく、キャリーフラグ (CF) を含むいくつかのフラグをクリアする副作用があります。

したがって、変更後のシーケンスは以下のようになります。

ZERO_CX (実質 XORQ CX, CX): CX レジスタをゼロクリアし、同時にキャリーフラグをクリアします。
SETCS CX: 直前の算術演算（ADCQ や SBBQ）によって設定されたキャリーフラグの値に基づいて、CX の最下位バイトを0または1に設定します。

この変更により、キャリーフラグの取得に必要な命令数が削減され、特に多倍長整数演算のループ内で頻繁に実行されるため、全体的なパフォーマンス向上に寄与します。ベンチマーク結果が示すように、特に大きな数値（1e2 から 1e5）の加算において顕著な改善が見られます。これは、アンロールされたループがより効率的に実行されるようになったためと考えられます。

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

変更は src/pkg/math/big/arith_amd64.s ファイルに集中しています。

1. `ZERO_CX` マクロの追加

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -5,6 +5,16 @@
 // This file provides fast assembly versions for the elementary
 // arithmetic operations on vectors implemented in arith.go.
 
+// Literal instruction for MOVQ $0, CX.
+// (MOVQ $0, reg is translated to XORQ reg, reg and clears CF.)
+#define ZERO_CX BYTE $0x48; \
+\t\tBYTE $0xc7; \
+\t\tBYTE $0xc1; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00
+
 // func mulWW(x, y Word) (z1, z0 Word)
 TEXT ·mulWW(SB),7,$0
 	MOVQ x+0(FP), AX

2. `addVW` 関数内の変更

addVW 関数は、多倍長整数の加算を行うアセンブリルーチンです。アンロールされたループ (U3:) と、アンロールされていないループ (L3:) の両方で変更が行われています。

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -151,15 +161,15 @@ U3:\t// n >= 0
 	MOVQ 16(R8)(SI*8), R13
 	MOVQ 24(R8)(SI*8), R14
 	ADDQ CX, R11
+\tZERO_CX
 	ADCQ $0, R12
 	ADCQ $0, R13
 	ADCQ $0, R14
+\tSETCS CX\t\t// c = 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\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $4, SI\t\t// i += 4
 	SUBQ $4, DI\t\t// n -= 4
@@ -171,8 +181,8 @@ V3:\tADDQ $4, DI\t\t// n += 4
 L3:\t// n > 0
 	ADDQ 0(R8)(SI*8), CX
 	MOVQ CX, 0(R10)(SI*8)
+\tZERO_CX
 \tRCLQ $1, CX\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $1, SI\t\t// i++
 	SUBQ $1, DI\t\t// n--

3. `subVW` 関数内の変更

subVW 関数は、多倍長整数の減算を行うアセンブリルーチンです。こちらもアンロールされたループ (U4:) と、アンロールされていないループ (L4:) の両方で変更が行われています。

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -203,15 +213,15 @@ U4:\t// n >= 0
 	MOVQ 16(R8)(SI*8), R13
 	MOVQ 24(R8)(SI*8), R14
 	SUBQ CX, R11
+\tZERO_CX
 	SBBQ $0, R12
 	SBBQ $0, R13
 	SBBQ $0, R14
+\tSETCS CX\t\t// c = 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\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $4, SI\t\t// i += 4
 	SUBQ $4, DI\t\t// n -= 4
@@ -224,8 +234,8 @@ L4:\t// n > 0
 	MOVQ 0(R8)(SI*8), R11
 	SUBQ CX, R11
 	MOVQ R11, 0(R10)(SI*8)
+\tZERO_CX
 \tRCLQ $1, CX\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $1, SI\t\t// i++
 	SUBQ $1, DI\t\t// n--

コアとなるコードの解説

変更の主要な部分は、addVW および subVW 関数内のキャリーフラグ (CF) の処理ロジックです。

変更前:

; ... 算術演算 (ADDQ/ADCQ または SUBQ/SBBQ) ...
RCLQ $1, CX        // c = CF
ANDQ $1, CX

このシーケンスでは、算術演算によって設定されたキャリーフラグ (CF) の値を CX レジスタに格納していました。RCLQ はCFを CX の最下位ビットに移動させ、ANDQ はそれ以外のビットをクリアしていました。

変更後:

; ... 算術演算 (ADDQ/ADCQ または SUBQ/SBBQ) ...
ZERO_CX            ; CXをゼロクリア (実質 XORQ CX, CX)
SETCS CX           // c = CF

ZERO_CX: これは新しく定義されたマクロで、MOVQ $0, CX の機械語バイト列に展開されます。Goのアセンブラでは、MOVQ $0, reg は XORQ reg, reg に最適化されることが多く、この命令は CX レジスタをゼロクリアします。重要なのは、XORQ reg, reg が実行されると、キャリーフラグ (CF) もクリアされるという副作用がある点です。
SETCS CX: この命令は、直前の算術演算（ADCQ や SBBQ）によって設定されたキャリーフラグ (CF) の状態に基づいて、CX レジスタの最下位バイトを0または1に設定します。ZERO_CX によって CX が事前にゼロクリアされているため、SETCS は CX レジスタ全体に正確なキャリーフラグの値（0または1）を格納できます。

この変更により、キャリーフラグの値をレジスタに取得するために必要な命令が2つから1つ（SETCS）に削減されました。ただし、SETCS の前にレジスタをゼロクリアする必要があるため、実質的には ZERO_CX と SETCS の2命令の組み合わせとなります。しかし、ZERO_CX は XORQ CX, CX に最適化されることが多く、これは非常に高速な命令です。全体として、RCLQ + ANDQ の組み合わせよりも ZERO_CX + SETCS の組み合わせの方が効率的であると判断されたため、この変更が適用されました。

ベンチマーク結果は、特に大きな数値の演算において、この最適化が実際にパフォーマンス向上に寄与していることを裏付けています。これは、多倍長整数演算のループ内でキャリーフラグの処理が頻繁に行われるため、その部分のわずかな改善が全体に大きな影響を与えることを示しています。

参考にした情報源リンク

Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/
Stack Overflow や技術ブログなど、アセンブリ命令に関する一般的な情報源。
Go言語のソースコード (src/pkg/math/big/arith_amd64.s)
Go言語のベンチマーク結果の解釈に関する情報。
RCL, AND, SETcc, XOR などのx86-64アセンブリ命令に関する資料。
多倍長整数演算のアルゴリズムに関する一般的な情報。I have provided the detailed explanation as requested, following all the specified sections and including the necessary technical details and links.

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

このコミットは、Go言語の `math/big` パッケージにおける、多倍長整数演算のパフォーマンス改善を目的としています。特に、AMD64アーキテクチャ向けのアンロールされたアセンブリコードにおいて、キャリーフラグ (CF) の処理方法を最適化しています。具体的には、`RCLQ` と `ANDQ` 命令の組み合わせを `SETCS` 命令に置き換えることで、より効率的なキャリーフラグの取得を実現しています。

## コミット

commit baf426f10fdcb3c11aa20d5034c05c5ba9b0c239 Author: Christopher Swenson cswenson@google.com Date: Tue Aug 28 09:29:45 2012 -0700

math/big: Replace RCLQ + ANDQ with SETCS in unrolled arithmetic assembly.

benchmark             old ns/op    new ns/op    delta
BenchmarkAddVW_1              8            8   +0.60%
BenchmarkAddVW_2             10            9   -8.64%
BenchmarkAddVW_3             10           10   -4.63%
BenchmarkAddVW_4             10           11   +3.67%
BenchmarkAddVW_5             11           12   +5.98%
BenchmarkAddVW_1e1           18           20   +6.38%
BenchmarkAddVW_1e2          129          115  -10.85%
BenchmarkAddVW_1e3         1270         1089  -14.25%
BenchmarkAddVW_1e4        13376        12145   -9.20%
BenchmarkAddVW_1e5       130392       125260   -3.94%

benchmark              old MB/s     new MB/s  speedup
BenchmarkAddVW_1        7709.10      7661.92    0.99x
BenchmarkAddVW_2       12451.10     13604.00    1.09x
BenchmarkAddVW_3       17727.81     18721.54    1.06x
BenchmarkAddVW_4       23552.64     22708.81    0.96x
BenchmarkAddVW_5       27411.40     25816.22    0.94x
BenchmarkAddVW_1e1     34063.19     32023.06    0.94x
BenchmarkAddVW_1e2     49529.97     55360.55    1.12x
BenchmarkAddVW_1e3     50380.44     58764.18    1.17x
BenchmarkAddVW_1e4     47843.59     52696.10    1.10x
BenchmarkAddVW_1e5     49082.60     51093.66    1.04x

R=gri, rsc, r
CC=golang-dev
https://golang.org/cl/6480063


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

[https://github.com/golang/go/commit/baf426f10fdcb3c11aa20d5034c05c5ba9b0c239](https://github.com/golang/go/commit/baf426f10fdcb3c11aa20d5034c05c5ba9b0c239)

## 元コミット内容

このコミットの元々の内容は、`math/big` パッケージのアンロールされた算術アセンブリにおいて、`RCLQ` と `ANDQ` 命令の組み合わせを `SETCS` 命令に置き換えるというものです。これは、キャリーフラグ (CF) の値をレジスタに格納する際の効率を改善することを目的としています。

ベンチマーク結果も示されており、特に大きなサイズのデータ (`1e2` から `1e5`) において、`ns/op` (操作あたりのナノ秒) が減少し、`MB/s` (メガバイト/秒) が増加していることから、パフォーマンスが向上していることがわかります。

## 変更の背景

多倍長整数演算では、通常のCPUレジスタに収まらない非常に大きな数値を扱います。このような演算は、複数のワード（CPUのネイティブなデータサイズ、例えば64ビット）に分割して処理されます。加算や減算のような基本的な算術演算を行う際、あるワードの演算結果が次のワードの演算に影響を与える「キャリー」（繰り上がり）や「ボロー」（借り入れ）が発生します。このキャリー/ボローは、CPUのフラグレジスタにある「キャリーフラグ (CF)」によって示されます。

従来のコードでは、このキャリーフラグの値を汎用レジスタに格納するために、`RCLQ $1, CX` (Rotate Carry Left Quadword) と `ANDQ $1, CX` (Logical AND Quadword) という2つの命令を使用していました。`RCLQ $1, CX` は `CX` レジスタの内容を1ビット左に回転させ、同時にキャリーフラグの値を `CX` の最下位ビットに移動させます。その後、`ANDQ $1, CX` で `CX` レジスタの他のビットをクリアし、キャリーフラグの値（0または1）のみを `CX` に残していました。

この2つの命令の組み合わせは、キャリーフラグの値をレジスタに取得する一般的な方法ですが、より効率的な `SETCS` 命令が存在します。`SETCS` 命令は、キャリーフラグがセットされている（1である）場合に指定されたレジスタの最下位バイトを1に、それ以外の場合に0に設定します。これにより、1つの命令でキャリーフラグの値を直接レジスタに格納できるため、命令数を減らし、実行サイクルを短縮できます。

この変更の背景には、`math/big` パッケージの性能を最大限に引き出すために、アセンブリレベルでの細かな最適化を追求するというGo言語開発チームの姿勢があります。特に、多倍長整数演算は暗号化、科学技術計算、金融アプリケーションなど、パフォーマンスが非常に重要となる分野で利用されるため、このような低レベルでの最適化が全体の性能に大きく寄与します。

## 前提知識の解説

### 1. Go言語の `math/big` パッケージ

`math/big` パッケージは、Go言語で任意精度の算術演算（多倍長整数、有理数、浮動小数点数）を可能にするための標準ライブラリです。通常のGoの数値型（`int`, `int64`, `float64`など）では表現できない非常に大きな数値や、高い精度が要求される計算に用いられます。このパッケージは、内部的に数値をワードの配列として表現し、その演算の多くはパフォーマンスのためにアセンブリ言語で実装されています。

### 2. アセンブリ言語とパフォーマンス最適化

アセンブリ言語は、CPUが直接実行できる機械語命令を人間が読める形式で記述したものです。Go言語のような高水準言語で書かれたコードは、コンパイラによってアセンブリ言語に変換され、最終的に機械語になります。
`math/big` パッケージのように、極めて高いパフォーマンスが要求される部分では、コンパイラによる自動生成コードよりも、プログラマが手動で最適化したアセンブリコードの方が高速になることがあります。これは、プログラマが特定のCPUアーキテクチャの特性（レジスタの使い方、命令のレイテンシ、パイプライン処理など）を最大限に活用できるためです。

### 3. AMD64アーキテクチャ

AMD64（またはx86-64）は、現在のパーソナルコンピュータやサーバーで広く使われている64ビットのCPUアーキテクチャです。このアーキテクチャには、汎用レジスタ（`RAX`, `RBX`, `RCX`, `RDX`, `RSI`, `RDI`, `RBP`, `RSP`, `R8`～`R15`など）と、演算結果の状態を示すフラグレジスタ（`RFLAGS`）があります。

### 4. CPUフラグレジスタとキャリーフラグ (CF)

`RFLAGS` レジスタは、CPUが実行した算術演算や論理演算の結果に関する様々な状態を示すビット（フラグ）の集合です。その中でも特に重要なのが「キャリーフラグ (CF)」です。

*   **キャリーフラグ (CF)**: 加算命令（`ADD`, `ADC`など）で最上位ビットからの繰り上がりが発生した場合、または減算命令（`SUB`, `SBB`など）で借り入れが発生した場合にセット（1）されます。多倍長整数演算では、このキャリーフラグを次のワードの演算に引き継ぐために利用します。

### 5. アセンブリ命令の解説

*   **`RCLQ $1, CX` (Rotate Carry Left Quadword)**:
    *   `RCL` 命令は、指定されたレジスタ（ここでは `CX`）の内容を、キャリーフラグを含めて左に回転させる命令です。
    *   `$1` は回転させるビット数を指定します。
    *   この命令は、`CX` の最上位ビットをキャリーフラグに移動させ、同時にキャリーフラグの値を `CX` の最下位ビットに移動させます。
    *   元のキャリーフラグの値を `CX` レジスタの最下位ビットにコピーするために使われていました。

*   **`ANDQ $1, CX` (Logical AND Quadword)**:
    *   `AND` 命令は、ビットごとの論理積を計算します。
    *   `$1` と論理積を取ることで、`CX` レジスタの最下位ビット以外のすべてのビットを0にクリアします。
    *   `RCLQ` の後にこの命令を使うことで、`CX` レジスタにはキャリーフラグの値（0または1）のみが残るようにしていました。

*   **`SETCS CX` (Set Byte if Carry)**:
    *   `SETcc` 命令群の一つで、条件コード（`cc`）に基づいて指定されたレジスタの最下位バイトをセット（1）またはクリア（0）します。
    *   `CS` は "Carry Set" の略で、キャリーフラグ (CF) がセットされている（1である）場合に、`CX` レジスタの最下位バイトを1に設定し、それ以外の場合は0に設定します。
    *   この命令は、キャリーフラグの値を直接レジスタに格納する、より効率的な方法です。

*   **`MOVQ $0, CX` (Move Quadword Immediate to Register)**:
    *   即値 `0` を `CX` レジスタに移動させます。
    *   アセンブラによっては、`MOVQ $0, reg` は `XORQ reg, reg` に最適化されることがあります。
    *   `XORQ reg, reg` は、レジスタをゼロクリアするだけでなく、キャリーフラグ (CF) を含むいくつかのフラグをクリアする副作用があります。

*   **`XORQ reg, reg` (Exclusive OR Quadword)**:
    *   指定されたレジスタ自身との排他的論理和を取ることで、レジスタの内容をゼロクリアします。
    *   この命令は、キャリーフラグ (CF) を含むいくつかのフラグをクリアします。

### 6. アンロールされたアセンブリ (Unrolled Assembly)

ループアンローリング（Loop Unrolling）は、ループの反復回数を減らすために、ループ本体のコードを複数回コピーして展開する最適化手法です。例えば、4回繰り返すループがある場合、ループ本体を4回記述し、ループ制御のオーバーヘッド（カウンタのインクリメント、条件チェック、ジャンプなど）を削減します。

`math/big` パッケージでは、多倍長整数演算の際に、複数のワードを一度に処理するためにこの手法が用いられています。これにより、ループのオーバーヘッドが減少し、CPUのパイプライン効率が向上し、全体的な実行速度が向上します。このコミットで変更されているコードも、`U3`, `U4` といったラベルが見られることから、アンロールされたループの一部であることがわかります。

## 技術的詳細

このコミットの核心は、AMD64アセンブリにおけるキャリーフラグ (CF) の取得方法の最適化です。

従来のコードでは、キャリーフラグの値を `CX` レジスタに格納するために、以下の2つの命令を使用していました。

1.  `RCLQ $1, CX`: `CX` レジスタとキャリーフラグを結合して左に1ビット回転させます。これにより、元のキャリーフラグの値が `CX` の最下位ビットに移動します。
2.  `ANDQ $1, CX`: `CX` レジスタの最下位ビット以外のすべてのビットをクリアし、`CX` にはキャリーフラグの値（0または1）のみが残るようにします。

この2命令の組み合わせは機能的には正しいですが、より効率的な `SETCS` 命令が存在します。`SETCS` 命令は、キャリーフラグがセットされている（1である）場合に指定されたレジスタの最下位バイトを1に、それ以外の場合に0に設定します。これにより、1つの命令で同じ目的を達成できます。

しかし、`SETCS` 命令は指定されたレジスタの最下位バイトのみを操作し、残りのバイトは変更しません。そのため、`SETCS` を使用する前に、対象のレジスタ（ここでは `CX`）をゼロクリアしておく必要があります。もしゼロクリアせずに `SETCS` を使用すると、予期せぬ結果を招く可能性があります。

このコミットでは、このゼロクリアのために新しいマクロ `ZERO_CX` を導入しています。

```assembly
#define ZERO_CX BYTE $0x48; \
		BYTE $0xc7; \
		BYTE $0xc1; \
		BYTE $0x00; \
		BYTE $0x00; \
		BYTE $0x00; \
		BYTE $0x00

したがって、変更後のシーケンスは以下のようになります。

ZERO_CX (実質 XORQ CX, CX): CX レジスタをゼロクリアし、同時にキャリーフラグをクリアします。
SETCS CX: 直前の算術演算（ADCQ や SBBQ）によって設定されたキャリーフラグの値に基づいて、CX の最下位バイトを0または1に設定します。

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

変更は src/pkg/math/big/arith_amd64.s ファイルに集中しています。

1. `ZERO_CX` マクロの追加

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -5,6 +5,16 @@
 // This file provides fast assembly versions for the elementary
 // arithmetic operations on vectors implemented in arith.go.
 
+// Literal instruction for MOVQ $0, CX.
+// (MOVQ $0, reg is translated to XORQ reg, reg and clears CF.)
+#define ZERO_CX BYTE $0x48; \
+\t\tBYTE $0xc7; \
+\t\tBYTE $0xc1; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00; \
+\t\tBYTE $0x00
+
 // func mulWW(x, y Word) (z1, z0 Word)
 TEXT ·mulWW(SB),7,$0
 	MOVQ x+0(FP), AX

2. `addVW` 関数内の変更

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -151,15 +161,15 @@ U3:\t// n >= 0
 	MOVQ 16(R8)(SI*8), R13
 	MOVQ 24(R8)(SI*8), R14
 	ADDQ CX, R11
+\tZERO_CX
 	ADCQ $0, R12
 	ADCQ $0, R13
 	ADCQ $0, R14
+\tSETCS CX\t\t// c = 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\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $4, SI\t\t// i += 4
 	SUBQ $4, DI\t\t// n -= 4
@@ -171,8 +181,8 @@ V3:\tADDQ $4, DI\t\t// n += 4
 L3:\t// n > 0
 	ADDQ 0(R8)(SI*8), CX
 	MOVQ CX, 0(R10)(SI*8)
+\tZERO_CX
 \tRCLQ $1, CX\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $1, SI\t\t// i++
 	SUBQ $1, DI\t\t// n--

3. `subVW` 関数内の変更

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -203,15 +213,15 @@ U4:\t// n >= 0
 	MOVQ 16(R8)(SI*8), R13
 	MOVQ 24(R8)(SI*8), R14
 	SUBQ CX, R11
+\tZERO_CX
 	SBBQ $0, R12
 	SBBQ $0, R13
 	SBBQ $0, R14
+\tSETCS CX\t\t// c = 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\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $4, SI\t\t// i += 4
 	SUBQ $4, DI\t\t// n -= 4
@@ -224,8 +234,8 @@ L4:\t// n > 0
 	MOVQ 0(R8)(SI*8), R11
 	SUBQ CX, R11
 	MOVQ R11, 0(R10)(SI*8)
+\tZERO_CX
 \tRCLQ $1, CX\t\t// c = CF
-\tANDQ $1, CX
 
 	ADDQ $1, SI\t\t// i++
 	SUBQ $1, DI\t\t// n--

コアとなるコードの解説

変更の主要な部分は、addVW および subVW 関数内のキャリーフラグ (CF) の処理ロジックです。

変更前:

; ... 算術演算 (ADDQ/ADCQ または SUBQ/SBBQ) ...
RCLQ $1, CX        // c = CF
ANDQ $1, CX

変更後:

; ... 算術演算 (ADDQ/ADCQ または SUBQ/SBBQ) ...
ZERO_CX            ; CXをゼロクリア (実質 XORQ CX, CX)
SETCS CX           // c = CF

ZERO_CX: これは新しく定義されたマクロで、MOVQ $0, CX の機械語バイト列に展開されます。Goのアセンブラでは、MOVQ $0, reg は XORQ reg, reg に最適化されることが多く、この命令は CX レジスタをゼロクリアします。重要なのは、XORQ reg, reg が実行されると、キャリーフラグ (CF) もクリアされるという副作用がある点です。
SETCS CX: この命令は、直前の算術演算（ADCQ や SBBQ）によって設定されたキャリーフラグ (CF) の状態に基づいて、CX レジスタの最下位バイトを0または1に設定します。ZERO_CX によって CX が事前にゼロクリアされているため、SETCS は CX レジスタ全体に正確なキャリーフラグの値（0または1）を格納できます。

参考にした情報源リンク

Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/
Stack Overflow や技術ブログなど、アセンブリ命令に関する一般的な情報源。
Go言語のソースコード (src/pkg/math/big/arith_amd64.s)
Go言語のベンチマーク結果の解釈に関する情報。
RCL, AND, SETcc, XOR などのx86-64アセンブリ命令に関する資料。
多倍長整数演算のアルゴリズムに関する一般的な情報。

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. Go言語の `math/big` パッケージ

2. アセンブリ言語とパフォーマンス最適化

3. AMD64アーキテクチャ

4. CPUフラグレジスタとキャリーフラグ (CF)

5. アセンブリ命令の解説

6. アンロールされたアセンブリ (Unrolled Assembly)

技術的詳細

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

1. `ZERO_CX` マクロの追加

2. `addVW` 関数内の変更

3. `subVW` 関数内の変更

コアとなるコードの解説

関連リンク

参考にした情報源リンク

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

1. `ZERO_CX` マクロの追加

2. `addVW` 関数内の変更

3. `subVW` 関数内の変更

コアとなるコードの解説

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo