GC本を読む ~第2章 マークスイープGC~
ガベージコレクションのアルゴリズムと実装を読んだメモ第2弾．
マークスイープGC
1960年にJohn McCartyによって発表された最初のGCアルゴリズム1．
基本動作
次の2つのステップによって死んだオブジェクトを再利用可能な状態にする．
- マークフェーズ
- ミューテータのルートから辿れるオブジェクト(のヘッダ)全てに生きていると示すためのマークを付ける．
- スイープフェーズ
- ヒープ全体をスキャンしてマークのついていないオブジェクトを回収する．
処理は至ってシンプル．
スイープフェーズでは，$heap_startから$heap_endまで全てのオブジェクトのヘッダを確認している．
ゴミオブジェクトをどうやって回収するのかというと，使われていないオブジェクトの連結リストを作って，そこに追加していっている． p21の擬似コードでは，
sweeping.next = $free_list $free_list = sweeping
と書かれており，単純に後ろに追加していっているのではなく，追加したオブジェクトがリストの先頭になるように追加していっている．(こうすることで連結リストの末尾を指すポインタが必要無くなるし，$free_listがNULLを指しているときの条件分岐も要らなくなる)
スイープフェーズ時にはただゴミオブジェクトをフリーリストに追加するのではなく，もし前に追加したゴミオブジェクト(既に開放された状態なのでチャンク)とメモリ空間上で連続しているなら，これらを1つのチャンクと見なすという処理をする．こうすることでチャンクが細切れになってしまうのを防ぐ．これを合体(Coalescing)と呼ぶ．
アロケーション時は，このフリーリストを探索して，必要なサイズ以上のチャンクを見つけ次第それを返す． この方式はFirst-fitと呼ばれ，他にはBest-fitやWorst-fitなどがある．
メリット・デメリット
メリットとしては以下の2つが挙げられている．
- 実装が簡単
- 保守的GCとの相性が良い
実装が簡単であるから，他のGCアルゴリズムと組み合わせやすいらしい．他のGCアルゴリズムは後の章で紹介されるので，この時点ではまだこのメリット達がどの程度良いのかは分からない．
デメリットとしては以下の3つが挙げられている．
- フラグメンテーション(断片化)
- GCを繰り返すうちにチャンクが細分化される
- アロケーション速度
- アロケーションのたびにフリーリストを先頭から探索するため効率が悪い (
)
- アロケーションのたびにフリーリストを先頭から探索するため効率が悪い (
- コピーオンライト(Copy-On-Write)との相性
- ヘッダにmark情報を置いているため，GC時に書き換えが発生することで，そのプロセス用メモリへの全コピーが発生してしまう．
デメリットを解決するためのアプローチ
複数フリーリスト (Multiple free-list)
チャンクのサイズごとにフリーリストを分けておく．(本のリスト2.7のコードで指定のフリーリストにチャンクが余ってなかったときに上位のフリーリストを見に行かないようになっているのはバグかな？)．
これによって，基本でチャンクが見つかるようになる．
BiBOP法 (Big Bag Of Pages)
ヒープ領域を分割し，特定のブロックに特定のサイズのチャンクを集中させる． これである程度フラグメンテーションが緩和される (完全に解決はしない)．
ビットマップマーキング (Bitmap Marking)
オブジェクトのヘッダではなく，別のデータにそれぞれのオブジェクトのマークビットをテーブル形式でまとめる． これによってGC時にオブジェクトへの書き込みがなくなるのでCoWが働く．
遅延スイープ法
スイープ操作にかかる時間はヒープ領域のサイズに比例して大きくなる． これが大きくなるということは，ミューテータの最大停止時間が増えるということ．
遅延スイープ法は，アロケーションのときに欲しいサイズのチャンクが作れたところでスイープ操作をやめる．これによってミューテータの停止時間を減らしている．(次スイープ処理をするときは続きから見ていくのか？)
しかし，もしスイープ操作時に見ているオブジェクトが連続して生きているオブジェクトだった場合，そのサイズ分だけ停止時間が発生するため，一概にこれで解決するとは言えない．(むしろ生存オブジェクトが固まっているのは局所性の面で良いはず．) このスイープ処理で扱うヒープ領域のサイズを一定に保つ手法は8章で説明されるようだ．
次回
読んでる途中
