ガベージコレクション

ガベージコレクションは、一部のオブジェクトのメモリライフサイクルを自動的に管理します。ここで言う「ゴミ」は、通常、言語およびランタイムで観測可能な参照関係に基づいて判断され、コレクタがプログラムが将来決して使用しないものを正確に知っていることを意味するものではありません。グローバルキャッシュによって長期間参照されている不要なオブジェクトでも、保持される可能性があります。

GC を理解する際には、いくつかの次元を分離して考える必要があります。回収可能なオブジェクトの識別方法、オブジェクトの移動の有無、世代別アプローチの採用、並列または並行処理の実施、そしてコンパイラが参照をどのように報告するかです。これらは組み合わせて使用され、互いに排他的な選択肢ではありません。

ルート、オブジェクトグラフ、保守的近似

追跡型 GC は、ルート参照から出発してオブジェクトグラフをトラバースします。ルートはスレッドスタック、レジスタ、グローバルスロット、またはランタイムハンドルに存在する可能性があります。ただし、これらの領域のすべてのワードが必ずしもポインタであるとは限りません。

正確な GC は、型レイアウトとスタックマッピングを使用して参照スロットを識別します。保守的な GC は、アドレスのように見える数値も潜在的な参照として扱うため、不要なオブジェクトを誤って保持し、安全な移動の方法を制限する可能性があります。正確性と保守性は参照の識別能力を記述するものであり、世代別や並行処理の採用を直接決定するものではありません。

参照カウントは、参照が変更されるたびにカウントを維持し、カウントがゼロになると回収します。これは毎回ルートからグラフ全体をトラバースする必要はありませんが、互いに参照し合う到達不能な循環は自然にゼロにならないため、通常、循環を処理するための他のメカニズムが必要です。「すべての GC が同じルートトラバースを実行する」という定義は誤りです。

Mark-Sweep：生存オブジェクトの特定と未マーク領域の回収

マークフェーズでは、ルートから到達可能なオブジェクトをトラバースします。スキャンフェーズでは、マーク情報に基づいて未マークオブジェクトの領域を回収します。実装は、ページ、スパン、または割り当てメタデータ単位で動作し、予約済みアドレス空間全体をバイト単位でスキャンする必要はありません。

非移動スキャンはオブジェクトのアドレスを変更しないため、外部参照や固定アドレスの要件に適していますが、サイズが異なる空洞が残ります。アロケータのサイズ階層とフリーリスト管理は断片化を緩和できますが、「合計フリー領域が十分」であっても、すべての連続する大きなオブジェクトの割り当てを満たす保証はありません。

マークのコストは、生存オブジェクトのバイト量だけでなく、ポインタの数、オブジェクトのレイアウト、局所性にも依存します。大きなバイト配列と同等サイズの密集したポインタグラフでは、追跡作業に大きな差が生じる可能性があります。

コピーと圧縮：回収時にオブジェクトアドレスの変更

古典的な双半領域コレクタは、割り当て領域を from-space（コピー元）と to-space（コピー先）に分け、生存オブジェクトをターゲット領域にコピーして参照を修正し、その後、両領域の役割を交換します。Cheney アルゴリズムは、ターゲット領域の scan（スキャン位置）と free（フリー位置）の2つの位置を使用して、幅優先スキャンを構成します。新しくコピーされたオブジェクトは free に追加され、scan はその参照を順次処理し、両者が一致するまで続行します。

forwarding 情報は、複数の参照が同じオブジェクトを指している場合に、オブジェクトを1回だけコピーし、新しいアドレスを一貫して取得できるようにします。元の領域の回収は、再利用可能であることを意味しますが、必ずしも直ちにオペレーティングシステムに返却する必要があるわけではありません。

双半領域の単純な形式では、コピー先の領域として領域の半分を予約しますが、この比率をすべての移動型 GC の総利用効率として一般化することはできません。領域ベース、世代別、圧縮アルゴリズムにはそれぞれ異なる空間戦略があります。移動は、内部ポインタ、FFI ハンドル、固定オブジェクトの処理も必要であり、ルートの更新だけで完了するものではありません。

scan と free がオブジェクトグラフを完全に処理する仕組み

整数で旧オブジェクトアドレスを表します：10 は A で、B と C を指します。20 は B で、C も指します。30 は C で、子参照はありません。また、40 と 50 が到達不能な循環を形成しています。ルートは A のみです。オブジェクトサイズを1スロットに統一し、ポインタフィールドのみを残すことで、コピーアルゴリズムを以下の完全なモデルに縮小できます。

heap = {10: [20, 30], 20: [30], 30: [], 40: [50], 50: [40]}


def collect(heap, roots):
    forwarding, copied, queue = {}, [], []

    def evacuate(old):
        if old not in forwarding:
            forwarding[old] = len(copied)
            copied.append(None)  # まずスロットを確保して転送先を確立し、フィールドをスキャン
            queue.append(old)
        return forwarding[old]

    new_roots = [evacuate(old) for old in roots]
    scan, trace = 0, []
    while scan < len(copied):  # len(copied) は本モデルにおける free に相当
        old = queue[scan]
        copied[scan] = [evacuate(child) for child in heap[old]]
        scan += 1
        trace.append((scan, len(copied)))
    return new_roots, copied, forwarding, trace


roots, copied, moved, trace = collect(heap, [10, 10])
assert roots == [0, 0]  # 2つのルートはエイリアス関係を維持
assert copied == [[1, 2], [2], []]
assert moved == {10: 0, 20: 1, 30: 2}
assert trace == [(1, 3), (2, 3), (3, 3)]
assert collect(heap, [40])[1] == [[1], [0]]  # 到達可能な循環でも1回だけコピー
assert collect(heap, [])[1] == []

この順序は、forwarding の2つの役割を明らかにしています。それは、重複コピーの防止と、オブジェクトアイデンティティの維持です。A と B が元々 C を共有していた場合、回収後も同じ C を共有する必要があり、各自がコピーを作成して変更の可視性を密かに変更してはいけません。転送先を先に登録してからフィールドをスキャンすることで、到達可能な循環でも終了可能になります。

モデル内の新しいアドレスは配列インデックスですが、実際のコレクタはオブジェクトの実際のサイズとアライメントに基づいてバイトポインタを進め、コピー先の容量不足も処理する必要があります。ここでは、収集中にオブジェクトグラフが変化しないと仮定しており、並行バリア、弱参照、ファイナライザ、または内部ポインタは実装されていません。

2つの参照が同じオブジェクトを指しているのに、なぜ1回だけコピーするのか？

scan と free が分離されているのは、「コピー済み」不等于「フィールドが更新済み」だからです。以下のターゲット領域のスキャン待ちオブジェクトは、依然として旧アドレスを含んでいる可能性があります。それを処理する時点で初めてフィールドが修正されます。A と B の C への参照は、最終的に同じ新しいスロットに収まる必要があります。D をルートに追加すると、D/E の循環も、forwarding を先に登録することで重複コピーを防ぎます。ここでは、オブジェクトサイズを1スロットに統一しているだけで、実際のオブジェクトが等長であることを主張するものではありません。

$$[0,\mathrm{scan})\text{scanned},[\mathrm{scan},\mathrm{free})\text{pending}$$

世代別：長期生存オブジェクトのスキャン削減

弱い世代仮説は、多くのプログラムで大量のオブジェクトがすぐに廃棄されるというものです。この仮説がワークロードに適している場合、小さな若年世代を頻繁に収集することで、長期生存オブジェクトの重複スキャンを減らすことができます。昇格閾値、代数、および各世代のアルゴリズムは実装によって決定され、若年世代が統一されたサイズや回数を従う必要はありません。

カードテーブルは通常、小さなメモリ領域を粒度として潜在的な変更を記録しますが、リメンバードセットはより細かいオブジェクトまたは参照スロット表現を採用できます。これらは、若年世代の収集が、老年世代全体をスキャンすることなく、どの老年オブジェクトが入り口を提供する可能性があるかを把握できるようにします。

プログラムに長寿命オブジェクトが多く、世代間書き込みが頻繁、または若年オブジェクトが急速に昇格する場合、世代別の追加記録とコピーのコストが収益を相殺する可能性があります。世代別はワークロードに基づく最適化であり、すべての GC に必須のフェーズではありません。

並列、並行、インクリメンタルは同義語ではない

並列は、複数の収集スレッドが共同で作業することを意味し、アプリケーションは依然として一時停止する可能性があります。並行は、コレクタとアプリケーションのミューテータが同時に実行されることを意味します。インクリメンタルは、作業を小さなステップに分割することを意味します。これらの次元は同時に存在する可能性があります。

Mark-Sweep やコピーは、一時停止型ソリューションに使用することもできますし、対応するプロトコルの下で並行実行することもできます。並行であっても、ルートビューの構築、変換フェーズ、または完了処理のために短時間の一時停止が必要になる場合があり、アプリケーションが永久に一時停止しないとは限りません。

バリア：具体的なアルゴリズム要件の維持

三色抽象は、オブジェクトを白色（未発見）、灰色（発見済み、スキャン待ち）、黒色（スキャン済み）に分類します。単純な強三色不変量の下では、黒オブジェクトが保護されていない白オブジェクトを指すことは許可されません。並行変更はグラフを変更するため、バリアと作業キューを使用して正しさを維持する必要があります。

例えば、コレクタがすでに A をスキャンしており、アプリケーションがその後 B の参照を A に書き込み、B の最後のスキャン待ちパスがすでに削除されていたとします。対応する保護がない場合、B はアプリケーションによって参照され続けていてもマークされない可能性があります。

挿入バリアは、新しく書き込まれた参照を記録できます。削除バリアや SATB スタイルのバリアは、上書きされた旧参照を保持できます。混合バリアは異なる動作を組み合せます。異なるアルゴリズムが維持する不変量は異なるため、これらをすべて if black then gray と略すことはできません。

世代別バリアは主に世代間参照を記録し、並行マークバリアは追跡の正しさを保護し、移動型コレクタのリードバリアは forwarding の処理を行う可能性があります。リードバリアかライトバリアかを選択するのは、まずアルゴリズムの要件によります。読み書きの頻度はコストに影響しますが、それだけで正しいソリューションを決定するものではありません。

Go の公式 GC ガイドラインは、その並行・非移動追跡コレクタを記述しています。ランタイムのライトバリアソースコードは、混合バリアの目的を説明しています。これは、「若年世代はコピー、老年世代はスキャン」という汎用的な世代別の例としては使用できません。Go GC ガイドライン、Go ライトバリア実装説明

黒オブジェクトに新しい参照が追加された場合、その白オブジェクトを発見するのは誰か？

これは、すべてのバリアが1つのルールを共有することを意味するのではなく、不変量を観察するための固定されたインクリメンタル更新モデルを確立することです。A がすでにスキャンされた後に A→B が追加され、B がまだ白色の場合、新しい追跡タスクを残す必要があります。このエッジを先に作成し、G→B を削除すると、既存の灰色パスが消滅します。挿入バリアを有効にすると、B 自体がすでに灰色集合に含まれているため、情報は旧パスと一緒に失われません。

コンパイラが提供するもの

セーフポイントは、関数呼び出しやループヘッダに限定されず、実装は制限付き非同期一時停止メカニズムをサポートすることもできます。コンパイラがバリアを削除する場合、それが具体的なアルゴリズムに適合していることを証明する必要があります。「オブジェクトは直ちに割り当てられた」という理由だけで、すべてのバリアを省略できるわけではありません。LLVM は、これらの協調要件を GC 統合インターフェースの一部として提供しています。LLVM GC ドキュメント

コストとライフサイクルのクイックリファレンス

ヒープ予算を増やすと収集頻度は減少しますが、残留メモリは増加します。一時停止を短くすると、より多くの作業がミューテータバリアと並行 CPU に分散されます。移動はコンパクト性を改善しますが、コピーと参照修正のコストが増加します。評価には、割り当て率、生存セット、GC CPU、一時停止分布、ピークメモリを同時に観察する必要があります。

GC は、ファイル、ロック、または接続の適時解放を置き換えるものではありません。ファイナライザの実行タイミングは、通常、タイムリーなビジネスクリーンアップを担当するには適していません。言語が提供する明示的なライフサイクルメカニズムを使用してください。

制限付き予算モデルを使用して「頻度」と「1回の作業量」を分離する

各収集後の生存セットが 100 MiB で固定され、次の収集がヒープ使用量が 200 MiB に達したときにトリガーされ、アプリケーションが 50 MiB/s で継続的に割り当てていると仮定します。割り当て可能な余力は 100 MiB で、理想的な間隔は 2 秒です。閾値を 300 MiB に変更すると、余力は 200 MiB になり、間隔は 4 秒になります。これだけで、1回の一時停止が短縮されたことを直接証明するものではありません。

from fractions import Fraction
live, allocation_rate = 100, 50  # MiB, MiB/s
intervals = [Fraction(limit - live, allocation_rate) for limit in (200, 300)]
assert intervals == [2, 4]
# さらに、各ラウンドで同じ生存グラフを追跡するのに固定の 0.1 CPU 秒を消費すると仮定
cpu_per_second = [Fraction(1, 10) / interval for interval in intervals]
assert cpu_per_second == [Fraction(1, 20), Fraction(1, 40)]

上記のアンロードコストは、毎秒 0.05 CPU 秒から 0.025 CPU 秒に低下しますが、これは「固定ラウンドコスト、頻度のみ変更」モデルの結論です。実際のランタイムでは、並行マークが事前に開始され、ルートと生存セットは変化し、割り当て補助、昇格、またはメモリ制限圧力が発生する可能性があります。したがって、これら2つの数値を製品パフォーマンス予測として直接使用することはできません。

一時停止がまだ長い場合は、ルートスキャン、生存オブジェクトのコピー、または完了処理のいずれが支配的かをさらに特定する必要があります。総 CPU が高く一時停止が短い場合は、頻繁な収集または大量の並行作業が原因である可能性があります。ラウンドごとの時間、毎秒のラウンド数、およびアプリケーションのスループットを一緒に考慮して初めて、ヒープ予算の増加がどのコストを解決しているかを判断できます。Go GC コストモデル

参考文献

• Go GC ガイドライン。
• Go mbarrier.go。
• LLVM：Garbage Collection。

Keywords: GC, tracing, reference counting, root map, mark-sweep, copying, generational, remembered set, barrier, safepoint