12 分で読了 #compilers #ランタイム

このページの目次

ガベージコレクション

ランタイム時にどのオブジェクトが到達不能になったかを自動判定して回収する——mark-sweep から世代別 GC、並行三色マーキングへ。各 GC アルゴリズムはスループットとレイテンシの間で異なるバランスを取っており、write barrier はコンパイラによってポインタの書き込み箇所に埋め込まなければならない。

概要

手動メモリ管理（C/C++ の malloc/free、Rust の所有権システム）は、メモリ解放の責任をプログラマまたは型システムに負わせる。ガベージコレクション（GC）は別の道を選んだ：⁠ランタイム時にどのオブジェクトが到達不能になったかを自動判定し、それらが占めるメモリを回収する⁠。GC は GC 対応言語（JVM/Go/.NET/JS/Python）のランタイム基盤である——コンパイラはコードを生成するだけでなく、生成されたコードの中に GC 連携ポイント⁠（safepoint、write barrier）を埋め込まなければならない。ここでは主要な 4 つの GC アルゴリズムと、それらがコンパイラに課す要件について解説する。

核心概念：到達可能性とルートセット

GC の基礎となる問題は、「どのオブジェクトが生きているか」⁠である。定義：グローバル変数、スタック上のローカル変数、レジスタからなるルートセット（root set）⁠から出発し、ポインタを辿って到達可能なすべてのオブジェクトが生きている。それ以外はガベージ（ゴミ）である。

ルートセット = {グローバル変数, 各スレッドのスタック上の各ワード, 有効なレジスタ}
ルートセットから出発し、BFS/DFS でポインタを追跡 → 到達したオブジェクトを live とマーク
到達しなかったもの → ガベージ、回収可能

あらゆる GC はこの走査を行う。違いはいつ行うか、到達しなかったオブジェクトをどう回収するか、そして mutator（アプリケーションコード）にどのような影響を与えるかにある。

4つの核心アルゴリズム

1. Mark-Sweep: 基礎

mark フェーズ:
  ルートセットから出発し、オブジェクトグラフを走査し、到達した各オブジェクトに mark-bit を設定

sweep フェーズ:
  ヒープ全体を走査し、マークされていないオブジェクトを回収し、mark-bit をクリア（次回用に）

コスト：mark フェーズでは生きているオブジェクトの量だけ走査する。sweep では死んでいるオブジェクトを含むヒープ全体を走査するため、未使用メモリもすべてスキャンされる。
オブジェクトを移動させないため、ポインタの更新は不要 → シンプル。オブジェクトを移動できない C/C++ などの言語（Boehm GC など）に適している。
致命的な欠点：⁠断片化⁠。割り当てと解放が交互に行われると、ヒープは小さな断片に徐々に碎け、総空き容量が十分あっても、大きなオブジェクトの割り当てに失敗する可能性がある。

2. Copying (Semispace, Cheney): 空間を使って時間とコンパクト化を実現

ヒープを半分（from-space と to-space）に分け、常に半分だけを使用する：

収集:
  ルートセットから出発し、BFS/DFS で生きているオブジェクトを走査
  生きているオブジェクトを from-space から to-space にコピーする（一端にコンパクトに配置）
  これらのオブジェクトを指すすべてのポインタを更新する（旧アドレス → 新アドレス）
  from-space 全体を回収する（OS にとっては巨大なメモリブロックの解放と同じ）
  from と to の役割を入れ替える

コンパクト化（compaction）——生きているオブジェクトが密に配置され、断片化がない。
走査プロセス自体が BFS であり、Cheney の copying collector は BFS 走査を行うことで、自然とコンパクト化を実現する。
コスト：⁠ヒープの半分しか使えないため、メモリ利用率は 50% になる。GC 対応言語（JVM、Go）にとって、このコストは断片化なし + 割り当てはポインタの移動のみ（bump allocator）という恩恵と引き換えに、価値がある。

3. Generational GC: 「ほとんどのオブジェクトは早く死ぬ」を利用する

経験則（weak generational hypothesis）：⁠ほとんどのオブジェクトは割り当てられた直後にすぐにガベージになる⁠（ループ内で割り当てられる一時オブジェクトなど）。生き残った少数のオブジェクトは長く生き続ける傾向がある。

世代別 GC はヒープを若年世代（nursery）⁠と老年世代（tenured）⁠に分ける：

若年世代: 頻繁に収集（例：数 MB 割り当てごとにトリガー）、copying を使用——生き残りが少なく、コピーコストが低い
老年世代: 低頻度で収集（例：メモリがいっぱいになりそうになるまでトリガー）、mark-sweep または mark-compact を使用
若年世代で N 回の収集を生き残ったオブジェクト → 老年世代に昇格

重要なエンジニアリング課題：⁠世代間参照⁠。老年世代のオブジェクトが若年世代のオブジェクトを指している場合、若年世代だけをスキャンするとこの参照を見逃す（ルートセットに老年世代が含まれないため）。解決策：老年世代に remembered set を持つ——「若年世代へのポインタを含んでいる可能性のある老年世代のカード（card）」を記録する。若年世代の GC 時、remembered set 内の老年世代のカードがルートセットに追加される。

書き込みバリア（write barrier）：世代間参照の維持

ポインタの書き込み（*p = q）のたびに、コンパイラは小さなコードを挿入する：

write_barrier(p, q):
    if p が老年世代にあり、q が若年世代にある場合:
        p が属する card を dirty マーク → GC がこの領域をスキャンする
    *p = q

このバリアはコンパイラによってポインタの書き込みのたびに直接生成される⁠——ランタイムで解釈実行されるものではなく、マシンコードとして埋め込まれる。JVM の G1/Shenandoah、Go の GC、V8 の Oilpan はすべて、コンパイラが挿入する write barrier に依存している。

コンパイラの最適化は write barrier に優しい：コンパイラが p が新しく割り当てられたもの（必ず若年世代にある）であることを証明できれば、barrier をスキップできる。ループ内で同じ p に対して複数回書き込む場合、コンパイラは最初の barrier のみを残す可能性がある（その後の書き込みは card の状態を変更しないため）。

並行 GC：mutator を停止しない（または短時間だけ停止）

mark-sweep と copying はどちらも「スキャン中に mutator がオブジェクトグラフを変更してはならない」と要求する——これは stop-the-world (STW) による一時停止を意味する。現代の GC の大部分の作業は、mutator と並行して実行可能である：

三色不変条件（tri-color invariant）

並行マーキングアルゴリズムの理論的基礎。オブジェクトを 3 つのクラスに分ける：

白色（White）: まだマークされていない（初期状態、またはガベージの可能性）
灰色（Gray）: マーク済みだが、内部のポインタはまだスキャンされていない（worklist にある）
黒色（Black）: マーク済みであり、内部のポインタがすべてスキャン済み

不変条件：mark の終了時には、黒色オブジェクトが白色オブジェクトへのポインタを持つことはない。 この不変条件が違反されると（例：mutator がマーク完了済みの黒色オブジェクトに白色オブジェクトへのポインタを書き込む）、その白色オブジェクトはマーク漏れとなり、誤って回収される可能性がある。

不変条件を維持する方法：スキャン中に不変条件を破壊する書き込みをインターセプトする⁠（write barrier を使って「黒→白」のポインタ関係をキャプチャ）、または一時的なマーク漏れを許容し、後で修正する⁠（mutator が p.field = q と書き込み、p が黒色、q が白色の場合、q を灰色としてマークし、キューに再挿入する）。Go の GC は後者の手法を使用する。

読み込みバリア（read barrier）

write barrier が「書き込み」をインターセプトするのに対し、read barrier は「読み込み」をインターセプトする：⁠白色オブジェクトを読み込む際、まずそれを灰色としてマークする⁠。Baker の並行 copying collector は read barrier を使用している——mutator が読み込むすべてのポインタは to-space を指さなければならず、読み込みの瞬間にフォワーディングが行われる。

write barrier と read barrier の選択は、⁠書き込みが多いか読み込みが多いかによって決まる——ほとんどのシステムは write barrier を選択する（書き込みは読み込みより少なく、barrier のオーバーヘッドが低いため）。

GC に対するコンパイラの要件

GC はコンパイラがコードを書き終えれば完了する独立モジュールではない——コンパイラはコード生成時に GC サポートを埋め込まなければならない：

safepoint: いつでも GC できるわけではない——コンパイラはループの頭（バックエッジ）や関数呼び出しの箇所に safepoint チェックを挿入し、GC は safepoint のみでスレッドを一時停止する。
ルートマップ（root map）: コンパイラは各 safepoint に対して、ローカル変数/レジスタの有効なポインタマップ⁠（どのレジスタ/スタック位置に現在 GC 可視のポインタが格納されているか）を生成し、GC はこれに基づいてルートセットをスキャンする。
write barrier のインライン展開⁠: barrier が大きなオーバーヘッド（毎回関数呼び出し）を持つと、書き込み集中型のコードが 10 倍遅くなる可能性があるため、コンパイラは barrier をインラインのいくつかの命令として実装し、記録が必要な場合のみ slow path に進む。

参考文献

Jones/Hosking/Moss: 「The Garbage Collection Handbook」— GC 分野の権威あるリファレンス
Wilson (1992): 「Uniprocessor Garbage Collection Techniques」— GC の初期の総説
Go GC: src/runtime/mgc.go — 産業レベルの並行マーキング。明確な設計ドキュメントあり

Keywords: garbage collection, GC, mark-sweep, copying, semispace, Cheney, generational GC, weak generational hypothesis, write barrier, read barrier, card marking, remembered set, tri-color invariant, concurrent GC, stop-the-world, STW, safepoint, root map, compaction, fragmentation, bump allocator, nursery, tenure