[インデックス 18508] ファイルの概要
このコミットは、Go言語のmath/bigパッケージにおけるARMアセンブリコードのパフォーマンス最適化に焦点を当てています。具体的には、多倍長整数演算の基盤となるアセンブリルーチンが対象です。
コミット
commit eae09a59a044670d48bab9209e6afb8c9da4b973
Author: Nick Craig-Wood <nick@craig-wood.com>
Date: Thu Feb 13 16:19:38 2014 -0800
math/big: Optimise ARM assembler
Tweak the ARM assembler to improve its performance.
* Use TEQ instead of CMP which preserves the carry flag. This means
we can avoid saving and restoring CPSR which is very slow.
* Use conditional instructions to read the value of the carry flag.
* Use 3 argument ARM instructions to save instructions
* Improve scheduling for MOVW instructions (LDR)
* Use RSB constant to save an instruction in bitLen
Results of -test.bench 'VV|VW|VU|WW|Bit' -test.benchtime 3s on Samsung
Exynos5 Chromebook.
There are a few small regressions in the benchmarks which I believe to
be noise, perhaps due to different cacheline alignment.
The changes to bitLen are apparently no faster, however less
instructions means less I-cache usage which is a win. I suspect it
will be a win on older ARM processors.
benchmark old ns/op new ns/op delta
BenchmarkAddVV_1 48 14 -70.84%
BenchmarkAddVV_2 87 17 -80.25%
BenchmarkAddVV_3 126 20 -83.97%
BenchmarkAddVV_4 165 23 -86.00%
BenchmarkAddVV_5 204 26 -87.21%
BenchmarkAddVV_1e1 399 41 -89.72%
BenchmarkAddVV_1e2 3921 315 -91.97%
BenchmarkAddVV_1e3 39085 2972 -92.40%
BenchmarkAddVV_1e4 390330 29623 -92.41%
BenchmarkAddVV_1e5 3935366 343431 -91.27%
BenchmarkAddVW_1 20 10 -49.04%
BenchmarkAddVW_2 60 14 -76.53%
BenchmarkAddVW_3 99 16 -83.38%
BenchmarkAddVW_4 140 18 -86.50%
BenchmarkAddVW_5 179 21 -88.04%
BenchmarkAddVW_1e1 376 33 -91.20%
BenchmarkAddVW_1e2 3933 256 -93.49%
BenchmarkAddVW_1e3 39630 2378 -94.00%
BenchmarkAddVW_1e4 396218 23623 -94.04%
BenchmarkAddVW_1e5 3972901 238403 -94.00%
BenchmarkAddMulVVW_1 11 11 -4.27%
BenchmarkAddMulVVW_2 15 15 +0.00%
BenchmarkAddMulVVW_3 18 19 +4.37%
BenchmarkAddMulVVW_4 21 21 +4.29%
BenchmarkAddMulVVW_5 24 24 -0.82%
BenchmarkAddMulVVW_1e1 40 39 -2.70%
BenchmarkAddMulVVW_1e2 329 326 -0.91%
BenchmarkAddMulVVW_1e3 3200 3098 -3.19%
BenchmarkAddMulVVW_1e4 38457 40013 +4.05%
BenchmarkAddMulVVW_1e5 461880 428580 -7.21%
BenchmarkBitLen0 5 5 -0.19%
BenchmarkBitLen1 5 5 +0.00%
BenchmarkBitLen2 5 5 -0.56%
BenchmarkBitLen3 5 5 +0.38%
BenchmarkBitLen4 5 5 +0.19%
BenchmarkBitLen5 5 5 +0.56%
BenchmarkBitLen8 5 5 -0.19%
BenchmarkBitLen9 5 5 -0.56%
BenchmarkBitLen16 5 5 -0.19%
BenchmarkBitLen17 5 5 -0.37%
BenchmarkBitLen31 5 5 -1.30%
BenchmarkBitset 72 70 -2.49%
BenchmarkBitsetNeg 1584 396 -75.00%
BenchmarkBitsetOrig 1990 1980 -0.50%
BenchmarkBitsetNegOrig 4031 2877 -28.63%
benchmark old MB/s new MB/s speedup
BenchmarkAddVV_1 657.71 2251.28 3.42x
BenchmarkAddVV_2 730.65 3700.37 5.06x
BenchmarkAddVV_3 757.29 4754.30 6.28x
BenchmarkAddVV_4 772.95 5541.58 7.17x
BenchmarkAddVV_5 781.30 6125.59 7.84x
BenchmarkAddVV_1e1 800.33 7814.14 9.76x
BenchmarkAddVV_1e2 815.98 10129.62 12.41x
BenchmarkAddVV_1e3 818.73 10767.07 13.15x
BenchmarkAddVV_1e4 819.82 10802.12 13.18x
BenchmarkAddVV_1e5 813.14 9317.73 11.46x
BenchmarkAddVW_1 1539.56 3006.13 1.95x
BenchmarkAddVW_2 1057.66 4502.20 4.26x
BenchmarkAddVW_3 960.67 5797.65 6.04x
BenchmarkAddVW_4 913.19 6776.86 7.42x
BenchmarkAddVW_5 891.72 7467.82 8.37x
BenchmarkAddVW_1e1 850.12 9681.85 11.39x
BenchmarkAddVW_1e2 813.48 12494.27 15.36x
BenchmarkAddVW_1e3 807.45 13451.80 16.66x
BenchmarkAddVW_1e4 807.64 13545.64 16.77x
BenchmarkAddVW_1e5 805.46 13422.64 16.66x
BenchmarkAddMulVVW_1 2727.29 2847.66 1.04x
BenchmarkAddMulVVW_2 4162.30 4158.69 1.00x
BenchmarkAddMulVVW_3 5236.91 5015.98 0.96x
BenchmarkAddMulVVW_4 6090.27 5837.52 0.96x
BenchmarkAddMulVVW_5 6549.86 6598.60 1.01x
BenchmarkAddMulVVW_1e1 7850.72 8068.00 1.03x
BenchmarkAddMulVVW_1e2 9724.38 9794.40 1.01x
BenchmarkAddMulVVW_1e3 9997.18 10328.58 1.03x
BenchmarkAddMulVVW_1e4 8320.88 7997.39 0.96x
BenchmarkAddMulVVW_1e5 6928.20 7466.50 1.08x
LGTM=gri
R=golang-codereviews, dave, gri
CC=golang-codereviews
https://golang.org/cl/61290043
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/eae09a59a044670d48bab9209e6afb8c9da4b973
元コミット内容
このコミットは、Go言語のmath/bigパッケージ内のARMアセンブリコードを最適化することを目的としています。主な変更点は以下の通りです。
CMP命令からTEQ命令への置き換え:CMPは比較結果に基づいてフラグを設定しますが、キャリーフラグ（CPSRレジスタの一部）も変更します。一方、TEQはビット単位のXOR演算を行い、結果に基づいてフラグを設定しますが、キャリーフラグは変更しません。これにより、キャリーフラグの保存と復元という非常に遅い操作を回避できます。- 条件付き命令の使用: キャリーフラグの値を読み取るために、
MOVW.CS（Carry Setの場合に移動）やMOVW.CC（Carry Clearの場合に移動）のような条件付き命令を使用します。これにより、CPSRレジスタを直接操作することなく、効率的にキャリーフラグの状態をレジスタに反映できます。 - 3引数ARM命令の使用: 命令数を削減するために、3つのオペランドを取るARM命令（例:
ADD R4<<2, R1, R4）を使用します。これにより、中間結果を一時レジスタに格納する必要がなくなり、コードがよりコンパクトになります。 MOVW命令（LDR）のスケジューリング改善: メモリロード命令（LDR、GoアセンブリではMOVWとして表現されることが多い）の実行順序を最適化し、パイプラインのストールを減らし、全体的なスループットを向上させます。bitLen関数でのRSB定数の使用:bitLen関数において、32 - R0のような逆引き算を行う際に、SUB命令の代わりにRSB（Reverse Subtract）命令を使用します。RSBはoperand2 - operand1を計算するため、RSB $32, R0は32 - R0を1命令で実行でき、命令数を削減します。
これらの変更は、Samsung Exynos5 Chromebook上でのベンチマークで大幅なパフォーマンス向上を示しています。特にBenchmarkAddVVとBenchmarkAddVWでは、最大で90%以上の高速化が達成されています。bitLenの変更はベンチマーク上では速度向上に寄与していませんが、命令数の削減によりI-キャッシュの使用量が減少し、古いARMプロセッサでの性能向上が期待されます。
変更の背景
Go言語のmath/bigパッケージは、任意精度の算術演算を提供します。これは、標準の整数型では表現できない非常に大きな数や非常に小さな数を扱う際に不可欠です。このような演算は、暗号化、科学計算、金融アプリケーションなど、多岐にわたる分野で利用されます。
math/bigパッケージのパフォーマンスは、これらのアプリケーションの全体的な実行速度に直接影響します。特に、ARMアーキテクチャのような組み込みシステムやモバイルデバイスでは、リソースが限られているため、アセンブリレベルでの最適化が非常に重要になります。
このコミットの背景には、math/bigパッケージのARMアセンブリ実装において、より効率的な命令シーケンスとレジスタ利用パターンを見つけることで、演算速度をさらに向上させるという明確な目標がありました。特に、キャリーフラグの扱い、命令の引数形式、そして基本的なビット操作関数の最適化は、多倍長演算のループ処理において累積的な性能向上をもたらします。
前提知識の解説
ARMアーキテクチャとアセンブリ言語
ARM（Advanced RISC Machine）は、モバイルデバイス、組み込みシステム、サーバーなど、幅広い分野で使用されているRISC（Reduced Instruction Set Computer）プロセッサアーキテクチャです。Go言語は、パフォーマンスが重要な部分でアセンブリ言語を使用することがあり、特にmath/bigパッケージのような数値計算ライブラリでは、特定のアーキテクチャの特性を最大限に活用するためにアセンブリが用いられます。
ARMアセンブリ言語では、レジスタ、メモリ操作、条件コード、および命令セットの理解が不可欠です。
- レジスタ: ARMプロセッサには、汎用レジスタ（R0-R12）、スタックポインタ（SP/R13）、リンクレジスタ（LR/R14）、プログラムカウンタ（PC/R15）などがあります。
- CPSR (Current Program Status Register): プロセッサの現在の状態を示すレジスタです。これには、演算結果の条件コード（N: 負、Z: ゼロ、C: キャリー、V: オーバーフロー）が含まれます。これらのフラグは、条件付き実行や分岐命令で使用されます。
- 条件コード: 多くのARM命令は、命令の末尾に条件コード（例:
EQ(Equal),NE(Not Equal),CS(Carry Set),CC(Carry Clear)など）を付加することで、CPSRのフラグの状態に基づいて条件付きで実行できます。
math/bigパッケージ
Go言語のmath/bigパッケージは、任意精度の整数（Int）、有理数（Rat）、浮動小数点数（Float）を扱うための型と関数を提供します。これらの型は、Goの組み込み整数型（int, int64など）が表現できる範囲を超える数値を扱う必要がある場合に利用されます。
math/bigパッケージの内部では、これらの数値はWord型のスライス（配列）として表現されます。Wordは通常、システムのワードサイズ（32ビットまたは64ビット）に対応する符号なし整数型です。多倍長演算は、これらのWordの配列に対して、キャリー（繰り上がり）やボロー（借り入れ）を適切に処理しながら、基本的な算術演算（加算、減算、乗算など）を実装することで実現されます。
ARMアセンブリ命令の詳細
CMP(Compare): 2つのオペランドを比較し、その結果に基づいてCPSRの条件フラグ（N, Z, C, V）を設定します。内部的には、第1オペランドから第2オペランドを減算し、その結果を破棄しますが、フラグは更新します。この減算操作により、キャリーフラグも更新されます。TEQ(Test Equivalence): 2つのオペランドに対してビット単位のXOR演算を実行し、その結果に基づいてCPSRのZ（ゼロ）フラグとN（負）フラグを設定します。CMPとは異なり、キャリーフラグ（C）とオーバーフローフラグ（V）は変更しません。これが、このコミットでCMPの代わりにTEQが選択された主要な理由です。ループ内でキャリーフラグの状態を維持しながらループ条件をチェックできるため、CPSRの保存と復元のオーバーヘッドを回避できます。ADC(Add with Carry): 2つのオペランドとキャリーフラグの値を加算し、結果と新しいキャリーフラグを設定します。多倍長加算の各ワードの加算に使用されます。SBC(Subtract with Carry/Borrow): 2つのオペランドからキャリーフラグの値を考慮して減算し、結果と新しいキャリーフラグ（ボローフラグ）を設定します。多倍長減算の各ワードの減算に使用されます。MOVW.P(Move Word with Post-indexed addressing): Goのアセンブリ構文では、MOVW.P 4(R2), R5のように記述され、これはARMのLDR R5, [R2], #4に相当します。R2が指すアドレスからワードをR5にロードし、その後R2を4バイト（ワードサイズ）インクリメントします。これは配列の要素を順次処理するループで非常に効率的です。MOVW.CS(Move Word if Carry Set): 条件付き実行命令の一種です。CPSRのキャリーフラグがセットされている（C=1）場合にのみ、指定された値をレジスタに移動します。MOVW.CC(Move Word if Carry Clear): 同様に、CPSRのキャリーフラグがクリアされている（C=0）場合にのみ、指定された値をレジスタに移動します。CLZ(Count Leading Zeros): オペランドの最上位ビットから連続するゼロの数をカウントし、結果をレジスタに格納します。bitLen（ビット長）の計算に利用されます。例えば、32ビットワードでCLZがNを返した場合、そのワードのビット長は32 - Nとなります。RSB(Reverse Subtract):operand2 - operand1を計算します。通常のSUBがoperand1 - operand2であるのに対し、オペランドの順序が逆になります。これにより、32 - R0のような計算を1命令で効率的に行えます。
技術的詳細
このコミットの技術的詳細は、ARMプロセッサのパイプライン処理とCPSRレジスタの効率的な利用に深く関連しています。
1. TEQによるキャリーフラグの保存
多倍長演算では、各ワードの加算や減算の結果として発生するキャリー（繰り上がり）やボロー（借り入れ）を次のワードの演算に引き継ぐ必要があります。ARMプロセッサでは、このキャリー情報はCPSRレジスタのCフラグに格納されます。
従来のコードでは、ループの終了条件をチェックするためにCMP命令を使用していました。しかし、CMP命令は内部的に減算を行うため、CPSRの全てのフラグ（N, Z, C, V）を更新してしまいます。これにより、直前のADC.SやSBC.S命令で設定されたCフラグが上書きされてしまい、次のループイテレーションで正しいキャリー情報を使用できませんでした。この問題を回避するため、古いコードではMOVW CPSR, R0でCPSRを保存し、MOVW R0, CPSRで復元するという、非常にコストの高い操作を行っていました。
このコミットでは、CMPをTEQに置き換えることでこの問題を解決しています。TEQはビット単位のXOR演算を行い、ZフラグとNフラグのみを更新し、CフラグとVフラグは変更しません。これにより、ループの終了条件（レジスタが等しいか否か）をチェックしつつ、Cフラグの値をそのまま保持できるため、CPSRの保存と復元が不要になり、大幅な性能向上が実現されました。
2. 条件付き命令によるキャリーフラグの読み取り
ループの最後に、最終的なキャリー（またはボロー）の値を返す必要があります。古いコードでは、CPSRをレジスタに読み込み、ビットシフトとAND演算を使ってCフラグのビットを抽出していました。
MOVW CPSR, R0
MOVW R0>>CFLAG, R0
AND $1, R0
新しいコードでは、MOVW.CS $1, R0（加算の場合）やMOVW.CC $1, R0（減算の場合）のような条件付き命令を使用しています。これらの命令は、Cフラグの状態に基づいて直接R0レジスタに1または0を書き込みます。
MOVW.CS $1, R0: キャリーフラグがセットされている（C=1）場合、R0に1を移動します。MOVW.CC $1, R0: キャリーフラグがクリアされている（C=0）場合、R0に1を移動します（これは減算のボローフラグの論理に対応します）。
これにより、複数の命令を1つの条件付き命令に置き換えることができ、命令フェッチとデコードのオーバーヘッドが削減され、パイプラインの効率が向上します。
3. 3引数ARM命令の活用
ARMアーキテクチャの多くの命令は、3つのオペランドを取ることができます（例: ADD Rd, Rn, Rm は Rd = Rn + Rm）。古いコードでは、MOVW R4<<2, R4 のように、シフト演算の結果を同じレジスタに書き戻し、その後別の命令で加算を行うという2段階の操作を行っていました。
MOVW R4<<2, R4
ADD R1, R4
新しいコードでは、これをADD R4<<2, R1, R4のように1つの3引数命令に統合しています。
ADD R4<<2, R1, R4
これにより、命令数が削減され、レジスタ間のデータ転送が減り、パイプラインの効率が向上します。
4. MOVW (LDR) 命令のスケジューリング
コミットメッセージには「Improve scheduling for MOVW instructions (LDR)」とありますが、具体的なコード変更は明示されていません。しかし、一般的に、ロード命令（メモリからレジスタへのデータ転送）は、そのデータが後続の命令で必要になるまでの間に、他の独立した命令を実行することで、ロードレイテンシを隠蔽できます。コンパイラやアセンブラの最適化、または手動での命令並べ替えによって、ロード命令の後に依存関係のない命令を配置することで、パイプラインのストールを最小限に抑え、全体的な実行速度を向上させることができます。このコミットでは、他の最適化と合わせて、このようなスケジューリングの改善も行われた可能性があります。
5. bitLen関数でのRSBの使用
bitLen関数は、与えられたワードの有効ビット長を計算します。これは通常、最上位ビットから連続するゼロの数を数え（CLZ命令）、ワードの全ビット長からその数を引くことで求められます。
古いコードでは、CLZの後にSUB命令を使用していました。
CLZ R0, R0
MOVW $32, R1
SUB.S R0, R1
新しいコードでは、RSB（Reverse Subtract）命令を使用することで、この3命令を2命令に削減しています。
CLZ R0, R0
RSB $32, R0
RSB $32, R0は32 - R0を計算するため、CLZの結果（R0）を32から引くという操作を1命令で完結させることができます。これにより、命令数が減少し、I-キャッシュ（命令キャッシュ）の使用効率が向上します。コミットメッセージにもあるように、ベンチマーク上では速度向上は見られませんでしたが、命令数の削減はリソースが限られた環境や古いプロセッサでメリットがあります。
コアとなるコードの変更箇所
変更はsrc/pkg/math/big/arith_arm.sファイルに集中しています。
addVV関数とsubVV関数
#define CFLAG 29の削除。MOVW $0, R0とMOVW R0, CPSRの代わりにADD.S $0, R0(addVV) またはSUB.S $0, R0(subVV) を使用し、キャリー/ボローフラグを初期化。- ループ条件の
CMP R1, R4をTEQ R1, R4に変更。 - 最終的なキャリー/ボローの取得に
MOVW R0>>CFLAG, R0とAND $1, R0(addVV) またはEOR $1, R0(subVV) の代わりにMOVW.CS $1, R0(addVV) またはMOVW.CC $1, R0(subVV) を使用。 - アドレス計算で
MOVW R4<<2, R4とADD R1, R4の代わりにADD R4<<2, R1, R4のような3引数命令を使用。
addVW関数とsubVW関数
addVVとsubVVと同様に、CMPからTEQへの変更、および条件付き命令の使用。- アドレス計算で3引数命令の使用。
shlVU関数とshrVU関数
- ループ条件やシフト量チェックの
CMPをTEQに変更。 - アドレス計算で3引数命令の使用。例:
ADD R5<<2, R2, R2。
mulAddVWW関数とaddMulVVW関数
- ループ条件の
CMP R1, R5をTEQ R1, R5に変更。 - アドレス計算で3引数命令の使用。
bitLen関数
MOVW $32, R1とSUB.S R0, R1の代わりにRSB $32, R0を使用。
コアとなるコードの解説
変更されたアセンブリコードは、Goのmath/bigパッケージが提供する多倍長整数演算の基盤を形成しています。これらの関数は、Word型のスライス（Goの[]Word）に対して、ワード単位での加算、減算、乗算、シフトなどの基本的な操作を実行します。
例えば、addVV関数は2つの多倍長整数xとyを加算し、結果をzに格納し、最終的なキャリーを返します。この関数はループ内で各ワードを処理し、前のワードからのキャリーを次のワードの加算に含めます。
変更の核心は、このループ処理の効率化にあります。
変更前（簡略化）:
L1:
; ... ワードの加算 (ADC.S がキャリーフラグを設定) ...
MOVW CPSR, R0 ; CPSRをR0に保存 (キャリーフラグを含む)
; ...
E1:
CMP R1, R4 ; ループ終了条件チェック (CMPがCPSRを更新)
BNE L1 ; ループ続行
; ...
MOVW R0, CPSR ; 保存したCPSRを復元 (次のイテレーションのためにキャリーフラグを戻す)
; ... 最終キャリーの抽出 ...
このシーケンスでは、CMP命令がCPSRを上書きするため、ループの各イテレーションでCPSRを保存・復元する必要がありました。これは非常に遅い操作です。
変更後（簡略化）:
L1:
; ... ワードの加算 (ADC.S がキャリーフラグを設定) ...
E1:
TEQ R1, R4 ; ループ終了条件チェック (TEQはキャリーフラグを変更しない)
BNE L1 ; ループ続行
; ... 最終キャリーの抽出 (条件付き命令で直接読み取る) ...
MOVW.CS $1, R0 ; キャリーがセットされていればR0に1をセット
変更後では、TEQがCPSRのキャリーフラグを変更しないため、CPSRの保存と復元が不要になります。これにより、ループのオーバーヘッドが大幅に削減され、特に長い多倍長整数を扱う場合に顕著な性能向上が見られます。ベンチマーク結果が示すように、AddVVやAddVWのような基本的な演算で最大90%以上の高速化が達成されているのは、この最適化の直接的な効果です。
また、bitLen関数におけるRSBの使用は、命令数を1つ削減する小さな変更ですが、このような低レベルの最適化は、頻繁に呼び出される関数において累積的な性能向上に寄与します。命令数の削減は、命令キャッシュの効率向上にもつながり、特にキャッシュが小さい環境や古いプロセッサで有利に働きます。
関連リンク
- Go言語の
math/bigパッケージのドキュメント: https://pkg.go.dev/math/big - ARMアーキテクチャリファレンスマニュアル (ARMv7-A/R): https://developer.arm.com/documentation/ddi0406/latest/ (具体的なバージョンはコミット当時のものと異なる可能性がありますが、基本的な命令セットは共通です)
- Goのアセンブリ言語に関するドキュメント: https://go.dev/doc/asm
参考にした情報源リンク
- Go言語のソースコード (特に
src/pkg/math/big/arith_arm.s): https://github.com/golang/go/blob/master/src/math/big/arith_arm.s - ARM Assembly Language Programming & Architecture (Richard H. Barnett) - ARM命令セットの詳細な解説
- Stack Overflowや技術ブログ記事など、ARMアセンブリの最適化に関する一般的な情報
- Goのベンチマーク結果の解釈に関する一般的な知識