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

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

このコミットは、Go言語のランタイムにおけるガベージコレクション（GC）の内部構造から struct BitTarget を削除する変更です。これにより、GCのデータ処理フローが簡素化され、効率が向上します。

コミット

commit ee3c88482ba232a34e4b20c8474fdee64a37ca36
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Fri Mar 15 12:37:40 2013 -0400

    runtime: remove struct BitTarget
    
    R=golang-dev
    CC=dvyukov, golang-dev, rsc
    https://golang.org/cl/7845043

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

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

元コミット内容

runtime: remove struct BitTarget

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

変更の背景

Go言語のガベージコレクタは、ヒープ上のオブジェクトを効率的に管理するために様々な内部データ構造を使用します。このコミットが行われた2013年3月時点のGoのGCは、主にマーク＆スイープ方式を採用しており、オブジェクトのポインタを追跡し、到達可能なオブジェクトをマークするプロセスを含んでいました。

BitTarget 構造体は、GCのマークフェーズにおいて、ポインタのターゲットとその対応するビットマップ内の位置を一時的に保持するために使用されていました。しかし、GCの設計や実装の進化に伴い、この BitTarget が不要になった、あるいはその機能が他の既存の構造体（PtrTarget など）に統合できるようになったと考えられます。

この変更の主な背景は、GCのコードベースの簡素化と、それに伴うパフォーマンスの潜在的な改善です。不要なデータ構造を削除することで、メモリフットプリントの削減、コードの可読性の向上、そしてGCロジックの複雑性の低減が期待されます。特に、GCのようなパフォーマンスがクリティカルな部分では、わずかな最適化でも全体のスループットに大きな影響を与える可能性があります。

前提知識の解説

このコミットを理解するためには、Go言語のガベージコレクションの基本的な概念と、当時のGCの内部動作に関する知識が必要です。

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

GoのGCは、主に「並行マーク＆スイープ」アルゴリズムをベースにしています。これは、プログラムの実行と並行してGCが動作することで、アプリケーションの一時停止時間（ストップ・ザ・ワールド時間）を最小限に抑えることを目指しています。

GCの主要なフェーズは以下の通りです。

  1. マークフェーズ (Mark Phase):

    • GCのルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトを識別し、マークします。
    • このプロセス中に、新しいオブジェクトが割り当てられたり、既存のポインタが変更されたりする可能性があるため、「ライトバリア（Write Barrier）」と呼ばれるメカニズムが使用されます。ライトバリアは、ポインタの書き込み時にGCが必要な情報を記録するためのフックです。
    • マークフェーズでは、オブジェクトが「グレイ（Gray）」キューに追加され、そこからポインタがスキャンされ、参照先のオブジェクトがマークされて「ブラック（Black）」になります。参照されていないオブジェクトは「ホワイト（White）」のままです。

  2. スイープフェーズ (Sweep Phase):

    • マークされなかった（ホワイトのままの）オブジェクトは、到達不可能と判断され、メモリが解放されます。

GCにおける中間バッファ (PtrTarget, BitTarget, Workbuf)

GoのGCは、マークフェーズ中に見つかったポインタを効率的に処理するために、いくつかのバッファを使用します。

  • Workbuf (ワークバッファ): GCがスキャンすべきオブジェクトのポインタを保持する主要なバッファです。GCワーカーゴルーチンはここからポインタを取り出し、スキャンし、新しいポインタをここに追加します。
  • 中間バッファ (PtrTarget, BitTarget): Workbuf に直接書き込むのではなく、一時的にポインタ情報を保持するための小さなバッファです。これは、GCワーカーが頻繁にロックを取得して Workbuf にアクセスするオーバーヘッドを減らすために使用されます。
    • PtrTarget: ポインタのターゲットアドレスと、その型情報（ti）を保持する構造体です。これは、GCがオブジェクトをスキャンする際に、そのオブジェクトが指す他のオブジェクトを識別するために使用されます。
    • BitTarget (削除対象): このコミットで削除される構造体です。元のコメントによると、PtrTarget と同様にポインタのターゲットを保持しますが、それに加えて「ビットマップ内の対応する位置」に関する情報（bitp, shift）も保持していました。これは、GCがオブジェクトをマークする際に、そのオブジェクトがヒープのどこに位置し、どのビットがそのオブジェクトのマーク状態を示すか、といった情報を効率的に扱うために使われていたと考えられます。ビットマップは、ヒープ上の各オブジェクトのマーク状態をコンパクトに表現するために使用されるデータ構造です。

mgc0.c ファイル

src/pkg/runtime/mgc0.c は、GoランタイムのガベージコレクタのC言語部分の実装が含まれるファイルです。Goのランタイムは、Go言語とC言語（またはアセンブリ言語）のハイブリッドで書かれており、特にパフォーマンスが重要なGCやスケジューラなどの低レベルな部分はC言語で実装されていました（現在はGo言語への移行が進んでいます）。

技術的詳細

このコミットの核心は、BitTarget 構造体の削除と、それに伴うGCのデータフローの簡素化です。

BitTarget の役割（削除前）

コミット前の mgc0.c のコメントから、BitTarget は PtrTarget と共に中間バッファとして使用されていました。

// PtrTarget and BitTarget are structures used by intermediate buffers.
// The intermediate buffers hold GC data before it
// is moved/flushed to the work buffer (Workbuf).
// The size of an intermediate buffer is very small,
// so it can be allocated on stack.

そして、flushptrbuf 関数の説明図には、以下のようなフローが示されていました。

//  (find pointers)
//    Obj ------> PtrTarget (pointer targets)
//     ↑          |
//     |          | flushptrbuf (1st part,
//     |          | find block start)
//     |          ↓
//     `--------- BitTarget (pointer targets and the corresponding locations in bitmap)
//  flushptrbuf
//  (2nd part, mark and enqueue)

この図から、flushptrbuf 関数は2段階の処理を行っていたことがわかります。

  1. PtrTarget からポインタターゲットを見つけ、そのブロックの開始位置を特定する。
  2. その情報を使って BitTarget を生成し、その後 BitTarget を使ってマークとエンキュー（Workbuf への追加）を行う。

BitTarget は void *p; uintptr ti; uintptr *bitp, shift; というフィールドを持っていました。

  • p: ポインタのターゲットアドレス。
  • ti: 型情報。
  • bitp: ビットマップへのポインタ。
  • shift: ビットマップ内のビット位置を示すシフト値。

つまり、BitTarget は PtrTarget の情報に加えて、GCがオブジェクトをマークするために必要なビットマップ関連のメタデータを保持していたのです。

BitTarget 削除の理由と影響

BitTarget が削除されたということは、flushptrbuf 関数が PtrTarget の情報のみで、直接オブジェクトのマークとエンキューを行えるようになったことを意味します。これは、以下のいずれかの理由が考えられます。

  1. 情報の冗長性または統合: BitTarget が保持していたビットマップ関連の情報が、PtrTarget の型情報 (ti) から導出できるようになったか、あるいは flushptrbuf の処理ロジック内で動的に計算できるようになったため、別途構造体として保持する必要がなくなった。
  2. GCアルゴリズムの変更: GCのマークフェーズの内部アルゴリズムが変更され、BitTarget のような中間的なビットマップ情報保持構造体が不要になった。例えば、ビットマップの操作がより直接的に行われるようになった、あるいはマークの粒度が変更されたなどが考えられます。
  3. パフォーマンスの最適化: BitTarget の生成とコピーがオーバーヘッドになっていた場合、それを削除することでGCの効率が向上する。

この変更により、flushptrbuf の処理フローは以下のように簡素化されます。

//  (find pointers)
//    Obj ------> PtrTarget (pointer targets)
//     ↑          |
//     |          |
//     `----------'
//     flushptrbuf
//  (find block start, mark and enqueue)

BitTarget が削除されたことで、BufferList 構造体からも bittarget 配列が削除され、scanblock 関数内での BitTarget の割り当てや使用もなくなりました。これにより、GCのメモリ使用量がわずかに削減され、データ構造がシンプルになります。

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

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

  1. BitTarget 構造体の定義削除:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -270,7 +270,7 @@ found:
 	return true;
 }
 
-// PtrTarget and BitTarget are structures used by intermediate buffers.
+// PtrTarget is a structure used by intermediate buffers.
 // The intermediate buffers hold GC data before it
 // is moved/flushed to the work buffer (Workbuf).
 // The size of an intermediate buffer is very small,
@@ -282,19 +282,10 @@ struct PtrTarget
 	uintptr ti;
 };
 
-typedef struct BitTarget BitTarget;
-struct BitTarget
-{
-	void *p;
-	uintptr ti;
-	uintptr *bitp, shift;
-};
-

    BitTarget 構造体とその typedef が完全に削除されています。また、関連するコメントも更新され、PtrTarget のみが中間バッファとして言及されています。

  2. BufferList から bittarget 配列の削除:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -298,7 +289,6 @@ struct BufferList
 {
 	PtrTarget ptrtarget[IntermediateBufferCapacity];
-\tBitTarget bittarget[IntermediateBufferCapacity];
 	Obj obj[IntermediateBufferCapacity];
 	BufferList *next;
 };

    GCが使用する中間バッファをまとめる BufferList 構造体から、BitTarget の配列 bittarget が削除されました。

  3. flushptrbuf 関数のシグネチャ変更:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -319,14 +309,12 @@ static void enqueue(Obj obj, Workbuf **_wbuf, Obj **_wp, uintptr *_nobj);
 //  (find pointers)
 //    Obj ------> PtrTarget (pointer targets)
 //     ↑          |\n-//     |          | flushptrbuf (1st part,\n-//     |          | find block start)\n-//     |          ↓\n-//     `--------- BitTarget (pointer targets and the corresponding locations in bitmap)\n-//  flushptrbuf\n-//  (2nd part, mark and enqueue)\n+//     |          |\n+//     `----------\'\n+//     flushptrbuf\n+//  (find block start, mark and enqueue)\n static void
-flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj, BitTarget *bitbuf)\n+flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj)\n {\n     byte *p, *arena_start, *obj;\n     uintptr size, *bitp, bits, shift, j, x, xbits, off, nobj, ti, n;\n    ```
`flushptrbuf` 関数の最後の引数 `BitTarget *bitbuf` が削除されました。これにより、この関数が `BitTarget` を直接操作する必要がなくなったことが示されます。また、関連するコメントの図も簡素化されています。

  4. scanblock 関数内の BitTarget 関連の変数と初期化の削除:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -585,7 +573,6 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     	Frame *stack_ptr, stack_top, stack[GC_STACK_CAPACITY+4];\n     	BufferList *scanbuffers;\n     	PtrTarget *ptrbuf, *ptrbuf_end, *ptrbufpos;\n    -\tBitTarget *bitbuf;\n     	Obj *objbuf, *objbuf_end, *objbufpos;\n     	Eface *eface;\n     	Iface *iface;\
@@ -609,7 +596,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     	precise_type = false;\n     	nominal_size = 0;\n     \n    -\t// Allocate ptrbuf, bitbuf\n    +\t// Allocate ptrbuf\n     \t{\n     \t\truntime·lock(&lock);\n     \
@@ -624,7 +611,6 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \n     \t\tptrbuf = &scanbuffers->ptrtarget[0];\n     \t\tptrbuf_end = &scanbuffers->ptrtarget[0] + nelem(scanbuffers->ptrtarget);\n    -\t\tbitbuf = &scanbuffers->bittarget[0];\n     \t\tobjbuf = &scanbuffers->obj[0];\n     \t\tobjbuf_end = &scanbuffers->obj[0] + nelem(scanbuffers->obj);\

    scanblock 関数内で宣言されていた BitTarget *bitbuf 変数が削除され、ptrbuf と bitbuf の両方を割り当てるというコメントも ptrbuf のみになりました。また、bitbuf へのポインタを scanbuffers->bittarget[0] に設定する行も削除されています。

  5. flushptrbuf 関数の呼び出し箇所の変更:

    --- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -794,7 +780,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \t\t\tif((void*)iface->tab >= arena_start && (void*)iface->tab < arena_used) {\n     \t\t\t\t*ptrbufpos++ = (PtrTarget){iface->tab, (uintptr)itabtype->gc};\n     \t\t\t\tif(ptrbufpos == ptrbuf_end)\n    -\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);\n    +\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);\n     \t\t\t}\n     \n     \t\t\t// iface->data\
@@ -821,7 +807,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \t\t\t\tif(obj >= arena_start && obj < arena_used) {\n     \t\t\t\t\t*ptrbufpos++ = (PtrTarget){obj, 0};\n     \t\t\t\t\tif(ptrbufpos == ptrbuf_end)\n    -\t\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);\n    +\t\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);\n     \t\t\t\t}\n     \t\t\t}\n     \t\t\tgoto next_block;\
@@ -923,7 +909,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \t\t\twhile(hash_gciter_next(&map_iter, &d)) {\n     \t\t\t\t// buffers: reserve space for 2 objects.\n     \t\t\t\tif(ptrbufpos+2 >= ptrbuf_end)\n    -\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);\n    +\t\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);\n     \t\t\t\tif(objbufpos+2 >= objbuf_end)\n     \t\t\t\t\tflushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);\n     \
@@ -989,7 +975,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \t\tif(obj >= arena_start && obj < arena_used) {\n     \t\t\t*ptrbufpos++ = (PtrTarget){obj, objti};\n     \t\t\tif(ptrbufpos == ptrbuf_end)\n    -\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);\n    +\t\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);\n     \t\t}\n     \t}\n     \
@@ -998,7 +984,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)\n     \t\t// the loop by setting b, n, ti to the parameters for the next block.\n     \n     \t\tif(nobj == 0) {\n    -\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);\n    +\t\t\tflushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);\n     \t\t\tflushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);\n     \n     \t\t\tif(nobj == 0) {\

    scanblock 関数内の flushptrbuf の呼び出し箇所すべてで、最後の引数 bitbuf が削除されています。

コアとなるコードの解説

このコミットは、Goランタイムのガベージコレクタの内部実装における重要な簡素化を示しています。

BitTarget 構造体は、GCのマークフェーズ中にポインタのターゲットと、そのオブジェクトがヒープのビットマップ内でどこに位置するかという情報を一時的に保持するために設計されていました。これは、GCがオブジェクトをマークする際に、そのマーク状態をビットマップに効率的に記録するために使用されていたと考えられます。

BitTarget の削除は、flushptrbuf 関数が PtrTarget の情報（ポインタのターゲットアドレスと型情報）のみで、オブジェクトのマークと Workbuf へのエンキューを直接行えるようになったことを意味します。これは、GCの内部ロジックが進化し、ビットマップ関連の情報を BitTarget を介して明示的に渡す必要がなくなったことを示唆しています。

考えられるシナリオとしては、以下のいずれか、または複数の組み合わせが挙げられます。

  1. 型情報からのビットマップ位置の導出: PtrTarget の ti (型情報) から、オブジェクトのサイズやアライメント、そしてヒープ上の配置規則に基づいて、そのオブジェクトに対応するビットマップ内の位置を動的に計算できるようになった。これにより、BitTarget に bitp や shift を事前に格納しておく必要がなくなりました。
  2. ビットマップ操作の抽象化: flushptrbuf 内部で、ビットマップ操作がより高レベルな抽象化の下で行われるようになり、低レベルなビットマップポインタやシフト値を直接扱う必要がなくなった。
  3. GCアルゴリズムの最適化: GCのマークアルゴリズム自体が変更され、BitTarget が提供していたような中間的なビットマップ情報が不要になった。例えば、マーク処理がよりバッチ処理的になり、個々のポインタごとにビットマップ位置を計算するのではなく、より大きなブロック単位で処理するようになった可能性もあります。

この変更は、GCのコードベースをよりクリーンで理解しやすいものにし、同時にメモリ使用量をわずかに削減し、GCの実行パスを短縮することで、全体的なパフォーマンスの向上に貢献する可能性があります。特に、GCはGoアプリケーションのパフォーマンスに直接影響を与えるため、このような低レベルな最適化は非常に重要です。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント (当時のGCに関する情報)
  • Go言語のランタイムソースコード (src/pkg/runtime/mgc0.c の変更前後の比較)
  • ガベージコレクションに関する一般的なアルゴリズム（マーク＆スイープ、トライカラーマーキングなど）に関する情報
  • Go言語のGCに関するブログ記事や解説（特にGo 1.x 時代のもの）
  • Go言語のコミット履歴とGerritレビューシステム