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

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

このコミットは、Goランタイムのガベージコレクション（GC）におけるmarkspan関数のパフォーマンス最適化を目的としています。特に、メモリを大量に消費するプログラムがNUMA（Non-Uniform Memory Access）アーキテクチャを持つマルチプロセッサマシン上で実行される際のスループット向上に焦点を当てています。この変更により、8ノードのNUMAマシン上でメモリを大量に消費するプログラムのスループットが2倍に向上したと報告されています。

コミット

runtime: optimize markspan
Increases throughput by 2x on a memory hungry program on 8-node NUMA machine.

LGTM=rsc
R=rsc
CC=golang-codereviews
https://golang.org/cl/100230043

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

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

元コミット内容

runtime: optimize markspan
Increases throughput by 2x on a memory hungry program on 8-node NUMA machine.

変更の背景

Goのガベージコレクション（GC）は、プログラムの実行中に不要になったメモリを自動的に解放し、再利用可能にする重要な役割を担っています。GCの効率は、特にメモリを大量に割り当てたり、多くのオブジェクトを生成したりするアプリケーションにおいて、全体のパフォーマンスに直接影響します。

このコミットの背景には、GoランタイムのGCにおける「マークフェーズ」のパフォーマンスボトルネックがありました。マークフェーズでは、GCが到達可能な（まだ使用されている）オブジェクトを識別し、それらに「マーク」を付けます。このマーク付けのプロセスは、メモリ上のビットマップを更新することで行われます。

特に、NUMA（Non-Uniform Memory Access）アーキテクチャを持つシステムでは、メモリへのアクセス速度が、そのメモリがどのプロセッサに「近い」かによって異なります。ローカルメモリへのアクセスは高速ですが、他のプロセッサのローカルメモリ（リモートメモリ）へのアクセスは、インターコネクトを介した通信が必要となるため、遅延が大きくなります。

従来のmarkspan関数は、ビットマップの各ビットを更新する際に、対応するメモリワードを頻繁に読み書きしていました。メモリを大量に消費するプログラムでは、このmarkspan関数が頻繁に呼び出され、多数のビットマップワードが更新されます。NUMA環境下で複数のCPUが同じビットマップワードにアクセスしようとすると、キャッシュコヒーレンシの維持やリモートメモリへのアクセスによるオーバーヘッドが顕著になり、GCのスループットが低下していました。

このコミットは、この頻繁なメモリ書き込みを最適化し、特にNUMA環境でのGC性能を向上させることを目的としています。

前提知識の解説

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

GoのGCは、主に「三色マーク・アンド・スイープ」アルゴリズムをベースにしています。これは、オブジェクトを白（未訪問）、灰（訪問済みだが参照先は未訪問）、黒（訪問済みで参照先も訪問済み）の3色に分類しながら、到達可能なオブジェクトをマークしていく方式です。

  • マークフェーズ: GCの開始時に、すべてのオブジェクトは「白」と見なされます。GCはルート（グローバル変数、スタックなど）から到達可能なオブジェクトを探索し、それらを「灰」にマークし、キューに入れます。キューからオブジェクトを取り出し、その参照先を探索して「灰」にマークし、自身を「黒」にマークします。このプロセスをキューが空になるまで繰り返します。最終的に「黒」になったオブジェクトは到達可能であり、残りの「白」のオブジェクトは不要と判断されます。
  • スイープフェーズ: マークフェーズで「白」と判断されたオブジェクトが占めていたメモリ領域を解放し、再利用可能にします。

このコミットは、マークフェーズにおけるビットマップの更新処理、特にmarkspan関数に焦点を当てています。

Goのメモリ管理とSpan、Bitmap

Goのランタイムは、ヒープメモリを「span」と呼ばれる連続したメモリブロックに分割して管理しています。各spanは、特定のサイズのオブジェクトを格納するために使用されます。

GoのGCは、ヒープ上のオブジェクトの状態を追跡するためにビットマップを使用します。これらのビットマップは、各メモリワードがオブジェクトの開始点であるか、またはマークされているかなどの情報を示します。markspan関数は、GCのマークフェーズ中に、特定のメモリ領域（span）内のオブジェクトが到達可能であることを示すために、対応するビットマップのビットをセットする役割を担います。

NUMA (Non-Uniform Memory Access) アーキテクチャ

NUMAは、マルチプロセッサシステムにおけるメモリ設計の一種です。NUMAシステムでは、各プロセッサ（またはプロセッサグループ）が自身のローカルメモリを持ち、そのローカルメモリへのアクセスは非常に高速です。しかし、他のプロセッサのローカルメモリ（リモートメモリ）にアクセスする際には、プロセッサ間のインターコネクトを介した通信が必要となり、アクセスレイテンシが増加し、スループットが低下します。

メモリを頻繁に読み書きするようなワークロード、特に複数のCPUが同じメモリ領域にアクセスしようとする場合には、NUMAの特性がパフォーマンスに大きく影響します。キャッシュコヒーレンシの維持（複数のCPUキャッシュ間でデータの一貫性を保つこと）も、リモートメモリへのアクセスを伴う場合にオーバーヘッドを発生させます。

技術的詳細

このコミットの最適化は、runtime/mgc0.c内のruntime·markspan関数に適用されています。この関数は、GCのマークフェーズ中に、特定のメモリ領域（vからv + size * nまで）内のオブジェクトが到達可能であることを示すために、対応するビットマップのビットをセットします。

元の実装では、markspan関数はループ内で各オブジェクトに対応するビットマップのビットを個別に更新していました。この更新は、以下の行で行われていました。

*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);

ここで、bはビットマップワードへのポインタ、shiftはそのワード内でビットをセットする位置を示します。この操作は、*bの値を読み込み、ビットをセットし、その結果を*bに書き戻すという一連の「読み込み-変更-書き込み」サイクルを構成します。

NUMA環境では、この頻繁な「読み込み-変更-書き込み」サイクルがパフォーマンスのボトルネックとなっていました。特に、複数のゴルーチンが異なるNUMAノードから同じビットマップワードにアクセスしようとすると、キャッシュラインの競合（false sharingを含む）やリモートメモリへのアクセスが頻繁に発生し、システム全体のGCスループットが低下します。

このコミットによる最適化は、このビットマップワードへの書き込み回数を減らすことにあります。具体的には、b0とxという2つの新しい一時変数を導入しています。

  • b0: 現在処理中のビットマップワードのポインタをキャッシュします。
  • x: 現在処理中のビットマップワードにセットすべきビットの累積値を保持します。

変更後のロジックは以下のようになります。

// 新しい変数の宣言
uintptr *b, *b0, off, shift, i, x;
// ...
b0 = nil; // b0をnilで初期化
x = 0;    // xを0で初期化
for(; n-- > 0; p += size) {
    // ... (offとshiftの計算は変更なし)
    if(b0 != b) { // 現在のビットマップワードが、前回処理したワードと異なる場合
        if(b0 != nil) // b0がnilでない（つまり、前回のワードが存在する）場合
            *b0 = x;  // 前回のワードに累積したビット値を一度だけ書き込む
        b0 = b;       // b0を現在のワードに更新
        x = 0;        // xをリセット
    }
    x |= bitAllocated<<shift; // 現在のワードにセットすべきビットをxに累積
}
*b0 = x; // ループ終了後、最後に残った累積ビット値を書き込む

この最適化のポイントは、同じビットマップワードbに対して複数のビットをセットする場合、そのワードを一度だけ読み込み（if(b0 != b)の条件が真になった時）、必要なビットをxに累積し、最後にxの値を*b0に一度だけ書き込むという点です。これにより、*bへの読み書きの回数が大幅に削減されます。

例えば、連続する複数のオブジェクトが同じビットマップワードに属している場合、元のコードではそのオブジェクトの数だけ*bへの読み書きが発生していましたが、最適化後はそのビットマップワードへの書き込みが最大で1回（または、そのワードが最初に処理される時と、そのワードの処理が完了する時の2回）に削減されます。

この書き込み回数の削減は、特にNUMA環境において、キャッシュラインの競合を減らし、リモートメモリへのアクセス頻度を低下させることで、GCのスループットを劇的に向上させます。報告されている「2倍のスループット向上」は、この最適化がNUMA環境の特性に非常に効果的であったことを示しています。

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

diff --git a/src/pkg/runtime/mgc0.c b/src/pkg/runtime/mgc0.c
index 70c0c933ad..1ba0c0ee4a 100644
--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -2785,7 +2785,7 @@ runtime·checkfreed(void *v, uintptr n)
 void
 runtime·markspan(void *v, uintptr size, uintptr n, bool leftover)
 {
-	uintptr *b, off, shift, i;\n+\tuintptr *b, *b0, off, shift, i, x;
 	byte *p;
 
 	if((byte*)v+size*n > (byte*)runtime·mheap.arena_used || (byte*)v < runtime·mheap.arena_start)
@@ -2804,6 +2804,9 @@ runtime·markspan(void *v, uintptr size, uintptr n, bool leftover)
 \tp = v;\n \tif(leftover)\t// mark a boundary just past end of last block too\n \t\tn++;\n+\n+\tb0 = nil;\n+\tx = 0;\n \tfor(; n-- > 0; p += size) {\n \t\t// Okay to use non-atomic ops here, because we control\n \t\t// the entire span, and each bitmap word has bits for only\n@@ -2812,8 +2815,15 @@ runtime·markspan(void *v, uintptr size, uintptr n, bool leftover)\n \t\toff = (uintptr*)p - (uintptr*)runtime·mheap.arena_start;  // word offset\n \t\tb = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;\n \t\tshift = off % wordsPerBitmapWord;\n-\t\t*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);\n+\t\tif(b0 != b) {\n+\t\t\tif(b0 != nil)\n+\t\t\t\t*b0 = x;\n+\t\t\tb0 = b;\n+\t\t\tx = 0;\n+\t\t}\n+\t\tx |= bitAllocated<<shift;\n \t}\n+\t*b0 = x;\n }\n \n // unmark the span of memory at v of length n bytes.\n```

## コアとなるコードの解説

変更は`src/pkg/runtime/mgc0.c`ファイルの`runtime·markspan`関数に集中しています。

1.  **変数の追加**:
    ```diff
    -	uintptr *b, off, shift, i;
    +	uintptr *b, *b0, off, shift, i, x;
    ```
    `b0`（前回のビットマップワードポインタ）と`x`（現在のビットマップワードにセットすべきビットの累積値）という2つの新しい変数が追加されました。

2.  **初期化**:
    ```diff
    +	b0 = nil;
    +	x = 0;
    ```
    ループに入る前に、`b0`は`nil`に、`x`は`0`に初期化されます。これは、最初のビットマップワードの処理を開始する準備です。

3.  **ビットマップ更新ロジックの変更**:
    ```diff
    -		*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);
    +		if(b0 != b) {
    +			if(b0 != nil)
    +				*b0 = x;
    +			b0 = b;
    +			x = 0;
    +		}
    +		x |= bitAllocated<<shift;
    ```
    これが最適化の核心部分です。
    *   `if(b0 != b)`: 現在処理しているオブジェクトに対応するビットマップワード`b`が、前回処理したオブジェクトのビットマップワード`b0`と異なるかどうかをチェックします。
    *   `if(b0 != nil) *b0 = x;`: もし`b0`が`nil`でなく（つまり、前回のビットマップワードが存在し）、かつ現在のワードと異なる場合、前回のワード`*b0`に累積されたビット値`x`を一度だけ書き込みます。これにより、同じワードへの複数回の書き込みが回避されます。
    *   `b0 = b;`: `b0`を現在のビットマップワード`b`に更新します。
    *   `x = 0;`: `x`をリセットし、新しいビットマップワードのためのビット累積を開始します。
    *   `x |= bitAllocated<<shift;`: 現在のオブジェクトに対応するビットを`x`に累積します。この時点では、実際のメモリへの書き込みは行われません。

4.  **ループ後の最終書き込み**:
    ```diff
    +	*b0 = x;
    ```
    ループが終了した後、最後に処理されたビットマップワード`*b0`に、累積されたビット値`x`を書き込みます。これは、ループ内で`if(b0 != b)`の条件が真にならなかった（つまり、最後のいくつかのオブジェクトが同じビットマップワードに属していた）場合に、そのワードへの書き込みを確実に行うためです。

この変更により、`markspan`関数は、同じビットマップワードに対して複数のビットをセットする際に、そのワードへの物理的なメモリ書き込み回数を大幅に削減します。これにより、特にNUMA環境下でのキャッシュコヒーレンシのオーバーヘッドやリモートメモリへのアクセスが減少し、GCのパフォーマンスが向上します。

## 関連リンク

*   Go CL 100230043: [https://golang.org/cl/100230043](https://golang.org/cl/100230043)

## 参考にした情報源リンク

*   Goのガベージコレクションに関する公式ドキュメントやブログ記事 (一般的なGo GCの知識)
*   NUMAアーキテクチャに関する一般的な情報源 (NUMAの概念理解のため)
*   Goのランタイムソースコード (mgc0.cの理解のため)