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

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

このコミットは、Goランタイムのガベージコレクション（GC）におけるメモリ管理の最適化に関するものです。具体的には、フリーリスト（解放されたが再利用可能なメモリブロックのリスト）内のオブジェクトの扱いを変更し、GC中にこれらのオブジェクトを「割り当て済みかつスキャン不要」としてマークするようにしました。これにより、ポインタを持たないオブジェクトをmallocする際のビット変更のオーバーヘッドを削減し、全体的なパフォーマンス向上を目指しています。

コミット

commit 2d20c0d6257f5dfc57bb8a78f4e2824803bd6d0e
Author: Keith Randall <khr@golang.org>
Date:   Wed Dec 18 17:13:59 2013 -0800

    runtime: mark objects in free lists as allocated and unscannable.
    
    On the plus side, we don't need to change the bits when mallocing
    pointerless objects. On the other hand, we need to mark objects in the
    free lists during GC. But the free lists are small at GC time, so it
    should be a net win.
    
    benchmark                    old ns/op    new ns/op    delta
    BenchmarkMalloc8                    40           33  -17.65%
    BenchmarkMalloc16                   45           38  -15.72%
    BenchmarkMallocTypeInfo8            58           59   +0.85%
    BenchmarkMallocTypeInfo16           63           64   +1.10%
    
    R=golang-dev, rsc, dvyukov
    CC=cshapiro, golang-dev
    https://golang.org/cl/41040043

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

https://github.com/golang/go/commit/2d20c0d6257f5dfc57bb8a78f4e2824803bd6d0e

元コミット内容

runtime: mark objects in free lists as allocated and unscannable.

On the plus side, we don't need to change the bits when mallocing
pointerless objects. On the other hand, we need to mark objects in the
free lists during GC. But the free lists are small at GC time, so it
should be a net win.

benchmark                    old ns/op    new ns/op    delta
BenchmarkMalloc8                    40           33  -17.65%
BenchmarkMalloc16                   45           38  -15.72%
BenchmarkMallocTypeInfo8            58           59   +0.85%
BenchmarkMallocTypeInfo16           63           64   +1.10%

R=golang-dev, rsc, dvyukov
CC=cshapiro, golang-dev
https://golang.org/cl/41040043

変更の背景

Goのランタイムは、効率的なメモリ管理とガベージコレクション（GC）を実現するために、ヒープ上のオブジェクトの状態を管理するためのビットマップを使用しています。このビットマップは、各メモリワードが割り当てられているか、ポインタを含むか、マークされているかなどの情報を示します。

以前のGoランタイムでは、オブジェクトが解放されてフリーリストに戻されると、そのメモリ領域に対応するビットマップのビットが「解放済み」の状態を示すように変更されていました。しかし、その後、同じメモリ領域がポインタを持たない（スキャン不要な）オブジェクトのために再利用される場合、再びビットマップのビットを「割り当て済みかつスキャン不要」に変更する必要がありました。このビットの変更操作は、特に頻繁に小さなオブジェクトが割り当て・解放される場合に、オーバーヘッドとなっていました。

このコミットの背景にあるのは、このオーバーヘッドを削減することです。フリーリストにあるオブジェクトは、実際にはまだGCの対象ではない（再利用される可能性がある）ため、それらを「割り当て済みかつスキャン不要」として扱うことで、malloc時のビット変更を不要にすることができます。その代わり、GCのマークフェーズ中にフリーリスト内のオブジェクトを明示的にマークする必要が生じますが、コミットメッセージにあるように、GC時のフリーリストは通常小さいため、この追加のオーバーヘッドはmalloc時の削減分を上回り、全体としてパフォーマンスが向上すると見込まれました。

ベンチマーク結果は、特に小さなオブジェクトのmallocにおいて顕著な改善（BenchmarkMalloc8とBenchmarkMalloc16で約15-17%の高速化）を示しており、この最適化が成功したことを裏付けています。ポインタ情報を持つオブジェクトのmalloc（BenchmarkMallocTypeInfo）ではわずかな性能低下が見られますが、これはポインタを持たないオブジェクトのmallocの改善によって相殺されると判断されたと考えられます。

前提知識の解説

このコミットを理解するためには、Goランタイムのメモリ管理とガベージコレクションに関する以下の概念を理解しておく必要があります。

  1. ヒープとアリーナ: Goのプログラムが動的に確保するメモリは「ヒープ」と呼ばれます。ヒープはさらに「アリーナ」と呼ばれる大きな連続したメモリ領域に分割されます。
  2. MSpan: ヒープはMSpanと呼ばれる固定サイズのページ（通常は8KB）の連続したブロックに分割されます。MSpanは、そのページがどのサイズのオブジェクトを格納しているか、フリーリストの状態などを管理します。
  3. MCache: 各P（プロセッサ、Goスケジューラにおける論理CPU）は、ローカルなメモリキャッシュであるMCacheを持っています。MCacheは、小さなオブジェクトの割り当てを高速化するために、様々なサイズのオブジェクトに対応するフリーリストを保持しています。これにより、グローバルなヒープロックを避けて、並行性を高めます。
  4. フリーリスト: 解放されたがまだ再利用されていないメモリブロックのリストです。MCacheやMSpanが管理しています。
  5. ヒープビットマップ: Goランタイムは、ヒープ上の各メモリワードの状態を追跡するためにビットマップを使用します。このビットマップは、GCがオブジェクトをスキャンし、マークするために不可欠です。各メモリワードに対応するビットは、以下のような意味を持ちます（コミット当時の定義に近いもの）：
    • bitAllocated: そのメモリワードがオブジェクトの先頭であり、割り当て済みであることを示します。
    • bitNoScan (変更前) / bitScan (変更後): bitAllocatedが設定されている場合、そのオブジェクトがポインタを含まずスキャン不要であるか（bitNoScan）、またはポインタを含みスキャンが必要であるか（bitScanが設定されていない場合）を示します。このコミットでbitNoScanからbitScanに名称が変更され、意味が反転しています（bitScanが設定されていればスキャンが必要）。
    • bitMarked: GCのマークフェーズ中に、そのオブジェクトが到達可能（生きている）としてマークされたことを示します。
    • bitSpecial: そのオブジェクトがファイナライザを持つか、プロファイリングされているかなど、特別な処理が必要であることを示します。
    • bitBlockBoundary: bitAllocatedが設定されていない場合、そのメモリワードがブロックの境界であることを示します。これは、FlagNoGC（GCの対象外）のオブジェクトや、フリーリスト内のオブジェクトのマークにも使用されます。
  6. ガベージコレクションのフェーズ: GoのGCは主に以下のフェーズで構成されます。
    • マークフェーズ: ルート（スタック、グローバル変数など）から到達可能なすべてのオブジェクトを特定し、bitMarkedビットを設定します。
    • スイープフェーズ: マークされていない（到達不可能な）オブジェクトを解放し、そのメモリをフリーリストに戻します。

このコミットは、特にヒープビットマップのbitNoScan/bitScanとbitBlockBoundaryの利用方法、およびフリーリスト内のオブジェクトのGCマークフェーズでの扱い方に焦点を当てています。

技術的詳細

このコミットの主要な変更点は以下の通りです。

  1. bitNoScanからbitScanへの変更と意味の反転:

    • 以前はbitNoScanというビットがあり、これが設定されていると「スキャン不要」を意味していました。
    • このコミットではbitNoScanがbitScanに名称変更され、意味が反転しました。bitScanが設定されていると「スキャンが必要」を意味します。これにより、ポインタを持つオブジェクトを明示的にマークする形になります。
    • src/pkg/runtime/mgc0.cのビットマップ定義で、#define bitNoScanが#define bitScanに変更されています。
    • flushptrbufやdebug_scanblockなどの関数で、if((bits & bitNoScan) != 0)がif((bits & bitScan) == 0)に変更され、スキャン要否の判定ロジックが反転しています。

  2. runtime·markallocated関数の分割と新しいマーク関数:

    • 以前はruntime·markallocated(void *v, uintptr n, bool noscan)という単一の関数で、オブジェクトの割り当てとスキャン要否のマークを行っていました。
    • このコミットでは、この関数がruntime·markscan(void *v)とruntime·marknogc(void *v)の2つの関数に分割されました。
      • runtime·markscan(void *v): スキャンが必要な（ポインタを含む）オブジェクトをマークします。bitScanビットを設定します。
      • runtime·marknogc(void *v): GCの対象外（FlagNoGC）のオブジェクトをマークします。これはbitBlockBoundaryビットを設定することで行われます。
    • src/pkg/runtime/malloc.gocのruntime·mallocgc内で、runtime·markallocatedの呼び出しが新しい関数に置き換えられています。

  3. フリーリスト内のオブジェクトのGCマーク:

    • この変更の核心は、GCのマークフェーズ中にフリーリスト内のオブジェクトを明示的にマークすることです。
    • src/pkg/runtime/mgc0.cにaddfreelists()という新しい静的関数が追加されました。この関数は、各PのMCache内のフリーリストと、各MSpanのフリーリストを走査し、そこにあるオブジェクトをmarkonly（またはsweepspan内で直接ビットを操作）することで、bitMarkedビットを設定します。
    • gc()関数（GCのメインエントリポイント）内で、addroots()の後にaddfreelists()が呼び出されるようになりました。これにより、GCが開始されるとすぐにフリーリスト内のオブジェクトがマークされ、誤って回収されるのを防ぎます。
    • sweepspan関数内でも、s->freelistを走査し、フリーリスト内のオブジェクトのbitMarkedビットを直接設定するロジックが追加されました。これは、markonly関数を呼び出すよりも高速な方法です。

  4. runtime·markfreedの変更:

    • runtime·markfreed関数は、オブジェクトが解放されてフリーリストに戻される際に呼び出されます。
    • 以前は、解放されたオブジェクトのビットをbitBlockBoundaryに設定していました。
    • このコミットでは、解放されたオブジェクトのビットをbitAllocatedに設定するように変更されました。これは、フリーリスト内のオブジェクトを「割り当て済み」として扱うという新しい戦略に合致します。これにより、ポインタを持たないオブジェクトがmallocされた際に、ビットマップのbitAllocatedビットを変更する必要がなくなります。

  5. runtime·markspanの変更:

    • runtime·markspanは、新しいMSpanがヒープに割り当てられた際に、そのスパン内のビットマップを初期化するために使用されます。
    • 以前は、各ブロックの境界にbitBlockBoundaryを設定していました。
    • このコミットでは、各ブロックの境界にbitAllocatedを設定するように変更されました。これは、新しいスパンのメモリが割り当てられた直後から、その領域が「割り当て済み」として扱われることを意味します。

これらの変更により、Goランタイムは、フリーリスト内のオブジェクトをGCの対象外として扱い、malloc時のビットマップ操作を削減することで、特に小さなポインタレスオブジェクトの割り当て性能を向上させています。

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

src/pkg/runtime/malloc.goc

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -97,8 +97,10 @@ runtime·mallocgc(uintptr size, uintptr typ, uint32 flag)
 		runtime·markspan(v, 0, 0, true);
 	}
 
-	if(!(flag & FlagNoGC))
-		runtime·markallocated(v, size, (flag&FlagNoScan) != 0);
+	if(flag & FlagNoGC)
+		runtime·marknogc(v);
+	else if(!(flag & FlagNoScan))
+		runtime·markscan(v);
 
 	if(DebugTypeAtBlockEnd)
 		*(uintptr*)((uintptr)v+size-sizeof(uintptr)) = typ;

src/pkg/runtime/malloc.h

--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -449,7 +449,8 @@ void*	runtime·mallocgc(uintptr size, uintptr typ, uint32 flag);
 void*	runtime·persistentalloc(uintptr size, uintptr align, uint64 *stat);
 int32	runtime·mlookup(void *v, byte **base, uintptr *size, MSpan **s);
 void	runtime·gc(int32 force);
-void	runtime·markallocated(void *v, uintptr n, bool noptr);
+void	runtime·markscan(void *v);
+void	runtime·marknogc(void *v);
 void	runtime·checkallocated(void *v, uintptr n);
 void	runtime·markfreed(void *v, uintptr n);
 void	runtime·checkfreed(void *v, uintptr n);

src/pkg/runtime/mgc0.c

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -81,7 +81,7 @@ clearpools(void)
 // The bits in the word are packed together by type first, then by
 // heap location, so each 64-bit bitmap word consists of, from top to bottom,
 // the 16 bitSpecial bits for the corresponding heap words, then the 16 bitMarked bits,
-// then the 16 bitNoScan/bitBlockBoundary bits, then the 16 bitAllocated bits.
+// then the 16 bitScan/bitBlockBoundary bits, then the 16 bitAllocated bits.
 // This layout makes it easier to iterate over the bits of a given type.
 //
 // The bitmap starts at mheap.arena_start and extends *backward* from
@@ -97,13 +97,13 @@ clearpools(void)
 //	bits = *b >> shift;
 //	/* then test bits & bitAllocated, bits & bitMarked, etc. */
 //
-#define bitAllocated		((uintptr)1<<(bitShift*0))
-#define bitNoScan		((uintptr)1<<(bitShift*1))	/* when bitAllocated is set */
+#define bitAllocated		((uintptr)1<<(bitShift*0))	/* block start; eligible for garbage collection */
+#define bitScan			((uintptr)1<<(bitShift*1))	/* when bitAllocated is set */
 #define bitMarked		((uintptr)1<<(bitShift*2))	/* when bitAllocated is set */
 #define bitSpecial		((uintptr)1<<(bitShift*3))	/* when bitAllocated is set - has finalizer or being profiled */
-#define bitBlockBoundary	((uintptr)1<<(bitShift*1))	/* when bitAllocated is NOT set */
+#define bitBlockBoundary	((uintptr)1<<(bitShift*1))	/* when bitAllocated is NOT set - mark for FlagNoGC objects */
 
-#define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial)
+#define bitMask (bitAllocated | bitScan | bitMarked | bitSpecial)
 
 // Holding worldsema grants an M the right to try to stop the world.
 // The procedure is:
@@ -534,7 +534,7 @@ flushptrbuf(Scanbuf *sbuf)
 		}
 
 		// If object has no pointers, don't need to scan further.
-		if((bits & bitNoScan) != 0)
+		if((bits & bitScan) == 0)
 			continue;
 
 		// Ask span about size class.
@@ -1187,7 +1187,7 @@ debug_scanblock(byte *b, uintptr n)
 			runtime·printf("found unmarked block %p in %p\n", obj, vp+i);
 
 		// If object has no pointers, don't need to scan further.
-		if((bits & bitNoScan) != 0)
+		if((bits & bitScan) == 0)
 			continue;
 
 		debug_scanblock(obj, size);
@@ -1676,6 +1676,28 @@ addroots(void)
 		addroot((Obj){(byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]), 0});
 }
 
+static void
+addfreelists(void)
+{
+	int32 i;
+	P *p, **pp;
+	MCache *c;
+	MLink *m;
+
+	// Mark objects in the MCache of each P so we don't collect them.
+	for(pp=runtime·allp; p=*pp; pp++) {
+		c = p->mcache;
+		if(c==nil)
+			continue;
+		for(i = 0; i < NumSizeClasses; i++) {
+			for(m = c->list[i].list; m != nil; m = m->next) {
+				markonly(m);
+			}
+		}
+	}
+	// Note: the sweeper will mark objects in each span's freelist.
+}
+
 static bool
 handlespecial(byte *p, uintptr size)
 {
@@ -1722,7 +1744,7 @@ static void
 sweepspan(ParFor *desc, uint32 idx)
 {
 	int32 cl, n, npages;
-	uintptr size;
+	uintptr size, off, *bitp, shift;
 	byte *p;
 	MCache *c;
 	byte *arena_start;
@@ -1732,6 +1754,17 @@ sweepspan(ParFor *desc, uint32 idx)
 	byte compression;
 	uintptr type_data_inc;
 	MSpan *s;
+	MLink *x;
 
 	USED(&desc);
 	s = runtime·mheap.allspans[idx];
@@ -1751,6 +1784,17 @@ sweepspan(ParFor *desc, uint32 idx)
 	nfree = 0;
 	end = &head;
 	c = m->mcache;
+
+	// mark any free objects in this span so we don't collect them
+	for(x = s->freelist; x != nil; x = x->next) {
+		// This is markonly(x) but faster because we don't need
+		// atomic access and we're guaranteed to be pointing at
+		// the head of a valid object.
+		off = (uintptr*)x - (uintptr*)runtime·mheap.arena_start;
+		bitp = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
+		shift = off % wordsPerBitmapWord;
+		*bitp |= bitMarked<<shift;
+	}
 	
 	type_data = (byte*)s->types.data;
 	type_data_inc = sizeof(uintptr);
@@ -1794,8 +1838,8 @@ sweepspan(ParFor *desc, uint32 idx)
 				continue;
 		}
 
-		// Mark freed; restore block boundary bit.
-		*bitp = (*bitp & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
+		// Clear mark, scan, and special bits.
+		*bitp &= ~((bitScan|bitMarked|bitSpecial)<<shift);
 
 		if(cl == 0) {
 			// Free large span.
@@ -2213,6 +2257,7 @@ gc(struct gc_args *args)
 	work.debugmarkdone = 0;
 	work.nproc = runtime·gcprocs();
 	addroots();
+	addfreelists();
 	runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
 	runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap.nspan, nil, true, sweepspan);
 	if(work.nproc > 1) {
@@ -2439,18 +2484,35 @@ runfinq(void)
 	}
 }
 
-// mark the block at v of size n as allocated.
-// If noscan is true, mark it as not needing scanning.
 void
-runtime·markallocated(void *v, uintptr n, bool noscan)
+runtime·marknogc(void *v)
 {
 	uintptr *b, obits, bits, off, shift;
 
-\tif(0)
-\t\truntime·printf("markallocated %p+%p\n", v, n);
+\toff = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;  // word offset
+\tb = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
+\tshift = off % wordsPerBitmapWord;
 
-\tif((byte*)v+n > (byte*)runtime·mheap.arena_used || (byte*)v < runtime·mheap.arena_start)
-\t\truntime·throw("markallocated: bad pointer");
+\tfor(;;) {
+\t\tobits = *b;
+\t\tif((obits>>shift & bitMask) != bitAllocated)
+\t\t\truntime·throw("bad initial state for marknogc");
+\t\tbits = (obits & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;
+\t\tif(runtime·gomaxprocs == 1) {
+\t\t\t*b = bits;
+\t\t\tbreak;
+\t\t} else {
+\t\t\t// more than one goroutine is potentially running: use atomic op
+\t\t\tif(runtime·casp((void**)b, (void*)obits, (void*)bits))\n+\t\t\t\tbreak;
+\t\t}\n+\t}\n+}\n+\n+void
+runtime·markscan(void *v)
+{
+	uintptr *b, obits, bits, off, shift;
 
 \toff = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;  // word offset
 \tb = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
@@ -2458,9 +2520,9 @@ runtime·markallocated(void *v, uintptr n, bool noscan)
 
 	for(;;) {
 		obits = *b;
-\t\tbits = (obits & ~(bitMask<<shift)) | (bitAllocated<<shift);
-\t\tif(noscan)\n-\t\t\tbits |= bitNoScan<<shift;
+\t\tif((obits>>shift & bitMask) != bitAllocated)
+\t\t\truntime·throw("bad initial state for markscan");
+\t\tbits = obits | bitScan<<shift;
 		if(runtime·gomaxprocs == 1) {
 			*b = bits;
 			break;
@@ -2490,7 +2552,10 @@ runtime·markfreed(void *v, uintptr n)
 
 	for(;;) {
 		obits = *b;
-\t\tbits = (obits & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
+\t\t// This could be a free of a gc-eligible object (bitAllocated + others) or
+\t\t// a FlagNoGC object (bitBlockBoundary set).  In either case, we revert to
+\t\t// a simple no-scan allocated object because it is going on a free list.
+\t\tbits = (obits & ~(bitMask<<shift)) | (bitAllocated<<shift);
 		if(runtime·gomaxprocs == 1) {
 			*b = bits;
 			break;
@@ -2531,12 +2596,22 @@ runtime·checkfreed(void *v, uintptr n)
 void
 runtime·markspan(void *v, uintptr size, uintptr n, bool leftover)
 {
-\tuintptr *b, off, shift;\n+\tuintptr *b, off, shift, i;
 	byte *p;
 
 	if((byte*)v+size*n > (byte*)runtime·mheap.arena_used || (byte*)v < runtime·mheap.arena_start)
 		runtime·throw("markspan: bad pointer");
 
+\tif(runtime·checking) {
+\t\t// bits should be all zero at the start
+\t\toff = (byte*)v + size - runtime·mheap.arena_start;
+\t\tb = (uintptr*)(runtime·mheap.arena_start - off/wordsPerBitmapWord);
+\t\tfor(i = 0; i < size/PtrSize/wordsPerBitmapWord; i++) {
+\t\t\tif(b[i] != 0)\n+\t\t\t\truntime·throw("markspan: span bits not zero");
+\t\t}\n+\t}\n+\n 	p = v;
 	if(leftover)	// mark a boundary just past end of last block too
 		n++;
@@ -2548,7 +2623,7 @@ runtime·markspan(void *v, uintptr size, uintptr n, bool leftover)
 		off = (uintptr*)p - (uintptr*)runtime·mheap.arena_start;  // word offset
 		b = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
 		shift = off % wordsPerBitmapWord;
-\t\t*b = (*b & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
+\t\t*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);
 	}
 }

コアとなるコードの解説

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

  • runtime·mallocgc関数は、Goのオブジェクト割り当ての主要なエントリポイントです。
  • 変更前は、FlagNoGC（GC対象外）でないオブジェクトに対してruntime·markallocatedを呼び出し、FlagNoScanフラグに基づいてスキャン要否を渡していました。
  • 変更後は、FlagNoGCが設定されている場合は新しく導入されたruntime·marknogc(v)を呼び出します。これは、GC対象外のオブジェクトをbitBlockBoundaryとしてマークします。
  • FlagNoGCが設定されておらず、かつFlagNoScanが設定されていない（つまりスキャンが必要な）場合は、新しく導入されたruntime·markscan(v)を呼び出します。これは、ポインタを含むオブジェクトをbitScanとしてマークします。
  • この変更により、オブジェクトの性質（GC対象か否か、スキャン必要か否か）に応じて、より適切なビットマップ操作を行う関数が直接呼び出されるようになりました。特に、ポインタを持たないオブジェクト（FlagNoScanが設定されている場合）は、runtime·markscanが呼び出されないため、bitScanビットが設定されず、スキャン不要であることが明示されます。

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

  • runtime·markallocated関数の宣言が削除され、代わりにruntime·markscanとruntime·marknogcの新しい2つの関数の宣言が追加されました。これは、上記malloc.gocの変更と整合性を保つためのヘッダファイルの更新です。

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

  1. ビットマップ定義の変更:

    • #define bitNoScanが#define bitScanに変更され、そのコメントも「when bitAllocated is set」に変更されました。これは、bitScanが設定されている場合にスキャンが必要であることを示します。
    • bitAllocatedのコメントに「block start; eligible for garbage collection」が追加され、bitBlockBoundaryのコメントに「mark for FlagNoGC objects」が追加されました。これにより、各ビットの役割がより明確になりました。
    • bitMaskの定義からbitBlockBoundaryが削除され、代わりにbitScanが追加されました。これは、bitMaskがbitAllocatedが設定されている場合のオブジェクトの状態ビットのマスクとして機能することを明確にします。

  2. スキャンロジックの反転:

    • flushptrbufとdebug_scanblock関数内のスキャン要否のチェックが、if((bits & bitNoScan) != 0)からif((bits & bitScan) == 0)に変更されました。これは、bitNoScanからbitScanへの意味の反転に対応するものです。bitScanが0であればスキャン不要、1であればスキャン必要となります。

  3. addfreelists()関数の追加:

    • この新しい関数は、GCのマークフェーズ中にフリーリスト内のオブジェクトをマークするために導入されました。
    • runtime·allpを走査し、各PのMCache内のフリーリスト（c->list[i].list）にあるすべてのMLink（フリーオブジェクト）をmarkonly(m)でマークします。markonlyは、オブジェクトのbitMarkedビットを設定する関数です。
    • コメントにあるように、sweepspan関数もスパンのフリーリスト内のオブジェクトをマークするため、ここではMCacheのフリーリストに焦点を当てています。

  4. sweepspan関数内のフリーリストマークロジックの追加:

    • sweepspan関数は、GCのスイープフェーズ中に各MSpanを処理します。
    • この関数内に、s->freelist（スパンのフリーリスト）を走査し、各フリーオブジェクトxのbitMarkedビットを直接設定するループが追加されました。
    • *bitp |= bitMarked<<shift;という直接的なビット操作は、markonly(x)を呼び出すよりも高速であり、アトミックアクセスが不要なため、このコンテキストで効率的です。

  5. sweepspan関数内のビットクリアロジックの変更:

    • オブジェクトが解放される際、以前は*bitp = (*bitp & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);として、bitBlockBoundaryを設定していました。
    • 変更後は、*bitp &= ~((bitScan|bitMarked|bitSpecial)<<shift);として、bitScan、bitMarked、bitSpecialビットをクリアするようになりました。これは、解放されたオブジェクトがフリーリストに入る際に、これらのビットをクリアし、bitAllocatedの状態を維持するという新しい戦略に合致します。

  6. gc()関数内のaddfreelists()呼び出し:

    • GCのメイン関数であるgc()内で、addroots()の直後にaddfreelists()が呼び出されるようになりました。これにより、GCのマークフェーズの初期段階で、フリーリスト内のオブジェクトが確実にマークされ、誤って回収されるのを防ぎます。

  7. runtime·marknogc関数の追加:

    • この新しい関数は、FlagNoGCが設定されたオブジェクト（GC対象外）をマークするために使用されます。
    • オブジェクトのビットマップのbitAllocatedビットをクリアし、代わりにbitBlockBoundaryビットを設定します。これは、GC対象外のオブジェクトがヒープ上で占有しているが、GCによってスキャンもマークもされないことを示します。

  8. runtime·markscan関数の追加:

    • この新しい関数は、ポインタを含む（スキャンが必要な）オブジェクトをマークするために使用されます。
    • オブジェクトのビットマップのbitScanビットを設定します。これにより、GCがこのオブジェクトをスキャンする必要があることを示します。

  9. runtime·markfreed関数の変更:

    • オブジェクトが解放されてフリーリストに戻される際、以前はbitBlockBoundaryを設定していました。
    • 変更後は、bitMaskをクリアし、bitAllocatedを設定するように変更されました。これは、フリーリスト内のオブジェクトを「割り当て済み」として扱うという新しい戦略に合致します。これにより、malloc時にbitAllocatedビットを変更する必要がなくなります。

  10. runtime·markspan関数の変更:

    • 新しいスパンがヒープに割り当てられた際、以前は各ブロックの境界にbitBlockBoundaryを設定していました。
    • 変更後は、各ブロックの境界にbitAllocatedを設定するように変更されました。これは、新しいスパンのメモリが割り当てられた直後から、その領域が「割り当て済み」として扱われることを意味します。また、デバッグビルドでは、初期状態のビットがすべてゼロであることを確認するチェックが追加されました。

これらの変更は、Goランタイムのメモリ管理とGCの効率を向上させるために、ヒープビットマップのセマンティクスとフリーリストの扱い方を根本的に見直したものです。特に、ポインタを持たないオブジェクトのmalloc性能が向上したことは、この最適化の成功を示しています。

関連リンク

参考にした情報源リンク

  • Goの公式ドキュメントやソースコード（特にsrc/runtimeディレクトリ）
  • Goのガベージコレクションに関する技術ブログや論文（コミット当時のGo 1.2前後のGCに関する情報）
  • Goのメモリ管理に関する解説記事