実験の問いと対象を固定する
この実験では、参照の図を入力として、ルートから到達できる点だけを残す模型を作ります。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の統計ではありません。
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の版を含めます。「循環を回収できた」だけで終わらず、ルートから到達不能だった循環と、到達可能だった循環を分けて述べてください。