[インデックス 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は、引数とローカル変数に対して別々のビットマップ(LocalPointersMap
とArgPointersMap
)を使用し、スタックメモリをスキャンします。
技術的詳細
このコミットの主要な技術的アプローチは、スタックフレーム上の変数の配置順序を最適化し、GCビットマップのサイズを最小化することです。
-
スタック変数のソート順序の変更:
src/cmd/gc/pgen.c
内のcmpstackvar
関数が変更され、スタック変数のソート順序が調整されました。新しいソート順序は以下のようになります。PAUTO
(自動変数)は他の変数タイプよりも後に配置されます。PAUTO
内では、未使用の変数が使用済みの変数よりも後に配置されます。- 使用済みの
PAUTO
内では、ポインタを含む変数がポインタを含まない変数よりも先に配置されます。 - ポインタを含む変数間では、サイズが大きいものから小さいものへと降順に配置されます。
- これにより、メモリ上ではポインタを含む変数がスタックの上位アドレス(スタックの先頭に近い方)に、ポインタを含まない変数が下位アドレスに集約されるようになります。
-
GCビットマップの範囲の限定:
src/cmd/gc/pgen.c
内のdumpgclocals
関数が変更され、GCビットマップの生成範囲がstkptrsize
(ポインタを含むスタックのプレフィックスサイズ)に限定されるようになりました。これにより、ポインタを含まないデータが配置されているスタックの下位アドレス部分はビットマップの対象外となり、ビットマップのサイズが大幅に削減されます。 -
Type.haspointers
フィールドの追加と最適化:src/cmd/gc/go.h
にType
構造体にhaspointers
フィールドが追加されました。これは、その型がポインタを含んでいるかどうかをキャッシュするためのフィールドです(0: 不明, 1: 含まない, 2: 含む)。src/cmd/gc/reflect.c
内のhaspointers
関数が変更され、このhaspointers
フィールドを利用して、型のポインタ含有情報を一度計算したらキャッシュするようになりました。これにより、同じ型のポインタ含有情報を繰り返し計算するオーバーヘッドが削減されます。 -
stkptrsize
の導入:src/cmd/gc/go.h
にstkptrsize
という新しいグローバル変数が導入されました。これは、現在のスタックフレームにおいてポインタを含む部分のサイズを示すものです。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
とすることで、ポインタを含む変数(haspointers
が1
または2
を返す)が、ポインタを含まない変数(haspointers
が0
を返す)よりも先に配置されるようになります。if(a->type->width < b->type->width) return +1; if(a->type->width > b->type->width) return -1;
ポインタを含む変数間では、幅(サイズ)が大きいものから小さいものへと降順にソートされます。これは、スタックがアドレスが減少する方向に伸びるため、メモリ上ではサイズが大きいものがスタックの先頭に近い方に配置されることを意味します。
このソートロジックにより、スタックフレームの先頭部分にポインタを含むデータが集中し、その後にポインタを含まないデータが続くというレイアウトが実現されます。
allocauto
におけるptrlimit
とstkptrsize
の計算 (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
のままであれば(つまり、スタックフレームにポインタが一つも含まれていない場合)、stkptrsize
は0
に設定されます。そうでなければ、stksize
(スタックフレーム全体のサイズ)からptrlimit
を引くことで、ポインタを含む部分のサイズが計算され、stkptrsize
に設定されます。
この計算により、GCビットマップがカバーすべき正確な範囲が決定されます。
haspointers
のキャッシュ化 (reflect.c)
haspointers
関数は、与えられた型がポインタを含んでいるかどうかを再帰的に判定します。変更前は毎回計算していましたが、変更後はType.haspointers
フィールドを利用して計算結果をキャッシュするようになりました。
if(t->haspointers != 0) return t->haspointers - 1;
関数が呼び出された際に、まずt->haspointers
が0
でないか(つまり、既に計算結果がキャッシュされているか)を確認します。キャッシュされていれば、その値を返します。t->haspointers = 1+ret; return ret;
計算が完了した後、結果(ret
)をt->haspointers
に1
を加えて保存します(0
が不明、1
がポインタなし、2
がポインタありなので、ret
が0
なら1
、1
なら2
を保存)。これにより、次回同じ型がチェックされた際に再計算が不要になります。
この最適化は、コンパイル時のパフォーマンス向上に寄与します。
関連リンク
- Go CL 12541047: https://golang.org/cl/12541047
参考にした情報源リンク
- Go garbage collector (GC) utilizes bitmaps to efficiently identify pointers within stack frames: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHv2dhzdWgUOe-e53wUFCgb0cs0tvs2FKrfEQ3_Q_nSaMyPNPvup-kGuO3THszaxSZ0Qs5GyvmmUXhq_T-_CWbge-2REsrJaEH51FdCw-BsDzNu3pN0kwvaOGb0rZrsjaI=
- Stack Frame Purpose: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFGZQ0cjP850MRbnGER0RmX5OANnzTw204-uqppUQRHhbJPw8X34H4sy52ZERWZgBBvYg7qDz98GnwJBhoMA2Ni4oyj5WLM_90qUm_miAh3fdX9RTVZvIZ8Lr23DhH0lynkd8LEqXVXCigjBrpwFC6NlQY4-njpASw-uFrdtZhhsxjr0o87
- GC Roots: [https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFsRlY9UeXPO1p8Q8DzF_jOwQAOsVW6Ja8ECaP1QGB2KvoFh7eCxrjXJL5t-cLdEKAmlF3kSe-0PqE9uwRLTd4XVtElIWnH_AHf2ZMr3uYt9y8D8nFg0JPvul95nnBliWsjFpOPFYpIjwHkk48HRTsadyvkFTQbgcKULlUgMfRFNf2qypgDlvWZ1w28AvVPW2KqdqRzywfrXwvN1hyfMg==](https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFsRlY9UeXPO1p8Q8DzF_jOwQAOsVW6Ja8ECaP1QGB2KvoFh7eCxrjXJL5t-cLdEKAmlF3kSe-0PqE9uwRLTd4XVtElIWnH_AHf2ZMr3uYt9y8D8nFg0JPvul95nnBliWsjFpOPFYpIjwHkk48HRTsadyvkFTQbgcKULlUgMfRFNf2qypgDlvWZ1w28AvVPW2KqdqRzywfrXwvN1hyP Mg==)
- Efficient Scanning: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGGBmQHsMfBxNdsHyIKkGc0Sj2vfAo1QEqfr0KWAOZlzUlQCmxeUjwMik2ydeDJ-jFXKHHaVwRnN5_ZjE4Zg7Ay0yVBXeLTt9orRNgrwqEQfUCYJPZGwx1SRRMG6AXI4yrOXAH-CpLh18v-8Tchm5-QLQbE6rRVhSxh08RvBhbyxx-5BI2RsuFc7qLc1ec=
- Separate Bitmaps for Arguments and Locals: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEFOgbBcPkQ-AIStTaZ-m1y1mwoQQs8Q6WVnevKsa0fx_PAMghAxbYo6v3FIS4YX0MpzDFmPbCD5_k5HswzVRdkroDGiMpkM00qgcwN2B8SKFxPi0F138vrzFHjd5hh4t-8GqGckyuaKJn43ESlfHk=
- Dynamic Stacks: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQH0NmQ8C6P28FTjn2MGvqTZq7ZeJeL3ufRIitUCGRbpiZfo2_Bj7NFCI-LpMtI-zgUhQOYZuScWYZLM7lQeyR2Sbo2shlc6QsrTzF5rw60du0ki1AbTBg7NWgUXLJJadXibhhZKSFxsZWGkamz04ftt6TlGUTuaCfShMR7e04mp3wYJhGS7ebCnacbuSfdPY5qnSoA1JcYar9CGxckR80
src/runtime/stack.go
andsrc/runtime/mbitmap.go
: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEGmQqV5Bj2u8k0oJL3L2kSLdSh-T-x_QZwCIFUzK4ltWfPe498N6iMkIN5tOxOgbFSmRVhihgGYQoCwE9l3VWisRFCt3BAEiu3HbwbQOadsB1VxDNivgeiAbU4Z3_CKR8U0yYMOTPl8aTSYocFP_nUFD79j_3oihg=go.dev
(general Go documentation): https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQF7TngqUJTsfoRZTgE8NcN8xLHmpRBC1H101idP6N5MnRYrVmHa2j3_NIl1mM5icN4bco029yKksXD98BCEf7P_-zcFxz2EzuL-NySDWMUDDpNaNKtjUOI3MBmrauHL