実験・実装 · 基礎から応用へ

到達可能性を使うGCの模型を作る

循環・共有・ルートの変更を小さなグラフで試し、生存集合と回収候補をassertで確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 実験の問いと対象を固定する
  2. 実行前に二つの循環と共有を手で追う
  3. 保存して全assertを実行する
  4. ループの不変条件から停止を説明する
  5. 変えてよい条件と壊れる条件を分ける
  6. ルートを増やしたときの性質を追加で試す
  7. 課題と解答で結果の安定性を確かめる
  8. この記事をロゲイアに質問する理解を確かめる

実験の問いと対象を固定する

この実験では、参照の図を入力として、ルートから到達できる点だけを残す模型を作ります。Python 3.12の標準機能だけを使い、プロセスの実ヒープを操作することはありません。各オブジェクトは文字列の識別子、その参照先は文字列の一覧として表します。Python自身がこの辞書をどう回収するかは測りません。先に「到達可能性から理解するGC」を読み、ルートから矢印をたどる規則を説明できる状態で始めてください。

確認したいのは、到達不能な循環を落とせるか、共有先を何度も展開せずに済むか、ルートの追加で結果が変わるかです。実GCの停止時間、世代、並行動作、メモリの移動は対象に含めません。結果を記録する際も「GCを再現した」ではなく、固定したグラフに対するマークと回収の模型を検証したと書きます。Pythonの辞書から要素を除いたことと、OSへ領域が返ったことも区別します。

実行前に二つの循環と共有を手で追う

ヒープのaはbとcを参照し、bもcを参照します。cはaへ戻るため、a・b・cは循環と共有を含みます。d・eは別の循環です。cacheはpayloadを保持します。ルートがaだけなら、生存集合はa・b・cであり、d・e・cache・payloadは回収候補です。まずこの集合を紙に書いてから、コードのassertと照らし合わせます。

ルートをaとbに増やしても、bはすでに到達できるので生存集合は変わりません。aとcacheにすれば、cacheとpayloadの二つが追加されます。ルートを空にすると、生存集合も空になります。この三つは、コードの行数や実行速度ではなく、到達可能性の意味を確かめる入力です。共有先のcを最初に見つけた経路だけで判断せず、訪問済み集合によって重複処理を防ぐ点も追ってください。

保存して全assertを実行する

次のコードをgc_model.pyへ保存し、python3.12 gc_model.pyで実行します。markは探索だけを行い、collectは結果に含まれる点から新しい辞書を作ります。入力を直接書き換えないため、同じヒープに異なるルートを与える比較ができます。識別子がヒープ内にない場合はValueErrorで止めます。壊れた参照を黙って無視すると、入力の誤りと回収候補を取り違えてしまうためです。

出力にはliveとしてa・b・c、reclaimedとしてcache・d・e・payloadが並び、最後にGC graph assertions passedと表示されます。並び順はsortedで固定していますが、探索の途中の順序そのものを正しさの条件にはしません。Python 3.12.14で全assertが成功することを確認しています。比較するのは識別子の集合であり、バイト数、時間、実GCの統計ではありません。

python
heap = {
    'a': ['b', 'c'],
    'b': ['c'],
    'c': ['a'],
    'd': ['e'],
    'e': ['d'],
    'cache': ['payload'],
    'payload': [],
}

def mark(heap, roots):
    pending = list(roots)
    live = set()
    while pending:
        obj = pending.pop()
        if obj not in heap:
            raise ValueError('dangling reference: ' + obj)
        if obj in live:
            continue
        live.add(obj)
        pending.extend(heap[obj])
    return live

def collect(heap, roots):
    live = mark(heap, roots)
    return {obj: list(refs) for obj, refs in heap.items() if obj in live}

assert mark(heap, {'a'}) == {'a', 'b', 'c'}
assert mark(heap, {'a', 'b'}) == {'a', 'b', 'c'}
assert mark(heap, {'a', 'cache'}) == {'a', 'b', 'c', 'cache', 'payload'}
assert mark(heap, set()) == set()
remaining = collect(heap, {'a'})
assert set(remaining) == {'a', 'b', 'c'}
assert remaining == collect(remaining, {'a'})
assert set(heap) == {'a', 'b', 'c', 'd', 'e', 'cache', 'payload'}
try:
    mark(heap, {'missing'})
except ValueError as error:
    assert str(error) == 'dangling reference: missing'
else:
    raise AssertionError('invalid root accepted')
print('live:', sorted(remaining))
print('reclaimed:', sorted(set(heap) - set(remaining)))
print('GC graph assertions passed')

ループの不変条件から停止を説明する

pendingには、まだ調べる必要がある参照が入ります。liveに入った点は、ルートから何らかの経路で見つかった点です。一度liveへ入った点は、再びpendingから取り出されても参照先を追加しません。そのため、有限のヒープでは循環を何度も展開せずに探索を終えられます。cからaへ戻る矢印を、実際に一回追って確認してください。

共有があるため、pendingへ同じ識別子が複数回入ることはあります。重複が入らないことを保証する実装ではありません。保証しているのは、訪問済みの点の枝を再展開しないことです。点の数をV、辺の数をEとすると、この表現のマーク作業は概ねO(V+E)で考えられますが、識別子の扱いや集合操作について通常の仮定を置いています。最後のcollectには辞書全体の走査もあります。小さな例の実行時間から一般の停止時間を推定しないでください。

変えてよい条件と壊れる条件を分ける

次に、cの参照先へdを追加して実行します。aからc、d、eへ到達するため、元の最初のassertは失敗します。これは模型の不具合ではなく、入力を変えたのに期待する集合を変えていないためです。新しい期待値をa・b・c・d・eとして、回収候補も書き直してください。cacheとpayloadへの経路はまだありません。

一方、存在しない識別子をルートへ与える最後の試験では、ValueErrorが必要です。成功表示へ進んだだけでは不十分で、異常な入力を受け入れなかったことを確かめます。この模型は参照先が変わらない間にmarkとcollectを終える前提です。探索中にヒープを書き換える実験へ広げるなら、どの瞬間の図を対象にするかという別の規則が必要になります。リストを増やしながらたどるだけで、並行GCを実装したことにはなりません。

ルートを増やしたときの性質を追加で試す

同じヒープでルート集合を増やしても、以前に到達できた点が到達不能へ変わることはありません。たとえばmark(heap, {'a'})がmark(heap, {'a', 'cache'})の部分集合になることを追加のassertで確かめられます。前提は、二回の間にヒープの辺を変更しないことです。ルートを増やす変化と参照を削る変化を同時に行うと、この説明をそのまま当てられなくなります。比較の条件を一つだけ変える習慣を、グラフの実験でも保ってください。

課題と解答で結果の安定性を確かめる

課題は三つです。第一に、同じルートで二度collectしても結果が変わらない理由を説明します。解答では、最初の回収後には到達不能な点だけが除かれ、生存点を結ぶ経路は保たれるからです。第二に、元のheapが変わっていないことを確認するassertの役割を説明します。これは、別条件の比較で入力が知らない間に変わるのを防ぎます。

第三に、ルートへcacheを加えたとき、payloadをアプリケーションがもう使わないという説明だけで回収できるか考えます。答えは、この模型ではできません。参照経路が残っているためです。提出する記録には、変更した辺、ルート集合、予測した生存集合、実行結果、Pythonの版を含めます。「循環を回収できた」だけで終わらず、ルートから到達不能だった循環と、到達可能だった循環を分けて述べてください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 20

学習コースから次を選ぶ