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

このコミットは、Goランタイムのガベージコレクタ（GC）において、オブジェクトのマーキング処理における同期メカニズムを改善するものです。具体的には、従来のロック（lock()）を用いた排他制御を、アトミック操作であるCompare-And-Swap Pointer（casp()）に置き換えることで、GCの並行性を向上させ、パフォーマンスのボトルネックを解消することを目的としています。

コミット

commit 2924638d2631bf30f490e30ed120c4089c716b71
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Fri Mar 15 09:02:36 2013 +0100

    runtime: replace lock() with casp() in the GC
    
    Note: BitTarget will be removed by a forthcoming changeset.
    
    R=golang-dev, dvyukov
    CC=golang-dev, rsc
    https://golang.org/cl/7837044

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

https://github.com/golang/go/commit/2924638d2631bf30f490e30ed120c4089c716b71

元コミット内容

Goランタイムのガベージコレクタにおいて、ロック（lock()）を使用していた箇所をcasp()（Compare-And-Swap Pointer）に置き換える変更です。この変更は、将来のコミットでBitTargetが削除されることにも関連しています。

変更の背景

Goのガベージコレクタは、プログラムの実行と並行して動作する並行GC（Concurrent GC）を採用しています。並行GCでは、複数のゴルーチン（Goの軽量スレッド）が同時にヒープ上のオブジェクトを操作する可能性があるため、GCのマーキング処理（どのオブジェクトがまだ使用されているかを識別するプロセス）において、データの一貫性を保つための同期メカニズムが不可欠です。

従来のGC実装では、オブジェクトのマークビット（オブジェクトがマーク済みかどうかを示すフラグ）を更新する際に、ミューテックス（lock()とunlock()）を使用して排他制御を行っていました。しかし、ロックは粒度が粗く、複数のゴルーチンが同時にマーク処理を行おうとすると、ロックの競合が発生し、GCの並行性が阻害され、結果としてアプリケーション全体のパフォーマンスが低下するボトルネックとなる可能性がありました。特に、GCのマークフェーズは頻繁に実行されるため、このボトルネックは顕著になります。

このコミットの背景には、このようなロック競合によるパフォーマンス低下を解消し、GCの並行性をさらに高めるという目的があります。ロックの代わりにアトミックなCompare-And-Swap（CAS）操作を使用することで、ロックフリーまたはロックアボイダンスなデータ構造を実現し、複数のゴルーチンが同時にマークビットを更新しようとした場合でも、競合を最小限に抑え、より効率的な並行処理を可能にします。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはやどの部分からも参照されなくなった（到達不能になった）メモリ領域を自動的に解放し、再利用可能にする仕組みです。これにより、プログラマは手動でのメモリ管理から解放され、メモリリークやダングリングポインタといった問題のリスクを低減できます。GoのGCは、主に「マーク・アンド・スイープ（Mark-and-Sweep）」アルゴリズムをベースにしています。

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

GoのGCは、アプリケーションの実行と並行してマークフェーズの一部を実行する「並行GC」であり、アプリケーションの一時停止時間（ストップ・ザ・ワールド、STW）を最小限に抑えるように設計されています。

並行性 (Concurrency) と並列性 (Parallelism)

並行性 (Concurrency): 複数のタスクが「同時に進行しているように見える」状態を指します。これは、シングルコアCPU上でも、タスクを高速に切り替えることで実現できます。Goのゴルーチンとチャネルは、並行プログラミングを容易にするための強力なプリミティブです。
並列性 (Parallelism): 複数のタスクが「実際に同時に実行されている」状態を指します。これは、マルチコアCPU上で、異なるコアが異なるタスクを同時に実行することで実現されます。

GCの文脈では、並行GCはアプリケーションとGCが並行して動作することを意味し、CASのようなアトミック操作は、複数のCPUコアが同時にメモリを操作する際の並列性を安全に実現するために重要です。

ロック (Mutexes)

ミューテックス（Mutex、Mutual Exclusionの略）は、共有リソースへのアクセスを制御するための同期プリミティブです。複数のスレッドやゴルーチンが同時に同じ共有リソースにアクセスしようとすると、データ競合が発生し、プログラムの動作が予測不能になる可能性があります。ミューテックスは、一度に一つのスレッド/ゴルーチンだけが共有リソースにアクセスできるようにすることで、この問題を解決します。

lock(): ミューテックスをロックします。すでにロックされている場合は、ロックが解放されるまで呼び出し元のスレッド/ゴルーチンはブロックされます。
unlock(): ミューテックスをアンロックします。これにより、他の待機中のスレッド/ゴルーチンがロックを取得できるようになります。

ロックはシンプルで強力な同期メカニズムですが、粒度が粗い場合や競合が多い場合には、パフォーマンスのボトルネックとなる可能性があります。ロックの取得と解放にはオーバーヘッドがあり、また、ロックが保持されている間は他のスレッド/ゴルーチンが待機しなければならないため、並列性が低下します。

Compare-And-Swap (CAS) 操作

Compare-And-Swap（CAS）は、アトミックな（不可分な）操作の一種です。これは、メモリ上の特定のアドレスにある値が、期待する値と一致する場合にのみ、その値を新しい値に更新するという操作です。この一連の操作は、他のスレッド/ゴルーチンによる割り込みなしに、単一の不可分なステップとして実行されます。

CAS操作は通常、以下の3つの引数を取ります。

メモリ上のアドレス (Memory Address): 操作対象のメモリ位置。
期待する値 (Expected Value): メモリ上の現在値がこの値と一致することを期待する値。
新しい値 (New Value): 期待する値と一致した場合に、メモリ上の値を更新する新しい値。

CAS操作は、成功した場合はtrue（または新しい値）、失敗した場合はfalse（または古い値）を返します。失敗した場合、それは他のスレッド/ゴルーチンが期待する値が読み取られた後にメモリ上の値を変更したことを意味します。この場合、呼び出し元のスレッド/ゴルーチンは通常、操作を再試行します。

CASは、ロックを使用せずに並行データ構造を構築するための基本的な構成要素です。ロックフリーアルゴリズムやロックアボイダンスアルゴリズムにおいて、競合を最小限に抑えながら並行性を高めるために広く使用されます。Goのsync/atomicパッケージには、CAS操作を含むアトミック操作が提供されています。このコミットで言及されているruntime·caspは、Goランタイム内部で使用されるCAS操作です。

技術的詳細

このコミットの核心は、GoランタイムのGCにおけるオブジェクトのマーク処理を、ロックベースの同期からCASベースの同期へと移行することです。これは、特にマルチプロセッサ環境下でのGCの効率と並行性を大幅に向上させるための重要な変更です。

`markonly` 関数の変更

markonly関数は、特定のオブジェクトをマークする役割を担っています。変更前は、この関数がスレッドセーフではないとコメントされていましたが、変更後は「この関数はオブジェクトをどのバッファにも追加しない」というコメントに変わっています。これは、マーク処理自体がアトミックに行われるようになったため、バッファへの追加とは独立して安全に実行できるようになったことを示唆しています。

最も重要な変更は、markonly関数内でオブジェクトのマークビットを更新する部分です。

変更前:
```
*bitp |= bitMarked<<shift;
```
これは単なるビット演算による更新であり、複数のゴルーチンが同時に同じ*bitpを更新しようとすると、競合状態が発生し、マークが正しく設定されない可能性がありました。
変更後:
```
if(work.nproc == 1)
	*bitp |= bitMarked<<shift;
else {
	for(;;) {
		x = *bitp;
		if(x & (bitMarked<<shift))
			return false;
		if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
			break;
	}
}
```
この変更により、システムがシングルプロセッサ（work.nproc == 1）の場合は従来通りの直接更新を行いますが、マルチプロセッサ環境の場合はCASループを使用するようになりました。
1. x = *bitp;: 現在のマークビットの状態を読み取ります。
2. if(x & (bitMarked<<shift)) return false;: 既にマークされている場合は、何もせずにfalseを返します。これは、他のゴルーチンが既にこのオブジェクトをマークしたことを意味します。
3. if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift)))) break;: ここがCAS操作の核心です。*bitpの値がx（読み取った時点の値）と一致する場合にのみ、x|(bitMarked<<shift)（マークビットを立てた新しい値）に更新します。CASが成功すればループを抜けます。
4. CASが失敗した場合（つまり、xを読み取った後に他のゴルーチンが*bitpの値を変更した場合）、ループは続行され、再度*bitpを読み取り、CASを再試行します。これにより、競合が発生しても最終的には正しくマークが設定されることが保証されます。

このCASループの導入により、オブジェクトのマーク処理はロックフリーで並行に実行できるようになり、ロック競合によるパフォーマンス低下が回避されます。

`flushptrbuf` 関数の変更

flushptrbuf関数は、ポインタバッファをフラッシュし、そこに含まれるオブジェクトをマークして、必要に応じてワークバッファに追加する役割を担っています。この関数における変更は、主に以下の点です。

BitTarget構造体と関連コードの削除: 変更前は、BitTargetという構造体とそれに関連するbitbufpos, btといった変数が存在し、マークすべきオブジェクトのビット情報が一時的にbitbufに格納されていました。その後、runtime·lock(&lock)とruntime·unlock(&lock)で保護されたループ内で、bitbuf内の各BitTargetに対してマーク処理が行われていました。このコミットでは、BitTarget構造体、bitbufpos変数、およびbitbufを介したマーク処理のループが完全に削除されています。これは、オブジェクトのマーク処理がmarkonly関数内で直接CASによって並行に行われるようになったため、マーク情報を一時的にバッファリングして後でまとめてロック下で処理する必要がなくなったことを意味します。
flushptrbuf内のマーク処理のインライン化とCAS化: flushptrbufのマルチスレッドバージョン（// Multi-threaded version.コメント以下）において、各オブジェクトのマーク処理がmarkonly関数と同様にCASループに置き換えられました。
```
// 変更前:
// *bitbufpos++ = (BitTarget){obj, ti, bitp, shift};
// ...
// runtime·lock(&lock);
// for(bt=bitbuf; bt<bitbufpos; bt++){
//     ...
//     *bt->bitp = xbits | (bitMarked << bt->shift); // ロック下でのマーク
// ...
// runtime·unlock(&lock);

// 変更後:
if(work.nproc == 1)
	*bitp |= bitMarked<<shift;
else {
	for(;;) {
		x = *bitp;
		if(x & (bitMarked<<shift))
			goto continue_obj; // 既にマーク済みなら次のオブジェクトへ
		if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
			break;
	}
}
```
これにより、flushptrbuf内でもオブジェクトのマークがロックフリーで実行されるようになり、GCの並行性がさらに向上します。goto continue_obj;は、CASが失敗して既にマークされていることが判明した場合に、現在のオブジェクトの処理をスキップして次のオブジェクトに移るためのものです。

`scanblock` 関数の変更

scanblock関数は、マークされたオブジェクトをスキャンし、そこから参照されている他のオブジェクトをマークする役割を担っています。ここでも、markonly関数の呼び出し方が変更されています。

変更前:

runtime·lock(&lock);
didmark = markonly(hmap);
runtime·unlock(&lock);
if(didmark) { ... }

markonlyの呼び出しがロックで囲まれていました。

変更後:
```
if(markonly(hmap)) { ... }
```
markonly関数自体がCASによってスレッドセーフになったため、呼び出し側で明示的にロックする必要がなくなりました。これにより、scanblock内でのハッシュマップ（hmap）のマーク処理も並行性が向上します。同様に、d.st（スタックトレース関連のデータ）のマーク処理もロックが削除されています。

これらの変更は、GoのGCがより多くのCPUコアを効率的に利用し、アプリケーションの実行を妨げることなく、より高速にガベージコレクションを実行できるようにするための重要なステップです。ロックの粒度を細かくするのではなく、ロック自体を排除することで、スケーラビリティとパフォーマンスを向上させています。

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

`src/pkg/runtime/mgc0.c`

`markonly` 関数内 (L191付近)

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -191,7 +191,7 @@ static struct {

 // markonly marks an object. It returns true if the object
 // has been marked by this function, false otherwise.
-// This function isn\'t thread-safe and doesn\'t append the object to any buffer.\n+// This function doesn\'t append the object to any buffer.
 static bool
 markonly(void *obj)
 {
@@ -254,7 +254,17 @@ found:
 	// Only care about allocated and not marked.
 	if((bits & (bitAllocated|bitMarked)) != bitAllocated)
 		return false;
-	*bitp |= bitMarked<<shift;
+	if(work.nproc == 1)
+		*bitp |= bitMarked<<shift;
+	else {
+		for(;;) {
+			x = *bitp;
+			if(x & (bitMarked<<shift))
+				return false;
+			if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
+				break;
+		}
+	}

 	// The object is now marked
 	return true;

`flushptrbuf` 関数内 (L325付近)

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -325,7 +335,6 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
 	Obj *wp;
 	Workbuf *wbuf;
 	PtrTarget *ptrbuf_end;
-	BitTarget *bitbufpos, *bt;

 	arena_start = runtime·mheap->arena_start;

@@ -359,8 +368,6 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
 	{
 		// Multi-threaded version.

-		bitbufpos = bitbuf;
-
 		while(ptrbuf < ptrbuf_end) {
 			obj = ptrbuf->p;
 			ti = ptrbuf->ti;
@@ -438,26 +445,22 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
 			// Only care about allocated and not marked.
 			if((bits & (bitAllocated|bitMarked)) != bitAllocated)
 				continue;
-
-			*bitbufpos++ = (BitTarget){obj, ti, bitp, shift};
-		}
-
-		runtime·lock(&lock);
-		for(bt=bitbuf; bt<bitbufpos; bt++){
-			xbits = *bt->bitp;
-			bits = xbits >> bt->shift;
-			if((bits & bitMarked) != 0)
-				continue;
-
-			// Mark the block
-			*bt->bitp = xbits | (bitMarked << bt->shift);
+			if(work.nproc == 1)
+				*bitp |= bitMarked<<shift;
+			else {
+				for(;;) {
+					x = *bitp;
+					if(x & (bitMarked<<shift))
+						goto continue_obj;
+					if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
+						break;
+				}
+			}

 			// If object has no pointers, don\'t need to scan further.
 			if((bits & bitNoPointers) != 0)
 				continue;

-			obj = bt->p;
-
 			// Ask span about size class.
 			// (Manually inlined copy of MHeap_Lookup.)
 			x = (uintptr)obj >> PageShift;
@@ -467,11 +470,11 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
 
 			PREFETCH(obj);
 
-			*wp = (Obj){obj, s->elemsize, bt->ti};
+			*wp = (Obj){obj, s->elemsize, ti};
 			wp++;
 			nobj++;
+		continue_obj:;
 		}
-		runtime·unlock(&lock);

 		// If another proc wants a pointer, give it some.
 		if(work.nwait > 0 && nobj > handoffThreshold && work.full == 0) {

`scanblock` 関数内 (L894付近)

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -894,10 +897,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n 			pc += 3;\n 			continue;\n 		}\n-		runtime·lock(&lock);\n-		didmark = markonly(hmap);\n-		runtime·unlock(&lock);\n-		if(didmark) {\n+		if(markonly(hmap)) {\n 			maptype = (MapType*)pc[2];\n 			if(hash_gciter_init(hmap, &map_iter)) {\n 				mapkey_size = maptype->key->size;\
@@ -927,11 +927,9 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n 				if(objbufpos+2 >= objbuf_end)\n 					flushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);\n 
-			if(d.st != nil) {\n-				runtime·lock(&lock);\
+			if(d.st != nil)\n 					markonly(d.st);\
-				runtime·unlock(&lock);\
-			}\n+
 			if(d.key_data != nil) {\n 				if(!(mapkey_kind & KindNoPointers) || d.indirectkey) {\n 					if(!d.indirectkey)\

コアとなるコードの解説

`markonly` 関数の変更

コメントの変更: // This function isn't thread-safe and doesn't append the object to any buffer. から // This function doesn't append the object to any buffer. へと変更されました。これは、markonly関数自体がCAS操作によってスレッドセーフになったことを示唆しています。
CASループの導入: 最も重要な変更は、オブジェクトのマークビットを立てる部分です。
- if(work.nproc == 1): システムがシングルプロセッサの場合、競合の心配がないため、従来の直接ビット操作（*bitp |= bitMarked<<shift;）でマークします。
- else { for(;;) { ... } }: マルチプロセッサ環境では、CASループが使用されます。
  - x = *bitp;: 現在のマークビットの状態を読み取ります。
  - if(x & (bitMarked<<shift)) return false;: 読み取った時点で既にマークされている場合、他のゴルーチンが先にマークしたことを意味するため、falseを返して処理を終了します。
  - if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift)))) break;: runtime·caspは、*bitpがx（読み取った時点の値）と一致する場合にのみ、*bitpを新しい値（マークビットを立てた値）に更新します。この操作はアトミックに行われます。CASが成功すればループを抜けます。失敗した場合（他のゴルーチンがxを読み取った後に*bitpを変更した場合）、ループは続行され、再試行されます。このCASループにより、複数のゴルーチンが同時に同じオブジェクトをマークしようとしても、ロックを使用せずに安全かつ効率的にマーク処理が行えるようになります。

`flushptrbuf` 関数の変更

BitTarget関連の削除: BitTarget構造体、bitbufpos変数、およびbitbufを介したマーク処理のループが削除されました。これは、オブジェクトのマーク処理がmarkonly関数内で直接CASによって並行に行われるようになったため、マーク情報を一時的にバッファリングして後でまとめてロック下で処理する必要がなくなったためです。これにより、コードが簡素化され、不要な同期オーバーヘッドが削減されます。
マーク処理のCAS化: flushptrbuf内の各オブジェクトのマーク処理も、markonly関数と同様のCASループに置き換えられました。これにより、flushptrbufが処理するオブジェクトのマークもロックフリーで実行されるようになり、GCの並行性がさらに向上します。goto continue_obj;は、CASが失敗して既にマークされていることが判明した場合に、現在のオブジェクトの処理をスキップして次のオブジェクトに移るための最適化です。

`scanblock` 関数の変更

ロックの削除: scanblock関数内でmarkonly(hmap)やmarkonly(d.st)を呼び出す際に、以前はruntime·lock(&lock)とruntime·unlock(&lock)で囲まれていました。markonly関数自体がCASによってスレッドセーフになったため、これらの明示的なロックが不要になりました。これにより、scanblock内でのオブジェクトのマーク処理もロック競合なしに並行して実行できるようになり、GCの効率が向上します。

これらの変更は、Goランタイムのガベージコレクタが、マルチコアプロセッサの能力を最大限に活用し、アプリケーションの実行をよりスムーズにするための重要な進化を示しています。ロックの代わりにCASを使用することで、より細かい粒度での並行処理が可能になり、GCの一時停止時間をさらに短縮し、全体的なアプリケーションのスループットを向上させることができます。

参考にした情報源リンク

https://github.com/golang/go/commit/2924638d2631bf30f490e30ed120c4089c716b71
Go言語のガベージコレクションに関する一般的な知識
並行プログラミングにおけるロックとアトミック操作に関する一般的な知識
Compare-And-Swap (CAS) の概念に関する一般的な情報

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

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

並行性 (Concurrency) と並列性 (Parallelism)

ロック (Mutexes)

Compare-And-Swap (CAS) 操作

技術的詳細

`markonly` 関数の変更

`flushptrbuf` 関数の変更

`scanblock` 関数の変更

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

`src/pkg/runtime/mgc0.c`

`markonly` 関数内 (L191付近)

`flushptrbuf` 関数内 (L325付近)

`scanblock` 関数内 (L894付近)

コアとなるコードの解説

`markonly` 関数の変更

`flushptrbuf` 関数の変更

`scanblock` 関数の変更

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo