GC/extend/TwoFinger
最終更新：
author_nari 2008年11月03日(月) 13:07:33履歴
TwoFinger -Mark&Compact- 
空いてる所につっこむ
アルゴリズム
先に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を超えていれば移動された事になるので
(式は雰囲気のみ味わって欲しい)
簡単に言えば、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]といった形でポインタを更新する。
(式は雰囲気のみ味わって欲しい)
利点
- アルゴリズムが単純で中々高速
- 無駄な領域を使用しない
欠点
- オブジェクトのサイズが同じでなければならない(サイズの違い毎にHeapを作る事で回避可能)
- 順序がバラバラになり局所性が低下する
実コードを見たい場合
・不明
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
このページへのコメント
Hi, I think your blog might be having browser compatibility issues. When I look at your website in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, great blog!|
シーバイクロエ 財布 新作 2013 http://www.koobe.org/
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You definitely know what youre talking about, why waste your intelligence on just posting videos to your blog when you could be giving us something informative to read?|
アグ ブーツ 正規品 http://www.mwhittlephoto.com/