日本語の資料がすくないGCアルゴリズムについて詳細に解説します

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を超えていれば移動された事になるので
if (pointer > live) pointer = Heap[pointer]
といった形でポインタを更新する。
(式は雰囲気のみ味わって欲しい)

利点

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

欠点

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

実コードを見たい場合

 ・不明

このページへのコメント

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/

Posted by シーバイクロエ 財布 新作 2013 2014年01月19日(日) 23:04:56

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/

Posted by アグ ブーツ 正規品 2013年12月26日(木) 02:51:17

コメントをかく


画像に記載されている文字を下のフォームに入力してください。

「http://」を含む投稿は禁止されています。

利用規約をご確認のうえご記入下さい

×

この広告は60日間更新がないwikiに表示されております。

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です