回収の判断は参照の図から始める
配列を変数へ入れたあと、その変数を使わなくなれば、配列の領域はすぐ空くのでしょうか。この問いに答えるには、ソース上の変数名だけでなく、実行時にどこからその配列へ到達できるかを見る必要があります。GCは一般に、アプリケーションにとってその内容が今後役立つかを判断する仕組みではありません。処理系が扱う参照の関係に基づいて、回収してよい領域を見つけます。
ここでは、オブジェクトを点、ほかのオブジェクトへの参照を矢印として描く、停止中の小さな模型を使います。ルートは、実行中のフレームや静的な保持先など、探索の出発点として処理系が認識する参照です。具体的に何がルートになるかは実装に依存します。まずはルート集合を明示してから図をたどり、実際の処理系の最適化や並行動作は後で区別します。所有権の教材を先に読んだ場合も、誰が解放責任を持つかという問いから、どの経路が値を保持しているかという問いへ視点を移してください。
同じヒープでもルートで生存集合が変わる
ヒープにa、b、c、d、eがあり、aからbとc、bからc、cからa、dからe、eからdへの参照があるとします。ルートをaだけにすると、a、b、cへは到達できます。dとeは互いを参照していますが、ルートから入る経路がありません。この二つは、参照が一つもないからではなく、ルートから到達できないため、この模型では回収候補になります。
次に、ルートへdを追加すると、オブジェクトの矢印を変えなくても五つすべてが生存集合へ入ります。aをルートから外してdだけにすれば、今度はdとeだけが残ります。この順番で考えると、「循環があるとGCでは回収できない」という一般化が誤りだと分かります。到達可能性を追跡する方式は、到達不能な循環も見つけられます。一方、単純な参照カウントだけでは、互いの参照が残る循環に追加の対策が必要になります。方式を名指しせずに、GC全体の性質として説明しないことが大切です。
| ルート | 到達可能な集合 | 到達不能な循環 |
|---|---|---|
| a | a, b, c | d, e |
| a, d | a, b, c, d, e | なし |
| d | d, e | a, b, c |
マークと回収を別の作業として追う
マークの作業では、未処理の参照を入れる集合と、すでに訪れたオブジェクトの集合を用意します。ルートを未処理集合へ入れ、一つ取り出して未訪問なら印を付け、その参照先を追加します。すでに訪問した点では再び枝を展開しません。これにより、循環があっても同じ点を無限に処理せずに済みます。未処理集合が空になったとき、印の付いた集合が、この図での到達可能な集合です。
回収は、その結果を使う次の作業です。模型ではヒープの全点から生存集合にない点を除きます。マーク中に見つからなかった点を、探索の途中で直ちに削除してはいけません。別の枝から到達する可能性がまだあるためです。探索で点を一度だけ展開しても、保持する矢印を調べる費用と、ヒープを走査する費用は残ります。点と辺の数を基に作業量を考え、短いコードだから停止時間も一定だとは結論しないでください。
不要なキャッシュも参照があれば残る
ルートからcacheへ、cacheから大きなpayloadへ参照が続いている場合を追加します。アプリケーションがpayloadを二度と使わないとしても、cacheがその参照を保持している限り、この模型のGCはpayloadを回収できません。これはGCが壊れているという意味ではありません。プログラムが表現している保持関係と、開発者が意図した必要期間が食い違っています。
キャッシュの問題を調べるときは、メモリ量の増加だけでなく、どのルートからどの保持先を通って対象へ到達するかを確認します。無制限のキー、解除されないイベント購読、終了した要求を保持する一覧などが経路になり得ます。対策は上限や期限を設ける、登録を解除する、不要な参照を外すといった設計です。弱い参照を使う場合も、必要な値が回収され得る条件や再計算の責任を考える必要があります。弱い参照に変えるだけで、アプリケーションの保持方針が完成するわけではありません。
メモリとファイルの寿命を分ける
ファイルを包むオブジェクトが到達不能になっても、必要な時刻までにファイル記述子が閉じられるとは限りません。回収の開始時期、終了処理の有無、その呼出し順序は、言語や処理系の契約によって異なります。メモリ領域を回収する条件と、ファイル・ソケット・ロックなどの外部資源を返す条件を同じものとして扱わないでください。
たとえば、処理の途中で例外が起きてもファイルを閉じる要件なら、PythonのwithやJavaのtry-with-resourcesなど、その言語で範囲を明示する仕組みを選びます。終了処理を補助として持つ実装でも、それを通常の資源管理の予定表にはしません。特に、資源を持つオブジェクトが循環やキャッシュに残ると、メモリ量以上に記述子数などの上限へ先に達することがあります。レビューでは「GCがある」ではなく、取得地点、正常終了、異常終了、引渡し後の解放担当を一つずつ示すと、責任を確かめやすくなります。
実際のGCには動く対象との協調がある
ここまでの図は探索の間に変わりません。実際のアプリケーションはオブジェクトを作り、参照を書き換えます。探索がaを調べたあとで、別の場所から新しい参照が追加されるなら、どの時点の図を正しいものとして扱うかを決める必要があります。実装は停止、書込み時の記録、世代間の参照の管理など、採用した方式に応じた協調を行います。この模型はその仕組みを再現していません。
また、生存オブジェクトを移動して領域をまとめる方式では、参照を更新するか、移動しても正しく参照できる手段が必要です。外部のC関数へ渡したポインタを処理系が追跡できない場合は、固定やハンドルなどの契約が問題になります。GCの説明をFFIの教材へつなぐ理由はここにあります。回収できるかだけでなく、移動してよいか、処理系の外で誰が参照しているかも、境界をまたぐ際の確認事項です。
測定では使用量の意味を先に決める
GCの変更を評価するとき、「メモリが減った」の対象を決めます。ヒープ内の生存量、確保済み領域、プロセスの常駐メモリは同じ数値ではありません。到達不能なオブジェクトが回収されても、処理系が領域を次の割当てのために保持すれば、OSから見える値は直ちに下がらない場合があります。逆に、小さな例で使用量が一定でも、長時間の保持の問題がないとは言えません。
観測には処理系の版、GC方式、ヒープの設定、入力、測定区間を付けます。遅延を評価するなら平均だけでなく、停止や要求ごとの分布を見ます。割当て実験の教材ではスレッドが割り当てたバイト数を測りますが、それはこの教材の到達可能な集合の大きさとは別の指標です。指標を混ぜず、変更した条件と対応させることが、速度やメモリの説明を再現可能にします。
課題は保持経路を言葉で説明する
課題として、aを唯一のルートにした元の図で、cからdへの矢印を一つ追加してください。解答では、aからcを経由してdへ到達し、dからeもたどれるため、五つすべてが生存します。次に、aからcへの直接の矢印だけを消します。aからb、bからcという経路が残るので、生存集合は変わりません。最後にcacheをルートから外した場合を考えます。ほかにpayloadへの経路がなければ、cacheとpayloadはともに回収候補です。
答えには集合だけでなく、残った経路、消えた経路、仮定したルートを記してください。続く実験では同じ判断をPythonのグラフへ移し、共有と循環があっても探索が終わることをassertで確認します。実GCの停止時間やスループットを測ったことにはなりませんが、保持関係を理由付きで説明する土台になります。