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

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

このコミットは、Goランタイムのガベージコレクション（GC）におけるmarkonly関数のパフォーマンス改善を目的としています。具体的には、オブジェクトの割り当てビットをチェックする際に、flushptrbuf関数が既に行っていたビットマップワード内の後方検索をmarkonly関数にも適用することで、不要なスパン検索を削減し、GCの効率を向上させています。また、この変更には、GCのルックアップに関する統計情報を収集する機能も追加されています。

コミット

commit c51152f438bf7b348de915b7b25fed343ea2a758
Author: Carl Shapiro <cshapiro@google.com>
Date:   Thu Aug 29 13:52:38 2013 -0700

    runtime: check bitmap word for allocated bit in markonly
    
    When searching for an allocated bit, flushptrbuf would search
    backward in the bitmap word containing the bit of pointer
    being looked-up before searching the span.  This extra check
    was not replicated in markonly which, instead, after not
    finding an allocated bit for a pointer would directly look in
    the span.
    
    Using statistics generated from godoc, before this change span
    lookups were, on average, more common than word lookups.  It
    was common for markonly to consult spans for one third of its
    pointer lookups.  With this change in place, what were
    previously span lookups are overwhelmingly become by the word
    lookups making the total number of span lookups a relatively
    small fraction of the whole.
    
    This change also introduces some statistics gathering about
    lookups guarded by the CollectStats enum.
    
    R=golang-dev, khr
    CC=golang-dev
    https://golang.org/cl/13311043

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

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

元コミット内容

このコミットは、Goランタイムのガベージコレクション（GC）におけるmarkonly関数の動作を修正し、パフォーマンスを改善するものです。

既存のflushptrbuf関数は、ポインタの割り当てビットを検索する際に、まずビットマップワード内で後方検索を行い、それでも見つからない場合にスパン（メモリ領域の管理単位）を検索していました。しかし、markonly関数ではこのビットマップワード内の後方検索が行われておらず、割り当てビットが見つからない場合に直接スパンを検索していました。

この非対称な動作により、markonly関数はポインタのルックアップの約3分の1でスパンを頻繁に参照していました。これは、スパンのルックアップがビットマップワード内のルックアップよりもコストが高い操作であるため、GCの効率を低下させていました。

このコミットは、markonly関数にもビットマップワード内の後方検索ロジックを追加することで、この非効率性を解消します。これにより、以前はスパンルックアップが必要だったケースの大部分がビットマップワード内のルックアップで解決されるようになり、全体のスパンルックアップの回数が大幅に削減されます。

さらに、この変更には、CollectStatsという列挙型によって制御される、ルックアップに関する統計情報を収集する機能も導入されています。これにより、GCのパフォーマンス特性をより詳細に分析できるようになります。

変更の背景

Goのガベージコレクションは、プログラムの実行中に不要になったメモリを自動的に解放する重要な役割を担っています。GCの効率は、Goアプリケーション全体のパフォーマンスに直接影響します。

このコミットの背景には、GoランタイムのGCにおける特定の最適化の欠如がありました。GoのGCは、メモリを管理するために「スパン（MSpan）」と「ビットマップ」という2つの主要なデータ構造を使用します。

  • スパン (MSpan): 連続したメモリページのブロックを表し、特定のサイズのオブジェクトを格納するために使用されます。各スパンは、そのスパン内のオブジェクトに関するメタデータ（例えば、どのオブジェクトが割り当てられているか、どのオブジェクトがマークされているかなど）を保持します。
  • ビットマップ: メモリ内の各オブジェクトの割り当て状態やポインタの有無などを効率的に追跡するために使用されるデータ構造です。ビットマップは、メモリ上のオブジェクトに対応するビットの配列として表現され、各ビットは特定のオブジェクトの状態を示します。

GoのGCサイクル中、マーキングフェーズでは、到達可能なオブジェクトを特定し、マークする必要があります。このプロセスでは、ポインタが指すオブジェクトが実際に割り当てられているかどうかを効率的に判断する必要があります。

既存のflushptrbuf関数は、ポインタが指すメモリ位置が割り当て済みかどうかを判断する際に、まずそのポインタが属するビットマップワード内で後方検索を行い、割り当てビット（bitAllocated）やブロック境界ビット（bitBlockBoundary）を探していました。これは、ポインタがオブジェクトの先頭を正確に指しているとは限らず、オブジェクトの内部を指している可能性があるためです。後方検索によって、ポインタが属するオブジェクトの先頭を見つけることができます。この検索で割り当てビットが見つからない場合にのみ、よりコストの高いスパンルックアップ（MHeap_LookupMaybe）を実行していました。

しかし、markonly関数では、このビットマップワード内の後方検索ロジックが欠けていました。そのため、markonlyは、ポインタがオブジェクトの先頭を指していない場合、すぐにスパンルックアップにフォールバックしていました。コミットメッセージによると、この非効率性により、markonlyのポインタルックアップの約3分の1がスパンルックアップになっていました。これは、GCのパフォーマンスボトルネックとなっていました。

このコミットは、markonly関数にflushptrbufと同様のビットマップワード内の後方検索ロジックを導入することで、この非効率性を解消し、GCの全体的なパフォーマンスを向上させることを目的としています。

前提知識の解説

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

Goランタイムとメモリ管理

Goプログラムは、Goランタイム上で実行されます。Goランタイムは、メモリの割り当て、スケジューリング、ガベージコレクションなど、プログラムの実行に必要な低レベルの操作を管理します。

Goのメモリ管理は、ヒープと呼ばれる領域で行われます。ヒープは、プログラムが動的にメモリを割り当てる場所です。Goランタイムは、このヒープを効率的に管理するために、いくつかのデータ構造とアルゴリズムを使用します。

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

Goは、自動メモリ管理、すなわちガベージコレクションを採用しています。開発者が手動でメモリを解放する必要はありません。GoのGCは、主に「マーク＆スイープ」アルゴリズムのバリアントを使用しています。

  • マーキングフェーズ: プログラムが使用している（到達可能な）オブジェクトを特定し、マークします。
  • スイープフェーズ: マークされていない（到達不可能な）オブジェクトを「ガベージ」とみなし、それらが占めていたメモリを解放し、再利用可能にします。

このコミットは、マーキングフェーズにおけるオブジェクトのルックアップ（検索）の効率に関わるものです。

MSpan (Memory Span)

Goのメモリヒープは、MSpanと呼ばれる連続したメモリページのブロックに分割されています。各MSpanは、特定のサイズのオブジェクトを格納するために使用されます。例えば、小さなオブジェクト用のスパン、大きなオブジェクト用のスパンなどがあります。MSpan構造体は、そのスパン内のメモリブロックに関するメタデータ（例えば、どのブロックが空いているか、どのブロックが割り当てられているかなど）を保持します。

ビットマップ

GoのGCは、メモリ内のオブジェクトの状態を効率的に追跡するためにビットマップを使用します。ビットマップは、メモリ上の各オブジェクトに対応するビットの配列です。各ビットは、そのオブジェクトが割り当てられているか、ポインタを含んでいるか、ブロックの境界であるかなどの情報を示します。

  • bitAllocated: そのメモリ位置にオブジェクトが割り当てられていることを示すビット。
  • bitBlockBoundary: そのメモリ位置がオブジェクトのブロックの開始点であることを示すビット。

これらのビットは、GCがメモリをスキャンし、オブジェクトの境界を特定し、ポインタを追跡するために不可欠です。

markonly関数

markonly関数は、GoのGCのマーキングフェーズにおいて重要な役割を果たします。この関数は、特定のメモリアドレス（ポインタ）が指すオブジェクトをマークするために呼び出されます。markonlyの主なタスクは、与えられたポインタが有効なGoオブジェクトの内部を指しているかどうかを判断し、もしそうであればそのオブジェクトを「到達可能」としてマークすることです。

flushptrbuf関数

flushptrbuf関数は、GCのマーキングフェーズ中に、ポインタバッファに蓄積されたポインタを処理するために使用されます。GCは、プログラムの実行中に新しいポインタが作成されたり、既存のポインタが変更されたりするのを追跡します。これらのポインタは一時的にバッファに格納され、その後flushptrbufによって処理され、参照先のオブジェクトがマークされます。

CollectStats

CollectStatsは、Goランタイムのコンパイル時に設定できるフラグ（または列挙型）です。これが有効になっている場合、ランタイムは特定の内部統計情報（例えば、GCのルックアップ回数など）を収集します。これらの統計情報は、ランタイムのパフォーマンス特性を分析し、最適化の機会を特定するために役立ちます。

技術的詳細

このコミットの技術的詳細は、Goランタイムのメモリ管理におけるビットマップの利用と、オブジェクトの割り当て状態を効率的に判断するためのルックアップ戦略に焦点を当てています。

GoのGCは、ポインタが指すメモリ位置が実際に割り当てられたオブジェクトの一部であるかどうかを判断する必要があります。これは、ポインタがオブジェクトの先頭を正確に指しているとは限らず、オブジェクトの内部の任意の位置を指している可能性があるため、複雑になります。

ビットマップワード内の後方検索の重要性

Goのメモリヒープは、MSpanと呼ばれるチャンクに分割され、各MSpanはビットマップによって管理されます。ビットマップは、uintptrのワード（通常は64ビット）の配列として格納され、各ワードはメモリの特定のブロックに対応します。各ビットは、そのメモリブロック内の特定のバイトオフセットに対応し、そのバイトがオブジェクトの先頭であるか、割り当てられているかなどの情報を示します。

ポインタobjが与えられたとき、GCはまずそのポインタが属するビットマップワードを特定します。そして、そのワード内の対応するビットを調べます。しかし、ポインタがオブジェクトの先頭を指していない場合、そのビットだけではオブジェクトの境界を特定できません。

ここで、「ビットマップワード内の後方検索」が重要になります。これは、ポインタが指すビットから、そのビットマップワードの先頭に向かって逆方向にスキャンし、bitAllocatedまたはbitBlockBoundaryビットが設定されている最初の位置を見つけるプロセスです。この位置が、ポインタが指すオブジェクトの実際の先頭である可能性が高いです。

この後方検索は、スパン全体を検索するよりもはるかに高速です。スパン検索（MHeap_LookupMaybe）は、より広範なメモリ領域をカバーしますが、その分オーバーヘッドが大きくなります。したがって、ビットマップワード内の後方検索でオブジェクトの先頭を特定できれば、GCのパフォーマンスが大幅に向上します。

markonlyとflushptrbufの非対称性

コミットメッセージが指摘するように、以前はflushptrbuf関数はこのビットマップワード内の後方検索を行っていましたが、markonly関数は行っていませんでした。

  • flushptrbufの動作: ポインタが指すビットマップワード内で後方検索を行い、割り当てビットまたはブロック境界ビットを見つけようとします。見つからない場合にのみ、MHeap_LookupMaybeを呼び出してスパン全体を検索します。
  • markonlyの以前の動作: ポインタが指すビットがbitAllocatedまたはbitBlockBoundaryでない場合、すぐにMHeap_LookupMaybeを呼び出してスパン全体を検索していました。ビットマップワード内の後方検索をスキップしていました。

この非対称性により、markonlyは不必要に高コストなスパンルックアップを頻繁に実行していました。

統計情報の追加

このコミットでは、GCのルックアップに関する統計情報を収集するための新しいフィールドがgcstats構造体に追加されています。

typedef struct {
    // ... 既存のフィールド ...
    struct {
        uint64 foundbit;
        uint64 foundword;
        uint64 foundspan;
    } flushptrbuf;
    struct {
        uint64 foundbit;
        uint64 foundword;
        uint64 foundspan;
    } markonly;
} gcstats;
  • foundbit: ポインタが指すビットが直接bitAllocatedまたはbitBlockBoundaryであった場合にカウントされます。
  • foundword: ビットマップワード内の後方検索によってオブジェクトの先頭が見つかった場合にカウントされます。
  • foundspan: スパンルックアップ（MHeap_LookupMaybe）によってオブジェクトの先頭が見つかった場合にカウントされます。

これらの統計情報は、CollectStatsが有効な場合にのみ収集され、GCの実行後にruntime·printfによって出力されます。これにより、GCのルックアップ戦略の有効性を定量的に評価し、さらなる最適化の機会を特定できるようになります。

この変更は、GoのGCがより効率的にメモリをスキャンし、オブジェクトをマークできるようにすることで、全体的なアプリケーションのパフォーマンスを向上させることに貢献します。

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

変更は src/pkg/runtime/mgc0.c ファイルに集中しています。

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -199,6 +199,16 @@ static struct {
  	uint64 instr[GC_NUM_INSTR2];
  	uint64 putempty;
  	uint64 getfull;
+	struct {
+		uint64 foundbit;
+		uint64 foundword;
+		uint64 foundspan;
+	} flushptrbuf;
+	struct {
+		uint64 foundbit;
+		uint64 foundword;
+		uint64 foundspan;
+	} markonly;
  } gcstats;
 
  // markonly marks an object. It returns true if the object
@@ -208,7 +218,7 @@ static bool
  markonly(void *obj)
  {
  	byte *p;
-	uintptr *bitp, bits, shift, x, xbits, off;
+	uintptr *bitp, bits, shift, x, xbits, off, j;
  	MSpan *s;
  	PageID k;
 
@@ -230,8 +240,23 @@ markonly(void *obj)
  	bits = xbits >> shift;\n
  	// Pointing at the beginning of a block?
-\tif((bits & (bitAllocated|bitBlockBoundary)) != 0)\n
+\tif((bits & (bitAllocated|bitBlockBoundary)) != 0) {\n
+\t\tif(CollectStats)\n
+\t\t\truntime·xadd64(&gcstats.markonly.foundbit, 1);\n
  	\tgoto found;\n
+\t}\n
+\n+\t// Pointing just past the beginning?\n+\t// Scan backward a little to find a block boundary.\n+\tfor(j=shift; j-->0; ) {\n+\t\tif(((xbits>>j) & (bitAllocated|bitBlockBoundary)) != 0) {\n+\t\t\tshift = j;\n+\t\t\tbits = xbits>>shift;\n+\t\t\tif(CollectStats)\n+\t\t\t\truntime·xadd64(&gcstats.markonly.foundword, 1);\n+\t\t\tgoto found;\n+\t\t}\n+\t}\n
 
  	// Otherwise consult span table to find beginning.
  	// (Manually inlined copy of MHeap_LookupMaybe.)
@@ -257,6 +282,8 @@ markonly(void *obj)
  	shift = off % wordsPerBitmapWord;\n
  	xbits = *bitp;\n
  	bits = xbits >> shift;\n
+\tif(CollectStats)\n
+\t\truntime·xadd64(&gcstats.markonly.foundspan, 1);\n
 
  found:\n
  	// Now we have bits, bitp, and shift correct for
@@ -395,8 +422,11 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
  			bits = xbits >> shift;\n
  			// Pointing at the beginning of a block?
-\t\t\tif((bits & (bitAllocated|bitBlockBoundary)) != 0)\n
+\t\t\tif((bits & (bitAllocated|bitBlockBoundary)) != 0) {\n
+\t\t\t\tif(CollectStats)\n
+\t\t\t\t\truntime·xadd64(&gcstats.flushptrbuf.foundbit, 1);\n
  			\tgoto found;\n
+\t\t\t}\n
 
  		tti = 0;\n
 
@@ -407,6 +437,8 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
  					obj = (byte*)obj - (shift-j)*PtrSize;\n
  					shift = j;\n
  					bits = xbits>>shift;\n
+\t\t\t\t\tif(CollectStats)\n
+\t\t\t\t\t\truntime·xadd64(&gcstats.flushptrbuf.foundword, 1);\n
  					\tgoto found;\n
  				}\n
  			}\n
@@ -435,6 +467,8 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
  			shift = off % wordsPerBitmapWord;\n
  			xbits = *bitp;\n
  			bits = xbits >> shift;\n
+\t\t\tif(CollectStats)\n
+\t\t\t\truntime·xadd64(&gcstats.flushptrbuf.foundspan, 1);\n
 
  		found:\n
  			// Now we have bits, bitp, and shift correct for
@@ -2233,6 +2267,9 @@ gc(struct gc_args *args)\n
  		\truntime·printf(\"\\ttotal:\\t%D\\n\", ninstr);\n
 
  		\truntime·printf(\"putempty: %D, getfull: %D\\n\", gcstats.putempty, gcstats.getfull);\n
+\n+\t\t\truntime·printf(\"markonly base lookup: bit %D word %D span %D\\n\", gcstats.markonly.foundbit, gcstats.markonly.foundword, gcstats.markonly.foundspan);\n+\t\t\truntime·printf(\"flushptrbuf base lookup: bit %D word %D span %D\\n\", gcstats.flushptrbuf.foundbit, gcstats.flushptrbuf.foundword, gcstats.flushptrbuf.foundspan);\n
  		}\n
  	}\n

コアとなるコードの解説

1. gcstats構造体の拡張

gcstats構造体に、flushptrbufとmarkonlyそれぞれのルックアップ統計を格納するための新しいフィールドが追加されました。

	struct {
		uint64 foundbit;
		uint64 foundword;
		uint64 foundspan;
	} flushptrbuf;
	struct {
		uint64 foundbit;
		uint64 foundword;
		uint64 foundspan;
	} markonly;
  • foundbit: ポインタが指す位置が直接割り当て済みまたはブロック境界であった回数。
  • foundword: ビットマップワード内の後方検索によってオブジェクトの先頭が見つかった回数。
  • foundspan: スパンルックアップ（MHeap_LookupMaybe）によってオブジェクトの先頭が見つかった回数。

これらのカウンタは、CollectStatsが有効な場合にのみインクリメントされます。

2. markonly関数の変更

markonly関数に、ビットマップワード内の後方検索ロジックが追加されました。

 	// Pointing at the beginning of a block?
 	if((bits & (bitAllocated|bitBlockBoundary)) != 0) {
 		if(CollectStats)
 			runtime·xadd64(&gcstats.markonly.foundbit, 1);
 		goto found;
 	}

 	// Pointing just past the beginning?
 	// Scan backward a little to find a block boundary.
 	for(j=shift; j-->0; ) {
 		if(((xbits>>j) & (bitAllocated|bitBlockBoundary)) != 0) {
 			shift = j;
 			bits = xbits>>shift;
 			if(CollectStats)
 				runtime·xadd64(&gcstats.markonly.foundword, 1);
 			goto found;
 		}
 	}
  • 最初のifブロック: ポインタが指すビットが既にbitAllocatedまたはbitBlockBoundaryである場合、つまりオブジェクトの先頭を直接指している場合は、foundbitカウンタをインクリメントし、foundラベルにジャンプします。これは既存のロジックです。
  • forループ: ここが新しい追加部分です。ポインタがオブジェクトの先頭を直接指していない場合、このループが実行されます。
    • for(j=shift; j-->0; ): shiftは、objがビットマップワードの先頭からどれだけオフセットしているかを示します。このループは、現在のshiftから0まで（つまり、ビットマップワードの先頭に向かって）逆方向にイテレートします。
    • if(((xbits>>j) & (bitAllocated|bitBlockBoundary)) != 0): 各ビット位置jで、そのビットがbitAllocatedまたはbitBlockBoundaryであるかをチェックします。
    • shift = j; bits = xbits>>shift;: もし割り当てビットまたはブロック境界ビットが見つかった場合、新しいshiftとbitsを更新します。これにより、objが指すオブジェクトの実際の先頭が特定されます。
    • runtime·xadd64(&gcstats.markonly.foundword, 1);: foundwordカウンタをインクリメントします。
    • goto found;: オブジェクトの先頭が見つかったので、foundラベルにジャンプして後続の処理に進みます。

この変更により、markonlyはflushptrbufと同様に、まずビットマップワード内の後方検索を試み、それでも見つからない場合にのみスパンルックアップにフォールバックするようになりました。

3. markonlyとflushptrbufにおけるfoundspanのインクリメント

markonlyとflushptrbufの両方で、スパンルックアップ（MHeap_LookupMaybe）が実行された直後にfoundspanカウンタがインクリメントされるようになりました。

// markonly
 	// Otherwise consult span table to find beginning.
 	// (Manually inlined copy of MHeap_LookupMaybe.)
 	// ...
 	if(CollectStats)
 		runtime·xadd64(&gcstats.markonly.foundspan, 1);

// flushptrbuf
 	// Otherwise consult span table to find beginning.
 	// (Manually inlined copy of MHeap_LookupMaybe.)
 	// ...
 	if(CollectStats)
 		runtime·xadd64(&gcstats.flushptrbuf.foundspan, 1);

これにより、スパンルックアップが実際に何回発生したかを正確に追跡できるようになります。

4. GC統計の出力

gc関数（ガベージコレクションのメインエントリポイント）の最後に、新しいルックアップ統計が出力されるようになりました。

 	if(CollectStats) {
 		// ... 既存の統計出力 ...
 		runtime·printf("markonly base lookup: bit %D word %D span %D\n", gcstats.markonly.foundbit, gcstats.markonly.foundword, gcstats.markonly.foundspan);
 		runtime·printf("flushptrbuf base lookup: bit %D word %D span %D\n", gcstats.flushptrbuf.foundbit, gcstats.flushptrbuf.foundword, gcstats.flushptrbuf.foundspan);
 	}

この出力により、開発者はGCのルックアップ戦略がどれだけ効率的に機能しているかを把握し、さらなる最適化のヒントを得ることができます。コミットメッセージにある「godocから生成された統計」は、このような統計収集機能が既に存在し、今回の変更でさらに詳細な情報が追加されたことを示唆しています。

関連リンク

  • Goのガベージコレクションに関する公式ドキュメントやブログ記事:
  • Goのメモリ管理に関する詳細な解説記事（非公式）：
    • "Go's Memory Allocator" や "Go's Garbage Collector" といったキーワードで検索すると、多くの技術ブログや論文が見つかります。

参考にした情報源リンク

  • コミットメッセージ自体: https://github.com/golang/go/commit/c51152f438bf7b348de915b7b25fed343ea2a758
  • Goのソースコード: src/pkg/runtime/mgc0.c
  • Goのガベージコレクションとメモリ管理に関する一般的な知識 (Go公式ドキュメント、技術ブログ、論文など)
  • Goのruntimeパッケージのドキュメント (GoDoc)
  • runtime·xadd64のようなGoランタイム内部関数に関する情報 (Goのソースコードや関連する技術記事)
  • bitAllocated, bitBlockBoundaryなどのビットマップフラグに関する情報 (Goのソースコード)I have generated the detailed technical explanation in Markdown format, following all the specified instructions and chapter structure. The output is provided to standard output only, as requested.