ガベージコレクションアルゴリズムの内部（世代別・並行GC）

到達可能性という大前提

GCが回収するのは「使われていない」オブジェクトではなく、ルート集合から到達できないオブジェクトです。ルートはスタック上のローカル変数、レジスタ、静的フィールド、JNIハンドルなどで、ここから参照グラフを辿れる範囲が「生存（live）」、辿れなければ「ごみ（garbage）」とみなされます。GCの正しさは「到達可能なオブジェクトを決して回収しない」という安全性（soundness）に依存し、逆に到達不能を即座に回収するかどうかは方式により異なります。

基礎はガベージコレクションで扱ったので、本稿はトレース型GCの内部アルゴリズムと停止時間制御に踏み込みます。

マーク・スイープ・コンパクション・コピー

トレース型GCの基本操作は次の通りです。マークはルートからのグラフ探索（DFS/BFS）で生存オブジェクトに印を付けます。スイープは印の付かない領域を空き領域として回収します。

コピーGC（Cheneyのアルゴリズム）は、From空間の生存オブジェクトをTo空間へ移すと同時に詰めるため、マークとコンパクションを一度に行えます。確保（allocation）はバンプポインタ（空き先頭を加算するだけ）で済み、断片化も起きません。代償として常にヒープの半分が予備になりますが、生存率が低い領域なら「生きている分だけ」コピーすればよく、死んだオブジェクトのコストはゼロです。この性質が次の世代別GCと噛み合います。

世代仮説と世代別GC

経験則として「ほとんどのオブジェクトは生成直後に死ぬ（weak generational hypothesis）」が成り立ちます。そこでヒープを若い世代（young）と古い世代（old）に分け、若い世代だけを頻繁に回収するマイナーGCを行います。若い世代は生存率が低いためコピーGCが最適で、HotSpotではEden＋2つのSurvivor領域で構成し、一定回数生き延びたオブジェクトをoldへ**昇格（promotion）**させます。

世代別GCの効果は計算量の観点でも明確です。回収コストは概ね生存オブジェクト数に比例し、ヒープ全体ではなく若い世代の生存分だけを走査するため、停止時間が小さく保たれます（計算量と Big-O 記法）。

write barrier — 並行・世代別を支える仕組み

write barrierは、オブジェクトの参照フィールドへの書き込み（a.f = b）の前後に処理系が差し込む短いコードです。用途は2つあります。1つはカードテーブルの更新（世代別）、もう1つは並行マーク中の不変条件維持です。

// 概念的な write barrier（参照書込みをフック）
write(obj, field, newRef) {
    pre_barrier(obj.field);   // 旧値を退避（SATB系）
    obj.field = newRef;       // 実際の書き込み
    post_barrier(obj, newRef);// カード印付け / 色の伝播
}

並行マークの難しさは、マーカーがグラフを辿っている最中にアプリ（mutator）が参照を書き換えると、生存オブジェクトを見落としかねない点です。マーク状態を白（未到達）・灰（到達済だが子未走査）・黒（子まで走査済）の3色で表すと、危険なのは「黒→白の参照が新規に作られ、その白へ向かう灰の経路が消えた」場合です。これを防ぐ代表的な不変条件が2つあります。

• SATB（snapshot-at-the-beginning）: マーク開始時点の生存グラフを保証する。上書きで消える旧参照をpre-barrierで灰に積む。G1が採用。
• incremental update: 黒オブジェクトに白参照が入ったらpost-barrierで黒を灰に戻す。

停止時間制御 — G1とZGC

ここまでの部品で「いかに止めずに回収するか」が設計できます。マーク・スイープ自体を非同期的にアプリと並走させ、避けられないstop-the-world（STW）を極小化するのが現代GCの核心です。

G1（Garbage-First）はヒープを多数の固定サイズリージョンに分割し、世代を物理的に固定しません。並行マークでリージョンごとの生存量を見積もり、「ごみが多いリージョンを優先（garbage-first）」して回収します。コピー（evacuation）自体はSTWで行いますが、一時停止時間の**目標値（pause target）**を設定でき、その予算内に収まるリージョン数だけを選んで回収することで停止時間を制御します。

トレードオフを正しく読む

並行GCはタダではありません。バリアは全参照アクセスに小さなオーバーヘッドを課し、マーカーとアプリが同じCPUとメモリ帯域を奪い合うためスループットは低下しがちです。さらに、アプリが並走する以上、回収が確保に追いつかないallocation stall（確保の足止め）や、最悪STWへ退避する場面も残ります。

まとめ

トレース型GCはマーク・スイープ・コンパクション・コピーを部品とし、世代仮説によって「若い世代を小さく頻繁に」回収して停止時間を抑えます。世代を跨ぐ参照と並行マークの正しさはwrite barrierと3色不変条件（SATB / incremental update）が支え、G1はリージョン単位の予算制御で、ZGC/Shenandoahは色付きポインタとload barrierでコピーまで並行化して、停止時間をヒープ規模から切り離します。GC選択はスループット・停止時間・フットプリントのトレードオフであり、バリアコストや並行マークの仕組みまで理解して初めて、停止時間の正体と削り方が見えてきます。