ガベージコレクションの仕組み — GC技術の系譜と言語ごとの戦略

プログラミングにおいてメモリ管理は避けて通れない問題です。C/C++ では開発者が手動で malloc/free を呼ぶ必要がありますが、多くの現代的な言語はガベージコレクタ（GC）がメモリの回収を自動で行ってくれます。

この記事では、GC の基本概念からアルゴリズムの系譜、書き込みバリアの仕組み、そして主要言語がどのような GC 戦略を採用しているかを、具体例を交えて解説します。

なぜ GC が必要なのか

手動メモリ管理には 2 つの典型的なバグがあります。

メモリリーク

使わなくなったメモリを解放し忘れると、プログラムのメモリ使用量が際限なく増加し、最終的には OOM（Out of Memory）でクラッシュします。

void leak_example() {
    char *buf = malloc(1024);
    // buf を使って処理...
    if (error) return;  // ← free(buf) を忘れてリターン！
    free(buf);
}

この例では、error が真の場合に free が呼ばれず、1024 バイトのメモリがリークします。長時間稼働するサーバーアプリケーションでは致命的な問題になります。

ダングリングポインタ

まだ使用中のメモリを誤って解放してしまうと、解放済みメモリへのアクセス（Use-After-Free）が発生します。

void dangling_example() {
    char *a = malloc(64);
    char *b = a;  // a と b が同じメモリを指す
    free(a);
    // b はまだ解放済みメモリを指している（ダングリングポインタ）
    strcpy(b, "hello");  // 未定義動作！クラッシュやセキュリティ脆弱性の原因
}

GC はこれらの問題を根本的に解決します。開発者がメモリの解放タイミングを明示する必要がなくなり、プログラムの安全性と生産性が大幅に向上します。

GC は 1959 年に John McCarthy が Lisp のために考案しました。67 年以上の歴史を持つ技術であり、その間に多くのアルゴリズムが生まれ、洗練されてきました。

GC の基本戦略

GC のアルゴリズムは大きく参照カウント方式とトレース方式の 2 つの系統に分けられます。

⮳ 世代別・インクリメンタル・並行 GC は直交する最適化戦略であり、M&S 以外のアルゴリズムとも組み合わせ可能です。例えば Java の Young 世代はコピー GC を使います。上図は代表的な組み合わせを簡略化したものです。

参照カウント方式（Reference Counting）「自分を何箇所から参照されているか」をカウンタとして持ちます。参照が増えるとカウントをインクリメントし、参照が外れるとデクリメントします。カウンタが 0 になった時点で、そのオブジェクトは即座に解放されます。

参照カウントの動作例

a = Object()   # Object の ref_count = 1（a が参照）
b = a           # Object の ref_count = 2（a, b が参照）
a = None        # Object の ref_count = 1（b のみ参照）
b = None        # Object の ref_count = 0 → 即座に解放！

このように、参照カウント方式ではオブジェクトの寿命がリアルタイムに追跡され、不要になった瞬間にメモリが回収されます。

長所

• 実装がシンプル: カウンタの増減だけで管理でき、理解しやすい
• 即時回収: ゴミは発生した瞬間に回収される。レイテンシが予測しやすい
• Stop-The-World がない: アプリケーション全体を停止させる必要がない
• メモリ使用量が最小限: 不要になったオブジェクトがすぐに解放されるため、メモリのピーク使用量が抑えられる

短所

• 循環参照を回収できない: 最大の弱点。A→B→A のような循環参照があると、外部からの参照がなくなっても ref_count が 0 にならない

上図のように A と B が互いを参照していると、外部からの参照がなくなっても ref_count は 1 のまま残り、永久にリークします。

• カウンタ更新のオーバーヘッド: ポインタの代入のたびにカウンタの更新が必要。特にマルチスレッド環境ではアトミック操作（atomic_increment/atomic_decrement）が必要で、キャッシュラインの競合が発生する
• カスケード解放: 大きなデータ構造のルートの参照カウントが 0 になると、連鎖的に多数のオブジェクトの解放が走り、一時的なレイテンシスパイクになり得る

トレース方式（Tracing GC）

ルートの集合（スタック上の変数、グローバル変数、レジスタなど）からオブジェクトグラフを辿り、到達可能（reachable）なオブジェクトを「生きている」とマークします。到達不可能（unreachable）なオブジェクトはガベージとして回収されます。

ルートセットとは

トレース GC における「ルート」とは、プログラムから直接アクセス可能なポインタのことです。具体的には以下が含まれます：

• スタックフレーム上のローカル変数: 各 goroutine / スレッドのスタック
• グローバル変数: パッケージ / モジュールレベルの変数
• CPU レジスタ: 現在のスレッドが保持しているポインタ

ルートセットから辿れるオブジェクトだけが「生きている」と判断され、辿れないものはすべてガベージです。循環参照があっても、ルートから辿れなければ正しく回収されるのが、参照カウント方式に対する大きな利点です。

三色マーク & スイープ（Tri-color Mark & Sweep）

最も基本的かつ広く使われているトレース GC アルゴリズムです。Dijkstra らが 1978 年の論文 "On-the-Fly Garbage Collection: An Exercise in Cooperation" で提唱しました。

三色の意味

三色不変条件（Tri-color Invariant）

アルゴリズムの正しさは以下の不変条件に依存します：

黒色オブジェクトが白色オブジェクトを直接参照することはない

なぜこの条件が重要なのでしょうか？黒色のオブジェクトはもう GC がスキャンしません。もし黒から白を直接参照していると、その白オブジェクトはスキャンの機会を失い、「生きている」のに「ゴミ」として回収されてしまうからです。灰色オブジェクトが間にある限り、必ずスキャンの機会が訪れます。

アルゴリズムの流れ

1. 初期化: すべてのオブジェクトを白色にする
2. ルート発見: GC ルートがポイントするオブジェクトを灰色にし、灰色スタック（ワークリスト）に追加
3. スキャン: 灰色スタックからオブジェクトを一つ取り出し：
   • それが参照するオブジェクトのうち白色のものを灰色にし、灰色スタックに追加
   • 自身を黒色にする
4. 繰り返し: 灰色スタックが空になるまで 3 を繰り返す（マーク完了）
5. スイープ: ヒープを走査し、白色のまま残ったオブジェクトのメモリを解放する

以下のインタラクティブデモで、このプロセスをステップごとに確認できます。各オブジェクトの色が変わる様子と、灰色スタックの変化に注目してください：

Mark & Sweep の課題

基本的な Mark & Sweep には以下の課題があります：

• フラグメンテーション: 解放されたオブジェクトの間に隙間ができ、メモリが断片化する。大きなオブジェクトの割り当て時に連続領域が確保できないことがある
• Stop-The-World: マークとスイープの間、すべてのアプリケーションスレッドが停止する
• ヒープ全体の走査: スイープ時にヒープ全体を走査する必要があり、ヒープサイズに比例してコストが増大する

これらの課題を解決するために、さまざまなバリエーションが生まれました。

トレース GC の発展

マーク & コンパクト（Mark-Compact）

Mark & Sweep はオブジェクトを解放するとメモリの断片化（fragmentation）が起こります。Mark-Compact は生存オブジェクトをヒープの一端に詰め直すことで断片化を解消します。

上の図が示すように、スイープ後に生じた隙間をコンパクション（圧縮）で詰めることで、ヒープ末尾に連続した空き領域が作られます。

コンパクションのアルゴリズムにはいくつかの種類があります：

• Sliding compaction: オブジェクトをアドレス順にスライドさせる。オブジェクト同士の相対的な順序が保たれる
• Lisp 2 algorithm: ヒープを 3 回走査する。1回目で新アドレスを計算、2回目でポインタを更新、3回目でオブジェクトを移動
• Threaded compaction: 参照をリンクリストに変換して一時情報を保存する。追加メモリ不要だが複雑

コスト: オブジェクトの移動＋参照の書き換えが必要で重い処理ですが、割り当てはバンプポインタ（単純なポインタ移動）で高速になります。バンプポインタ割り当ては alloc(size) = ptr; ptr += size の一命令で済むため、フリーリスト方式（空きブロックを線形探索）に比べて大幅に高速です。

コピー GC（Copying / Semispace）

ヒープを 2 つの領域（From 空間 / To 空間）に分割します。オブジェクトの割り当ては From 空間で行い、GC 時に生存オブジェクトを To 空間にコピーします。コピー後、From と To を交換し、古い From を一括で解放します。

Cheney のアルゴリズム（1970年）が代表的な実装で、BFS（幅優先探索）でオブジェクトをコピーします：

scan = free = To空間の先頭
GCルートから参照されるオブジェクトをTo空間にコピー, freeを進める
while scan < free:
    scanが指すオブジェクトの各フィールドについて:
        参照先がFrom空間にあれば → To空間にコピー, freeを進める
        参照先にforwarding pointerを設定
    scanを次のオブジェクトに進める

• 長所: コンパクションが無料で付いてくる（コピー先は常に詰めて配置）、バンプポインタで高速割り当て、ヒープ全体のスイープが不要
• 短所: ヒープの半分しか使えない（メモリ効率が 50%）、オブジェクトのコピーは大きなオブジェクトに対してコストが高い

世代別 GC（Generational GC）

弱い世代仮説（Weak Generational Hypothesis）に基づく最適化です：

ほとんどのオブジェクトは生成直後に不要になる（若くして死ぬ）

実際の観測結果に基づいています。典型的なアプリケーションでは、新規割り当てされたオブジェクトの 80〜95% が最初の GC までに不要になります。

• Young 世代（新世代）: 新規オブジェクトを割り当てる小さな領域。頻繁に GC（Minor GC）が走りますが、ほとんどのオブジェクトが死んでいるため非常に高速（数ミリ秒）。Eden 領域で新規割り当てを行い、Minor GC で生存したオブジェクトは Survivor 空間にコピーされます
• Old 世代（旧世代）: 何度も Minor GC を生き延びたオブジェクトが昇格（promotion）する領域。GC の頻度は低いが、処理は重い（Major GC / Full GC で数十〜数百ミリ秒）

世代別 GC の実現にはリメンバードセット（Remembered Set）が必要です。Old 世代から Young 世代への参照を追跡する仕組みです。Minor GC 時に Old 世代全体をスキャンせずに済むようにするためのもので、カードテーブル方式が一般的です。Old 世代のメモリを 512 バイト程度のカード単位に分割し、Young 世代への参照を含むカードだけを「ダーティ」とマークしてスキャン対象にします。

インクリメンタル GC / 並行 GC

Stop-The-World（STW）の時間を短縮するため、GC 処理をアプリケーションの実行と並行して行います。

• Stop-The-World GC: マーク＋スイープの間、アプリケーションを完全に停止。実装は最もシンプルだが、停止時間が長い（ヒープサイズに比例）
• インクリメンタル GC: マーク処理を小さなステップに分割し、アプリケーションの実行と交互に進めます。各ステップの停止は短いが、合計の GC 時間は長くなる（書き込みバリアのオーバーヘッド）
• 並行 GC（Concurrent GC）: マーク処理を別スレッドで並行実行。アプリケーションの停止は最初（マーク開始）と最後（再マーク）のみで極めて短い

並行 GC では、アプリケーション（ミューテータ）と GC（コレクタ）が同時に動くため、マーク中にオブジェクトの参照関係が変わる可能性があります。これに対処するのが書き込みバリア（Write Barrier）です。

書き込みバリア（Write Barrier）

並行 / インクリメンタル GC において三色不変条件を維持するための仕組みです。アプリケーション（ミューテータ）がポインタを書き換える際に、GC に対して「通知」するコードが挿入されます。

なぜ書き込みバリアが必要か

以下のシナリオを考えてください：

1. GC がオブジェクト A を黒色にスキャン済み
2. アプリケーションが A.field = C（白色）を実行
3. アプリケーションが B.field = nil（B→C の参照を削除。B は灰色/白色）
4. GC は B をスキャンするが、もう C への参照がない
5. C は白色のまま → ガベージとして解放される → 生きているのに解放！

これはロストオブジェクト問題と呼ばれます。黒→白の参照が作られ（条件①）、同時にその白オブジェクトへの他の経路が切断された（条件②）場合に発生します。

主要な書き込みバリア

ポインタが新しいオブジェクトを参照する際に、参照先を灰色にマークします。

// A.field = C を実行する際に挿入されるバリア
writeBarrier(A, field, C):
    shade(C)      // まず C を灰色にする（黒→白の参照を防ぐ）
    A.field = C   // その後にストアを実行

ストアの前に shade を実行するのがポイントです。もし順序が逆だと、ストアと shade の間に「黒オブジェクト A が白オブジェクト C を参照している」状態が生まれ、並行して動く GC がその瞬間に C をガベージと判断してしまう可能性があります。

新しい参照が追加されるたびに、参照先が灰色になるので確実にスキャンされます。ただし、保守的に多くのオブジェクトを灰色にするため、浮遊ガベージ（本当はゴミだが今回は回収されない）が増える傾向があります。

参照が外されるオブジェクトを灰色にマークします。GC 開始時点のオブジェクトグラフの「スナップショット」を保存する考え方です。

// A.field が old → new に変わる前に挿入されるバリア
writeBarrier(A, field, new):
    old = A.field
    if old is white:
        shade(old)  // old を灰色にする
    A.field = new

GC 開始時に到達可能だったオブジェクトはすべてマークされることを保証できます。

Go は Dijkstra バリアと Yuasa バリアを組み合わせたハイブリッド書き込みバリアを採用しています。

writeBarrier(slot, new):
    shade(*slot)  // 削除バリア: 上書きされる古い値を灰色にする
    shade(new)    // 挿入バリア: 新しい値を灰色にする
    *slot = new

このハイブリッド方式の最大の利点は、スタックの再スキャンが不要になることです。Go 1.5〜1.7 の Dijkstra バリアのみの実装では、マーク終了時にすべての goroutine のスタックを再スキャンする必要があり、これが STW 時間の主要因でした。ハイブリッドバリアにより、Go の STW は通常 100μs 以下にまで短縮されました。

メモリアロケーション戦略

GC と密接に関連するのがメモリの割り当て方式です。GC アルゴリズムの選択は、割り当て戦略にも大きく影響します。

フリーリスト（Free List）

解放されたメモリブロックをリンクリストで管理します。割り当て時に適切なサイズのブロックを探します。

• First-fit: 最初に見つかった十分なサイズのブロックを使う
• Best-fit: 最もサイズが近いブロックを使う（断片化が少ない）
• Segregated-fit: サイズクラスごとに別のリストを持つ（Go, tcmalloc が採用）

バンプポインタ（Bump Pointer）

コンパクション済みのヒープや Copying GC で使われる方式。空きメモリの先頭にポインタを置き、割り当てのたびにポインタを進めるだけです。

alloc(size):
    result = freePtr
    freePtr += size
    return result

極めて高速（実質1命令）ですが、連続した空き領域が必要です。

TLAB（Thread-Local Allocation Buffer）

マルチスレッド環境での割り当て競合を避けるため、各スレッドにヒープの一部を事前に割り当てます。スレッド内での割り当てはロックフリーのバンプポインタで行えます。Java の HotSpot JVM や Go のランタイムが採用しています。

言語ごとの GC 戦略

主要なプログラミング言語がどのような GC を採用しているかを詳しく見ていきましょう。

Go — 並行三色マーク & スイープ

Go はシンプルさとレイテンシの低さを最優先にした設計です。

なぜ Go は世代別 GC ではないのか？Go はスタック割り当てを積極的に行います。コンパイラのエスケープ解析（escape analysis）により、関数外に参照が漏れないオブジェクトはスタックに割り当てられます。つまり、短命なオブジェクトの多くはそもそもヒープに到達しません。世代別 GC の前提（「多くのヒープオブジェクトが短命」）が弱くなるため、世代別の恩恵が小さく、書き込みバリアのコストに見合わないのです。

GC ペーサー: Go の GC は次の GC サイクルをいつ開始するか「ペーサー」が制御しています。GOGC=100（デフォルト）は、「前回の GC 後のライブヒープサイズに対して、ヒープが 100% 成長したら次の GC を開始する」という意味です。Go 1.19 では GOMEMLIMIT が追加され、メモリ上限をソフトリミットとして設定できるようになりました。

GC のソースコードは runtime/mgc.go にあります。

Java (HotSpot) — 世代別 + 多彩なコレクタ

Java は最も GC 研究が進んだエコシステムを持ち、用途に応じて複数のコレクタを選択できます。

G1 GC の仕組み: ヒープを均等なリージョン（通常 1〜32MB）に分割します。Young/Old の区別はリージョン単位で動的に割り当てられます。G1 は「ガベージの多いリージョン」を優先的に回収（Garbage-First）することで、限られた停止時間内で最大の効果を得ます。-XX:MaxGCPauseMillis=200 のように停止時間の目標を設定できます。

ZGC の着色ポインタ（Colored Pointers）: ZGC はオブジェクトポインタの未使用ビットに GC のメタデータ（マーク状態、リロケーション状態）を埋め込みます。これにより、オブジェクトヘッダにマーク情報を書き込む必要がなく、ロードバリアだけで並行マークとリロケーションを実現しています。TB 級のヒープでも STW が 1ms 以下を維持できるのはこの技術のおかげです。

Python (CPython) — 参照カウント + 世代別トレース GC

Python はハイブリッド方式を採用しています。

• 参照カウント（Primary）: メインのメモリ回収方式。オブジェクトの ob_refcnt が 0 になると即座に tp_dealloc が呼ばれて解放される
• 世代別トレース GC（Auxiliary）: 参照カウントでは回収できない循環参照を検出・回収するために、世代別のトレース GC をバックグラウンドで実行

3 世代の閾値システム:

オブジェクトは Gen N のコレクションを 1 回生存するだけで Gen N+1 に昇格します。つまり閾値はオブジェクトの生存回数ではなく、各世代のコレクション頻度を制御するパラメータです。gc.get_threshold() で確認、gc.set_threshold() で調整可能です。

CPython の GIL（Global Interpreter Lock）の存在により、参照カウントの更新はアトミック操作が不要です。ただし、Python 3.13+ の free-threaded モード（--disable-gil）ではバイアス参照カウント（biased reference counting）方式に変更されています。これはオーナースレッドは通常のインクリメント/デクリメントを行い、他のスレッドはアトミック操作でカウンタを更新する方式で、GIL なしでもスレッドセーフな参照カウントを実現します。

JavaScript (V8) — 世代別 + 並行マーク

V8 エンジン（Chrome, Node.js, Deno）は世代別 GC を採用しています。

Scavenger の仕組み: Young 世代は 2 つの semispace に分けられます。新規オブジェクトは「From」空間に割り当てられ、Minor GC（Scavenge）時に生存オブジェクトが「To」空間にコピーされます。2 回生存したオブジェクトは Old 世代に昇格します。

Orinoco: V8 の GC 最適化プロジェクトの名前です。メインスレッドと並行してマーク処理を行い、STW 時間を大幅に短縮しています。具体的な最適化手法：

• Concurrent Marking: ワーカースレッドがメインスレッドと並行してオブジェクトグラフを走査
• Parallel Scavenging: 複数のワーカースレッドが Young 世代の GC を並列実行
• Incremental Marking: マーク処理を細切れに進め、アイドル時間やタスク間の短い隙間で実行
• Lazy Sweeping: スイープ処理をオブジェクトの割り当て時に遅延実行

.NET (CLR) — 世代別 + セグメントベース

.NET の GC はサーバーワークロードに最適化された設計です。

Large Object Heap (LOH): 85,000 バイト以上のオブジェクトは LOH に直接割り当てられます。LOH はコンパクションされないのがデフォルトで、.NET 4.5.1+ では GCSettings.LargeObjectHeapCompactionMode で明示的にコンパクションを要求できます。

ピン留め（Pinning）: ネイティブコードとの相互運用時に、GC がオブジェクトを移動することを防ぎます。fixed ステートメントや GCHandle.Alloc(obj, GCHandleType.Pinned) で実現しますが、多用するとフラグメンテーションの原因になります。

Rust — GC なし（所有権システム）

Rust は GC に頼らず、所有権（ownership）+ 借用（borrowing）+ ライフタイムのコンパイル時チェックでメモリ安全を保証します。

所有権システム → コンパイル時にメモリ解放のタイミングが決定
             → ランタイムオーバーヘッドゼロ
             → GC 停止時間もゼロ

RAII（Resource Acquisition Is Initialization）パターンにより、変数がスコープを抜けると自動的に Drop トレイトが呼ばれてリソースが解放されます。これはコンパイル時に挿入されるコードなので、ランタイムコストはゼロです。

循環参照が必要な場合は Rc<T> / Arc<T> + Weak<T> を使い、参照カウントで管理します。Weak<T> は所有権を持たない参照で、Rc の参照カウントに含まれないため、循環を断ち切れます。

Swift — ARC（Automatic Reference Counting）

Swift はコンパイル時に参照カウントの増減コードを自動挿入する ARC を採用しています。

• ランタイムでのトレース GC は不要
• 予測可能なパフォーマンス: コンパイル時にすべての retain/release が挿入されるため、実行時のオーバーヘッドが予測しやすい
• 循環参照は weak（Optional になる）/ unowned（非 Optional、ライフサイクルが保証される場合）参照で開発者が明示的に解決する必要がある

Swift のコンパイラはARC 最適化として、不要な retain/release のペアを除去するパス（Copy-on-Write 最適化を含む）を持っています。

GC 技術の年表

まとめ

GC は「あれば便利」の機能ではなく、プログラミング言語のランタイム設計における最重要アーキテクチャ決定の一つです。参照カウントのシンプルさ、トレース GC の正確さ、世代別仮説による効率化、並行実行による低レイテンシ化 — それぞれの技術が特定のトレードオフの上に成り立っています。各言語のチームが数十年の研究成果を踏まえて最適なトレードオフを選んでいるところに、この分野の深さと面白さがあります。

参考文献

• The Garbage Collection Handbook — Richard Jones, Antony Hosking, Eliot Moss
• Go Blog: Getting to Go — The Journey of Go's Garbage Collector
• Go Blog: A Guide to the Go Garbage Collector
• V8 Blog: Trash talk — The Orinoco garbage collector
• ZGC — Oracle Documentation
• Python GC — CPython Developer Guide
• .NET GC — Microsoft Documentation
• Dijkstra et al., "On-the-Fly Garbage Collection: An Exercise in Cooperation," 1978
• R. Jones, A. Hosking, E. Moss, "The Garbage Collection Handbook: The Art of Automatic Memory Management," 2011