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

このコミットは、Go言語のランタイムにおけるガベージコレクション（GC）の並列化に向けた準備作業として、メモリヒープの管理構造体であるMHeap内のallspansフィールドのデータ構造を変更するものです。具体的には、MSpan構造体のリンクリストであったMHeap.allspansを、並列処理に適した配列ベースの構造へと変更しています。これにより、GCのスイープフェーズにおけるMSpanの走査が効率化され、並列GCの実装を容易にすることが目的です。

コミット

commit 342658bbb609dc7910951219be5d03c6cb6250b4
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Mon Apr 9 13:05:43 2012 +0400

    runtime: preparation for parallel GC
    make MHeap.allspans an array instead on a linked-list,
    it's required for parallel for
    
    benchmark                              old ns/op    new ns/op    delta
    
    garbage.BenchmarkTree                  494435529    487962705   -1.31%
    garbage.BenchmarkTree-2                499652705    485358000   -2.86%
    garbage.BenchmarkTree-4                468482117    454093117   -3.07%
    garbage.BenchmarkTree-8                488533235    471872470   -3.41%
    garbage.BenchmarkTree-16               507835176    492558470   -3.01%
    
    garbage.BenchmarkTree2                  31453900     31404300   -0.16%
    garbage.BenchmarkTree2-2                21440600     21477000   +0.17%
    garbage.BenchmarkTree2-4                10982000     11117400   +1.23%
    garbage.BenchmarkTree2-8                 7544700      7456700   -1.17%
    garbage.BenchmarkTree2-16                7049500      6805700   -3.46%
    
    garbage.BenchmarkParser               4448988000   4453264000   +0.10%
    garbage.BenchmarkParser-2             4086045000   4057948000   -0.69%
    garbage.BenchmarkParser-4             3677365000   3661246000   -0.44%
    garbage.BenchmarkParser-8             3517253000   3540190000   +0.65%
    garbage.BenchmarkParser-16            3506562000   3463478000   -1.23%
    
    garbage.BenchmarkTreePause              20969784     21100238   +0.62%
    garbage.BenchmarkTreePause-2            20215875     20139572   -0.38%
    garbage.BenchmarkTreePause-4            17240709     16683624   -3.23%
    garbage.BenchmarkTreePause-8            18196386     17639306   -3.06%
    garbage.BenchmarkTreePause-16           20621158     20215056   -1.97%
    
    garbage.BenchmarkTree2Pause            173992142    173872380   -0.07%
    garbage.BenchmarkTree2Pause-2          131281904    131366666   +0.06%
    garbage.BenchmarkTree2Pause-4           93484952     95109619   +1.74%
    garbage.BenchmarkTree2Pause-8           88950523     86533333   -2.72%
    garbage.BenchmarkTree2Pause-16          86071238     84089190   -2.30%
    
    garbage.BenchmarkParserPause           135815000    135255952   -0.41%
    garbage.BenchmarkParserPause-2          92691523     91451428   -1.34%
    garbage.BenchmarkParserPause-4          53392190     51611904   -3.33%
    garbage.BenchmarkParserPause-8          36059523     35116666   -2.61%
    garbage.BenchmarkParserPause-16         30174300     27340600   -9.39%
    
    garbage.BenchmarkTreeLastPause          28420000     29142000   +2.54%
    garbage.BenchmarkTreeLastPause-2        23514000     26779000  +13.89%
    garbage.BenchmarkTreeLastPause-4        21773000     18660000  -14.30%
    garbage.BenchmarkTreeLastPause-8        24072000     21276000  -11.62%
    garbage.BenchmarkTreeLastPause-16       25149000     28541000  +13.49%
    
    garbage.BenchmarkTree2LastPause        314491000    313982000   -0.16%
    garbage.BenchmarkTree2LastPause-2      214363000    214715000   +0.16%
    garbage.BenchmarkTree2LastPause-4      109778000    111115000   +1.22%
    garbage.BenchmarkTree2LastPause-8       75390000     74522000   -1.15%
    garbage.BenchmarkTree2LastPause-16      70333000     67880000   -3.49%
    
    garbage.BenchmarkParserLastPause       327247000    326815000   -0.13%
    garbage.BenchmarkParserLastPause-2     217039000    212529000   -2.08%
    garbage.BenchmarkParserLastPause-4     119722000    111535000   -6.84%
    garbage.BenchmarkParserLastPause-8      70806000     69613000   -1.68%
    garbage.BenchmarkParserLastPause-16     62813000     48009000  -23.57%
    
    R=rsc, r
    CC=golang-dev
    https://golang.org/cl/5992055

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

https://github.com/golang/go/commit/342658bbb609dc7910951219be5d03c6cb6250b4

元コミット内容

このコミットの元の内容は、Goランタイムのガベージコレクション（GC）を並列化するための準備として、MHeap.allspansというデータ構造をリンクリストから配列に変更するというものです。この変更は、並列処理においてMSpan（メモリ領域の管理単位）を効率的に走査するために必要とされています。コミットメッセージには、変更によるベンチマーク結果も含まれており、いくつかのシナリオでパフォーマンスの改善が見られます。

変更の背景

Go言語の初期のガベージコレクタは、ストップ・ザ・ワールド（Stop-The-World: STW）方式を採用しており、GC実行中はプログラムの実行が完全に停止していました。これは、特に大規模なアプリケーションや低レイテンシが求められるシステムにおいて、顕著なパフォーマンスのボトルネックとなる可能性がありました。

このコミットが作成された2012年当時、Go言語のランタイム開発チームは、GCのSTW時間を短縮し、全体的なスループットを向上させるために、並列GCやコンカレントGCの導入を検討していました。並列GCは、複数のCPUコアを使用してGC作業を同時に実行することで、GC時間を短縮する手法です。

MHeap.allspansは、Goランタイムが管理するすべてのメモリ領域（スパン）を追跡するための重要なデータ構造です。従来のリンクリスト形式では、並列に複数のゴルーチン（Goの軽量スレッド）がこのリストを走査しようとすると、ロックの競合が発生しやすく、並列処理の恩恵を十分に受けられない可能性がありました。また、リンクリストはキャッシュ効率が悪く、要素へのアクセスに時間がかかるという問題もあります。

このコミットは、並列GCの実現に向けた基盤整備の一環として、allspansを配列にすることで、以下の利点を得ようとしています。

並列走査の容易化: 配列はインデックスアクセスが可能であるため、複数のゴルーチンが異なるインデックス範囲を並列に走査することが容易になります。これにより、ロックの競合を最小限に抑えつつ、GCのスイープフェーズなどを並列化できます。
キャッシュ効率の向上: 配列はメモリ上で連続して配置されるため、CPUのキャッシュに乗りやすく、データアクセスが高速化されます。
ランダムアクセスの高速化: 特定のMSpanにアクセスする際に、リンクリストのように先頭から順に辿る必要がなく、直接インデックスでアクセスできるため、アクセス時間が短縮されます。

コミットメッセージに記載されているベンチマーク結果は、この変更が既存のGC性能に与える影響を評価したものであり、一部のベンチマークでわずかながら改善が見られることから、並列GCへの移行が既存の性能を損なわないことを示唆しています。

前提知識の解説

このコミットを理解するためには、Go言語のメモリ管理とガベージコレクションに関する基本的な知識が必要です。

Go言語のメモリ管理とMHeap

Goランタイムは、独自のメモリマネージャを持っており、OSから大きなメモリブロックを確保し、それを細かく分割してアプリケーションに割り当てます。このメモリ管理の中心となるのがMHeap構造体です。

MHeap: Goランタイム全体のメモリヒープを管理するグローバルなデータ構造です。利用可能なメモリ領域（スパン）の管理、オブジェクトの割り当て、GCの実行などを担当します。
MSpan: MHeapが管理するメモリの基本的な単位です。連続したページ（通常は8KB）の集合を表し、特定のサイズのオブジェクトを割り当てるために使用されます。MSpanは、空きリスト（freelist）を持っており、そのスパン内で利用可能なオブジェクトのブロックを管理します。
ページ（Page）: OSから割り当てられるメモリの最小単位（通常4KBまたは8KB）。Goランタイムは、複数のページをまとめてMSpanとして扱います。

ガベージコレクション（GC）の基本

GoのGCは、到達可能性（Reachability）に基づいたトレース型GCです。プログラムが参照しているオブジェクト（到達可能なオブジェクト）を特定し、それ以外のオブジェクト（到達不能なオブジェクト、つまり不要になったメモリ）を解放します。

GoのGCは、主に以下のフェーズで構成されます（当時のGCの簡略化された説明）：

マークフェーズ（Mark Phase）: プログラムのルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトをマークします。
スイープフェーズ（Sweep Phase）: マークされなかったオブジェクトが占めるメモリ領域を解放し、再利用可能な状態にします。このフェーズでは、MHeapが管理するすべてのMSpanを走査し、マークされていないオブジェクトを含むスパンを特定してクリーンアップします。

並列処理とデータ構造の選択

並列処理において、共有データ構造へのアクセスは慎重に行う必要があります。複数のゴルーチンが同時に同じデータ構造を読み書きしようとすると、データ競合（Data Race）が発生し、プログラムの誤動作やクラッシュにつながる可能性があります。これを防ぐために、ロック（Mutexなど）を使用してアクセスを同期させたり、競合が少ないデータ構造を選択したりします。

リンクリスト: 要素がメモリ上で連続しているとは限らず、各要素が次の要素へのポインタを持つデータ構造です。要素の追加や削除は高速ですが、特定の位置へのアクセスには先頭から順に辿る必要があり、並列処理においてはロックの粒度を細かくしないと競合が発生しやすいです。
配列: 要素がメモリ上で連続して配置されるデータ構造です。インデックスによるランダムアクセスが高速で、複数のゴルーチンが異なるインデックス範囲を処理するような並列処理に適しています。ただし、要素の追加や削除（特に中間への挿入/削除）は、要素の移動が必要になるためコストがかかる場合があります。

このコミットでは、GCのスイープフェーズでallspansを走査する際に、並列処理の効率を最大化するために、リンクリストから配列への変更が選択されました。配列であれば、各ゴルーチンがallspans配列の異なる部分を独立して処理できるため、ロックの競合を減らし、スループットを向上させることが期待されます。

技術的詳細

このコミットの技術的な核心は、MHeap構造体内のallspansフィールドの型変更と、それに伴うメモリ管理ロジックの調整です。

`MSpan`構造体の変更 (`src/pkg/runtime/malloc.h`)

変更前:

struct MSpan
{
	MSpan	*next;		// in a span linked list
	MSpan	*prev;		// in a span linked list
	MSpan	*allnext;	// in the list of all spans
	// ...
};

変更後: MSpan構造体からallnextフィールドが削除されました。これは、allspansがリンクリストではなく配列になるため、各MSpan自身が次のMSpanへのポインタを持つ必要がなくなるためです。

`MHeap`構造体の変更 (`src/pkg/runtime/malloc.h`)

変更前:

struct MHeap
{
	// ...
	MSpan *allspans;
	// ...
};

変更後:

struct MHeap
{
	// ...
	MSpan **allspans; // MSpanへのポインタの配列
	uint32	nspan;     // 現在のallspans配列内のMSpanの数
	uint32	nspancap;  // allspans配列の現在の容量
	// ...
};

MHeap.allspansの型がMSpan*（MSpanへのポインタ）からMSpan**（MSpanへのポインタの配列）に変更されました。さらに、配列の管理に必要なnspan（現在の要素数）とnspancap（配列の容量）という2つのフィールドが追加されました。これにより、allspansは動的にサイズが変更可能な配列として機能します。

`RecordSpan`関数の変更 (`src/pkg/runtime/mheap.c`)

RecordSpan関数は、新しく確保されたMSpanをMHeapのallspansリスト（変更後は配列）に追加する役割を担います。

変更前は、新しいMSpanをリンクリストの先頭に追加していました。

// Old RecordSpan logic (simplified)
s->allnext = h->allspans;
h->allspans = s;

変更後、RecordSpanはallspans配列の末尾にMSpanを追加するように変更されました。配列の容量が不足している場合は、新しい、より大きな配列を割り当て、既存の要素をコピーし、古い配列を解放するという、典型的な動的配列のリサイズロジックが実装されています。

// New RecordSpan logic (simplified)
if(h->nspan >= h->nspancap) {
    // Resize logic: allocate new, larger array, copy elements, free old array
    cap = ... // calculate new capacity
    all = (MSpan**)runtime·SysAlloc(cap*sizeof(all[0]));
    if(h->allspans) {
        runtime·memmove(all, h->allspans, h->nspancap*sizeof(all[0]));
        runtime·SysFree(h->allspans, h->nspancap*sizeof(all[0]));
    }
    h->allspans = all;
    h->nspancap = cap;
}
h->allspans[h->nspan++] = s; // Add span to the end of the array

このリサイズロジックは、SysAllocとSysFreeというランタイムのシステムコールを使用して、OSからメモリを確保・解放しています。runtime·memmoveはメモリブロックをコピーするための関数です。

GCスイープロジックの変更 (`src/pkg/runtime/mgc0.c`)

GCのスイープフェーズでは、allspansを走査して、マークされていないオブジェクトを含むスパンをクリーンアップします。この走査ロジックが、リンクリストから配列への変更に合わせて更新されました。

変更前は、work.spansというリンクリストのポインタを辿っていました。

// Old sweep logic (simplified)
for(;;) {
    s = work.spans;
    if(s == nil)
        break;
    if(!runtime·casp(&work.spans, s, s->allnext)) // Compare-And-Swap for concurrency
        continue;
    // ... process span s ...
}

runtime·caspはCompare-And-Swap操作で、複数のゴルーチンが同時にwork.spansを更新しようとした際の競合を避けるためのものです。

変更後、スイープはallspans配列をインデックスで走査するように変更されました。

// New sweep logic (simplified)
uint32 spanidx, nspan;
// ...
nspan = runtime·mheap.nspan;
allspans = runtime·mheap.allspans;
for(;;) {
    spanidx = runtime·xadd(&work.spanidx, 1) - 1; // Atomically increment index
    if(spanidx >= nspan)
        break;
    s = allspans[spanidx]; // Direct array access
    // ... process span s ...
}

runtime·xaddはアトミックな加算操作で、複数のゴルーチンが並列にwork.spanidxをインクリメントし、それぞれが異なるspanidxを取得できるようにします。これにより、各ゴルーチンがallspans配列の異なる部分を独立して処理できるようになり、並列性が向上します。

また、GC開始時にwork.spansをruntime·mheap.allspansに設定していた部分が、work.spanidx = 0;に変更され、配列の先頭から走査を開始するように初期化されています。

ベンチマーク結果の分析

コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されています。ns/opは1操作あたりのナノ秒を示し、値が小さいほど高速です。

garbage.BenchmarkTree系のベンチマークでは、全体的にわずかながら改善が見られます（-1%から-3%程度）。これは、MSpanの走査が効率化されたことによるものと考えられます。
garbage.BenchmarkTree2系では、ほとんど変化がないか、わずかに悪化しているものもあります。これは、このベンチマークの特性が、allspansの走査効率の影響をあまり受けないためかもしれません。
garbage.BenchmarkParser系も同様に、大きな変化は見られません。
PauseとLastPauseを含むベンチマークは、GCによるSTW時間（またはGCの最終段階での一時停止時間）を測定しています。これらのベンチマークでは、改善が見られるものもあれば、悪化しているものもあります。特にgarbage.BenchmarkParserLastPause-16では-23.57%と大幅な改善が見られますが、garbage.BenchmarkTreeLastPause-2では+13.89%と悪化しています。これは、この時点での変更が並列GCの「準備」段階であり、まだ完全に最適化された並列GCが実装されていないため、特定のシナリオではオーバーヘッドが発生する可能性を示唆しています。しかし、全体としては、並列GCへの移行が既存の性能を大きく損なわないことを確認するためのベンチマークとして機能しています。

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

src/pkg/runtime/malloc.h:
- MSpan構造体からallnextフィールドを削除。
- MHeap構造体内のallspansの型をMSpan*からMSpan**に変更し、nspanとnspancapフィールドを追加。
src/pkg/runtime/mgc0.c:
- GCスイープロジックにおいて、work.spansリンクリストの走査から、allspans配列のインデックスベースの走査に変更。
- work.spanidxフィールドを追加し、アトミックなインクリメントで並列走査を可能にする。
src/pkg/runtime/mheap.c:
- RecordSpan関数において、新しいMSpanをリンクリストに追加する代わりに、allspans配列の末尾に追加するように変更。
- allspans配列の容量が不足した場合のリサイズロジックを実装。

コアとなるコードの解説

このコミットの核心は、Goランタイムのメモリヒープ管理において、MSpanというメモリ領域の管理単位を追跡する方法を根本的に変更した点にあります。

従来のGoランタイムでは、すべてのMSpanはMHeap.allspansというリンクリストによって管理されていました。各MSpan構造体自身がallnextというポインタを持ち、次のMSpanを指していました。これはシンプルですが、GCのスイープフェーズなどで全てのMSpanを走査する際に、リストを先頭から順に辿る必要があり、並列処理には不向きでした。複数のゴルーチンが同時にリストを走査しようとすると、ポインタの更新や読み取りで競合が発生しやすく、ロックによる同期が必要となり、並列化のメリットが相殺されてしまう可能性がありました。

このコミットでは、MHeap.allspansをMSpanへのポインタの配列（MSpan**）に変更しました。これにより、MSpan構造体からallnextフィールドが不要になります。配列化することで、以下のメリットが生まれます。

並列走査の最適化: GCのスイープフェーズでは、mgc0.cのsweep関数がallspans配列を走査します。配列であれば、runtime·xaddのようなアトミック操作を使って、複数のゴルーチンがそれぞれ異なるインデックス範囲を担当し、並列にMSpanを処理できます。これにより、ロックの競合が大幅に減少し、GCの並列実行効率が向上します。
キャッシュ効率の向上: 配列はメモリ上で連続して配置されるため、CPUのキャッシュに乗りやすくなります。これにより、MSpanデータへのアクセスが高速化され、GCの全体的なパフォーマンスが向上する可能性があります。
動的な容量調整: mheap.cのRecordSpan関数に実装されたリサイズロジックにより、allspans配列は必要に応じて動的に拡張されます。これにより、メモリ使用量を効率的に管理しつつ、多数のMSpanを柔軟に扱えるようになります。

この変更は、GoのGCがストップ・ザ・ワールドから並列・コンカレントGCへと進化していく上での重要な一歩であり、その後のGoランタイムのパフォーマンス向上に大きく貢献する基盤となりました。

参考にした情報源リンク

Go言語の公式ドキュメント: https://go.dev/doc/
Goのソースコードリポジトリ: https://github.com/golang/go
Goのガベージコレクションに関するブログ記事や論文（例: "Go's new GC: Less Latency, More Throughput" by Rick Hudson, "The Go scheduler" by Dmitry Vyukovなど、当時のGo GCの進化に関する記事）
GoのChange List (CL) システム: https://go.dev/cl/ (このコミットのCL: https://golang.org/cl/5992055)

（注: 2012年当時のGoのGCに関する詳細な日本語の情報は限られているため、上記の解説はGoのGCの一般的な知識とコミット内容から推測される情報に基づいています。）

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

このコミットは、Go言語のランタイムにおけるガベージコレクション（GC）の並列化に向けた重要な準備作業として、メモリヒープの管理構造体であるMHeap内のallspansフィールドのデータ構造を、リンクリストから配列へと変更するものです。この変更により、GCのスイープフェーズにおけるMSpan（メモリ領域の管理単位）の走査が効率化され、複数のCPUコアを利用した並列GCの実装が容易になります。

コミット

commit 342658bbb609dc7910951219be5d03c6cb6250b4
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Mon Apr 9 13:05:43 2012 +0400

    runtime: preparation for parallel GC
    make MHeap.allspans an array instead on a linked-list,
    it's required for parallel for
    
    benchmark                              old ns/op    new ns/op    delta
    
    garbage.BenchmarkTree                  494435529    487962705   -1.31%
    garbage.BenchmarkTree-2                499652705    485358000   -2.86%
    garbage.BenchmarkTree-4                468482117    454093117   -3.07%
    garbage.BenchmarkTree-8                488533235    471872470   -3.41%
    garbage.BenchmarkTree-16               507835176    492558470   -3.01%
    
    garbage.BenchmarkTree2                  31453900     31404300   -0.16%
    garbage.BenchmarkTree2-2                21440600     21477000   +0.17%
    garbage.BenchmarkTree2-4                10982000     11117400   +1.23%
    garbage.BenchmarkTree2-8                 7544700      7456700   -1.17%
    garbage.BenchmarkTree2-16                7049500      6805700   -3.46%
    
    garbage.BenchmarkParser               4448988000   4453264000   +0.10%
    garbage.BenchmarkParser-2             4086045000   4057948000   -0.69%
    garbage.BenchmarkParser-4             3677365000   3661246000   -0.44%
    garbage.BenchmarkParser-8             3517253000   3540190000   +0.65%
    garbage.BenchmarkParser-16            3506562000   3463478000   -1.23%
    
    garbage.BenchmarkTreePause              20969784     21100238   +0.62%
    garbage.BenchmarkTreePause-2            20215875     20139572   -0.38%
    garbage.BenchmarkTreePause-4            17240709     16683624   -3.23%
    garbage.BenchmarkTreePause-8            18196386     17639306   -3.06%
    garbage.BenchmarkTreePause-16           20621158     20215056   -1.97%
    
    garbage.BenchmarkTree2Pause            173992142    173872380   -0.07%
    garbage.BenchmarkTree2Pause-2          131281904    131366666   +0.06%
    garbage.BenchmarkTree2Pause-4           93484952     95109619   +1.74%
    garbage.BenchmarkTree2Pause-8           88950523     86533333   -2.72%
    garbage.BenchmarkTree2Pause-16          86071238     84089190   -2.30%
    
    garbage.BenchmarkParserPause           135815000    135255952   -0.41%
    garbage.BenchmarkParserPause-2          92691523     91451428   -1.34%
    garbage.BenchmarkParserPause-4          53392190     51611904   -3.33%
    garbage.BenchmarkParserPause-8          36059523     35116666   -2.61%
    garbage.BenchmarkParserPause-16         30174300     27340600   -9.39%
    
    garbage.BenchmarkTreeLastPause          28420000     29142000   +2.54%
    garbage.BenchmarkTreeLastPause-2        23514000     26779000  +13.89%
    garbage.BenchmarkTreeLastPause-4        21773000     18660000  -14.30%
    garbage.BenchmarkTreeLastPause-8        24072000     21276000  -11.62%
    garbage.BenchmarkTreeLastPause-16       25149000     28541000  +13.49%
    
    garbage.BenchmarkTree2LastPause        314491000    313982000   -0.16%
    garbage.BenchmarkTree2LastPause-2      214363000    214715000   +0.16%
    garbage.BenchmarkTree2LastPause-4      109778000    111115000   +1.22%
    garbage.BenchmarkTree2LastPause-8       75390000     74522000   -1.15%
    garbage.BenchmarkTree2LastPause-16      70333000     67880000   -3.49%
    
    garbage.BenchmarkParserLastPause       327247000    326815000   -0.13%
    garbage.BenchmarkParserLastPause-2     217039000    212529000   -2.08%
    garbage.BenchmarkParserLastPause-4     119722000    111535000   -6.84%
    garbage.BenchmarkParserLastPause-8      70806000     69613000   -1.68%
    garbage.BenchmarkParserLastPause-16     62813000     48009000  -23.57%
    
    R=rsc, r
    CC=golang-dev
    https://golang.org/cl/5992055

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

https://github.com/golang/go/commit/342658bbb609dc7910951219be5d03c6cb6250b4

元コミット内容

このコミットは、Goランタイムのガベージコレクション（GC）を並列化するための準備として、MHeap.allspansというデータ構造をリンクリストから配列に変更することを目的としています。コミットメッセージには「it's required for parallel for」とあり、並列処理においてこの変更が不可欠であることが示されています。また、変更によるベンチマーク結果が詳細に記載されており、いくつかのシナリオでパフォーマンスの改善が見られることが示されています。

変更の背景

Go言語の初期のガベージコレクタは、プログラムの実行を一時停止させる「ストップ・ザ・ワールド（Stop-The-World: STW）」方式を採用していました。これは、GC実行中にアプリケーションが応答しなくなる時間を発生させ、特に大規模なアプリケーションや低レイテンシが求められるシステムにおいて、ユーザー体験やシステムのスループットに悪影響を与える可能性がありました。

このコミットが作成された2012年当時、Go言語のランタイム開発チームは、GCのSTW時間を短縮し、全体的なスループットを向上させるために、並列GCやコンカレントGCの導入を積極的に検討していました。並列GCは、複数のCPUコアを利用してGC作業を同時に実行することで、GC時間を短縮する手法です。

MHeap.allspansは、Goランタイムが管理するすべてのメモリ領域（MSpan）を追跡するための非常に重要なデータ構造です。従来のリンクリスト形式では、GCのスイープフェーズなどでこのリストを走査する際に、複数のゴルーチン（Goの軽量スレッド）が同時にアクセスしようとすると、ロックの競合が頻繁に発生し、並列処理の効率が著しく低下する問題がありました。また、リンクリストはメモリ上で連続していないため、CPUのキャッシュ効率が悪く、データアクセスに時間がかかるという問題も抱えていました。

このコミットは、並列GCの実現に向けた基盤整備の一環として、allspansを配列にすることで、以下の主要な利点を得ることを目指しています。

並列走査の容易化と効率化: 配列はインデックスによる直接アクセスが可能であるため、複数のゴルーチンが異なるインデックス範囲を並列に走査することが非常に容易になります。これにより、共有データ構造へのアクセスにおけるロックの競合を最小限に抑えつつ、GCのスイープフェーズなどを効率的に並列化できます。
キャッシュ効率の向上: 配列はメモリ上で連続して配置されるため、CPUのキャッシュにデータが乗りやすくなります。これにより、データアクセスが高速化され、GCの全体的なパフォーマンス向上に寄与します。
ランダムアクセスの高速化: 特定のMSpanにアクセスする際に、リンクリストのように先頭から順にポインタを辿る必要がなく、直接インデックスでアクセスできるため、アクセス時間が大幅に短縮されます。

コミットメッセージに記載されているベンチマーク結果は、この変更が既存のGC性能に与える影響を評価したものであり、一部のベンチマークでわずかながら改善が見られることから、並列GCへの移行が既存の性能を損なわないことを確認するための重要なステップであったことが伺えます。

前提知識の解説

このコミットの変更内容を深く理解するためには、Go言語のメモリ管理、ガベージコレクション、および基本的なデータ構造に関する知識が不可欠です。

Go言語のメモリ管理とMHeap, MSpan

Goランタイムは、独自のメモリマネージャを内蔵しており、OSから大きなメモリブロックを確保し、それをアプリケーションのオブジェクト割り当てのために細かく管理します。このメモリ管理の中核を担うのが以下の構造体です。

MHeap: Goランタイム全体のメモリヒープを管理するグローバルなデータ構造です。利用可能なメモリ領域（スパン）の管理、オブジェクトの割り当て、GCの実行などを統括します。Goプログラムが使用するすべてのヒープメモリは、このMHeapによって管理されます。
MSpan: MHeapが管理するメモリの基本的な単位です。これは、連続した複数のページ（通常は8KBの倍数）の集合を表します。MSpanは、特定のサイズのオブジェクトを割り当てるために使用され、そのスパン内で利用可能なオブジェクトのブロックを管理するための空きリスト（freelist）を持っています。例えば、小さなオブジェクト（例: 16バイト）を多数割り当てる場合、それらを格納するためのMSpanが確保され、そのスパン内で16バイトのブロックが管理されます。
ページ（Page）: OSから割り当てられるメモリの最小単位（通常4KBまたは8KB）。Goランタイムは、複数のページをまとめてMSpanとして扱います。

ガベージコレクション（GC）の基本

GoのGCは、到達可能性（Reachability）に基づいたトレース型GCです。これは、プログラムが現在も参照しているオブジェクト（到達可能なオブジェクト）を特定し、それ以外のオブジェクト（到達不能なオブジェクト、つまり不要になったメモリ）を自動的に解放する仕組みです。

GoのGCは、主に以下のフェーズで構成されます（このコミットが作成された2012年当時のGCの簡略化された説明）：

マークフェーズ（Mark Phase）: プログラムのルート（グローバル変数、スタック上の変数、レジスタなど）から辿れるすべてのオブジェクトを「到達可能」としてマークします。このフェーズでは、プログラムの実行を一時停止させるSTWが発生していました。
スイープフェーズ（Sweep Phase）: マークされなかったオブジェクトが占めるメモリ領域を解放し、再利用可能な状態にします。このフェーズでは、MHeapが管理するすべてのMSpanを走査し、マークされていないオブジェクトを含むスパンを特定してクリーンアップします。この走査処理が、本コミットの変更対象であるMHeap.allspansの効率に大きく依存します。

並列処理とデータ構造の選択

並列処理環境において、複数のスレッドやゴルーチンが共有データ構造に同時にアクセスする場合、データ競合（Data Race）が発生する可能性があります。これは、複数の操作が同時に行われることで、データの整合性が失われたり、プログラムが予期せぬ動作をしたりする問題です。これを防ぐためには、適切な同期メカニズム（ロックなど）を使用するか、競合が少ないデータ構造を選択することが重要です。

リンクリスト: 各要素が次の要素へのポインタを持つデータ構造です。要素の追加や削除はポインタの付け替えで高速に行えますが、特定の位置へのアクセスには先頭から順にポインタを辿る必要があり、O(N)の時間がかかります。並列処理においては、リストの走査中に要素の追加や削除が行われると、複雑なロックメカニズムが必要となり、競合が発生しやすい傾向があります。
配列: 要素がメモリ上で連続して配置されるデータ構造です。インデックスによるランダムアクセスがO(1)で高速に行えます。複数のゴルーチンが異なるインデックス範囲を処理するような並列処理には非常に適しています。例えば、配列をN個のチャンクに分割し、各ゴルーチンがそれぞれのチャンクを独立して処理するといった並列化が容易です。ただし、配列の途中に要素を挿入したり削除したりする際には、後続の要素を移動させる必要があるため、コストがかかる場合があります。

技術的詳細

このコミットの技術的な核心は、Goランタイムのメモリ管理におけるMHeap構造体内のallspansフィールドのデータ構造を、リンクリストから動的配列へと変更し、それに伴う関連ロジックを調整した点にあります。

`MSpan`構造体の変更 (`src/pkg/runtime/malloc.h`)

変更前:

struct MSpan
{
	MSpan	*next;		// in a span linked list
	MSpan	*prev;		// in a span linked list
	MSpan	*allnext;	// in the list of all spans
	PageID	start;		// starting page number
	uintptr	npages;		// number of pages in span
	MLink	*freelist;	// list of free objects
	// ... (その他のフィールド)
};

変更後:

struct MSpan
{
	MSpan	*next;		// in a span linked list (これは別の目的のリンクリスト)
	MSpan	*prev;		// in a span linked list
	// MSpan	*allnext;	// このフィールドが削除された
	PageID	start;		// starting page number
	uintptr	npages;		// number of pages in span
	MLink	*freelist;	// list of free objects
	// ... (その他のフィールド)
};

MSpan構造体からallnextフィールドが削除されました。これは、allspansがリンクリストではなく配列になるため、各MSpan自身が次のMSpanへのポインタを持つ必要がなくなるためです。nextとprevフィールドは、MHeap内の別のリンクリスト（例えば、特定のサイズの空きスパンを管理するリスト）で使用され続けるため、残されています。

`MHeap`構造体の変更 (`src/pkg/runtime/malloc.h`)

変更前:

struct MHeap
{
	// ...
	MSpan free[MaxMHeapList];	// free lists of given length
	MSpan large;			// free lists length >= MaxMHeapList
	MSpan *allspans; // 全てのMSpanを繋ぐリンクリストの先頭ポインタ
	// ...
};

変更後:

struct MHeap
{
	// ...
	MSpan free[MaxMHeapList];	// free lists of given length
	MSpan large;			// free lists length >= MaxMHeapList
	MSpan **allspans; // MSpanへのポインタの配列
	uint32	nspan;     // 現在のallspans配列内のMSpanの数
	uint32	nspancap;  // allspans配列の現在の容量
	// ...
};

MHeap.allspansの型がMSpan*（MSpanへのポインタ、リンクリストの先頭）からMSpan**（MSpanへのポインタの配列）に変更されました。さらに、配列の現在の要素数を追跡するnspanと、配列の現在の容量を追跡するnspancapという2つのフィールドが追加されました。これにより、allspansは動的にサイズが変更可能な配列として機能します。

`RecordSpan`関数の変更 (`src/pkg/runtime/mheap.c`)

RecordSpan関数は、新しく確保されたMSpanをMHeapのallspansリスト（変更後は配列）に追加する役割を担います。

変更前は、新しいMSpanをリンクリストの先頭に追加していました。

// 変更前のRecordSpanロジック (簡略化)
s->allnext = h->allspans;
h->allspans = s;

これは、リンクリストに要素を追加する典型的な方法です。

// 変更後のRecordSpanロジック (簡略化)
if(h->nspan >= h->nspancap) {
    // 配列のリサイズロジック:
    // 新しい、より大きな配列を割り当て
    cap = 64*1024/sizeof(all[0]); // 初期容量または最小拡張単位
    if(cap < h->nspancap*3/2) // 現在の容量の1.5倍、ただし最小値は上記
        cap = h->nspancap*3/2;
    all = (MSpan**)runtime·SysAlloc(cap*sizeof(all[0])); // OSからメモリを確保
    if(h->allspans) {
        runtime·memmove(all, h->allspans, h->nspancap*sizeof(all[0])); // 既存要素をコピー
        runtime·SysFree(h->allspans, h->nspancap*sizeof(all[0])); // 古い配列を解放
    }
    h->allspans = all;
    h->nspancap = cap;
}
h->allspans[h->nspan++] = s; // 配列の末尾にスパンを追加し、要素数をインクリメント

このリサイズロジックは、GoランタイムがOSから直接メモリを確保・解放するためのruntime·SysAllocとruntime·SysFreeを使用しています。runtime·memmoveはメモリブロックを効率的にコピーするための関数です。

GCスイープロジックの変更 (`src/pkg/runtime/mgc0.c`)

GCのスイープフェーズでは、allspansを走査して、マークされなかったオブジェクトを含むスパンをクリーンアップします。この走査ロジックが、リンクリストから配列への変更に合わせて更新されました。

変更前は、work.spansというリンクリストのポインタを辿っていました。

// 変更前のsweepロジック (簡略化)
for(;;) {
    s = work.spans;
    if(s == nil)
        break;
    // 複数のゴルーチンが同時にwork.spansを更新しようとした際の競合を避けるためのCAS操作
    if(!runtime·casp(&work.spans, s, s->allnext))
        continue;
    // ... スパン s を処理 ...
}

runtime·caspはCompare-And-Swap操作で、並行処理において共有変数へのアクセスを同期させるために使用されます。

変更後、スイープはallspans配列をインデックスで走査するように変更されました。

// 変更後のsweepロジック (簡略化)
uint32 spanidx, nspan;
// ...
nspan = runtime·mheap.nspan; // 全体のスパン数
allspans = runtime·mheap.allspans; // スパン配列のポインタ
for(;;) {
    // work.spanidxをアトミックにインクリメントし、その前の値を取得
    spanidx = runtime·xadd(&work.spanidx, 1) - 1;
    if(spanidx >= nspan) // 全てのMSpanを処理し終えたらループを抜ける
        break;
    s = allspans[spanidx]; // 配列への直接アクセス
    // ... スパン s を処理 ...
}

ベンチマーク結果の分析

コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されています。ns/opは1操作あたりのナノ秒を示し、値が小さいほど高速です。deltaは変化率です。

garbage.BenchmarkTree系: 全体的にわずかながら改善が見られます（-1%から-3%程度）。これは、MSpanの走査が効率化されたことによるものと考えられます。
garbage.BenchmarkTree2系、garbage.BenchmarkParser系: これらのベンチマークでは、ほとんど変化がないか、わずかに悪化しているものもあります。これは、これらのベンチマークの特性が、allspansの走査効率の影響をあまり受けないためかもしれません。
PauseとLastPauseを含むベンチマーク: これらはGCによるSTW時間（またはGCの最終段階での一時停止時間）を測定しています。これらのベンチマークでは、改善が見られるものもあれば、悪化しているものもあります。特にgarbage.BenchmarkParserLastPause-16では-23.57%と大幅な改善が見られますが、garbage.BenchmarkTreeLastPause-2では+13.89%と悪化しています。これは、この時点での変更が並列GCの「準備」段階であり、まだ完全に最適化された並列GCが実装されていないため、特定のシナリオではオーバーヘッドが発生する可能性を示唆しています。しかし、全体としては、並列GCへの移行が既存の性能を大きく損なわないことを確認するためのベンチマークとして機能しており、将来的な改善の余地があることを示唆しています。

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

src/pkg/runtime/malloc.h:
- MSpan構造体から、allspansリンクリストで使用されていたallnextフィールドが削除されました。
- MHeap構造体内のallspansフィールドの型が、リンクリストの先頭ポインタであるMSpan*から、MSpanへのポインタの配列であるMSpan**に変更されました。
- allspans配列の管理のために、現在の要素数を表すnspanと、配列の現在の容量を表すnspancapという2つのuint32型フィールドがMHeap構造体に追加されました。
src/pkg/runtime/mgc0.c:
- GCのスイープフェーズを実装するsweep関数において、MSpanを走査するロジックが変更されました。従来のリンクリストを辿る方式から、MHeap.allspans配列をインデックスで走査する方式に切り替わりました。
- 並列スイープを可能にするため、work構造体（GC作業の状態を保持）にspanidxフィールドが追加され、runtime·xadd（アトミック加算）を用いて複数のゴルーチンが並列に異なるスパンを処理できるように変更されました。
- GC開始時にwork.spansをruntime·mheap.allspansに設定していた初期化処理が、work.spanidx = 0;に変更されました。
src/pkg/runtime/mheap.c:
- 新しいMSpanが確保された際に、それをMHeap.allspansに追加するRecordSpan関数の実装が変更されました。リンクリストの先頭に追加する代わりに、allspans配列の末尾にMSpanのポインタを追加するようになりました。
- allspans配列の容量が不足した場合に、より大きな配列を動的に割り当て、既存の要素をコピーし、古い配列を解放するというリサイズロジックがRecordSpan関数内に実装されました。

コアとなるコードの解説

このコミットの最も重要な変更点は、Goランタイムのメモリヒープ管理において、すべてのMSpanオブジェクトを追跡するMHeap.allspansのデータ構造を、リンクリストから動的配列へと根本的に変更したことです。

従来のGoランタイムでは、MHeap.allspansはMSpan構造体内のallnextポインタを介して連結されたリンクリストとして機能していました。この構造はシンプルですが、GCのスイープフェーズのように、すべてのMSpanを効率的に走査する必要がある場面では、いくつかの課題がありました。

並列処理のボトルネック: リンクリストを走査する際、複数のゴルーチンが同時にリストを辿ろうとすると、ポインタの更新や読み取りにおいて競合が発生しやすくなります。これを避けるためには、ロックによる厳密な同期が必要となり、並列化のメリットが相殺されてしまう可能性がありました。特に、runtime·caspのようなアトミック操作を使っても、リストの先頭から順に要素を取り出すモデルでは、本質的な並列性に限界がありました。
キャッシュ効率の悪さ: リンクリストの要素はメモリ上で連続して配置されるとは限りません。そのため、CPUのキャッシュにデータが乗りづらく、メモリアクセスが遅くなる傾向がありました。

このコミットでは、これらの課題を解決するために、MHeap.allspansをMSpanへのポインタの配列（MSpan**）に変更しました。この変更により、以下のような重要なメリットがもたらされます。

真の並列走査の実現: mgc0.cのsweep関数における変更がその典型です。runtime·xaddというアトミックな加算操作を用いて、複数のゴルーチンがそれぞれ異なるインデックスを取得し、allspans配列の異なる部分を独立して処理できるようになりました。これにより、ロックの競合を最小限に抑えつつ、GCのスイープフェーズを真に並列に実行することが可能になります。各ゴルーチンは、配列の特定の範囲を責任を持って処理できるため、効率的な負荷分散が実現されます。
キャッシュ効率の劇的な向上: 配列はメモリ上で連続して配置されるため、CPUのキャッシュにデータが乗りやすくなります。これにより、MSpanデータへのアクセスが高速化され、GCの全体的なパフォーマンス向上に大きく寄与します。連続したメモリ領域へのアクセスは、現代のCPUアーキテクチャにおいて非常に効率的です。
動的な拡張性: mheap.cのRecordSpan関数に実装されたリサイズロジックにより、allspans配列は必要に応じて動的に拡張されます。これにより、メモリ使用量を効率的に管理しつつ、多数のMSpanを柔軟に扱えるようになります。これは、Goプログラムが実行中に大量のメモリを確保・解放するようなシナリオにおいて特に重要です。

この変更は、GoのGCが初期のSTW方式から、より高性能な並列・コンカレントGCへと進化していく上での極めて重要な基盤整備でした。このコミットによって、Goランタイムは、GCの実行中にアプリケーションの停止時間を最小限に抑え、全体的なスループットを向上させるための道筋を確立しました。

参考にした情報源リンク

Go言語の公式ドキュメント: https://go.dev/doc/
Goのソースコードリポジトリ: https://github.com/golang/go
GoのChange List (CL) システム: https://go.dev/cl/
Web検索結果: "Go language garbage collection 2012 parallel GC MHeap.allspans"
- dev.to: https://dev.to/ (GoのGCに関する一般的な情報)
- stackoverflow.com: https://stackoverflow.com/ (GoのGCに関する一般的な情報)
- go.dev: https://go.dev/ (GoのGCに関する公式情報)
- github.com: https://github.com/ (Goのソースコードに関する情報)
- medium.com: https://medium.com/ (GoのGCに関する一般的な情報)
- golang.org: https://golang.org/ (Goの公式ウェブサイト)

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

Go言語のメモリ管理とMHeap

ガベージコレクション（GC）の基本

並列処理とデータ構造の選択

技術的詳細

`MSpan`構造体の変更 (`src/pkg/runtime/malloc.h`)

`MHeap`構造体の変更 (`src/pkg/runtime/malloc.h`)

`RecordSpan`関数の変更 (`src/pkg/runtime/mheap.c`)

GCスイープロジックの変更 (`src/pkg/runtime/mgc0.c`)

ベンチマーク結果の分析

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

コアとなるコードの解説

関連リンク

参考にした情報源リンク

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

Go言語のメモリ管理とMHeap, MSpan

ガベージコレクション（GC）の基本

並列処理とデータ構造の選択

技術的詳細

`MSpan`構造体の変更 (`src/pkg/runtime/malloc.h`)

`MHeap`構造体の変更 (`src/pkg/runtime/malloc.h`)

`RecordSpan`関数の変更 (`src/pkg/runtime/mheap.c`)

GCスイープロジックの変更 (`src/pkg/runtime/mgc0.c`)

ベンチマーク結果の分析

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

コアとなるコードの解説

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo