Matzにっき

_ [Ruby] GCアルゴリズム

マークに用いるカラーをローテートすることで、 マークフェーズとスイープフェーズを並行に行うことができるので、 これで効率化だ、と思ったのだが、 考えてみれば、カラーを変えようがなにしようが、 これではマークフェーズとミューテーターが同時に動けない。 やはりライトバリアは必要なのであった。

スイープが並行にできるのは嬉しいことも多いだろうけどね。

自分の間抜けさ加減が悔しいので(だから研究者にはなれないんだ)、 もうちょっと考察してみることにする。

あるプロセスで割り当てられるオブジェクト数をn、 参照されなくなるオブジェクト数をmとする時(だから当然n>m)、

n小、m小

あまりオブジェクトを使わないこのタイプのプロセスでは GCは実行効率に影響を与えない。 どんなアルゴリズムを選んでも関係ない。

n大、m小

たくさんオブジェクトを作ってあまり解放しないタイプのプロセスでは 生きているオブジェクトが多いことになるので、 マークフェーズに時間がかかる。 スループットを重視するなら世代別GCが欲しくなるケース。 停止時間を重視するならマークフェーズのインクリメンタル化が必要。

n大、m大

たくさんオブジェクトを作って、たくさん捨てるこのタイプでは スイープフェーズに時間がかかる(生きているオブジェクトが相対的に少ないから)。 停止時間を意識するならばスイープのインクリメンタル化が有効。

となる。実際問題としてRubyが救済しなければならないケースはどれなのだろう。

スイープのインクリメンタル化は簡単な割に効果がありそう。 コストもあまりかからないしね。

マークのインクリメンタル化にしても、 世代別GCにしても、いずれもライトバリアが必要なので、 実行効率に影響を与える可能性がある。

_ Mostly-Concurrent Mark & Sweep GC のアルゴリズム

インクリメンタルGCのアルゴリズムの紹介。 ちゃんとスレッドを意識している。