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

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

このコミットは、Goランタイムのガベージコレクション（GC）メカニズムにおける重要な改善を導入しています。特に、GCルートの収集方法を変更し、GCの一時停止時間を短縮することで、並列性を向上させています。

コミット

commit cb133c66073303b08e893d6b71faf98bda2402e9
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Jan 21 13:06:57 2014 +0400

    runtime: do not collect GC roots explicitly
    Currently we collect (add) all roots into a global array in a single-threaded GC phase.
    This hinders parallelism.
    With this change we just kick off parallel for for number_of_goroutines+5 iterations.
    Then parallel for callback decides whether it needs to scan stack of a goroutine
    scan data segment, scan finalizers, etc. This eliminates the single-threaded phase entirely.
    This requires to store all goroutines in an array instead of a linked list
    (to allow direct indexing).
    This CL also removes DebugScan functionality. It is broken because it uses
    unbounded stack, so it can not run on g0. When it was working, I've found
    it helpless for debugging issues because the two algorithms are too different now.
    This change would require updating the DebugScan, so it's simpler to just delete it.
    
    With 8 threads this change reduces GC pause by ~6%, while keeping cputime roughly the same.
    
    garbage-8
    allocated                 2987886      2989221      +0.04%
    allocs                      62885        62887      +0.00%
    cputime                  21286000     21272000      -0.07%
    gc-pause-one             26633247     24885421      -6.56%
    gc-pause-total             873570       811264      -7.13%
    rss                     242089984    242515968      +0.18%
    sys-gc                   13934336     13869056      -0.47%
    sys-heap                205062144    205062144      +0.00%
    sys-other                12628288     12628288      +0.00%
    sys-stack                11534336     11927552      +3.41%
    sys-total               243159104    243487040      +0.13%
    time                      2809477      2740795      -2.44%
    
    R=golang-codereviews, rsc
    CC=cshapiro, golang-codereviews, khr
    https://golang.org/cl/46860043

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

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

元コミット内容

このコミットの元の内容は、Goランタイムのガベージコレクション（GC）におけるルート収集の明示的な処理を廃止することです。以前は、GCルート（GCが到達可能性を判断するための開始点となるオブジェクト）を単一スレッドのGCフェーズでグローバルな配列に明示的に収集していました。この方法は並列性を阻害していました。

この変更により、GCルートの明示的な収集は行われず、代わりにnumber_of_goroutines + 5回の並列処理を起動します。この並列処理のコールバック内で、各ゴルーチンのスタック、データセグメント、ファイナライザなどをスキャンする必要があるかどうかを判断します。これにより、GCにおける単一スレッドフェーズが完全に排除されます。

この変更を実現するためには、すべてのゴルーチンをリンクリストではなく配列に格納する必要があります（直接インデックスアクセスを可能にするため）。

また、このコミットではDebugScan機能も削除されています。これは、無制限のスタックを使用するためg0（Goランタイムの特別なゴルーチン）上で実行できないという問題があり、現在のGCアルゴリズムとは大きく異なるため、デバッグには役立たないと判断されたためです。

パフォーマンス面では、8スレッドで実行した場合、GCの一時停止時間が約6%削減され、CPU時間はほぼ同じに保たれることが報告されています。

変更の背景

Goのガベージコレクションは、プログラムの実行中に不要になったメモリを自動的に解放する重要な機能です。しかし、GCが動作する際には、プログラムの実行が一時的に停止する「一時停止（pause）」が発生することがあります。この一時停止時間が長くなると、アプリケーションの応答性やスループットに悪影響を与える可能性があります。

このコミットが導入される以前のGoのGCでは、GCルート（プログラムが直接参照しているオブジェクト）の収集が単一スレッドで行われていました。GCルートは、GCがヒープ上のオブジェクトの到達可能性を判断するための出発点となるため、GCの初期段階で必ず収集される必要があります。しかし、この「ルート収集」フェーズが単一スレッドで実行されることは、GC全体の並列性を阻害し、特にマルチコア環境でのGC一時停止時間のボトルネックとなっていました。

開発者は、この単一スレッドのルート収集フェーズを排除し、GCの並列性をさらに高めることで、GC一時停止時間を短縮し、Goアプリケーションの全体的なパフォーマンスを向上させることを目指しました。

前提知識の解説

ガベージコレクション (GC) の基本

ガベージコレクションは、プログラムが動的に割り当てたメモリのうち、もはや到達不可能（参照されていない）になったものを自動的に解放するプロセスです。これにより、プログラマは手動でのメモリ管理から解放され、メモリリークのリスクを低減できます。

GoのGCは、主に「マーク＆スイープ」アルゴリズムをベースにしています。

  1. マークフェーズ (Mark Phase): GCルートから到達可能なすべてのオブジェクトを「マーク」します。GCルートとは、プログラムが直接アクセスできる変数（グローバル変数、スタック上の変数、レジスタ内の値など）が参照するオブジェクトのことです。
  2. スイープフェーズ (Sweep Phase): マークされなかった（到達不可能な）オブジェクトを「スイープ」（解放）し、それらのメモリを再利用可能にします。

GoのGCは、並行（Concurrent）かつ並列（Parallel）に動作するように設計されています。

  • 並行 (Concurrent): GCの一部がアプリケーションの実行と同時に動作します。これにより、アプリケーションの一時停止時間を短縮できます。
  • 並列 (Parallel): 複数のCPUコアやスレッドを使用してGCの作業を同時に実行します。これにより、GCの全体的なスループットが向上します。

GCルート (GC Roots)

GCルートは、ガベージコレクタがオブジェクトの到達可能性を判断するための出発点となるオブジェクトの集合です。これらは、GCによって「生きている」と見なされるオブジェクトの最小限のセットであり、ここから参照をたどることで、プログラムが現在使用しているすべてのオブジェクトを特定できます。

一般的なGCルートの種類には以下が含まれます。

  • グローバル変数: プログラム全体からアクセス可能な変数。
  • スタック変数: 現在実行中の関数のスタックフレームにあるローカル変数や引数。
  • レジスタ: CPUのレジスタに格納されている値。
  • ファイナライザ: オブジェクトがGCされる直前に実行される関数が登録されているオブジェクト。
  • データセグメント: プログラムの静的データが格納されている領域。

並列処理と ParFor

Goランタイムには、並列処理を効率的に行うための内部メカニズムがあります。このコミットで言及されているParForは、Goランタイムが内部的に使用する並列ループの抽象化であると考えられます。これは、指定された数のイテレーションを複数のヘルパースレッドに分散して実行させるためのものです。

ゴルーチン (Goroutines) の管理

Goのゴルーチンは、軽量な並行実行単位です。Goランタイムは、多数のゴルーチンを効率的にスケジューリングし、実行する必要があります。ゴルーチンの管理方法（リンクリストか配列か）は、ランタイムのパフォーマンス、特にGCのような全ゴルーチンを走査する必要がある操作に大きな影響を与えます。

  • リンクリスト: ゴルーチンがリンクリストで管理されている場合、特定のゴルーチンにアクセスするにはリストを先頭から順にたどる必要があります。これはO(N)の時間計算量がかかります。
  • 配列: ゴルーチンが配列で管理されている場合、インデックスを使って直接アクセスできます。これはO(1)の時間計算量で、特に多数のゴルーチンが存在する場合に高速です。

g0 とスタック

g0は、Goランタイムが内部的な処理（スケジューリング、GC、システムコールなど）を実行するために使用する特別なゴルーチンです。g0は、通常のゴルーチンとは異なる、より大きな固定サイズのスタックを持っています。Goランタイムの内部処理は、g0のスタック上で実行されることが多く、スタックのサイズや使用方法には制約があります。

技術的詳細

このコミットの核心は、GoのGCにおける「マークフェーズ」の初期段階、特にGCルートの収集方法の抜本的な変更にあります。

従来のルート収集の課題

以前のGo GCでは、GCが開始されると、まずすべてのアプリケーションゴルーチンを停止し（World-Stop）、その間にGCルートを明示的に収集していました。このルート収集は、以下の要素をグローバルなObj構造体の配列（work.roots）に追加する形で行われていました。

  • データセグメント (data, bss)
  • ファイナライザ (allfin)
  • MSpanの型情報 (MSpan.types)
  • MSpanの特殊情報 (MSpan.specials、特にファイナライザが登録されたオブジェクト）
  • すべてのゴルーチンのスタック

このaddroots関数は単一スレッドで実行され、すべてのGCルートを収集し終えるまで、他のGC作業やアプリケーションの実行をブロックしていました。これは、GC一時停止時間の主要な原因の一つとなっていました。

新しい並列ルートスキャン

このコミットでは、addroots関数が完全に削除され、GCルートの明示的な収集がなくなりました。代わりに、gc関数内でruntime·parforsetup(work.markfor, work.nproc, RootCount + runtime·allglen, nil, false, markroot)という呼び出しが行われます。

  • work.markfor: 並列マーク処理のためのParForディスクリプタ。
  • work.nproc: GCヘルパースレッドの数。
  • RootCount + runtime·allglen: これが並列処理のイテレーション数となります。
    • RootCountは、データセグメント、BSSセグメント、ファイナライザ、スパンタイプ、キャッシュフラッシュといった固定のGCルートの種類を表す定数（このコミットで導入されたRootDataからRootFlushCachesまでの5種類）。
    • runtime·allglenは、現在存在するゴルーチンの総数です。
  • markroot: 各イテレーションで呼び出されるコールバック関数。

markroot関数は、引数i（イテレーションインデックス）に基づいて、どの種類のGCルートをスキャンするかを決定します。

  • i < RootCountの場合: 固定のGCルート（データ、BSS、ファイナライザ、スパンタイプ、キャッシュフラッシュ）を処理します。これらのルートは、enqueue1関数を使ってWorkbuf（GC作業キュー）に追加され、その後scanblockによってスキャンされます。
  • i >= RootCountの場合: i - RootCountをインデックスとしてruntime·allg配列から特定のゴルーチンを取得し、そのゴルーチンのスタックをaddstackroots関数を使ってスキャンします。

このアプローチにより、GCルートの収集とスキャンが並列化され、単一スレッドでのボトルネックが解消されます。

ゴルーチン管理の変更

この並列ルートスキャンを実現するために、すべてのゴルーチンを直接インデックスでアクセスできる必要があります。そのため、runtime·allgがリンクリスト（G* runtime·allg;とG* alllink;）から動的配列（G** runtime·allg;とuintptr runtime·allglen;）に変更されました。

  • src/pkg/runtime/proc.cにおいて、runtime·allgがG*からG**に、runtime·allglenが追加され、allglockというロックが導入されています。
  • allgadd関数が新設され、ゴルーチンが作成される際にこの配列に動的に追加されるようになりました。必要に応じて配列のサイズも拡張されます。
  • これにより、markroot関数内でruntime·allg[i - RootCount]のように直接ゴルーチンにアクセスできるようになりました。

DebugScan機能の削除

DebugScanは、GCのデバッグ目的で使用されていた機能ですが、このコミットで削除されました。コミットメッセージによると、DebugScanは無制限のスタックを使用するため、g0上で実行できないという根本的な問題がありました。また、現在のGCアルゴリズムとは大きく異なるため、デバッグツールとしての有用性が低いと判断されました。この変更により、コードベースが簡素化され、将来のGC改善の妨げとなる要素が一つ排除されました。

パフォーマンスへの影響

コミットメッセージに記載されているベンチマーク結果は、この変更の有効性を示しています。

  • gc-pause-one (単一のGC一時停止時間) が6.56%削減。
  • gc-pause-total (GC一時停止の合計時間) が7.13%削減。
  • cputime (CPU時間) はほぼ変化なし。
  • sys-stack (システムスタック使用量) が3.41%増加していますが、これはゴルーチンを配列で管理するためのオーバーヘッドや、並列スキャンによる一時的なスタック使用量の増加が考えられます。

これらの結果は、GCの一時停止時間を短縮するという主要な目標が達成されたことを示しています。

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

このコミットは、主に以下のファイルに影響を与えています。

  1. src/pkg/runtime/mgc0.c:

    • GCルートを明示的に収集するaddroots関数が削除されました。
    • markroot関数が大幅に書き換えられ、並列処理のコールバックとして機能し、RootData、RootBss、RootFinalizers、RootSpanTypes、RootFlushCaches、そしてゴルーチンのスタックを並列にスキャンするように変更されました。
    • scanblock関数が簡素化され、DebugMark関連のコードが削除されました。
    • scanstack関数が削除され、addstackroots関数がWorkbufポインタを受け取るように変更され、runtime·gentracebackを直接呼び出すようになりました。
    • enqueue1という新しいヘルパー関数が追加され、Workbufへのオブジェクトの追加を簡素化しています。
    • flushallmcaches関数が独立した関数として抽出されました。
    • gc関数内のruntime·parforsetupの呼び出しが変更され、RootCount + runtime·allglenをイテレーション数として渡すようになりました。

  2. src/pkg/runtime/mprof.goc:

    • GoroutineProfile関数内で、ゴルーチンをリンクリストで走査していた部分が、runtime·allg配列をインデックスで走査するように変更されました。

  3. src/pkg/runtime/proc.c:

    • runtime·allgがリンクリストのヘッドポインタから、ゴルーチンポインタの配列（G** runtime·allg;）に変更されました。
    • runtime·allglenとallgcapが追加され、配列の長さと容量を管理します。
    • allglockというロックが追加され、runtime·allg配列へのアクセスを保護します。
    • allgaddという新しい関数が追加され、新しいゴルーチンをruntime·allg配列に追加する責任を負います。
    • runtime·tracebackothers、runtime·gcount、checkdead、runtime·schedtraceなどの関数で、ゴルーチンをリンクリストで走査していた部分が、runtime·allg配列をインデックスで走査するように変更されました。

  4. src/pkg/runtime/runtime.h:

    • G構造体からalllinkフィールドが削除されました。
    • runtime·allgの宣言がG*からG**に変更され、runtime·allglenが追加されました。

コアとなるコードの解説

src/pkg/runtime/mgc0.c の変更点

markroot 関数の刷新

static void
markroot(ParFor *desc, uint32 i)
{
	Workbuf *wbuf;
	FinBlock *fb;
	MSpan **allspans, *s;
	uint32 spanidx;
	G *gp;

	USED(&desc);
	wbuf = getempty(nil); // 新しいWorkbufを取得

	switch(i) {
	case RootData:
		enqueue1(&wbuf, (Obj){data, edata - data, (uintptr)gcdata});
		break;

	case RootBss:
		enqueue1(&wbuf, (Obj){bss, ebss - bss, (uintptr)gcbss});
		break;

	case RootFinalizers:
		for(fb=allfin; fb; fb=fb->alllink)
			enqueue1(&wbuf, (Obj){(byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]), 0});
		break;

	case RootSpanTypes:
		// mark span types and MSpan.specials (to walk spans only once)
		allspans = runtime·mheap.allspans;
		for(spanidx=0; spanidx<runtime·mheap.nspan; spanidx++) {
			Special *sp;
			SpecialFinalizer *spf;

			s = allspans[spanidx];
			if(s->state != MSpanInUse)
				continue;
			// ... (型情報とファイナライザの処理) ...
		}
		break;

	case RootFlushCaches:
		flushallmcaches();
		break;

	default:
		// the rest is scanning goroutine stacks
		if(i - RootCount >= runtime·allglen)
			runtime·throw("markroot: bad index");
		gp = runtime·allg[i - RootCount]; // 配列からゴルーチンを直接取得
		// ... (ゴルーチンの状態チェック) ...
		addstackroots(gp, &wbuf); // スタックルートを追加
		break;
	}

	if(wbuf)
		scanblock(wbuf, false); // Workbufをスキャン
}

このmarkroot関数は、ParForによって並列に実行される各タスクのコールバックです。iの値に基づいて、データセグメント、BSSセグメント、ファイナライザ、スパンタイプ、キャッシュフラッシュ、または特定のゴルーチンのスタックを処理します。これにより、GCルートの収集が並列化され、単一スレッドのボトルネックが解消されます。

addroots 関数の削除

以前のaddroots関数は、すべてのGCルートを単一スレッドで収集していましたが、このコミットで完全に削除されました。これにより、GCのマークフェーズにおける初期の単一スレッド処理がなくなりました。

src/pkg/runtime/proc.c の変更点

runtime·allg の配列化

// 以前: G* runtime·allg;
// 変更後:
static	Lock allglock;	// the following vars are protected by this lock or by stoptheworld
G**	runtime·allg;
uintptr runtime·allglen;
static	uintptr allgcap;

runtime·allgがリンクリストのヘッドポインタから、ゴルーチンポインタの動的配列に変更されました。runtime·allglenは配列の現在の長さ、allgcapは容量を示します。allglockは、この配列への並行アクセスを保護するためのロックです。

allgadd 関数の追加

static void
allgadd(G *gp)
{
	G **new;
	uintptr cap;

	runtime·lock(&allglock);
	if(runtime·allglen >= allgcap) {
		cap = 4096/sizeof(new[0]);
		if(cap < 2*allgcap)
			cap = 2*allgcap;
		new = runtime·malloc(cap*sizeof(new[0]));
		if(new == nil)
			runtime·throw("runtime: cannot allocate memory");
		if(runtime·allg != nil) {
			runtime·memmove(new, runtime·allg, runtime·allglen*sizeof(new[0]));
			runtime·free(runtime·allg);
		}
		runtime·allg = new;
		allgcap = cap;
	}
	runtime·allg[runtime·allglen++] = gp;
	runtime·unlock(&allglock);
}

この関数は、新しいゴルーチンが作成されるたびに呼び出され、runtime·allg配列にゴルーチンを追加します。配列の容量が不足している場合は、新しいより大きな配列を割り当て、既存のゴルーチンをコピーします。これにより、ゴルーチンへのO(1)アクセスが可能になります。

ゴルーチン走査の変更

runtime·tracebackothers、runtime·gcount、checkdead、runtime·schedtraceなどの関数で、以前はfor(gp = runtime·allg; gp; gp = gp->alllink)のようにリンクリストを走査していましたが、変更後はfor(i = 0; i < runtime·allglen; i++) { gp = runtime·allg[i]; ... }のように配列をインデックスで走査するようになりました。これにより、これらの操作のパフォーマンスが向上します。

関連リンク

  • Goのガベージコレクションに関する公式ドキュメントやブログ記事
  • Goのランタイムソースコード（特にsrc/runtimeディレクトリ）
  • Goの並行処理とスケジューリングに関する資料

参考にした情報源リンク

  • Goの公式ドキュメント
  • Goのソースコード
  • Goのガベージコレクションに関する技術ブログや論文
  • コミットメッセージに記載されているGo CL (Change List) のリンク: https://golang.org/cl/46860043