[インデックス 13211] ファイルの概要
このコミットは、Goコンパイラのcmd/6g（x86-64アーキテクチャ向けコンパイラ）における対称二項演算（sbop）のオペランドスワップロジックの変更に関するものです。特に、浮動小数点定数の扱いを改善し、Mandelbrotベンチマークで顕著なパフォーマンス向上を実現しました。
コミット
commit de96df1b029af554886f6d83a08deb812b0416b6
Author: Russ Cox <rsc@golang.org>
Date: Wed May 30 10:22:33 2012 -0400
cmd/6g: change sbop swap logic
I added the nl->op == OLITERAL case during the recent
performance round, and while it helps for small integer constants,
it hurts for floating point constants. In the Mandelbrot benchmark
it causes 2*Zr*Zi to compile like Zr*2*Zi:
0x000000000042663d <+249>: movsd %xmm6,%xmm0
0x0000000000426641 <+253>: movsd $2,%xmm1
0x000000000042664a <+262>: mulsd %xmm1,%xmm0
0x000000000042664e <+266>: mulsd %xmm5,%xmm0
instead of:
0x0000000000426835 <+276>: movsd $2,%xmm0
0x000000000042683e <+285>: mulsd %xmm6,%xmm0
0x0000000000426842 <+289>: mulsd %xmm5,%xmm0
It is unclear why that has such a dramatic performance effect
in a tight loop, but it's obviously slightly better code, so go with it.
benchmark old ns/op new ns/op delta
BenchmarkBinaryTree17 5957470000 5973924000 +0.28%
BenchmarkFannkuch11 3811295000 3869128000 +1.52%
BenchmarkGobDecode 26001900 25670500 -1.27%
BenchmarkGobEncode 12051430 11948590 -0.85%
BenchmarkGzip 177432 174821 -1.47%
BenchmarkGunzip 10967 10756 -1.92%
BenchmarkJSONEncode 78924750 79746900 +1.04%
BenchmarkJSONDecode 313606400 307081600 -2.08%
BenchmarkMandelbrot200 13670860 8200725 -40.01% !!!
BenchmarkRevcomp25M 1179194000 1206539000 +2.32%
BenchmarkTemplate 447931200 443948200 -0.89%
BenchmarkMD5Hash1K 2856 2873 +0.60%
BenchmarkMD5Hash8K 22083 22029 -0.24%
benchmark old MB/s new MB/s speedup
BenchmarkGobDecode 29.52 29.90 1.01x
BenchmarkGobEncode 63.69 64.24 1.01x
BenchmarkJSONEncode 24.59 24.33 0.99x
BenchmarkJSONDecode 6.19 6.32 1.02x
BenchmarkRevcomp25M 215.54 210.66 0.98x
BenchmarkTemplate 4.33 4.37 1.01x
BenchmarkMD5Hash1K 358.54 356.31 0.99x
BenchmarkMD5Hash8K 370.95 371.86 1.00x
R=ken2
CC=golang-dev
https://golang.org/cl/6261051
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/de96df1b029af554886f6d83a08deb812b0416b6
元コミット内容
このコミットは、Goコンパイラのcmd/6g（x86-64アーキテクチャ向けコンパイラ）における対称二項演算のオペランドスワップロジックを変更するものです。以前の変更で、小さな整数定数に対するパフォーマンス向上のためにnl->op == OLITERALという条件が追加されましたが、これが浮動小数点定数に対しては逆にパフォーマンスを低下させていました。特にMandelbrotベンチマークにおいて、2*Zr*Ziのような式が非効率なアセンブリコードにコンパイルされる問題が発生していました。このコミットは、この問題を修正し、より効率的なコード生成を目指します。
変更の背景
Goコンパイラは、生成されるアセンブリコードの効率性を常に追求しています。コンパイラ最適化の一環として、二項演算のオペランドの順序を入れ替えることで、より効率的なCPU命令シーケンスを生成できる場合があります。特に、定数と変数の組み合わせの場合、定数を特定の位置に配置することで、レジスタの使用を最適化したり、即値オペランド（命令に直接埋め込まれる値）を活用したりすることが可能です。
以前の最適化では、OLITERAL（リテラル定数）であるオペランドを優先的に右側に配置するロジックが導入されました。これは、小さな整数定数が即値として扱える場合に特に有効でした。しかし、このロジックが浮動小数点定数にも一律に適用された結果、Mandelbrotベンチマークのような浮動小数点演算が多用されるシナリオで、かえって非効率なコードが生成される問題が浮上しました。
具体的には、2*Zr*Ziという式において、定数2が浮動小数点数として扱われる場合、以前のロジックではZr*2*Ziのように2が中央に配置されるようなアセンブリが生成されていました。これにより、定数2を一時的なレジスタにロードし、そのレジスタを使って乗算を行うという、余分なステップが発生していました。理想的には、定数2を直接演算結果を保持するレジスタにロードし、そのレジスタで連続して乗算を行う方が効率的です。
このコミットは、この非効率性を解消し、浮動小数点定数と整数定数で異なる最適化戦略を適用することで、全体的なパフォーマンス向上を図ることを目的としています。
前提知識の解説
このコミットを理解するためには、以下の概念についての知識が役立ちます。
-
Goコンパイラ (
cmd/6g):- Go言語のコンパイラは、複数のバックエンド（ターゲットアーキテクチャごとのコード生成部分）を持っています。
cmd/6gは、AMD64（x86-64）アーキテクチャ向けのコンパイラバックエンドを指します。Goのソースコードをこのアーキテクチャで実行可能なバイナリに変換する役割を担います。
- Go言語のコンパイラは、複数のバックエンド（ターゲットアーキテクチャごとのコード生成部分）を持っています。
-
コンパイラ最適化:
- コンパイラがソースコードを機械語に変換する際に、実行速度の向上、メモリ使用量の削減、バイナリサイズの縮小などを目的として、コードの変換や再編成を行うプロセスです。本コミットでは、特に実行速度の向上を目的とした最適化が扱われています。
-
抽象構文木 (AST) とノード (
Node,OLITERAL):- コンパイラは、ソースコードを解析して抽象構文木（AST）と呼ばれるツリー構造に変換します。ASTの各要素は「ノード」と呼ばれ、変数、定数、演算子、関数呼び出しなどを表現します。
OLITERALは、Goコンパイラの内部表現において、リテラル定数（例:10,3.14,"hello")を表すノードの種類です。
-
対称二項演算 (
sbop):- 加算（
+）や乗算（*）のように、オペランドの順序を入れ替えても結果が変わらない演算を指します（例:A + BはB + Aと同じ）。コンパイラはこのような演算の特性を利用して、オペランドの順序を最適化のために変更することがあります。
- 加算（
-
Ullman数 (
ullman):- Ullman数は、コンパイラ最適化におけるヒューリスティックの一つで、式ツリーを評価するために必要な最小レジスタ数を推定するのに使われます。一般的に、Ullman数が小さいサブツリーは、より少ないレジスタで計算できる、あるいは計算コストが低いと見なされます。コンパイラは、Ullman数に基づいてオペランドの順序を決定し、レジスタ割り当てや命令スケジューリングを最適化しようとします。
-
アセンブリ言語とレジスタ (
%xmm0,%xmm1,movsd,mulsd):- レジスタ: CPU内部にある高速な記憶領域で、演算の対象となるデータを一時的に保持します。x86-64アーキテクチャでは、汎用レジスタの他に、浮動小数点演算やSIMD（Single Instruction, Multiple Data）演算に特化した
XMMレジスタ（%xmm0,%xmm1など）があります。 movsd(Move Scalar Double-precision Floating-Point): 浮動小数点数をレジスタ間で移動したり、メモリからレジスタへ、またはその逆へ移動したりする命令です。mulsd(Multiply Scalar Double-precision Floating-Point): 2つの倍精度浮動小数点数を乗算する命令です。- 即値オペランド: アセンブリ命令に直接埋め込まれる定数値を指します（例:
movsd $2,%xmm0の$2）。即値はメモリからのロードが不要なため、非常に高速です。
- レジスタ: CPU内部にある高速な記憶領域で、演算の対象となるデータを一時的に保持します。x86-64アーキテクチャでは、汎用レジスタの他に、浮動小数点演算やSIMD（Single Instruction, Multiple Data）演算に特化した
-
命令スケジューリングとパイプライン処理:
- 現代のCPUは、複数の命令を同時に処理するパイプライン構造を持っています。命令の実行順序を適切にスケジューリングすることで、パイプラインのストール（停止）を減らし、CPUの利用効率を最大化できます。本コミットで示されたアセンブリコードの差は、この命令スケジューリングとレジスタ利用の効率に影響を与えます。
技術的詳細
このコミットの核心は、src/cmd/6g/cgen.cファイル内のcgen関数にあるsbop（symmetric binary operation）ラベル内のオペランドスワップロジックの変更です。
変更前のロジック:
if(nl->ullman < nr->ullman || nl->op == OLITERAL) {
// ... swap nl and nr ...
}
このロジックは、以下のいずれかの条件が満たされた場合に、左オペランドnlと右オペランドnrをスワップしていました（つまり、nrを左に、nlを右に移動）。
nlのUllman数がnrのUllman数よりも小さい場合。nlがOLITERAL（リテラル定数）である場合。
この「リテラル定数であれば常に右に置く」という単純なルールは、小さな整数定数（例: 1, 2）が即値としてアセンブリ命令に直接埋め込める場合に非常に効果的でした。例えば、x * 2のような式では、2を右に置くことでimul x, 2のような効率的な命令を生成できました。
しかし、浮動小数点定数（例: 2.0）の場合、即値として直接命令に埋め込むことはできません。通常、浮動小数点定数はメモリ上の定数プールに格納され、そこからmovsd命令などを使ってレジスタにロードする必要があります。
変更後のロジック:
if(nl->ullman < nr->ullman ||
(nl->ullman == nr->ullman &&
(smallintconst(nl) || (nr->op == OLITERAL && !smallintconst(nr))))) {
// ... swap nl and nr ...
}
新しいロジックは、Ullman数による比較を維持しつつ、Ullman数が等しい場合の挙動をより詳細に制御します。
nl->ullman < nr->ullman: Ullman数が小さい方を右に置くという基本的なヒューリスティックは変わりません。(nl->ullman == nr->ullman && ...): Ullman数が等しい場合、以下の条件でスワップを検討します。smallintconst(nl): もし左オペランドnlが「小さな整数定数」であれば、スワップして右に置きます。これは、小さな整数定数が即値として利用できるため、右に置くことで効率的なコード生成が期待できるからです。(nr->op == OLITERAL && !smallintconst(nr)): もし右オペランドnrがリテラル定数であり、かつそれが小さな整数定数ではない場合、スワップは行われません。この条件が重要です。- 以前のロジックでは、
nlが浮動小数点リテラルであってもOLITERALであれば右にスワップされていました。 - 新しいロジックでは、
nrが浮動小数点リテラル（!smallintconst(nr)）の場合、nlがsmallintconstでない限り、スワップは行われません。これにより、浮動小数点リテラルが左側に配置される可能性が高まります。
- 以前のロジックでは、
Mandelbrotベンチマークの例 (2*Zr*Zi):
ZrとZiは浮動小数点変数、2は浮動小数点定数と仮定します。- 変更前は、
2がOLITERALであるため、Zr * 2のように2が右側にスワップされる傾向がありました。これにより、2を%xmm1にロードし、%xmm0と%xmm1を乗算するという非効率なシーケンスが生成されていました。movsd %xmm6,%xmm0 ; Zr を %xmm0 にロード movsd $2,%xmm1 ; 定数 2 を %xmm1 にロード mulsd %xmm1,%xmm0 ; %xmm0 = %xmm0 * %xmm1 (Zr * 2) mulsd %xmm5,%xmm0 ; %xmm0 = %xmm0 * %xmm5 (結果 * Zi) - 変更後は、浮動小数点定数
2がsmallintconstではないため、nlがsmallintconstでない限り、2が右側にスワップされる可能性が低くなります。これにより、2が左側に配置され、直接%xmm0にロードされ、その後の乗算がより効率的に行われます。movsd $2,%xmm0 ; 定数 2 を直接 %xmm0 にロード mulsd %xmm6,%xmm0 ; %xmm0 = %xmm0 * %xmm6 (2 * Zr) mulsd %xmm5,%xmm0 ; %xmm0 = %xmm0 * %xmm5 (結果 * Zi)
この変更により、浮動小数点定数を扱う際に余分なレジスタロードと乗算が削減され、特にタイトなループ内で浮動小数点演算が頻繁に行われるMandelbrotのようなベンチマークで大幅なパフォーマンス向上が見られました。
コアとなるコードの変更箇所
変更はsrc/cmd/6g/cgen.cファイル内のcgen関数のsbopラベル直下の条件分岐にあります。
--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -396,7 +396,25 @@ cgen(Node *n, Node *res)
goto ret;
sbop: // symmetric binary
- if(nl->ullman < nr->ullman || nl->op == OLITERAL) {
+ /*
+ * put simplest on right - we'll generate into left
+ * and then adjust it using the computation of right.
+ * constants and variables have the same ullman
+ * count, so look for constants specially.
+ *
+ * an integer constant we can use as an immediate
+ * is simpler than a variable - we can use the immediate
+ * in the adjustment instruction directly - so it goes
+ * on the right.
+ *
+ * other constants, like big integers or floating point
+ * constants, require a mov into a register, so those
+ * might as well go on the left, so we can reuse that
+ * register for the computation.
+ */
+ if(nl->ullman < nr->ullman ||
+ (nl->ullman == nr->ullman &&
+ (smallintconst(nl) || (nr->op == OLITERAL && !smallintconst(nr))))) {
r = nl;
nl = nr;
nr = r;
コアとなるコードの解説
変更された条件式は以下の通りです。
変更前:
if(nl->ullman < nr->ullman || nl->op == OLITERAL)
この条件は、左オペランドnlと右オペランドnrをスワップするかどうかを決定していました。
nl->ullman < nr->ullman:nlのUllman数がnrより小さい場合、nlを右に移動させます。これは、より複雑な式を左に、より単純な式を右に置くことで、コード生成を効率化する一般的なヒューリスティックです。nl->op == OLITERAL:nlがリテラル定数である場合、Ullman数に関わらずnlを右に移動させます。この部分が、浮動小数点定数に対して非効率なコードを生成する原因となっていました。
変更後:
if(nl->ullman < nr->ullman ||
(nl->ullman == nr->ullman &&
(smallintconst(nl) || (nr->op == OLITERAL && !smallintconst(nr)))))
新しい条件式は、より洗練されたスワップロジックを導入しています。
nl->ullman < nr->ullman: この部分は変更されていません。Ullman数に基づく基本的なスワップロジックは維持されます。(nl->ullman == nr->ullman && ...): Ullman数が等しい場合に、さらに詳細な条件でスワップを判断します。smallintconst(nl): もし左オペランドnlが「小さな整数定数」であれば、スワップして右に置きます。小さな整数定数は即値として利用できるため、右に置くことで命令の効率が向上します。(nr->op == OLITERAL && !smallintconst(nr)): この部分が最も重要な変更点です。nr->op == OLITERAL: 右オペランドnrがリテラル定数であること。!smallintconst(nr): かつ、そのリテラル定数が小さな整数定数ではないこと。- この二つの条件が同時に真の場合、スワップは行われません。つまり、右オペランドが浮動小数点定数や大きな整数定数である場合、それを右に置くことを避けます。これにより、これらの定数が左側に配置され、レジスタを再利用するようなより効率的なコードパスが選択されるようになります。
この変更により、コンパイラは定数の種類（小さな整数、大きな整数、浮動小数点数）に応じて、より適切なオペランドの配置を決定できるようになり、特に浮動小数点演算のパフォーマンスが改善されました。
関連リンク
- Go言語の公式リポジトリ: https://github.com/golang/go
- このコミットのChange List (CL): https://golang.org/cl/6261051
- Goコンパイラのソースコード (
src/cmd/6g/cgen.c): https://github.com/golang/go/blob/master/src/cmd/6g/cgen.c (コミット当時のバージョンとは異なる可能性があります)
参考にした情報源リンク
- Go言語のコンパイラに関するドキュメントやブログ記事 (一般的なコンパイラ最適化、Ullman数、Goコンパイラの内部構造に関する情報)
- x86-64アセンブリ言語の命令セットリファレンス (movsd, mulsd, xmmレジスタに関する情報)
- Mandelbrot集合の計算に関する情報 (浮動小数点演算のベンチマークとしてのMandelbrotの利用)
- Go言語のベンチマーク結果に関する情報 (Goのベンチマークツールの使い方や結果の解釈)
- GoのIssueトラッカーやメーリングリストでの関連議論 (このコミットに至るまでの背景や議論)