Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goコンパイラ（cmd/gc）におけるライブネス解析のボトルネックを解消し、コンパイル時間を大幅に短縮することを目的としています。特に、splicebefore関数の計算量をO(n)からO(1)に改善したことと、twobitwalktype1関数における剰余演算をビット演算に置き換えたことが主要な変更点です。

コミット

commit 0e97f4187e4326e6d323ce07610efdae13e7fcc8
Author: Russ Cox <rsc@golang.org>
Date:   Fri Dec 20 14:24:48 2013 -0500

    cmd/gc: address 1½ liveness bottlenecks
    
    As much as 7x speedup on some programs, cuts all.bash time by 20%.
    
    Change splicebefore function from O(n) to O(1).
    The approach was suggested by Carl during the code's review
    but apparently did not make it into the tree.
    It makes a huge difference on huge programs.
    
    Make twobitwalktype1 slightly faster by using & instead of %.
    Really it needs to be cached; left a note to that effect.
    (Not a complete fix, hence the ½.)
    
    big.go (output of test/chan/select5.go)
     47.53u   0.50s  48.14r before this CL
      7.09u   0.47s   7.59r with splicebefore change (6.7x speedup)
      6.15u   0.42s   6.59r with twobitwalktype1 change (1.15x speedup; total 7.7x)
    
    slow.go (variant of program in go.text, by mpvl)
     77.75u   2.11s  80.03r before this CL
     24.40u   1.97s  26.44r with splicebefore change (3.2x speedup)
     18.12u   2.19s  20.38r with twobitwalktype1 change (1.35x speedup; total 4.3x)
    
    test/run
    150.63u  49.57s  81.08r before this CL
     88.01u  45.60s  46.65r after this CL (1.7x speedup)
    
    all.bash
    369.70u 115.64s 256.21r before this CL
    298.52u 110.35s 214.67r after this CL (1.24x speedup)
    
    The test programs are at
    https://rsc.googlecode.com/hg/testdata/big.go (36k lines, 276kB)
    https://rsc.googlecode.com/hg/testdata/slow.go (7k lines, 352kB)
    
    R=golang-codereviews, gobot, r
    CC=cshapiro, golang-codereviews
    https://golang.org/cl/43210045

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

https://github.com/golang/go/commit/0e97f4187e4326e6d323ce07610efdae13e7fcc8

元コミット内容

このコミットは、Goコンパイラ（cmd/gc）のライブネス解析におけるパフォーマンスボトルネックを解消するためのものです。具体的には、以下の2つの主要な変更が含まれています。

  1. splicebefore関数の計算量改善: 命令ストリームに新しい命令を挿入するsplicebefore関数が、O(n)の計算量からO(1)に改善されました。これにより、特に大規模なプログラムのコンパイル速度が大幅に向上しました。
  2. twobitwalktype1関数の最適化: 型のビットマップをウォークするtwobitwalktype1関数において、剰余演算（%）をビット単位AND演算（&）に置き換えることで、わずかながら高速化が図られました。これは、アライメントやポインタ幅が2のべき乗であるという特性を利用した最適化です。

これらの変更により、特定のプログラムでは最大7倍の高速化が実現され、all.bash（Goプロジェクト全体のテストスクリプト）の実行時間も20%短縮されました。

変更の背景

Goコンパイラは、プログラムのコンパイル時に様々な最適化と解析を行います。その中でも「ライブネス解析（Liveness Analysis）」は、変数がプログラムのどの時点で「生きている」（将来的に使用される可能性がある）かを判断する重要なプロセスです。この解析は、ガベージコレクションの効率化やレジスタ割り当ての最適化に不可欠です。

しかし、大規模なプログラムでは、このライブネス解析の処理がコンパイル時間の大きなボトルネックとなることがありました。特に、命令ストリームの途中に新しい命令を挿入する操作（splicebefore）が頻繁に行われる場合、その計算量がO(n)であるために、プログラムのサイズに比例して処理時間が急増するという問題がありました。また、型のビットマップを走査するtwobitwalktype1関数も、頻繁に呼び出されるため、わずかな非効率性でも全体的なコンパイル時間に影響を与えていました。

このコミットは、これらの具体的なパフォーマンスボトルネックを特定し、Goコンパイラの全体的な応答性と効率を向上させることを目的としています。特に、splicebeforeの改善は、コードレビュー中にCarl氏によって提案されたものの、これまでのコミットには含まれていなかった最適化であり、その効果の大きさが認識されたことで今回導入されました。

前提知識の解説

ライブネス解析 (Liveness Analysis)

ライブネス解析は、コンパイラのデータフロー解析の一種です。プログラムの各ポイントにおいて、どの変数が「ライブ（live）」であるか、すなわちその変数の値が将来の計算で使用される可能性があるかを決定します。逆に、ライブでない変数は「デッド（dead）」と呼ばれ、そのストレージは再利用可能と判断されます。

  • 目的:
    • レジスタ割り当て: ライブな変数をレジスタに割り当てることで、メモリアクセスを減らし、実行速度を向上させます。
    • ガベージコレクション: ライブでないオブジェクトはガベージコレクタによって回収され、メモリを解放できます。
    • デッドコード削除: ライブな変数に影響を与えないデッドコードを削除できます。
  • 動作原理: 通常、プログラムの制御フローグラフ（CFG）を逆方向に（プログラムの終わりから始まりへ）トラバースし、各命令が変数のライブネスにどのように影響するかを計算します。

Goコンパイラ (cmd/gc)

cmd/gcは、Go言語の公式コンパイラです。Goのソースコードを機械語に変換する役割を担っています。Goコンパイラは、その設計思想として高速なコンパイルを重視しており、そのためにはライブネス解析のような重要なステップの効率が非常に重要になります。

命令ストリームと基本ブロック (Instruction Stream and Basic Blocks)

コンパイラは、ソースコードを中間表現（IR）に変換し、それを命令のシーケンスとして扱います。このシーケンスが「命令ストリーム」です。 「基本ブロック（Basic Block）」は、以下の特性を持つ命令のシーケンスです。

  • 単一のエントリポイント（最初の命令のみがジャンプのターゲットになり得る）。
  • 単一のエグジットポイント（最後の命令のみがジャンプを実行し得る）。
  • ブロック内のすべての命令は、最初の命令が実行されれば必ず実行される。

コンパイラは、プログラムを基本ブロックに分割し、それらの間の制御フローを解析することで、最適化やデータフロー解析を行います。

計算量 (Time Complexity)

アルゴリズムの効率性を示す指標で、入力サイズ（n）が増加したときに、そのアルゴリズムが実行する操作の数がどのように増えるかを表します。

  • O(1) (定数時間): 入力サイズに関わらず、操作の数が一定。非常に効率的。
  • O(n) (線形時間): 入力サイズに比例して操作の数が増加。

ビット演算と剰余演算

  • 剰余演算 (%): 除算を行い、その余りを計算します。一般的に、CPUにとっては除算は比較的コストの高い操作です。
  • ビット単位AND演算 (&): 2つの数値の対応するビットを比較し、両方が1の場合にのみ結果のビットを1にします。2のべき乗（例: 2, 4, 8, 16...）で割った余りを求める場合、N % P（Pは2のべき乗）は N & (P - 1) と等価になります。ビット演算はCPUにとって非常に高速な操作です。

例: 10 % 4 は 2 です。4 は 2^2 なので、4 - 1 = 3（バイナリで 011）。 10（バイナリで 1010）と 3（バイナリで 0011）のビットANDは 0010、つまり 2 となります。

技術的詳細

splicebefore関数のO(1)化

元のsplicebefore関数は、currという既存の命令の前にprevという新しい命令を挿入する際に、命令ストリーム全体（lv->ptxt）を走査していました。この走査の目的は、currをターゲットとしていたすべての制御フロー（ジャンプやフォールスルー）を、新しく挿入されたprevをターゲットにするように調整することでした。この走査がO(n)の計算量となり、命令ストリームが長くなるほどパフォーマンスが低下していました。

新しい実装では、このO(n)の走査を回避するために、より巧妙なアプローチが取られています。

  1. 内容の入れ替え: currとprevの命令の内容（オペコード、オペランドなど）を入れ替えます。これにより、prevのデータがcurrの元の位置に「移動」し、currの元のデータは一時変数tmpを介してnextという新しいProg構造体に格納されます。
  2. リンクの調整: currのopt（後方リンク）とlink（前方リンク）は、元のcurrが持っていたリンクを保持します。
  3. nextの挿入: next（元のcurrのデータを持つ）を、新しいcurr（元のprevのデータを持つ）の直後に挿入します。
  4. 後方リンクの更新: next->linkが存在し、そのoptがcurrを指している場合、next->link->optをnextに更新します。これは、nextが挿入されたことで、その次の命令の後方リンクがnextを指すようにするためです。
  5. 基本ブロックのlastポインタの更新: もしcurrが基本ブロックの最後の命令だった場合、bb->lastをnextに更新します。

このアプローチの鍵は、currを指していた外部からの参照を直接変更するのではなく、currの「中身」を入れ替えることで、外部からの参照が引き続き正しい命令（元のprevのデータを持つ命令）を指すようにすることです。これにより、命令ストリーム全体を走査する必要がなくなり、操作がO(1)で完了するようになりました。

twobitwalktype1関数の最適化

twobitwalktype1関数は、Goの型システムにおけるビットマップの生成に関連しています。この関数は、型のメモリレイアウトをウォークし、ポインタが含まれるオフセットをビットマップに記録します。これはガベージコレクションの際に正確なポインタを識別するために重要です。

元のコードでは、アライメントチェックやポインタ幅のチェックに剰余演算（%）が使用されていました。 例: (*xoffset % t->align) != 0

このコミットでは、これらの剰余演算がビット単位AND演算（&）に置き換えられました。 例: (*xoffset & (t->align - 1)) != 0

この最適化は、t->alignやwidthptr（ポインタの幅）が常に2のべき乗であるというGoのメモリレイアウトの特性に基づいています。2のべき乗で割った余りを求める場合、N % PはN & (P - 1)と等価であり、ビット演算はCPUレベルで非常に高速に実行できるため、パフォーマンスが向上します。

コミットメッセージには、twobitwalktype1がslow.goのコンパイル時間の40%を占めていたという言及があり、この最適化が全体的なコンパイル速度に与える影響の大きさが示唆されています。また、この関数には将来的にビットマップをキャッシュするさらなる最適化の余地があることも示されています。

livenessepilogue関数のループ修正

livenessepilogue関数内のループが、splicebeforeの変更に合わせて修正されました。 元のループ: for(p = bb->last; p != nil; p = p->opt) 修正後のループ: for(p = bb->last; p != nil; p = next) { next = p->opt; }

この変更は、splicebeforeがp->opt（現在の命令の前の命令へのポインタ）を内部で変更する可能性があるためです。もしループ内でsplicebeforeが呼び出され、p->optが変更された場合、次のイテレーションでp = p->optとすると、意図しない命令にジャンプしたり、無限ループに陥ったりする可能性があります。

修正後のコードでは、ループの開始時に次の命令へのポインタ（p->opt）をnext変数に一時的に保存しています。これにより、ループ本体でp->optが変更されても、次のイテレーションは正しくnextに保存された値を使用するため、安全にループを継続できます。これは、リスト構造を走査しながら要素を変更する際の一般的なパターンです。

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

変更はすべて src/cmd/gc/plive.c ファイル内で行われています。

splicebefore 関数の変更

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -149,29 +149,43 @@ addedge(BasicBlock *from, BasicBlock *to)
 	arrayadd(to->pred, &from);
 }
 
-// Inserts a new instruction ahead of an existing instruction in the instruction
+// Inserts prev before curr in the instruction
 // stream.  Any control flow, such as branches or fall throughs, that target the
 // existing instruction are adjusted to target the new instruction.
 static void
 splicebefore(Liveness *lv, BasicBlock *bb, Prog *prev, Prog *curr)
 {
-	Prog *p;
+	Prog *next, tmp;
 
-	prev->opt = curr->opt;
-	curr->opt = prev;
-	prev->link = curr;
-	if(prev->opt != nil)
-		((Prog*)prev->opt)->link = prev;
-	else
-		bb->first = prev;
-	for(p = lv->ptxt; p != nil; p = p->link) {
-		if(p != prev) {
-			if(p->link == curr)
-				p->link = prev;
-			if(p->as != ACALL && p->to.type == D_BRANCH && p->to.u.branch == curr)
-				p->to.u.branch = prev;
-		}
-	}
+	USED(lv);
+
+	// There may be other instructions pointing at curr,
+	// and we want them to now point at prev. Instead of
+	// trying to find all such instructions, swap the contents
+	// so that the problem becomes inserting next after curr.
+	// The "opt" field is the backward link in the linked list.
+
+	// Overwrite curr's data with prev, but keep the list links.
+	tmp = *curr;
+	*curr = *prev;
+	curr->opt = tmp.opt;
+	curr->link = tmp.link;
+	
+	// Overwrite prev (now next) with curr's old data.
+	next = prev;
+	*next = tmp;
+	next->opt = nil;
+	next->link = nil;
+
+	// Now insert next after curr.
+	next->link = curr->link;
+	next->opt = curr;
+	curr->link = next;
+	if(next->link && next->link->opt == curr)
+		next->link->opt = next;
+
+	if(bb->last == curr)
+		bb->last = next;
 }
 
 // A pretty printer for basic blocks.

twobitwalktype1 関数の変更

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -949,6 +963,10 @@ checkptxt(Node *fn, Prog *firstp)
 	}
 }
 
+// NOTE: The bitmap for a specific type t should be cached in t after the first run
+// and then simply copied into bv at the correct offset on future calls with
+// the same type t. On https://rsc.googlecode.com/hg/testdata/slow.go, twobitwalktype1
+// accounts for 40% of the 6g execution time.
 static void
 twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 {
@@ -957,7 +975,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 	vlong o;
 	Type *t1;
 
-\tif(t->align > 0 && (*xoffset % t->align) != 0)
+\tif(t->align > 0 && (*xoffset & (t->align - 1)) != 0)
 	\tfatal("twobitwalktype1: invalid initial alignment, %T", t);
 
 \tswitch(t->etype) {
@@ -986,7 +1004,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 	case TFUNC:
 	case TCHAN:
 	case TMAP:
-\t\tif(*xoffset % widthptr != 0)
+\t\tif((*xoffset & (widthptr-1)) != 0)
 	\t\tfatal("twobitwalktype1: invalid alignment, %T", t);
 	\t\tbvset(bv, (*xoffset / widthptr) * BitsPerPointer);
 	\t\t*xoffset += t->width;
@@ -994,7 +1012,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 
 	case TSTRING:
 	\t// struct { byte *str; intgo len; }\n-\t\tif(*xoffset % widthptr != 0)
+\t\tif((*xoffset & (widthptr-1)) != 0)
 	\t\tfatal("twobitwalktype1: invalid alignment, %T", t);
 	\t\tbvset(bv, (*xoffset / widthptr) * BitsPerPointer);
 	\t\t*xoffset += t->width;
@@ -1004,7 +1022,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 	\t// struct { Itab *tab;\tunion { void *ptr, uintptr val } data; }\n 	\t// or, when isnilinter(t)==true:\n 	\t// struct { Type *type; union { void *ptr, uintptr val } data; }\n-\t\tif(*xoffset % widthptr != 0)
+\t\tif((*xoffset & (widthptr-1)) != 0)
 	\t\tfatal("twobitwalktype1: invalid alignment, %T", t);
 	\t\tbvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 1);
 	\t\tif(isnilinter(t))
@@ -1019,7 +1037,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv)
 	\t\tfatal("twobitwalktype1: invalid bound, %T", t);
 	\t\tif(isslice(t)) {
 	\t\t\t// struct { byte *array; uintgo len; uintgo cap; }\n-\t\t\t\tif(*xoffset % widthptr != 0)
+\t\t\t\tif((*xoffset & (widthptr-1)) != 0)
 	\t\t\t\tfatal("twobitwalktype1: invalid TARRAY alignment, %T", t);
 	\t\t\tbvset(bv, (*xoffset / widthptr) * BitsPerPointer);
 	\t\t\t*xoffset += t->width;

livenessepilogue 関数のループ修正

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -1285,7 +1303,7 @@ livenessepilogue(Liveness *lv)
 	Bvec *varkill;
 	Bvec *args;
 	Bvec *locals;
-\tProg *p;\n+\tProg *p, *next;
 	int32 i;
 	int32 nvars;
 	int32 pos;
@@ -1329,7 +1347,8 @@ livenessepilogue(Liveness *lv)
 			fatal("livenessepilogue");
 		}
 
-\t\tfor(p = bb->last; p != nil; p = p->opt) {
+\t\tfor(p = bb->last; p != nil; p = next) {
+\t\t\tnext = p->opt; // splicebefore modifies p->opt
 	\t\t// Propagate liveness information
 	\t\tprogeffects(p, lv->vars, uevar, varkill);
 	\t\tbvcopy(liveout, livein);

コアとなるコードの解説

splicebefore の変更点詳細

  • 旧実装:

    • prev->opt = curr->opt; curr->opt = prev; prev->link = curr; でprevをcurrの前に挿入し、リンクを調整。
    • その後、for(p = lv->ptxt; p != nil; p = p->link) ループで命令ストリーム全体を走査し、currをターゲットとするすべてのジャンプ命令（p->to.u.branch == curr）のターゲットをprevに書き換えていました。この線形走査がパフォーマンスボトルネックでした。

  • 新実装:

    • tmp = *curr; *curr = *prev; でcurrとprevの内容を入れ替えます。これにより、currが指すメモリ位置にはprevのデータが入り、prevが指すメモリ位置にはcurrの元のデータがtmpを介して入ります。
    • curr->opt = tmp.opt; curr->link = tmp.link; で、currのリンクは元のcurrが持っていたリンクを保持します。つまり、currは元の位置に留まり、その中身だけがprevのものに変わったと考えることができます。
    • next = prev; *next = tmp; で、prevが指していたメモリ位置に、元のcurrのデータ（tmp）をコピーし、これをnextとします。
    • next->link = curr->link; next->opt = curr; curr->link = next; で、nextを新しいcurrの直後に挿入します。
    • if(next->link && next->link->opt == curr) next->link->opt = next; は、nextの次の命令が存在し、その命令の後方リンクがcurrを指している場合、それをnextを指すように更新します。これは、nextがcurrとnext->linkの間に挿入されたため、next->linkの後方リンクがnextを指すようにするためです。
    • if(bb->last == curr) bb->last = next; は、基本ブロックの最後の命令がcurrだった場合、それをnextに更新します。

この変更により、命令ストリーム全体を走査することなく、既存の参照を有効に保ちつつ命令を挿入できるようになり、計算量がO(1)に削減されました。

twobitwalktype1 の変更点詳細

  • 旧実装:

    • (*xoffset % t->align) != 0
    • (*xoffset % widthptr) != 0 剰余演算子 % を使用して、アライメントチェックを行っていました。

  • 新実装:

    • (*xoffset & (t->align - 1)) != 0
    • (*xoffset & (widthptr - 1)) != 0 剰余演算子をビット単位AND演算子 & に置き換えました。これは、t->alignとwidthptrが2のべき乗であるという前提に基づいています。2のべき乗 P で割った余りは、P-1 とのビット単位ANDで効率的に計算できます。この変更は、CPUの命令レベルでの効率向上に寄与し、頻繁に呼び出されるこの関数のパフォーマンスを改善します。

livenessepilogue のループ修正詳細

  • 旧実装:

    • for(p = bb->last; p != nil; p = p->opt) ループ変数の更新が p = p->opt となっており、ループ内で p->opt が変更されると、次のイテレーションで不正なアドレスを参照したり、無限ループに陥ったりする可能性がありました。

  • 新実装:

    • for(p = bb->last; p != nil; p = next) { next = p->opt; } ループの各イテレーションの開始時に、次の要素へのポインタ p->opt を一時変数 next に保存します。これにより、ループ本体で p または p->opt が変更されても、次のイテレーションは next に保存された正しいポインタを使用するため、安全にリストを走査できます。これは、リストを走査しながら要素を削除または挿入する際の一般的な安全策です。

関連リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • Goコンパイラに関するドキュメント（Goのソースコード内）: src/cmd/gc/README など
  • Goのライブネス解析に関する一般的な情報（Goのガベージコレクションやコンパイラ最適化に関する論文やブログ記事）

参考にした情報源リンク