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

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

このコミットは、Goランタイムのガベージコレクション（GC）における並列スキャンフェーズのパフォーマンス改善を目的としています。具体的には、src/pkg/runtime/mgc0.c と src/pkg/runtime/proc.c の2つのファイルが変更されています。

  • src/pkg/runtime/mgc0.c: Goランタイムのガベージコレクタの主要なロジックが含まれています。特に、オブジェクトのスキャン、ワークバッファの管理、GCヘルパーの動作に関連する部分が変更されています。
  • src/pkg/runtime/proc.c: Goランタイムのプロセッサ（M）、ゴルーチン（G）、スケジューラ（P）の管理に関連するコードが含まれています。GCヘルパーのM（OSスレッド）への割り当てと管理に関する変更が含まれています。

コミット

このコミットは、Goランタイムの並列ガベージコレクションの高速化を目的としています。グローバルなミューテックスで保護されたプールを使用する代わりに、スレッドごとのワークバッファを使用することで、並列スキャンフェーズにおける競合を排除しています。これにより、GCのパフォーマンスが大幅に向上しています。

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

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

元コミット内容

runtime: faster parallel GC
Use per-thread work buffers instead of global mutex-protected pool. This eliminates contention from parallel scan phase.

benchmark                             old ns/op    new ns/op    delta
garbage.BenchmarkTree2-8               97100768     71417553  -26.45%
garbage.BenchmarkTree2LastPause-8     970931485    714103692  -26.45%
garbage.BenchmarkTree2Pause-8         469127802    345029253  -26.45%
garbage.BenchmarkParser-8            2880950854   2715456901   -5.74%
garbage.BenchmarkParserLastPause-8    137047399    103336476  -24.60%
garbage.BenchmarkParserPause-8         80686028     58922680  -26.97%

R=golang-dev, 0xe2.0x9a.0x9b, dave, adg, rsc, iant
CC=golang-dev
https://golang.org/cl/7816044

変更の背景

この変更の主な背景は、Goランタイムのガベージコレクション（GC）のパフォーマンスボトルネックの解消です。特に、並列GCのスキャンフェーズにおいて、複数のGCヘルパーゴルーチン（またはM/OSスレッド）が共有のワークバッファプールにアクセスする際に発生する競合（コンテンション）が問題となっていました。

従来のGoのGCは、並列処理を行う際に、GCヘルパーがマーク済みオブジェクトを処理するためのワークバッファをグローバルなプールから取得し、処理後にそのプールに戻していました。このグローバルプールへのアクセスはミューテックスによって保護されていたため、複数のGCヘルパーが同時にアクセスしようとすると、ミューテックスのロック/アンロックが頻繁に発生し、これがパフォーマンスの低下を引き起こしていました。特に、CPUコア数が多い環境や、大量のオブジェクトを処理するアプリケーションでは、この競合が顕著になり、GCの一時停止時間（ポーズタイム）の増加や全体のスループットの低下につながっていました。

このコミットは、この競合を緩和し、GCの効率を向上させることを目的としています。ベンチマーク結果が示すように、GC関連の操作において大幅な時間短縮が実現されており、これはGCの一時停止時間の削減とアプリケーション全体の応答性向上に直結します。

前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

  1. ガベージコレクション (GC):

    • プログラムが動的に確保したメモリ領域のうち、もはや使用されなくなった領域を自動的に解放する仕組みです。これにより、メモリリークを防ぎ、開発者が手動でメモリ管理を行う手間を省きます。
    • GoのGCは「並行（concurrent）」かつ「並列（parallel）」なマーク＆スイープ方式を採用しています。
      • 並行GC: アプリケーションの実行とGCのマークフェーズが同時に進行します。これにより、GCによるアプリケーションの一時停止時間を最小限に抑えます。
      • 並列GC: GCの特定のフェーズ（例: マーク、スキャン）が複数のCPUコアやスレッドを使って同時に実行されます。これにより、GCの処理時間を短縮します。

  2. マーク＆スイープ方式:

    • マークフェーズ: プログラムが現在使用している（到達可能な）オブジェクトを特定し、マークします。ルートセット（グローバル変数、スタック上の変数など）から参照をたどり、到達可能なすべてのオブジェクトにマークを付けます。
    • スイープフェーズ: マークされなかった（到達不可能な）オブジェクトを「ガベージ」とみなし、それらが占めていたメモリ領域を解放し、再利用可能にします。

  3. ワークバッファ:

    • GCのマークフェーズにおいて、到達可能なオブジェクトを探索する際に、次にスキャンすべきオブジェクトのポインタを一時的に格納するためのデータ構造です。
    • 並列GCでは、複数のGCヘルパーが同時にオブジェクトをスキャンするため、それぞれがワークバッファを使用して作業を進めます。

  4. ミューテックス (Mutex):

    • "Mutual Exclusion"（相互排他）の略で、複数のスレッドが共有リソースに同時にアクセスするのを防ぐための同期メカニズムです。
    • ミューテックスがロックされている間は、他のスレッドはそのリソースにアクセスできず、ロックが解放されるまで待機します。
    • 頻繁なロック/アンロックは、特に競合が多い場合に、スレッドの待機時間やコンテキストスイッチのオーバーヘッドにより、パフォーマンスのボトルネックとなることがあります。

  5. 競合 (Contention):

    • 複数のスレッドやプロセスが同時に同じ共有リソース（例: ミューテックスで保護されたデータ構造、共有メモリ領域）にアクセスしようとするときに発生する状況です。
    • 競合が高いと、スレッドはリソースの解放を待つ必要があり、並列処理の効率が低下します。

  6. GoランタイムのM, P, G:

    • Goのスケジューラは、M（Machine/OSスレッド）、P（Processor/論理プロセッサ）、G（Goroutine）という3つの主要なエンティティで構成されます。
    • G (Goroutine): Goの軽量な並行実行単位。数百万個作成することも可能です。
    • P (Processor): Goの論理プロセッサ。Gを実行するためのコンテキストを提供します。通常、CPUコア数と同じかそれ以上のPが作成されます。
    • M (Machine): OSスレッド。Pに割り当てられ、Gを実行します。
    • GCヘルパーは、これらのM/P/Gの仕組みを利用して並列に動作します。特に、GC中は一部のMがGCヘルパーとして動作し、GCタスクを処理します。m->helpgc は、MがGCヘルパーとして動作しているかどうか、およびどのGCヘルパーに割り当てられているかを示すフラグとして使用されます。

技術的詳細

このコミットの核心は、並列GCのスキャンフェーズにおけるワークバッファの管理方法を、グローバルなミューテックス保護されたプールから、スレッド（M）ごとの専用ワークバッファへと変更した点にあります。

変更前は、BufferList *bufferList というグローバルなポインタがワークバッファのリンクリストの先頭を指しており、scanblock 関数内でワークバッファを取得・解放する際に runtime·lock(&lock) と runtime·unlock(&lock) を使用してグローバルなミューテックス lock を取得・解放していました。これにより、複数のGCヘルパーが同時にワークバッファにアクセスしようとすると、ミューテックスの競合が発生し、並列処理の効率が低下していました。

変更後は、以下の点が大きく異なります。

  1. BufferList の配列化とミューテックスの削除:

    • static BufferList *bufferList; が static BufferList bufferList[MaxGcproc]; に変更されました。これは、BufferList がグローバルなリンクリストではなく、MaxGcproc（最大GCヘルパー数）分の要素を持つ静的な配列になったことを意味します。
    • これにより、各GCヘルパー（M）は、配列の自身のインデックスに対応するBufferList要素を直接使用できるようになります。
    • グローバルなミューテックス static Lock lock; が削除されました。これにより、ワークバッファの取得・解放における競合が完全に排除されます。

  2. m->helpgc の活用:

    • 各M（OSスレッド）には m->helpgc というフィールドがあり、これはMがGCヘルパーとして動作している場合に、そのGCヘルパーのID（0から MaxGcproc-1 の範囲）を格納するようになりました。
    • scanblock 関数内でワークバッファを取得する際に、scanbuffers = &bufferList[m->helpgc]; のように、現在のMに割り当てられたGCヘルパーID (m->helpgc) をインデックスとして使用し、bufferList 配列から対応するワークバッファを直接取得します。これにより、ミューテックスなしで排他的なワークバッファへのアクセスが可能になります。

  3. ワークバッファのビジー状態管理:

    • BufferList 構造体に uint32 busy; フィールドが追加されました。これは、そのワークバッファが現在使用中であるかどうかを示すフラグです。
    • gchelperstart 関数が導入され、GCヘルパーが開始される際に runtime·xchg(&bufferList[m->helpgc].busy, 1) を使用して、アトミックに busy フラグを1に設定します。これにより、同じワークバッファが二重に使用されることを防ぎます。もし既にビジーであれば、ランタイムエラーをスローします。
    • GCヘルパーの処理が完了した後、bufferList[m->helpgc].busy = 0; を設定してワークバッファを解放します。

  4. proc.c における m->helpgc の設定:

    • runtime·helpgc 関数（GCヘルパーMを起動する関数）内で、各GCヘルパーMに一意の n 値（0から nproc-1）を mp->helpgc = n; として割り当てています。これにより、各GCヘルパーMが自身の専用ワークバッファを識別できるようになります。
    • mhelpgc や runtime·mstart、retry ラベルの後のコードで m->helpgc の初期化やリセットが行われ、GCヘルパーのライフサイクルとワークバッファの割り当てが適切に管理されるようになっています。

この変更により、並列GCのスキャンフェーズにおけるワークバッファの取得・解放がミューテックスフリーになり、複数のGCヘルパーが独立して作業を進められるようになりました。結果として、競合が大幅に減少し、GCの効率が向上し、ベンチマーク結果に示されるようなパフォーマンス改善が実現されました。

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

src/pkg/runtime/mgc0.c

  • BufferList 構造体の変更:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -287,11 +288,12 @@ struct BufferList
 {
 	PtrTarget ptrtarget[IntermediateBufferCapacity];
 	Obj obj[IntermediateBufferCapacity];
-	BufferList *next;
+	uint32 busy;
+	byte pad[CacheLineSize];
 };
-static BufferList *bufferList;
+#pragma dataflag 16  // no pointers
+static BufferList bufferList[MaxGcproc];
 
-static Lock lock;
 static Type *itabtype;
    • BufferList *next; が削除され、uint32 busy; と byte pad[CacheLineSize]; が追加。
    • static BufferList *bufferList; が static BufferList bufferList[MaxGcproc]; に変更。
    • static Lock lock; が削除。

  • scanblock 関数内のワークバッファ取得ロジックの変更:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -598,23 +600,11 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n \n     // Allocate ptrbuf\n     {\n    -	runtime·lock(&lock);\n    -\n    -	if(bufferList == nil) {\n    -		bufferList = runtime·SysAlloc(sizeof(*bufferList));\n    -		if(bufferList == nil)\n    -			runtime·throw("runtime: cannot allocate memory");\n    -		bufferList->next = nil;\n    -	}\n    -	scanbuffers = bufferList;\n    -	bufferList = bufferList->next;\n    -\n    +	scanbuffers = &bufferList[m->helpgc];
 	ptrbuf = &scanbuffers->ptrtarget[0];
 	ptrbuf_end = &scanbuffers->ptrtarget[0] + nelem(scanbuffers->ptrtarget);\n     	objbuf = &scanbuffers->obj[0];
 	objbuf_end = &scanbuffers->obj[0] + nelem(scanbuffers->obj);\n    -\n    -	runtime·unlock(&lock);\n     }\n    ```
- グローバルロックとリンクリストからの取得ロジックが削除され、`bufferList[m->helpgc]` から直接取得する形に変更。

  • scanblock 関数内のワークバッファ解放ロジックの変更:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -1056,11 +1046,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     	nobj--;\n     }\n     \n    -endscan:\n    -	runtime·lock(&lock);\n    -	scanbuffers->next = bufferList;\n    -	bufferList = scanbuffers;\n    -	runtime·unlock(&lock);\n    +endscan:;\n     }\n    ```
- グローバルロックとリンクリストへの解放ロジックが削除。

  • runtime·gchelper 関数と gc 関数への gchelperstart の追加:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -1688,6 +1674,8 @@ runtime·memorydump(void)\n     void\n     runtime·gchelper(void)\n     {\n    +	gchelperstart();\n    +\n     	// parallel mark for over gc roots\n     	runtime·parfordo(work.markfor);\n     \n    @@ -1701,6 +1689,7 @@ runtime·gchelper(void)\n     	}\n     \n     	runtime·parfordo(work.sweepfor);\n    +	bufferList[m->helpgc].busy = 0;\n     	if(runtime·xadd(&work.ndone, +1) == work.nproc-1)\n     		runtime·notewakeup(&work.alldone);\n     }\n    @@ -1892,6 +1881,7 @@ gc(struct gc_args *args)\n     \n     	t1 = runtime·nanotime();\n     \n    +	gchelperstart();\n     	runtime·parfordo(work.markfor);\n     	scanblock(nil, nil, 0, true);\n     \n    @@ -1903,6 +1893,7 @@ gc(struct gc_args *args)\n     	t2 = runtime·nanotime();\n     \n     	runtime·parfordo(work.sweepfor);\n    +	bufferList[m->helpgc].busy = 0;\n     	t3 = runtime·nanotime();\n     \n     	if(work.nproc > 1)\n    ```
- GCヘルパーの開始時とGCの開始時に `gchelperstart()` が呼び出され、終了時に `bufferList[m->helpgc].busy = 0;` でbusyフラグをクリア。

  • gchelperstart 関数の追加:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -2043,6 +2034,15 @@ runtime∕debug·setGCPercent(intgo in, intgo out)\n     	FLUSH(&out);\n     }\n     \n    +static void\n    +gchelperstart(void)\n    +{\n    +\tif(m->helpgc < 0 || m->helpgc >= MaxGcproc)\n    +\t\truntime·throw("gchelperstart: bad m->helpgc");\n    +\tif(runtime·xchg(&bufferList[m->helpgc].busy, 1))\n    +\t\truntime·throw("gchelperstart: already busy");\n    +}\n    +\n     static void\n     runfinq(void)\n     {\n    ```
- `m->helpgc` の範囲チェックと、アトミック操作 `runtime·xchg` を用いた `busy` フラグの設定。

src/pkg/runtime/proc.c

  • runtime·helpgc 関数内の m->helpgc の設定: 
    --- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -332,7 +332,7 @@ runtime·helpgc(int32 nproc)\n     		mp = mget();\n     		if(mp == nil)\n     			runtime·throw("runtime·gcprocs inconsistency");\n    -		mp->helpgc = 1;\n    +		mp->helpgc = n;\n     		mp->mcache = runtime·allp[pos]->mcache;\n     		pos++;\n     		runtime·notewakeup(&mp->park);\n    ```
- `mp->helpgc` に一意のGCヘルパーID `n` を割り当てるように変更。
  • mhelpgc 関数内の m->helpgc の設定: 
    --- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -386,7 +386,7 @@ runtime·stoptheworld(void)\n     static void\n     mhelpgc(void)\n     {\n    -	m->helpgc = 1;\n    +	m->helpgc = -1;\n     }\n    ```
- `m->helpgc` を `-1` に設定し、GCヘルパーではないことを示す。
  • runtime·mstart 関数内の m->helpgc の設定: 
    --- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -485,7 +485,7 @@ runtime·mstart(void)\n     		m->mstartfn();\n     \n     	if(m->helpgc) {\n    -		m->helpgc = false;\n    +		m->helpgc = 0;\n     		stopm();\n     	} else if(m != &runtime·m0) {\n     		acquirep(m->nextp);\n    ```
- `m->helpgc` を `0` に設定し、GCヘルパーの役割を終えたことを示す。
  • retry ラベル後の m->helpgc の設定: 
    --- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -794,8 +794,8 @@ retry:\n     	runtime·notesleep(&m->park);\n     	runtime·noteclear(&m->park);\n     	if(m->helpgc) {\n    -		m->helpgc = 0;\n     		runtime·gchelper();\n    +		m->helpgc = 0;\n     		m->mcache = nil;\n     		goto retry;\n     	}\n    ```
- `runtime·gchelper()` 呼び出し後にも `m->helpgc = 0;` を設定し、確実にリセット。

コアとなるコードの解説

このコミットの主要な変更は、GCのワークバッファ管理戦略を根本的に変えることで、並列GCの効率を劇的に向上させています。

  1. BufferList の配列化とミューテックスの削除:

    • 変更前は、GCヘルパーがワークバッファを必要とするたびに、グローバルなリンクリスト bufferList からバッファを取得し、使用後にそこに戻していました。この操作は lock ミューテックスによって保護されていたため、複数のGCヘルパーが同時にバッファを要求すると、ロックの競合が発生し、処理が直列化されていました。
    • 変更後は、BufferList が MaxGcproc（最大GCヘルパー数）分の要素を持つ静的な配列 bufferList[MaxGcproc] になりました。これにより、各GCヘルパーは、自身のID (m->helpgc) をインデックスとして使用し、配列内の専用のワークバッファに直接アクセスできるようになりました。
    • グローバルミューテックス lock が削除されたことで、ワークバッファの取得・解放における競合が完全に排除され、GCヘルパーは互いに干渉することなく並列に作業を進めることが可能になりました。これは、特にマルチコア環境でのGCパフォーマンスに大きな影響を与えます。

  2. m->helpgc を用いたスレッドごとのワークバッファ割り当て:

    • m->helpgc は、現在のM（OSスレッド）がGCヘルパーとして動作している場合に、そのGCヘルパーに割り当てられた一意のID（0から MaxGcproc-1）を保持します。
    • scanblock 関数内で scanbuffers = &bufferList[m->helpgc]; とすることで、現在のMが使用すべきワークバッファが直接指定されます。これにより、各GCヘルパーは他のGCヘルパーのワークバッファにアクセスすることなく、自身の専用バッファで安全に作業できます。
    • この仕組みは、共有リソースへのアクセスを排他的にするためにミューテックスを使用するのではなく、最初からリソースを分割して各スレッドに専用割り当てすることで、競合自体を発生させないという設計思想に基づいています。

  3. gchelperstart と busy フラグによるワークバッファのライフサイクル管理:

    • gchelperstart 関数は、GCヘルパーが作業を開始する直前に呼び出されます。この関数内で runtime·xchg(&bufferList[m->helpgc].busy, 1) を使用して、対応するワークバッファの busy フラグをアトミックに1に設定します。runtime·xchg は、値を設定すると同時に以前の値を返すアトミック操作であり、これにより、もし既に busy が1であれば、二重使用の試みとしてランタイムエラーをスローします。これは、ワークバッファの排他利用を保証するための重要なチェックです。
    • GCヘルパーの作業が完了すると、bufferList[m->helpgc].busy = 0; を設定して busy フラグをクリアし、ワークバッファが再利用可能になったことを示します。
    • この busy フラグと gchelperstart の導入により、各GCヘルパーが自身のワークバッファを安全かつ排他的に利用できることが保証されます。

これらの変更により、Goの並列GCは、ワークバッファの管理におけるボトルネックを解消し、より効率的に動作するようになりました。ベンチマーク結果が示すように、GCの一時停止時間と全体のスループットが大幅に改善され、Goアプリケーションのパフォーマンス向上に貢献しています。

関連リンク

参考にした情報源リンク