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

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

このコミットは、Go言語のコンパイラ(cmd/gc)におけるガベージコレクション(GC)のビットマップ生成ロジックを最適化し、スタックフレーム上のポインタ情報を含むビットマップのサイズを削減することを目的としています。特に、大きなバイトバッファをスタック上に持つプログラムにおいて、GCビットマップのサイズが大幅に短縮され、GCの効率が向上します。また、ARMビルドの問題も修正されています。

コミット

  • コミットハッシュ: f91e682cca2eb51a0a8b1511678a5e2b4d8a83de
  • Author: Russ Cox rsc@golang.org
  • Date: Thu Aug 8 16:38:02 2013 -0400

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

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

元コミット内容

cmd/gc: make bitmaps shorter

Sort non-pointer-containing data to the low end of the
stack frame, and make the bitmaps only cover the
pointer-containing top end.

Generates significantly less garbage collection bitmap
for programs with large byte buffers on the stack.

Only 2% shorter for godoc, but 99.99998% shorter
in some test cases.

Fixes arm build.

TBR=golang-dev
CC=cshapiro, golang-dev, iant
https://golang.org/cl/12541047

変更の背景

Go言語のガベージコレクタは、スタックフレーム上のポインタを正確に識別するためにビットマップを使用します。このビットマップは、スタックフレーム内のどのワードがポインタを含んでいるかを示すもので、GCがライブオブジェクトを追跡する上で不可欠です。

しかし、従来のGoコンパイラでは、スタックフレーム上の変数の配置が最適化されておらず、特に大きなバイトバッファ(ポインタを含まないデータ)がスタックの下位アドレスに配置される場合でも、GCビットマップはスタックフレーム全体をカバーするように生成されていました。これにより、ポインタを含まない大部分のデータに対しても不要なビットマップ情報が生成され、GCビットマップのサイズが肥大化するという問題がありました。

この肥大化したビットマップは、メモリ使用量の増加だけでなく、GCがスタックをスキャンする際のオーバーヘッドにも影響を与えます。特に、大量の非ポインタデータを持つ関数が頻繁に呼び出されるようなシナリオでは、この問題が顕著になります。

このコミットは、この問題を解決するために、スタックフレーム上の変数の配置順序を変更し、ポインタを含まないデータをスタックフレームの下位アドレスに、ポインタを含むデータを上位アドレスに集約することで、GCビットマップがカバーすべき範囲を最小限に抑えることを目的としています。これにより、GCビットマップのサイズが大幅に削減され、GCの効率が向上します。

前提知識の解説

Go言語のガベージコレクション (GC)

Go言語は、自動メモリ管理のためにトレース型ガベージコレクタを採用しています。GCは、プログラムが動的に確保したメモリ領域(ヒープ)のうち、もはや到達不可能(参照されていない)なオブジェクトを自動的に解放し、メモリリークを防ぎます。GoのGCは、並行(concurrent)かつ低遅延(low-latency)であることを特徴としています。

GCは、プログラムの実行中に「ルートオブジェクト」から到達可能なすべてのオブジェクトをマークし、マークされなかったオブジェクトを「ガベージ」として認識し、解放します。ルートオブジェクトには、グローバル変数や、現在実行中のゴルーチン(Goの軽量スレッド)のスタックフレーム上のポインタなどが含まれます。

スタックフレーム

関数が呼び出されるたびに、その関数に必要なローカル変数、引数、戻りアドレスなどを格納するためのメモリ領域がスタック上に確保されます。この領域を「スタックフレーム」と呼びます。Goのゴルーチンは動的にサイズが変化するスタックを使用し、必要に応じてスタックが拡張・縮小されます。

GCビットマップ

GoのGCは、スタックフレームを効率的にスキャンするために「GCビットマップ」を利用します。GCビットマップは、スタックフレーム内の各ワードがポインタであるか否かを示すビット列です。

  • ビットが1の場合:対応するワードはポインタであり、GCがそのポインタをたどって参照先のオブジェクトをマークする必要があります。
  • ビットが0の場合:対応するワードはポインタではない(スカラー値など)ため、GCはそのワードを無視できます。

このビットマップにより、GCはスタックフレーム内のすべてのワードを個別に検査することなく、ポインタの位置を迅速に特定し、効率的なスタックスキャンを実現します。GoのGCは、引数とローカル変数に対して別々のビットマップ(LocalPointersMapArgPointersMap)を使用し、スタックメモリをスキャンします。

技術的詳細

このコミットの主要な技術的アプローチは、スタックフレーム上の変数の配置順序を最適化し、GCビットマップのサイズを最小化することです。

  1. スタック変数のソート順序の変更: src/cmd/gc/pgen.c内のcmpstackvar関数が変更され、スタック変数のソート順序が調整されました。新しいソート順序は以下のようになります。

    • PAUTO(自動変数)は他の変数タイプよりも後に配置されます。
    • PAUTO内では、未使用の変数が使用済みの変数よりも後に配置されます。
    • 使用済みのPAUTO内では、ポインタを含む変数がポインタを含まない変数よりも先に配置されます。
    • ポインタを含む変数間では、サイズが大きいものから小さいものへと降順に配置されます。
    • これにより、メモリ上ではポインタを含む変数がスタックの上位アドレス(スタックの先頭に近い方)に、ポインタを含まない変数が下位アドレスに集約されるようになります。
  2. GCビットマップの範囲の限定: src/cmd/gc/pgen.c内のdumpgclocals関数が変更され、GCビットマップの生成範囲がstkptrsize(ポインタを含むスタックのプレフィックスサイズ)に限定されるようになりました。これにより、ポインタを含まないデータが配置されているスタックの下位アドレス部分はビットマップの対象外となり、ビットマップのサイズが大幅に削減されます。

  3. Type.haspointersフィールドの追加と最適化: src/cmd/gc/go.hType構造体にhaspointersフィールドが追加されました。これは、その型がポインタを含んでいるかどうかをキャッシュするためのフィールドです(0: 不明, 1: 含まない, 2: 含む)。 src/cmd/gc/reflect.c内のhaspointers関数が変更され、このhaspointersフィールドを利用して、型のポインタ含有情報を一度計算したらキャッシュするようになりました。これにより、同じ型のポインタ含有情報を繰り返し計算するオーバーヘッドが削減されます。

  4. stkptrsizeの導入: src/cmd/gc/go.hstkptrsizeという新しいグローバル変数が導入されました。これは、現在のスタックフレームにおいてポインタを含む部分のサイズを示すものです。allocauto関数内でこの値が計算され、GCビットマップの生成範囲を決定するために使用されます。

これらの変更により、特に大きなバイトバッファを持つプログラムにおいて、GCビットマップのサイズが劇的に削減されます。コミットメッセージにあるように、一部のテストケースでは99.99998%もの削減が達成されています。これは、GCの効率向上とメモリ使用量の削減に大きく貢献します。

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

src/cmd/gc/go.h

--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -153,6 +153,7 @@ struct	Type
 	uchar	broke;  	// broken type definition.
 	uchar	isddd;		// TFIELD is ... argument
 	uchar	align;
+	uchar	haspointers;	// 0 unknown, 1 no, 2 yes
 
 	Node*	nod;		// canonical OTYPE node
 	Type*	orig;		// original type (type literal or predefined type)
@@ -937,6 +938,7 @@ EXTERN	NodeList*	lastconst;
 EXTERN	Node*	lasttype;
 EXTERN	vlong	maxarg;
 EXTERN	vlong	stksize;		// stack size for current frame
+EXTERN	vlong	stkptrsize;		// prefix of stack containing pointers for current frame
 EXTERN	int32	blockgen;		// max block number
 EXTERN	int32	block;			// current block number
 EXTERN	int	hasdefer;		// flag that curfn has defer statetment
  • Type構造体にhaspointersフィールドが追加されました。
  • stkptrsizeという新しいグローバル変数が追加されました。

src/cmd/gc/pgen.c

--- a/src/cmd/gc/pgen.c
+++ b/src/cmd/gc/pgen.c
@@ -336,12 +336,12 @@ dumpgclocals(Node* fn, Sym *sym)
 	int32 i;
 	int off;
 
-	bv = bvalloc(rnd(stksize, widthptr) / widthptr);
+	bv = bvalloc(stkptrsize / widthptr);
 	for(ll = fn->dcl; ll != nil; ll = ll->next) {
 		node = ll->n;
 		if(node->class == PAUTO && node->op == ONAME) {
 			if(haspointers(node->type)) {
-				xoffset = node->xoffset + rnd(stksize,widthptr);
+				xoffset = node->xoffset + stksize;
 				walktype1(node->type, &xoffset, bv);
 			}
 		}
@@ -354,25 +354,40 @@ dumpgclocals(Node* fn, Sym *sym)
 	ggloblsym(sym, off, 0, 1);
 }
 
-// Sort the list of stack variables.  autos after anything else,
-// within autos, unused after used, and within used on reverse alignment.
-// non-autos sort on offset.
+// Sort the list of stack variables. Autos after anything else,
+// within autos, unused after used, within used, things with
+// pointers first, and then decreasing size.
+// Because autos are laid out in decreasing addresses
+// on the stack, pointers first and decreasing size
+// really means, in memory, pointers near the top of the 
+// stack and increasing in size.
+// Non-autos sort on offset.
 static int
 cmpstackvar(Node *a, Node *b)
 {
+	int ap, bp;
+
 	if (a->class != b->class)
-		return (a->class == PAUTO) ? 1 : -1;
+		return (a->class == PAUTO) ? +1 : -1;
 	if (a->class != PAUTO) {
 		if (a->xoffset < b->xoffset)
 			return -1;
 		if (a->xoffset > b->xoffset)
-			return 1;
+			return +1;
 		return 0;
 	}
 	if ((a->used == 0) != (b->used == 0))
 		return b->used - a->used;
-	return b->type->align - a->type->align;
+
+	ap = haspointers(a->type);
+	bp = haspointers(b->type);
+	if(ap != bp)
+		return bp - ap;
+	if(a->type->width < b->type->width)
+		return +1;
+	if(a->type->width > b->type->width)
+		return -1;
+	return 0;
 }
 
 // TODO(lvd) find out where the PAUTO/OLITERAL nodes come from.
@@ -382,9 +397,13 @@ allocauto(Prog* ptxt)
 	NodeList *ll;
 	Node* n;
 	vlong w;
+	vlong ptrlimit;
 
-	if(curfn->dcl == nil)
+	if(curfn->dcl == nil) {
+		stksize = 0;
+		stkptrsize = 0;
 		return;
+	}
 
 	// Mark the PAUTO's unused.
 	for(ll=curfn->dcl; ll != nil; ll=ll->next)
@@ -402,6 +421,7 @@ allocauto(Prog* ptxt)
 		// No locals used at all
 		curfn->dcl = nil;
 		stksize = 0;
+		stkptrsize = 0;
 		fixautoused(ptxt);
 		return;
 	}
@@ -417,6 +437,7 @@ allocauto(Prog* ptxt)
 
 	// Reassign stack offsets of the locals that are still there.
 	stksize = 0;
+	ptrlimit = -1;
 	for(ll = curfn->dcl; ll != nil; ll=ll->next) {
 		n = ll->n;
 		if (n->class != PAUTO || n->op != ONAME)
@@ -428,6 +449,8 @@ allocauto(Prog* ptxt)
 		if(w == 0)
 			fatal("bad width");
 		stksize += w;
 		stksize = rnd(stksize, n->type->align);
+		if(ptrlimit < 0 && haspointers(n->type))
+			ptrlimit = stksize - w;
 		if(thechar == '5')
 			stksize = rnd(stksize, widthptr);
 		if(stksize >= (1ULL<<31)) {
@@ -436,11 +459,18 @@ allocauto(Prog* ptxt)
 		}
 		n->stkdelta = -stksize - n->xoffset;
 	}
+	stksize = rnd(stksize, widthptr);
+
+	if(ptrlimit < 0)
+		stkptrsize = 0;
+	else
+		stkptrsize = stksize - ptrlimit;
+	stkptrsize = rnd(stkptrsize, widthptr);
 
 	fixautoused(ptxt);
 
 	// The debug information needs accurate offsets on the symbols.
-	for(ll = curfn->dcl ;ll != nil; ll=ll->next) {
+	for(ll = curfn->dcl; ll != nil; ll=ll->next) {
 		if (ll->n->class != PAUTO || ll->n->op != ONAME)
 			continue;
 		ll->n->xoffset += ll->n->stkdelta;
  • dumpgclocals: bvallocの引数がstksizeからstkptrsizeに変更され、GCビットマップの範囲が限定されました。
  • cmpstackvar: スタック変数のソートロジックが大幅に変更され、ポインタを含む変数が優先的に配置されるようになりました。
  • allocauto: stkptrsizeの計算ロジックが追加され、ptrlimitを用いてポインタを含むデータの境界を特定しています。

src/cmd/gc/reflect.c

--- a/src/cmd/gc/reflect.c
+++ b/src/cmd/gc/reflect.c
@@ -459,6 +459,10 @@ int
 haspointers(Type *t)
 {
 	Type *t1;\n+\tint ret;\n+\n+\tif(t->haspointers != 0)\n+\t\treturn t->haspointers - 1;\n \n 	switch(t->etype) {
 	case TINT:
@@ -477,16 +477,24 @@ haspointers(Type *t)
 	case TCOMPLEX64:
 	case TCOMPLEX128:
 	case TBOOL:
-\t\treturn 0;\n+\t\tret = 0;\n+\t\tbreak;\n 	case TARRAY:
-\t\tif(t->bound < 0)\t// slice
-\t\t\treturn 1;\n-\t\treturn haspointers(t->type);\n+\t\tif(t->bound < 0) {\t// slice
+\t\t\tret = 1;\n+\t\t\tbreak;\n+\t\t}\n+\t\tret = haspointers(t->type);\n+\t\tbreak;\n 	case TSTRUCT:
-\t\tfor(t1=t->type; t1!=T; t1=t1->down)\n-\t\t\tif(haspointers(t1->type))\n-\t\t\t\treturn 1;\n-\t\treturn 0;\n+\t\tret = 0;\n+\t\tfor(t1=t->type; t1!=T; t1=t1->down) {\n+\t\t\tif(haspointers(t1->type)) {\n+\t\t\t\tret = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\tbreak;\n 	case TSTRING:
 	case TPTR32:
 	case TPTR64:
@@ -496,8 +508,12 @@ haspointers(Type *t)
 	case TMAP:
 	case TFUNC:
 	default:
-\t\treturn 1;\n+\t\tret = 1;\n+\t\tbreak;\n 	}\n+\t\n+\tt->haspointers = 1+ret;\n+\treturn ret;\n }\n \n /*
  • haspointers関数が変更され、Type.haspointersフィールドを利用して計算結果をキャッシュするようになりました。これにより、同じ型のポインタ含有情報を繰り返し計算するのを防ぎます。

コアとなるコードの解説

Type.haspointers (go.h)

このフィールドは、Goの型がポインタを含んでいるかどうかをキャッシュするために導入されました。0は不明、1はポインタを含まない、2はポインタを含むことを示します。これにより、haspointers関数の呼び出しが最適化され、型のポインタ含有情報を繰り返し計算するコストが削減されます。

stkptrsize (go.h)

この新しいグローバル変数は、現在の関数(スタックフレーム)において、ポインタを含むデータが配置されているスタックのプレフィックス(先頭からの)サイズをバイト単位で表します。この値はallocauto関数で計算され、GCビットマップの生成範囲を決定するために使用されます。GCビットマップは、このstkptrsizeの範囲のみをカバーするように生成されるため、ポインタを含まないデータがスタックの下位アドレスに配置されていても、その部分はビットマップの対象外となります。

dumpgclocalsにおけるbvalloc(stkptrsize / widthptr) (pgen.c)

dumpgclocals関数は、GCビットマップを生成する役割を担っています。変更前はbvalloc(rnd(stksize, widthptr) / widthptr)のように、スタックフレーム全体のサイズに基づいてビットマップを割り当てていました。変更後はbvalloc(stkptrsize / widthptr)となり、stkptrsize(ポインタを含む部分のサイズ)に基づいてビットマップを割り当てるようになりました。widthptrはポインタのサイズ(ワードサイズ)です。これにより、ビットマップのサイズがポインタを含むデータのみに限定され、大幅な削減が実現されます。

cmpstackvarの変更 (pgen.c)

この関数は、スタック変数を配置する際のソート順序を決定します。変更の核心は、ポインタを含む変数をスタックの上位アドレス(スタックの先頭に近い方)に集約することです。

  • ap = haspointers(a->type); bp = haspointers(b->type); if(ap != bp) return bp - ap; この部分が最も重要で、haspointersの結果(ポインタを含むか否か)に基づいて変数をソートします。bp - apとすることで、ポインタを含む変数(haspointers1または2を返す)が、ポインタを含まない変数(haspointers0を返す)よりも先に配置されるようになります。
  • if(a->type->width < b->type->width) return +1; if(a->type->width > b->type->width) return -1; ポインタを含む変数間では、幅(サイズ)が大きいものから小さいものへと降順にソートされます。これは、スタックがアドレスが減少する方向に伸びるため、メモリ上ではサイズが大きいものがスタックの先頭に近い方に配置されることを意味します。

このソートロジックにより、スタックフレームの先頭部分にポインタを含むデータが集中し、その後にポインタを含まないデータが続くというレイアウトが実現されます。

allocautoにおけるptrlimitstkptrsizeの計算 (pgen.c)

allocauto関数は、自動変数(ローカル変数)のスタックオフセットを割り当てる役割を担っています。

  • ptrlimit = -1; ptrlimitは、ポインタを含むデータが始まるスタックオフセットを追跡するための変数です。初期値は-1で、まだポインタを含むデータが見つかっていないことを示します。
  • if(ptrlimit < 0 && haspointers(n->type)) ptrlimit = stksize - w; スタック変数を処理するループ内で、もしptrlimitがまだ設定されておらず、かつ現在の変数nがポインタを含む場合、その変数の開始オフセット(stksize - w)をptrlimitとして記録します。これにより、スタックフレーム内でポインタを含むデータが始まる最初の位置が特定されます。
  • if(ptrlimit < 0) stkptrsize = 0; else stkptrsize = stksize - ptrlimit; ループの終了後、ptrlimit-1のままであれば(つまり、スタックフレームにポインタが一つも含まれていない場合)、stkptrsize0に設定されます。そうでなければ、stksize(スタックフレーム全体のサイズ)からptrlimitを引くことで、ポインタを含む部分のサイズが計算され、stkptrsizeに設定されます。

この計算により、GCビットマップがカバーすべき正確な範囲が決定されます。

haspointersのキャッシュ化 (reflect.c)

haspointers関数は、与えられた型がポインタを含んでいるかどうかを再帰的に判定します。変更前は毎回計算していましたが、変更後はType.haspointersフィールドを利用して計算結果をキャッシュするようになりました。

  • if(t->haspointers != 0) return t->haspointers - 1; 関数が呼び出された際に、まずt->haspointers0でないか(つまり、既に計算結果がキャッシュされているか)を確認します。キャッシュされていれば、その値を返します。
  • t->haspointers = 1+ret; return ret; 計算が完了した後、結果(ret)をt->haspointers1を加えて保存します(0が不明、1がポインタなし、2がポインタありなので、ret0なら11なら2を保存)。これにより、次回同じ型がチェックされた際に再計算が不要になります。

この最適化は、コンパイル時のパフォーマンス向上に寄与します。

関連リンク

参考にした情報源リンク