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

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

このコミットは、Go言語のランタイムにおけるガベージコレクション（GC）の「スイープフェーズ」のパフォーマンスを向上させるための変更です。具体的には、スイープ処理をより効率的に並列化することで、GCの実行時間を短縮し、全体的なアプリケーションのパフォーマンスを改善しています。

コミット

commit 845aa1fc2c86d761a96d31de5e168d2a0f76f0da
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue May 22 13:35:52 2012 -0400

    runtime: faster GC sweep phase
    benchmark                              old ns/op    new ns/op    delta
    
    garbage.BenchmarkParser               3731065750   3715543750   -0.41%
    garbage.BenchmarkParser-2             3631299750   3495248500   -3.75%
    garbage.BenchmarkParser-4             3386486000   3339353000   -1.39%
    garbage.BenchmarkParser-8             3267632000   3286422500   +0.58%
    garbage.BenchmarkParser-16            3299203000   3316081750   +0.51%
    
    garbage.BenchmarkTree                  977532888    919453833   -5.94%
    garbage.BenchmarkTree-2                919948555    853478000   -7.23%
    garbage.BenchmarkTree-4                841329000    790207000   -6.08%
    garbage.BenchmarkTree-8                787792777    740380666   -6.01%
    garbage.BenchmarkTree-16               899257166    846594555   -5.86%
    
    garbage.BenchmarkTree2                 574876300    571885800   -0.52%
    garbage.BenchmarkTree2-2               348162700    345888900   -0.65%
    garbage.BenchmarkTree2-4               184912500    179137000   -3.22%
    garbage.BenchmarkTree2-8               104243900    103485600   -0.73%
    garbage.BenchmarkTree2-16               97269500     85137100  -14.25%
    
    garbage.BenchmarkParserPause           141101976    157746974  +11.80%
    garbage.BenchmarkParserPause-2         103096051     83043048  -19.45%
    garbage.BenchmarkParserPause-4          52153133     45951111  -11.89%
    garbage.BenchmarkParserPause-8          36730190     38901024   +5.91%
    garbage.BenchmarkParserPause-16         32678875     29578585   -9.49%
    
    garbage.BenchmarkTreePause              29487065     29648439   +0.55%
    garbage.BenchmarkTreePause-2            22443494     21306159   -5.07%
    garbage.BenchmarkTreePause-4            15799691     14985647   -5.15%
    garbage.BenchmarkTreePause-8            10768112     9531420   -12.97%
    garbage.BenchmarkTreePause-16           16329891     15205158   -6.89%
    
    garbage.BenchmarkTree2Pause           2586957240   2577533200   -0.36%
    garbage.BenchmarkTree2Pause-2         1683383760   1673923800   -0.56%
    garbage.BenchmarkTree2Pause-4         1102860320   1074040280   -2.68%
    garbage.BenchmarkTree2Pause-8          902627920    886122400   -1.86%
    garbage.BenchmarkTree2Pause-16         856470920    804152320   -6.50%
    
    garbage.BenchmarkParserLastPause       277316000    280839000   +1.25%
    garbage.BenchmarkParserLastPause-2     179446000    163687000   -8.78%
    garbage.BenchmarkParserLastPause-4     106752000     94144000  -11.81%
    garbage.BenchmarkParserLastPause-8      57758000     61640000   +6.72%
    garbage.BenchmarkParserLastPause-16     51235000     42552000  -16.95%
    
    garbage.BenchmarkTreeLastPause          45244000     50786000  +12.25%
    garbage.BenchmarkTreeLastPause-2        37163000     34654000   -6.75%
    garbage.BenchmarkTreeLastPause-4        24178000     21967000   -9.14%
    garbage.BenchmarkTreeLastPause-8        20390000     15648000  -30.30%
    garbage.BenchmarkTreeLastPause-16       22398000     20180000   -9.90%
    
    garbage.BenchmarkTree2LastPause       5748706000   5718809000   -0.52%
    garbage.BenchmarkTree2LastPause-2     3481570000   3458844000   -0.65%
    garbage.BenchmarkTree2LastPause-4     1849073000   1791330000   -3.22%
    garbage.BenchmarkTree2LastPause-8     1042375000   1034811000   -0.73%
    garbage.BenchmarkTree2LastPause-16     972637000    851323000  -14.25%
    
    There is also visible improvement in consumed CPU time:
    tree2 -heapsize=8000000000 -cpus=12
    before: 248.74user 6.36system 0:52.74elapsed 483%CPU
    after:  229.86user 6.33system 0:51.08elapsed 462%CPU
    -1.66s of real time, but -18.91s of consumed CPU time
    
    R=golang-dev
    CC=golang-dev
    https://golang.org/cl/6215065

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

https://github.com/golang/go/commit/845aa1fc2c86d761a96d31de5e168d2a0f76f0da

元コミット内容

このコミットの目的は、Goランタイムのガベージコレクション（GC）におけるスイープフェーズの速度を向上させることです。ベンチマーク結果が示されており、多くのシナリオでns/op（1操作あたりのナノ秒）が減少しており、これはパフォーマンスの改善を意味します。特にgarbage.BenchmarkTreeやgarbage.BenchmarkTree2系のベンチマークで顕著な改善が見られます。また、CPU時間の消費も減少しており、全体的な効率が向上していることが示されています。

変更の背景

Go言語の初期のガベージコレクションは、ストップ・ザ・ワールド（Stop-The-World: STW）方式を採用しており、GC実行中はアプリケーションの実行が完全に停止していました。このSTW時間は、特にヒープサイズが大きくなるにつれて顕著になり、アプリケーションのレイテンシに悪影響を与えていました。GCの各フェーズ（マーク、スイープなど）の効率を向上させることは、STW時間を短縮し、Goアプリケーションの応答性とスループットを改善するための重要な課題でした。

このコミットは、GCのスイープフェーズに焦点を当てています。スイープフェーズは、マークフェーズで到達可能とマークされなかったオブジェクトが占めるメモリを解放し、再利用可能にする役割を担います。この処理をより高速かつ並列に行うことで、GC全体のオーバーヘッドを削減し、特にマルチコア環境でのパフォーマンスを最大化することが背景にあります。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはや使用されていない（到達不可能になった）ものを自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ管理の煩雑さから解放され、メモリリークのリスクを低減できます。Go言語のGCは、主に以下のフェーズで構成されます。

  1. マークフェーズ (Mark Phase): プログラムが現在使用している（到達可能な）オブジェクトを特定し、マークします。GoのGCは、初期には三色マーク＆スイープアルゴリズムのバリアントを使用していました。
  2. スイープフェーズ (Sweep Phase): マークされなかった（到達不可能な）オブジェクトが占めるメモリ領域を解放し、今後のメモリ割り当てのために利用可能にします。このフェーズでは、ヒープ全体を走査し、マークされていないメモリ領域を「フリーリスト」に戻すなどの処理が行われます。

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

STWは、GCが実行される際に、アプリケーションの全てのゴルーチン（スレッド）の実行を一時的に停止させる期間を指します。この停止期間中にGCはメモリの状態を安全に検査・変更します。STW時間が長いと、アプリケーションの応答性が低下し、ユーザー体験に悪影響を与える可能性があります。GoのGCは、STW時間を最小限に抑えるように設計されていますが、完全にゼロにすることは困難です。

Goランタイムの並列処理

Goランタイムは、複数のCPUコアを効率的に利用するために、ゴルーチンとスケジューラを提供します。GCのようなシステムレベルのタスクも、可能な限り並列化して実行することで、マルチコアプロセッサの恩恵を受け、全体のスループットを向上させます。

MSpan

Goランタイムのメモリ管理において、ヒープはMSpanと呼ばれる連続したメモリブロックの集合として管理されます。各MSpanは特定のサイズのオブジェクトを格納するために使用され、GCのスイープフェーズでは、これらのMSpanを単位としてメモリの解放が行われます。

ParFor (Parallel For)

ParForはGoランタイム内部で使用される並列処理の抽象化です。これは、特定のタスク（この場合はスイープ処理）を複数のワーカー（ゴルーチン）に分割し、並列に実行するためのメカニズムを提供します。通常、ParForはワークスチール（work-stealing）キューなどの技術を利用して、ワーカー間の負荷分散を効率的に行い、アイドル状態のワーカーが他のワーカーのタスクを「盗む」ことで、全体のスループットを向上させます。

技術的詳細

このコミットの主要な技術的変更点は、GCスイープフェーズの並列化戦略を、より汎用的で効率的なParForメカニズムに移行したことです。

以前のスイープ処理は、work.spanidxという共有カウンタをruntime·xadd（アトミック加算）でインクリメントしながら、各ゴルーチンがMSpanを順次取得して処理する方式でした。これは基本的な並列化ですが、負荷分散やワーカー間の同期にオーバーヘッドが生じる可能性がありました。

新しいアプローチでは、ParFor構造体と関連する関数（runtime·parforalloc, runtime·parforsetup, runtime·parfordo）を導入しています。

  1. work.sweepforの導入: work構造体内にParFor *sweepfor;というフィールドが追加されました。これはスイープ処理専用のParForインスタンスを指します。
  2. sweep関数の削除とsweepspanの変更: 以前のsweep関数は削除され、sweepspan関数のシグネチャがsweepspan(ParFor *desc, uint32 idx)に変更されました。これにより、sweepspanはParForフレームワークによって呼び出されるコールバック関数となり、特定のMSpanのインデックスを受け取ってそのスイープ処理を実行するようになります。
  3. runtime·gcにおけるParForのセットアップと実行:
    • runtime·gcprocs()でGCに利用可能なプロセッサ数（ゴルーチン数）を取得します。
    • runtime·parforalloc(MaxGcproc)でParForインスタンスを確保します。
    • runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap.nspan, nil, true, sweepspan);を呼び出し、ParForを初期化します。ここで、runtime·mheap.nspanはスイープ対象のMSpanの総数であり、sweepspanが各MSpanに対して並列に実行されるタスクとして登録されます。
    • runtime·parfordo(work.sweepfor);を呼び出すことで、設定されたParForが実行され、複数のゴルーチンがsweepspanを並列に実行します。これにより、スイープ処理が効率的に並列化されます。
  4. 同期メカニズムの簡素化: 以前使用されていたmarkgateやsweepgateといった明示的なロックが削除されました。これは、ParForが内部でより洗練された同期とワークスチールメカニズムを提供するため、これらの高レベルなロックが不要になったことを示唆しています。
  5. 統計情報の収集: ParForの実行によって得られるnprocyield（プロセッサの切り替え回数）、nosyield（OSスケジューラへのyield回数）、nsleep（スリープ回数）、nsteal（ワークスチール回数）、nstealcnt（ワークスチール試行回数）といった詳細な統計情報がGCトレース出力に追加され、GCの動作分析に役立つようになっています。

この変更により、スイープフェーズは複数のCPUコアを最大限に活用し、より高速に完了するようになります。特に、ヒープサイズが大きく、スイープ対象のMSpanが多い場合に、その効果が顕著に現れます。

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

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

  1. work構造体の変更:

    • debugmarkdoneフィールドの追加。
    • markgate、sweepgate、spanidxフィールドの削除。
    • sweepforフィールド（ParForへのポインタ）の追加。
    // 変更前
// static struct {
//     // ...
//     Lock    markgate;
//     Lock    sweepgate;
//     uint32  spanidx;
//     // ...
// } work;

// 変更後
static struct {
    // ...
    volatile uint32 debugmarkdone; // 追加
    ParFor  *sweepfor;             // 追加
    // ...
} work;

  2. sweep関数の削除:

    • 以前のsweep関数全体が削除されました。
    // 変更前: この関数全体が削除された
// static void
// sweep(void)
// {
//     // ...
// }

  3. sweepspan関数のシグネチャと実装の変更:

    • 引数がMSpan *sからParFor *desc, uint32 idxに変更され、MSpanの取得方法も変更されました。
    // 変更前
// static void
// sweepspan(MSpan *s)
// {
//     // ...
// }

// 変更後
static void
sweepspan(ParFor *desc, uint32 idx) // シグネチャ変更
{
    MSpan *s; // ローカル変数として宣言
    USED(&desc);
    s = runtime·mheap.allspans[idx]; // idxからMSpanを取得
    // ...
}

  4. runtime·gchelper関数の変更:

    • markgateとsweepgateに関するロック/アンロック処理の削除。
    • runtime·parfordo(work.sweepfor);の呼び出しを追加。
    // 変更前
// void
// runtime·gchelper(void)
// {
//     runtime·lock(&work.markgate);
//     runtime·unlock(&work.markgate);
//     scanblock(nil, 0);
//     runtime·lock(&work.sweepgate);
//     runtime·unlock(&work.sweepgate);
//     sweep();
//     // ...
// }

// 変更後
void
runtime·gchelper(void)
{
    scanblock(nil, 0);
    // ... debugmarkdoneの待機ロジック追加
    runtime·parfordo(work.sweepfor); // ParForによる並列スイープの実行
    // ...
}

  5. runtime·gc関数の変更:

    • markgateとsweepgateに関するロック/アンロック処理の削除。
    • work.sweepforの初期化とruntime·parforsetupによる設定。
    • sweep()の呼び出しをruntime·parfordo(work.sweepfor);に置き換え。
    • ParForからの統計情報（nsteal, nstealcntなど）の取得と出力への追加。
    // 変更前
// void
// runtime·gc(int32 force)
// {
//     // ...
//     runtime·lock(&work.markgate);
//     runtime·lock(&work.sweepgate);
//     // ...
//     runtime·unlock(&work.markgate);
//     mark(scanblock);
//     // ...
//     work.spanidx = 0;
//     runtime·unlock(&work.sweepgate);
//     sweep();
//     // ...
// }

// 変更後
void
runtime·gc(int32 force)
{
    // ...
    work.nwait = 0;
    work.ndone = 0;
    work.debugmarkdone = 0; // 初期化
    work.nproc = runtime·gcprocs();
    if(work.sweepfor == nil)
        work.sweepfor = runtime·parforalloc(MaxGcproc); // ParForの確保
    runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap.nspan, nil, true, sweepspan); // ParForのセットアップ
    // ...
    mark(scanblock);
    // ... debugmarkdoneの設定
    runtime·parfordo(work.sweepfor); // ParForによる並列スイープの実行
    // ...
    stats.nprocyield += work.sweepfor->nprocyield; // 統計情報の取得
    stats.nosyield += work.sweepfor->nosyield;
    stats.nsleep += work.sweepfor->nsleep;
    // ... gctrace出力にnsteal, nstealcntを追加
}

コアとなるコードの解説

このコミットの核心は、Goランタイムのガベージコレクタのスイープフェーズを、カスタムの並列処理フレームワークであるParForを利用して完全に並列化することです。

  1. ParForの導入と役割:

    • ParForは、Goランタイムが内部で並列タスクを実行するために設計された汎用的なメカニズムです。これは、タスクのチャンクを複数のゴルーチン（GCヘルパーゴルーチンやメインGCゴルーチン）に分散させ、それぞれが独立して作業を進めることを可能にします。
    • work.sweepforは、スイープフェーズ専用のParForインスタンスとして機能します。

  2. スイープ処理のタスク分割:

    • GoのヒープはMSpanと呼ばれるメモリブロックに分割されています。スイープフェーズでは、これらのMSpanを一つずつ処理していく必要があります。
    • runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap.nspan, nil, true, sweepspan);の呼び出しにより、ParForはruntime·mheap.nspan（ヒープ内の全MSpanの数）をタスクの総数として認識し、sweepspan関数を各タスク（各MSpanのスイープ）の実行ハンドラとして登録します。
    • work.nprocは、この並列処理に参加するゴルーチンの数を指定します。

  3. 並列実行とワークスチール:

    • runtime·parfordo(work.sweepfor);が呼び出されると、ParForは内部的に複数のゴルーチンを起動（または既存のGCヘルパーゴルーチンを利用）し、登録されたsweepspan関数を並列に実行します。
    • ParForは通常、ワークスチールアルゴリズムを実装しています。これは、あるゴルーチンが自分のタスクキューを使い果たしてアイドル状態になった場合、他のゴルーチンのタスクキューから未処理のタスクを「盗む」ことで、CPUコアの利用率を最大化し、負荷分散を最適化する手法です。これにより、スイープ処理の全体的な完了時間が短縮されます。

  4. 同期の簡素化:

    • 以前のバージョンでは、markgateやsweepgateといった明示的なロックを使用して、GCヘルパーゴルーチンとメインGCゴルーチン間の同期を行っていました。
    • ParForは内部でより低レベルかつ効率的な同期プリミティブ（アトミック操作など）を使用するため、これらの高レベルなロックが不要になり、コードが簡素化されるとともに、ロック競合によるオーバーヘッドが削減されます。

この変更により、GoのGCスイープフェーズは、単一のゴルーチンが順次MSpanを処理するのではなく、複数のゴルーチンが同時に異なるMSpanを処理できるようになり、マルチコア環境でのGC性能が大幅に向上しました。

関連リンク

  • Go言語のガベージコレクションに関する公式ドキュメントやブログ記事（当時のもの）
  • Goランタイムのソースコード（特にsrc/runtime/mgc.goやsrc/runtime/mgc0.cの進化）
  • GoのParForメカニズムに関する詳細な技術解説（もし公開されているものがあれば）

参考にした情報源リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • このコミットのGerrit Change-ID: https://golang.org/cl/6215065
  • Go言語のガベージコレクションに関する一般的な知識（Goのドキュメント、技術ブログ、論文など）
  • 並列処理におけるワークスチールアルゴリズムに関する一般的な知識

（注: ParForはGoランタイムの内部実装の詳細であり、外部に詳細なドキュメントが公開されていない場合があります。この解説は、コミットのコード変更とGoのGCの一般的な知識に基づいて推測されたものです。）