Partial Mark and Sweep algorithm -Cycle Collection-

rootの定義の仕方が非常に面白くかったので、メモ
(あとでGCWikiに転記する予定)
 

CycleCollectionとは

referenceCoountingGCで発生する循環参照をどうにかしたいGCのこと
 

Partial Mark and Sweep algorithm

CycleCollectionの実装の一つ。
その他はWeakPointer algorithmとかある。
(これについても後述したい。)
 

実装方法

reference countは行い。countが0になればそのObjectはfreeする。
ここは通常のreference countingと一緒。だが、循環参照をどうするのかという問題が残る。
通常はあるタイミングでMark and Sweepを行うのだが、このアルゴリズムでは違う方法をとる。
rootbufferという配列を取り、デクリメントする際、つまり、参照を切る際にrootbufferにaddする。
つまり、このアルゴリズムではrootが参照が切れているかもしれないリストになる。
その後、このrootをもとにMarkandSweepを行う。
参照カウントが0以下になっているものはwhite、それ以外はblackとし、
whiteに紐づくObjectはrootの分を除く為、-1をする。
そうすると循環参照は自然と全て0になるから解放されると言う仕組みだ。
 

rootの考え方が違う

もともとrootはスタックなどからとってきた確実に参照されているリストだが、
この場合、参照されていないだろうリストになる。
ここら辺の真逆の考え方が分かったとき、鳥肌がぞぞーっときました。
 

と書いてみたものの

まったく分からないので図説つきで、あげたい所。
また、下記の論文が大変参考になるので、特に擬似コードの所は英語関係なく読めるので
読んでみるといいかと思います。
Concurrent Cycle Collection in Reference Counted Systems