GCアルゴリズム詳細解説

ちょっとづつGC

基本アルゴリズムのCopyingとMark&Sweepでは一気にオブジェクトの走査、解放を行うため、
GCによる停止時間が非常に長かった。
この欠点を補うのがこのアルゴリズムである。

Incremental GC はGC の探索処理を細切れにして、ユーザプログラムと交互に動かす。
これにより一回あたりの停止時間を短くするアプローチであり、リアルタイム性の必要なプログラムに適している。
交互で動かす最もメジャーな方法は、allocate 処理を行なうときに、こっそり少しづつGCを進めるというものである。
以下では、mark sweep GC をincremental 化する場合について述べる。
Incremental GC を実装するには、いくつか問題点をクリアしなければならない。

• GC 処理のスケジューリング。これまでのように、ヒープが満杯になったらGC を始める・・のでは間に合わない。

　　GC の再帰探索が一通り終るより先に、メモリが尽きるという状況は極力避けなければならない。
　　ちなみに、GC の仕事を少し行なったからといって、メモリをすぐに解放してくれるわけではない(=省メモリ性は相変わらず悪い) ことに注意

• writebarrierが必要になる。

なぜ、writebarrierが必要になるかというと、GCの細切れで動かす本アルゴリズムはMarkの途中で
ユーザープログラムの処理へ戻ることになる。
その際に、Mark済みのオブジェクトへの新規参照が追加され、またその新規参照されたオブジェクトが
Mark済みオブジェクトからしか参照されていなかった場合、SweepフェイズでそのオブジェクトはMarkが付いていないのでゴミと判断され解放されてしまう。
それを防ぐ為にwritebarrierを用いて、変更があったオブジェクトに印をつけ、もう一度Markし直す処理が必要になる。

基本的には、incremental GC は停止時間を短くするのが目的であって、GC の仕事の量を減らそうとするものではない。
このため、非incremental GC と比べてトータル実行時間は短くならない。
逆に仕事の切替えオーバヘッドやwrite barrier の分、遅くなるだろう。
Incremental を使うべきかどうかはプログラムの性質に応じて決める必要がある。

最近のスクリプト言語にはこのアルゴリズムが使用されていることが多い。

1. 停止時間が短い

1. スケジューリングが結構大変
2. writebarrierの分、ミュテータに一律負荷が増加する

　・Io処理系
　・Lua処理系
　・BoehmGC