yaotti's diary

QiitaやKobito、Qiita:Teamを作っています。Software is Eating the World

複製に基づくインクリメンタルコンパクションのアルゴリズム

Garbage Collection Advent Calendar 2012の12日目の記事です.激しく遅れましたごめんなさい.
研究で取り組んでいたインクリメンタルコンパクションについて説明します.

なお,ヒープコンパクションやGCの基本的な用語は知ってる前提です.コンパクションの説明とか用語説明入れるとめっちゃ長くなったので適当にぐぐってください

コンパクションの問題

  1. コンパクション対象領域にあるオブジェクトの移動
  2. 移動させたオブジェクトを指しているポインタの更新

コンパクションでは上記2つの重い処理が走るが,オブジェクトの移動やポインタ更新中にはミューテータの処理を行えないためミューテータを長時間止めなければならない.
これを避けるためいくつかインクリメンタルコンパクションの手法が提案されている.

複製に基くインクリメンタルコンパクション

ここでは複製に基くインクリメンタルコンパクションのアルゴリズムを紹介する. 論文: http://www.computer.org/csdl/proceedings/isorc/2008/3132/00/3132a516-abs.html

コンパクション中にミューテータを動かしたときに問題となるのは"移動させたオブジェクトの移動元への書き込みや参照"なので,移動元及び移動先のオブジェクトを常に同じオブジェクトとして扱うことが出来れば良い.
この手法では(重い)リードバリアは利用せず,オブジェクトの複製と3種のバリアを利用する.

処理の流れ

  1. コンパクション対象領域にある各オブジェクトの複製を連続した空き領域に作る
  2. 複製元オブジェクトを指しているポインタを複製先を指すよう更新する
  3. 複製元オブジェクトを一掃する(これにより連続した大きな空き領域ができる)

疑似コードで書くと以下みたいな処理

compaction_source_area = choose_fragmented_area
compaction_destination_area = allocate ENOUGH_SIZE
# 1. オブジェクトの複製作成
objects_in(compaction_source_area).each do |object|
  object.clone_in compaction_destination_area
end
# 2. 複製元を指すポインタを複製先を指すよう更新
objects_in(heap_area).each do |object|
  object.update_pointers_pointing_to compaction_destination_area
end
# 3. 複製元のオブジェクトを指すポインタはなくなったので,領域を開放
compaction_source_area.free

ここで1及び2の処理は,後述するバリアによって並列に実行可能となる.

3種のバリア

ただ複製しただけでは複製元と複製先を同じオブジェクトとしては扱えないため,以下の問題が生じる.

  1. 複製先(もしくは複製元)への書き込みがもう一方に反映されない
  2. 複製間での一貫性が保たれない
  3. ポインタ更新処理中(上記2の処理)にミューテータの処理によって複製元ポインタが書き込まれる可能性がある
  4. ポインタ更新が終わったオブジェクトで起きると,複製元を指すポインタが残り続けてしまう(null pointerになる)
  5. 複製元と複製先を比較すると別オブジェクトとみなされfalseが返る

それぞれの問題の疑似コード.

A2 = A.clone # 複製の作成
# 問題1. 
A.foo = 'bar'
A2.foo #=> 'bar'にならない
# 問題2. 
B.a = A # Bのポインタ更新処理が終わった後にこれが実行されると,B.aは複製元(A)を指し続けてしまう
# 問題3. 
A == A2 #=> false. trueとなるべき

これらの問題を解決するために3種のバリア(ライトバリア,ポインタ更新バリア,比較バリア)を利用する.

  1. ライトバリア: 書き込み処理の対象が複製されたオブジェクトなら,対応するオブジェクトにも同じ書き込みを行う→一貫性が保たれる
  2. ポインタ更新バリア: 更新後のポインタが複製元オブジェクトを指す場合は,複製先オブジェクトを指すように更新する
  3. 比較バリア: 複製元と複製先を比較した場合はtrueを返すようにする

以上の工夫により,「オブジェクトの複製中」「ヒープ内オブジェクトのポインタの更新処理」の部分を並列に実行できる.

まとめ

この説明では厳密さよりも平易さを優先しているため(ルートセットとか無視),詳しく知りたい人は論文を参照してください.
http://www.computer.org/csdl/proceedings/isorc/2008/3132/00/3132a516-abs.html