部分的なマーク・アンド・スイープ( Partial Mark and Sweep )の詳細について
昨晩、Twitter上で、循環参照問題*1を機械的に排除する方法について意見を求めたところ id:DigitalGhost さん( @DecimalBloat )から...
http://wiki.livedoor.jp/author_nari/d/GC/extend/Partial%20Mark%20and%20Sweep
...というものをご紹介頂いたのですが、「4.scan」の記述が非常に残念な状態になっています。
で、今日、たまたま id:DigitalGhost さんと名古屋でお会いすることになっていたので、これ幸いと id:DigitalGhost さんからその詳細を教えて頂きました。その際のメモを以下に残しておきます。
あるべき挙動のモデル
表記
| 表記 | 説明 |
|---|---|
| S1,S2,S3 | スタックからの参照 |
| A,B,C,D | 循環参照を形成しているオブジェクト群 |
| X | 循環参照を形成しているオブジェクト群から参照されている外部のオブジェクト |
| 吹き出しの数字 | それぞれのオブジェクトの被参照カウント |
初期状態
スタックからの参照のひとつが切れるがまだ別のスタックからの参照が残っている状態
最後のスタックからの参照が切れる状態
循環参照オブジェクトが解放された状態
部分的なマーク・アンド・スイープ( Partial Mark and Sweep )での挙動
※件のページと併せてご参照ください。
「4.scan」の記述が致命的なのは「4.scan」は実際には 「3. Mark Gray」と同様の「Mark Black」という操作と「whiten」操作をごっちゃに記述していることです。これらはそれぞれ...
- Mark Black
- Mark Gray と同様の操作を行なう。ただし非grayのオブジェクトをgrayに置き換えるのではなく、参照カウントが非0で且つgrayのオブジェクトをblackに置き換え、また参照カウントを -1 するのではなく代わりに +1 する。
- Whiten
- 「Mark Black」を実施後、grayで且つ参照カウントが0のオブジェクトをwhiteにする。
...のようになります。*2
スタックからの参照のひとつが切れるがまだ別のスタックからの参照が残っている時の挙動
最後のスタックからの参照が切れた時の挙動
追記
微妙に解釈が間違っているようです。詳細はコメント欄を参照。
