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

このコミットは、Goランタイムのガベージコレクション（GC）のマークフェーズを高速化することを目的としています。具体的には、GCの並列処理能力を向上させ、ロックフリーなデータ構造を導入することで、GCの一時停止時間と全体的な実行時間を削減しています。

コミット

commit b0702bd0dba1451f908f9d503a82a8fd3cf3f2c9
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu May 24 10:55:50 2012 +0400

    runtime: faster GC mark phase
    Also bump MaxGcproc to 8.
    
    benchmark             old ns/op    new ns/op    delta
    Parser               3796323000   3763880000   -0.85%
    Parser-2             3591752500   3518560250   -2.04%
    Parser-4             3423825250   3334955250   -2.60%
    Parser-8             3304585500   3267014750   -1.14%
    Parser-16            3313615750   3286160500   -0.83%
    
    Tree                  984128500    942501166   -4.23%
    Tree-2                932564444    883266222   -5.29%
    Tree-4                835831000    799912777   -4.30%
    Tree-8                819238500    789717333   -3.73%
    Tree-16               880837833    837840055   -5.13%
    
    Tree2                 604698100    579716900   -4.13%
    Tree2-2               372414500    356765200   -4.20%
    Tree2-4               187488100    177455900   -5.56%
    Tree2-8               136315300    102086700  -25.11%
    Tree2-16               93725900     76705800  -22.18%
    
    ParserPause           157441210    166202783   +5.56%
    ParserPause-2          93842650     85199900   -9.21%
    ParserPause-4          56844404     53535684   -5.82%
    ParserPause-8          35739446     30767613  -16.15%
    ParserPause-16         32718255     27212441  -16.83%
    
    TreePause              29610557     29787725   +0.60%
    TreePause-2            24001659     20674421  -13.86%
    TreePause-4            15114887     12842781  -15.03%
    TreePause-8            13128725     10741747  -22.22%
    TreePause-16           16131360     12506901  -22.47%
    
    Tree2Pause           2673350920   2651045280   -0.83%
    Tree2Pause-2         1796999200   1709350040   -4.88%
    Tree2Pause-4         1163553320   1090706480   -6.67%
    Tree2Pause-8          987032520    858916360  -25.11%
    Tree2Pause-16         864758560    809567480   -6.81%
    
    ParserLastPause       280537000    289047000   +3.03%
    ParserLastPause-2     183030000    166748000   -8.90%
    ParserLastPause-4     105817000     91552000  -13.48%
    ParserLastPause-8      65127000     53288000  -18.18%
    ParserLastPause-16     45258000     38334000  -15.30%
    
    TreeLastPause          45072000     51449000  +12.39%
    TreeLastPause-2        39269000     37866000   -3.57%
    TreeLastPause-4        23564000     20649000  -12.37%
    TreeLastPause-8        20881000     15807000  -24.30%
    TreeLastPause-16       23297000     17309000  -25.70%
    
    Tree2LastPause       6046912000   5797120000   -4.13%
    Tree2LastPause-2     3724034000   3567592000   -4.20%
    Tree2LastPause-4     1874831000   1774524000   -5.65%
    Tree2LastPause-8     1363108000   1020809000  -12.79%
    Tree2LastPause-16     937208000    767019000  -22.18%
    
    R=rsc, 0xe2.0x9a.0x9b
    CC=golang-dev
    https://golang.org/cl/6223050

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

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

元コミット内容

GoランタイムのGCマークフェーズを高速化し、MaxGcproc の値を8に引き上げます。

ベンチマーク結果は以下の通りです。

変更の背景

このコミットが行われた2012年当時、Goのガベージコレクタは「ストップ・ザ・ワールド（Stop-The-World, STW）」方式を採用しており、GC実行中はアプリケーションの実行が完全に停止していました。特に、GCのマークフェーズは、到達可能なオブジェクトを全て探索する必要があるため、ヒープサイズが大きくなるにつれてSTW時間が長くなる傾向にありました。これは、リアルタイム性が求められるアプリケーションや、レイテンシに敏感なサービスにとって大きな問題となります。

このコミットの主な目的は、GCのマークフェーズをより効率的に、そして並列に実行できるようにすることで、STW時間を短縮し、全体的なアプリケーションのパフォーマンスを向上させることにあります。特に、マルチコアプロセッサの普及に伴い、より多くのCPUコアをGCに活用できるようにすることは、スケーラビリティの観点からも重要でした。MaxGcproc の引き上げは、この並列化の恩恵を最大限に引き出すための変更です。

ベンチマーク結果を見ると、特にTree2やTreePause系のベンチマークで大幅な改善が見られます。これは、GCの一時停止時間（Pause）が短縮されたことを示しており、ユーザー体験の向上に直結します。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはや使用されていない（到達不可能になった）ものを自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ管理から解放され、メモリリークなどのバグを減らすことができます。

GoのGCは、主に以下のフェーズで構成されます。

1. マークフェーズ (Mark Phase): プログラムのルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトを特定し、マークします。マークされたオブジェクトは「生きている」と判断され、解放されません。
2. スイープフェーズ (Sweep Phase): マークされなかったオブジェクト（「死んでいる」オブジェクト）をメモリから解放し、その領域を再利用可能にします。

このコミットは、特にマークフェーズの効率化に焦点を当てています。

ストップ・ザ・ワールド (Stop-The-World, STW)

STWは、GCが実行される際に、アプリケーションの全てのゴルーチン（スレッド）の実行を一時的に停止させる期間を指します。STW中、アプリケーションは一切処理を進めることができません。STW時間が長くなると、アプリケーションの応答性が低下し、ユーザー体験に悪影響を与えます。GoのGCは、このSTW時間を最小限に抑えることを目標として進化してきました。

並列処理と並行処理

• 並行処理 (Concurrency): 複数のタスクが同時に進行しているように見える状態。Goのゴルーチンとチャネルは並行処理を実現するための強力なプリミティブです。
• 並列処理 (Parallelism): 複数のタスクが物理的に同時に実行されている状態。マルチコアCPU上で複数のゴルーチンが同時に実行されることで実現されます。

このコミットでは、GCのマークフェーズを複数のCPUコアで並列に実行することで、処理時間を短縮しています。

ロックフリーデータ構造 (Lock-Free Data Structures)

複数のスレッドが共有データにアクセスする際、データの整合性を保つためにロック（ミューテックスなど）を使用するのが一般的です。しかし、ロックは競合が発生するとスレッドのブロックを引き起こし、パフォーマンスのボトルネックとなる可能性があります。

ロックフリーデータ構造は、ロックを使用せずに複数のスレッドが同時にデータ構造を操作できるように設計されたものです。通常、アトミック操作（Compare-And-Swap, CASなど）を利用して、競合が発生した場合でもスレッドがブロックされることなく処理を続行できるようにします。これにより、並列処理におけるスケーラビリティとパフォーマンスが向上します。このコミットでは、GCのワークバッファ管理にロックフリースタックが導入されています。

GCルート (GC Roots)

GCルートとは、ガベージコレクタがオブジェクトの到達可能性を判断する際の起点となるオブジェクトのことです。これらは常に「生きている」と見なされ、ここから参照されているオブジェクトも「生きている」と判断されます。一般的なGCルートには以下のようなものがあります。

• グローバル変数: プログラム全体からアクセス可能な変数。
• スタック上の変数: 現在実行中の関数のローカル変数や引数。
• レジスタ: CPUのレジスタに格納されている値。

GCのマークフェーズでは、これらのルートからヒープ上のオブジェクトグラフを辿り、到達可能なオブジェクトをマークしていきます。

技術的詳細

このコミットは、GoランタイムのGCマークフェーズを大幅に改善するために、以下の主要な技術的変更を導入しています。

1. MaxGcproc の引き上げ:

   • src/pkg/runtime/malloc.h において、GCが利用できる最大プロセッサ数を示す MaxGcproc の値を 4 から 8 に変更しています。
   • これにより、GCのマークフェーズがより多くのCPUコアを並列に利用できるようになり、マルチコア環境でのGC性能が向上します。コメントも「collector scales well to 4 cpus」から「collector scales well to 8 cpus」に変更されています。

2. ロックフリーなワークバッファ管理の導入:

   • src/pkg/runtime/mgc0.c において、GCのマークフェーズで使用されるワークバッファ（Workbuf）の管理方法が、ロックベースからロックフリーな方式へと変更されています。
   • Workbuf 構造体に LFNode node; が追加され、work 構造体の full と empty リストが Lock から uint64 型のロックフリースタック（runtime·lfstackpush, runtime·lfstackpop を使用）に変更されました。
   • これにより、複数のGCワーカーゴルーチンがワークバッファの取得・解放を行う際の競合が減少し、スケーラビリティが向上します。特に、getempty, putempty, getfull, handoff 関数がロックフリー操作を使用するように書き換えられています。

3. GCルートの並列スキャン:

   • GCのマークフェーズの開始時に、データセグメント、スタック、ファイナライザを持つオブジェクトなど、すべてのGCルートを事前に収集する新しいメカニズムが導入されました。
   • GcRoot 構造体と addroot 関数が追加され、runtime·gc 関数内で addroots() が呼び出され、すべてのルートが work.roots 配列に格納されます。
   • その後、runtime·parforsetup と runtime·parfordo を使用して、これらのルートを並列にスキャンする markroot 関数が実行されます。これにより、ルートスキャン自体も並列化され、STW時間の短縮に貢献します。
   • 以前は mark(scanblock) のように直接 scanblock を呼び出してルートをスキャンしていましたが、この変更により、ルートの収集とスキャンが分離され、並列処理に適した形になりました。

4. ワークスティーリングの改善:

   • scanblock 関数内で、他のプロセッサがポインタを必要としている場合に、現在処理中のワークバッファから一部のオブジェクトを「横取り（steal）」させるロジックが改善されました。
   • 具体的には、if(work.nwait > 0 && nobj > 4 && work.full == 0) という条件が追加され、より積極的にワークを他の待機中のプロセッサに渡すようになっています。これにより、GCワーカー間の負荷分散が効率化され、全体のスループットが向上します。

これらの変更は、GoのGCがより並列に動作し、マルチコア環境でのパフォーマンスを最大限に引き出すための重要なステップでした。特に、ロックフリーデータ構造の採用は、GCのボトルネックを解消し、STW時間の削減に大きく貢献しています。

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

src/pkg/runtime/malloc.h

--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -124,8 +124,8 @@ enum
 	// Max number of threads to run garbage collection.
 	// 2, 3, and 4 are all plausible maximums depending
 	// on the hardware details of the machine.  The garbage
-	// collector scales well to 4 cpus.
-	MaxGcproc = 4,
+	// collector scales well to 8 cpus.
+	MaxGcproc = 8,
 };

src/pkg/runtime/mgc0.c

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -13,6 +13,7 @@ enum {
 	Debug = 0,
 	PtrSize = sizeof(void*),
 	DebugMark = 0,  // run second pass to check mark
+	DataBlock = 8*1024,
 
 	// Four bits per word (see #defines below).\
 	wordsPerBitmapWord = sizeof(void*)*8/4,
@@ -72,9 +73,9 @@ static int32 gctrace;
 typedef struct Workbuf Workbuf;
 struct Workbuf
 {
-	Workbuf *next;\n+\tLFNode node; // must be first
 	uintptr nobj;
-	byte *obj[512-2];\n+\tbyte *obj[512-(sizeof(LFNode)+sizeof(uintptr))/sizeof(byte*)];
 };
 
 typedef struct Finalizer Finalizer;
@@ -112,21 +113,32 @@ static Workbuf* getfull(Workbuf*);
 static void	putempty(Workbuf*);
 static Workbuf* handoff(Workbuf*);
 
+typedef struct GcRoot GcRoot;
+struct GcRoot
+{
+	byte *p;
+	uintptr n;
+};
+
 static struct {
-	Lock fmu;
-	Workbuf	*full;
-	Lock emu;
-	Workbuf	*empty;
+	uint64	full;  // lock-free list of full blocks
+	uint64	empty; // lock-free list of empty blocks
+	byte	pad0[CacheLineSize]; // prevents false-sharing between full/empty and nproc/nwait
 	uint32	nproc;
 	volatile uint32	nwait;
 	volatile uint32	ndone;
 	volatile uint32 debugmarkdone;
 	Note	alldone;
+	ParFor	*markfor;
 	ParFor	*sweepfor;
 
 	Lock;
 	byte	*chunk;
 	uintptr	nchunk;
+
+	GcRoot	*roots;
+	uint32	nroot;
+	uint32	rootcap;
 } work;
 
 // scanblock scans a block of n bytes starting at pointer b for references
@@ -162,7 +174,7 @@ scanblock(byte *b, int64 n)
 	nobj = 0;  // number of queued objects
 
 	// Scanblock helpers pass b==nil.
-	// The main proc needs to return to make more
+	// Procs needs to return to make more
 	// calls to scanblock.  But if work.nproc==1 then
 	// might as well process blocks as soon as we
 	// have them.
@@ -246,6 +258,14 @@ scanblock(byte *b, int64 n)
 			bits = xbits >> shift;
 
 		found:
+			// If another proc wants a pointer, give it some.
+			if(work.nwait > 0 && nobj > 4 && work.full == 0) {
+				wbuf->nobj = nobj;
+				wbuf = handoff(wbuf);
+				nobj = wbuf->nobj;
+				wp = wbuf->obj + nobj;
+			}
+
 			// Now we have bits, bitp, and shift correct for
 			// obj pointing at the base of the object.
 			// Only care about allocated and not marked.
@@ -269,14 +289,6 @@ scanblock(byte *b, int64 n)
 
 			PREFETCH(obj);
 
-			// If another proc wants a pointer, give it some.
-			if(nobj > 4 && work.nwait > 0 && work.full == nil) {
-				wbuf->nobj = nobj;
-				wbuf = handoff(wbuf);
-				nobj = wbuf->nobj;
-				wp = wbuf->obj + nobj;
-			}
-
 			// If buffer is full, get a new one.
 			if(wbuf == nil || nobj >= nelem(wbuf->obj)) {
 				if(wbuf != nil)
@@ -296,7 +308,8 @@ scanblock(byte *b, int64 n)
 		// Fetch b from the work buffer.
 		if(nobj == 0) {
 			if(!keepworking) {
-				putempty(wbuf);
+				if(wbuf)
+					putempty(wbuf);
 				return;
 			}
 			// Emptied our buffer: refill.
@@ -401,53 +414,33 @@ debug_scanblock(byte *b, int64 n)
 	}
 }
 
+static void
+markroot(ParFor *desc, uint32 i)
+{
+	USED(&desc);
+	scanblock(work.roots[i].p, work.roots[i].n);
+}
+
 // Get an empty work buffer off the work.empty list,
 // allocating new buffers as needed.
 static Workbuf*
 getempty(Workbuf *b)
 {
-	if(work.nproc == 1) {
-		// Put b on full list.
-		if(b != nil) {
-			b->next = work.full;
-			work.full = b;
-		}
-		// Grab from empty list if possible.
-		b = work.empty;
-		if(b != nil) {
-			work.empty = b->next;
-			goto haveb;
-		}
-	} else {
-		// Put b on full list.
-		if(b != nil) {
-			runtime·lock(&work.fmu);
-			b->next = work.full;
-			work.full = b;
-			runtime·unlock(&work.fmu);
-		}
-		// Grab from empty list if possible.
-		runtime·lock(&work.emu);
-		b = work.empty;
-		if(b != nil)
-			work.empty = b->next;
-		runtime·unlock(&work.emu);
-		if(b != nil)
-			goto haveb;
-	}
-
-	// Need to allocate.
-	runtime·lock(&work);
-	if(work.nchunk < sizeof *b) {
-		work.nchunk = 1<<20;
-		work.chunk = runtime·SysAlloc(work.nchunk);
-	}
-	b = (Workbuf*)work.chunk;
-	work.chunk += sizeof *b;
-	work.nchunk -= sizeof *b;
-	runtime·unlock(&work);
-
-haveb:
+	if(b != nil)
+		runtime·lfstackpush(&work.full, &b->node);
+	b = (Workbuf*)runtime·lfstackpop(&work.empty);
+	if(b == nil) {
+		// Need to allocate.
+		runtime·lock(&work);
+		if(work.nchunk < sizeof *b) {
+			work.nchunk = 1<<20;
+			work.chunk = runtime·SysAlloc(work.nchunk);
+		}
+		b = (Workbuf*)work.chunk;
+		work.chunk += sizeof *b;
+		work.nchunk -= sizeof *b;
+		runtime·unlock(&work);
+	}
 	b->nobj = 0;
 	return b;
 }
@@ -455,19 +448,7 @@ haveb:
 static void
 putempty(Workbuf *b)
 {
-	if(b == nil)
-		return;
-
-	if(work.nproc == 1) {
-		b->next = work.empty;
-		work.empty = b;
-		return;
-	}
-
-	runtime·lock(&work.emu);
-	b->next = work.empty;
-	work.empty = b;
-	runtime·unlock(&work.emu);
+	runtime·lfstackpush(&work.empty, &b->node);
 }
 
 // Get a full work buffer off the work.full list, or return nil.
@@ -475,54 +456,21 @@ static Workbuf*
 getfull(Workbuf *b)
 {
 	int32 i;
-	Workbuf *b1;
-
-	if(work.nproc == 1) {
-		// Put b on empty list.
-		if(b != nil) {
-			b->next = work.empty;
-			work.empty = b;
-		}
-		// Grab from full list if possible.
-		// Since work.nproc==1, no one else is
-		// going to give us work.
-		b = work.full;
-		if(b != nil)
-			work.full = b->next;
+
+	if(b != nil)
+		runtime·lfstackpush(&work.empty, &b->node);
+	b = (Workbuf*)runtime·lfstackpop(&work.full);
+	if(b != nil || work.nproc == 1)
 		return b;
-	}
-
-	putempty(b);
-
-	// Grab buffer from full list if possible.
-	for(;;) {
-		b1 = work.full;
-		if(b1 == nil)
-			break;
-		runtime·lock(&work.fmu);
-		if(work.full != nil) {
-			b1 = work.full;
-			work.full = b1->next;
-			runtime·unlock(&work.fmu);
-			return b1;
-		}
-		runtime·unlock(&work.fmu);
-		continue;
-	}
 
 	runtime·xadd(&work.nwait, +1);
 	for(i=0;; i++) {
-		b1 = work.full;
-		if(b1 != nil) {
-			runtime·lock(&work.fmu);
-			if(work.full != nil) {
-				runtime·xadd(&work.nwait, -1);
-				b1 = work.full;
-				work.full = b1->next;
-				runtime·unlock(&work.fmu);
-				return b1;
-			}
-			runtime·unlock(&work.fmu);
-			continue;
+		if(work.full != 0) {
+			runtime·xadd(&work.nwait, -1);
+			b = (Workbuf*)runtime·lfstackpop(&work.full);
+			if(b != nil)
+				return b;
+			runtime·xadd(&work.nwait, +1);
 		}
 		if(work.nwait == work.nproc)
 			return nil;
@@ -555,17 +503,35 @@ handoff(Workbuf *b)
 	m->gcstats.nhandoffcnt += n;
 
 	// Put b on full list - let first half of b get stolen.
-	runtime·lock(&work.fmu);
-	b->next = work.full;
-	work.full = b;
-	runtime·unlock(&work.fmu);
-
+	runtime·lfstackpush(&work.full, &b->node);
 	return b1;
 }
 
-// Scanstack calls scanblock on each of gp's stack segments.
 static void
-scanstack(void (*scanblock)(byte*, int64), G *gp)
+addroot(byte *p, uintptr n)
+{
+	uint32 cap;
+	GcRoot *new;
+
+	if(work.nroot >= work.rootcap) {
+		cap = PageSize/sizeof(GcRoot);
+		if(cap < 2*work.rootcap)
+			cap = 2*work.rootcap;
+		new = (GcRoot*)runtime·SysAlloc(cap*sizeof(GcRoot));
+		if(work.roots != nil) {
+			runtime·memmove(new, work.roots, work.rootcap*sizeof(GcRoot));
+			runtime·SysFree(work.roots, work.rootcap*sizeof(GcRoot));
+		}
+		work.roots = new;
+		work.rootcap = cap;
+	}
+	work.roots[work.nroot].p = p;
+	work.roots[work.nroot].n = n;
+	work.nroot++;
+}
+
+static void
+addstackroots(G *gp)
 {
 	M *mp;
 	int32 n;
@@ -598,15 +564,13 @@ scanstack(void (*scanblock)(byte*, int64), G *gp)
 		}
 	}
 
-	if(Debug > 1)
-		runtime·printf("scanstack %d %p\n", gp->goid, sp);
 	n = 0;
 	while(stk) {
 		if(sp < guard-StackGuard || (byte*)stk < sp) {
 			runtime·printf("scanstack inconsistent: g%d#%d sp=%p not in [%p,%p]\n", gp->goid, n, sp, guard-StackGuard, stk);
 			runtime·throw("scanstack");
 		}
-		scanblock(sp, (byte*)stk - sp);
+		addroot(sp, (byte*)stk - sp);
 		sp = stk->gobuf.sp;
 		guard = stk->stackguard;
 		stk = (Stktop*)stk->stackbase;
@@ -614,30 +578,22 @@ scanstack(void (*scanblock)(byte*, int64), G *gp)
 	}
 }
 
-// Markfin calls scanblock on the blocks that have finalizers:
-// the things pointed at cannot be freed until the finalizers have run.
 static void
-markfin(void *v)
+addfinroots(void *v)
 {
 	uintptr size;
 
 	if(!runtime·mlookup(v, &v, &size, nil))
 		runtime·throw("mark - finalizer inconsistency");
 
 	// do not mark the finalizer block itself.  just mark the things it points at.
-	scanblock(v, size);
-}
-
-static void
-debug_markfin(void *v)
-{
-	uintptr size;
-
-	if(!runtime·mlookup(v, &v, &size, nil))
-		runtime·throw("debug_mark - finalizer inconsistency");
-	debug_scanblock(v, size);
+	addroot(v, size);
 }
 
-// Mark
 static void
-mark(void (*scan)(byte*, int64))
+addroots(void)
 {
 	G *gp;
 	FinBlock *fb;
+	byte *p;
+
+	work.nroot = 0;
 
 	// mark data+bss.
-	scan(data, ebss - data);
+	for(p=data; p<ebss; p+=DataBlock)
+		addroot(p, p+DataBlock < ebss ? DataBlock : ebss-p);
 
-	// mark stacks
 	for(gp=runtime·allg; gp!=nil; gp=gp->alllink) {
 		switch(gp->status){
 		default:
@@ -648,27 +594,20 @@ mark(void (*scan)(byte*, int64))
 		case Grunning:
 			if(gp != g)
 				runtime·throw("mark - world not stopped");
-			scanstack(scan, gp);
+			addstackroots(gp);
 			break;
 		case Grunnable:
 		case Gsyscall:
 		case Gwaiting:
-			scanstack(scan, gp);
+			addstackroots(gp);
 			break;
 		}
 	}
 
-	// mark things pointed at by objects with finalizers
-	if(scan == debug_scanblock)
-		runtime·walkfintab(debug_markfin);
-	else
-		runtime·walkfintab(markfin);
+	runtime·walkfintab(addfinroots);
 
 	for(fb=allfin; fb; fb=fb->alllink)
-		scanblock((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
-
-	// in multiproc mode, join in the queued work.
-	scan(nil, 0);
+		addroot((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
 }
 
 static bool
@@ -825,6 +768,9 @@ sweepspan(ParFor *desc, uint32 idx)
 void
 runtime·gchelper(void)
 {
+	// parallel mark for over gc roots
+	runtime·parfordo(work.markfor);
+	// help other threads scan secondary blocks
 	scanblock(nil, 0);
 
 	if(DebugMark) {
@@ -902,6 +848,7 @@ runtime·gc(int32 force)
 	uint64 heap0, heap1, obj0, obj1;
 	byte *p;
 	GCStats stats;
+	uint32 i;
 
 	// The gc is turned off (via enablegc) until
 	// the bootstrap has completed.\n@@ -953,6 +904,10 @@ runtime·gc(int32 force)
 	work.ndone = 0;
 	work.debugmarkdone = 0;
 	work.nproc = runtime·gcprocs();
+	addroots();
+	if(work.markfor == nil)
+		work.markfor = runtime·parforalloc(MaxGcproc);
+	runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
 	if(work.sweepfor == nil)
 		work.sweepfor = runtime·parforalloc(MaxGcproc);
 	runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap.nspan, nil, true, sweepspan);
@@ -961,9 +916,12 @@ runtime·gc(int32 force)
 		runtime·helpgc(work.nproc);
 	}
 
-	mark(scanblock);
+	runtime·parfordo(work.markfor);
+	scanblock(nil, 0);
+
 	if(DebugMark) {
-		mark(debug_scanblock);
+		for(i=0; i<work.nroot; i++)
+			debug_scanblock(work.roots[i].p, work.roots[i].n);
 		runtime·atomicstore(&work.debugmarkdone, 1);
 	}
 	t1 = runtime·nanotime();

コアとなるコードの解説

src/pkg/runtime/malloc.h の変更

• MaxGcproc の値を 4 から 8 に変更しています。これは、GCのマークフェーズが最大8つのCPUコアを並列に利用できるようになったことを意味します。これにより、マルチコア環境でのGCのスループットが向上し、GCの一時停止時間が短縮される可能性があります。

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

1. Workbuf 構造体の変更:

   • Workbuf はGCのマークフェーズ中にオブジェクトポインタを一時的に格納するためのバッファです。以前は Workbuf *next; を用いて単方向リストを形成していましたが、この変更で LFNode node; が追加されました。LFNode はロックフリースタックの要素として機能し、ロックフリーなデータ構造への移行を示しています。
   • obj 配列のサイズ計算も LFNode のサイズを考慮するように変更され、メモリレイアウトの整合性を保っています。

2. work 構造体の変更:

   • work 構造体はGCのグローバルな状態を管理します。
   • Lock fmu; と Lock emu; (full/empty work buffer mutex) が削除され、代わりに uint64 full; と uint64 empty; が導入されました。これらはロックフリースタックのヘッドポインタとして機能します。
   • ParFor *markfor; と GcRoot *roots;, uint32 nroot;, uint32 rootcap; が追加されました。これらはGCルートの並列スキャンをサポートするための新しいフィールドです。markfor は並列処理フレームワーク ParFor のインスタンスを指し、roots はスキャン対象のGCルートの配列、nroot はルートの数、rootcap はルート配列の容量を示します。

3. scanblock 関数の変更:

   • scanblock はメモリブロックをスキャンし、到達可能なオブジェクトをマークする主要な関数です。
   • ワークスティーリングのロジックが改善されました。以前は nobj > 4 && work.nwait > 0 && work.full == nil という条件でワークを渡していましたが、新しいコードでは if(work.nwait > 0 && nobj > 4 && work.full == 0) となり、より積極的にワークを他の待機中のプロセッサに渡すようになっています。work.full == 0 はロックフリースタックが空であることを意味し、他のプロセッサがワークを必要としている可能性が高い状況を示します。

4. getempty, putempty, getfull, handoff 関数の変更:

   • これらの関数はワークバッファの取得、解放、およびワークスティーリングの際に使用されます。
   • 以前はロック（runtime·lock, runtime·unlock）を使用していましたが、このコミットにより runtime·lfstackpush と runtime·lfstackpop といったロックフリーなアトミック操作を使用するように変更されました。これにより、これらの操作における競合が大幅に減少し、GCの並列性が向上します。

5. GCルート処理の変更 (addroot, addstackroots, addfinroots, addroots, markroot):

   • GcRoot 構造体と addroot 関数: 新たに GcRoot 構造体が定義され、addroot 関数が導入されました。addroot は、スキャンすべきメモリ領域（ポインタ p とサイズ n）を work.roots 配列に追加します。必要に応じて work.roots 配列は動的に拡張されます。
   • addstackroots と addfinroots: 以前は scanstack や markfin が直接 scanblock を呼び出していましたが、これらの関数は addroot を呼び出すように変更されました。これにより、スタックやファイナライザを持つオブジェクトからのルートが、まず work.roots 配列に収集されるようになりました。
   • addroots 関数: この新しい関数は、データセグメント、すべてのゴルーチンのスタック、およびファイナライザを持つオブジェクトからのすべてのGCルートを work.roots 配列に収集します。
   • markroot 関数: ParFor フレームワークによって並列に実行される関数です。work.roots 配列から一つのGCルートを取り出し、そのルートが指すメモリ領域を scanblock でスキャンします。

6. runtime·gc 関数の変更:

   • GCのメインエントリポイントである runtime·gc 関数内で、GCマークフェーズの開始時に addroots() が呼び出され、すべてのGCルートが収集されます。
   • その後、runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot); が呼び出され、収集されたルートを MaxGcproc で指定された数のプロセッサで並列に markroot 関数を使ってスキャンするように設定されます。
   • 最後に runtime·parfordo(work.markfor); が呼び出され、GCルートの並列スキャンが開始されます。
   • 以前の mark(scanblock); の呼び出しは削除され、より洗練された並列ルートスキャンメカニズムに置き換えられました。

これらの変更により、GoのGCマークフェーズは、ロックの競合を減らし、複数のCPUコアを効率的に利用することで、より高速かつ並列に実行されるようになりました。

関連リンク

• Goのガベージコレクションに関する公式ドキュメントやブログ記事（コミット当時の情報を見つけるのは難しいかもしれませんが、GoのGCの進化の歴史を辿る上で参考になります）
• ロックフリーデータ構造に関する一般的な情報源

参考にした情報源リンク

• Goのソースコード (特に src/pkg/runtime/mgc0.c と src/pkg/runtime/malloc.h)
• Goのコミット履歴
• Goのガベージコレクションに関する一般的な知識
• 並列処理とロックフリーデータ構造に関する一般的なコンピュータサイエンスの知識