GCアルゴリズム詳細解説

空いてる所につっこむ

先にMark＆Compactについて説明しておく。
簡単に言えば、Markを行った後で、フラグメント化したHeap領域を再配置し、
Compactionを行う手法である。

CopyingGCでは分割されたHeap領域にてCompactionを行っていたが、
このアルゴリズムではHeap領域は分割せず単一のHeap領域内で行う事が可能。
もちろん、Compactionを行うことでメモリの局所性がましキャッシュなど色々な恩恵を受けることができる。
また、オブジェクトの割り当てもポインタをずらすだけなので早い。
しかし、その分、再配置にかかる時間がプラスされ停止時間は増大する。
また、Compaction時にポインタを更新する為、原則としてConsevertiveなGCには使えない。

ここで紹介するのはMark&Compactの手法の一つであるTwoFingerアルゴリズムである。
図を見てもらうと分かるとおり「free」「live」の二つのポインタを使う。（これが名前の由来だと思う）

まず、Markフェイズで生きているObjectを数えておく。
その後、上図のように両端からscanしてゆき、freeとliveが出会ったらCompactionは終了。

その後、CopyingGCを同じ様にrootでさしていたポインタ、オブジェクト内で指しているポインタの
書き換えを行う。
その際、ポインタがliveを超えていれば移動された事になるので

if (pointer > live) pointer = Heap[pointer]

といった形でポインタを更新する。
(式は雰囲気のみ味わって欲しい)

1. アルゴリズムが単純で中々高速
2. 無駄な領域を使用しない

1. オブジェクトのサイズが同じでなければならない(サイズの違い毎にHeapを作る事で回避可能)
2. 順序がバラバラになり局所性が低下する

　・不明