ガベージコレクションのアルゴリズムと実装 第5章「マークコンパクトGC(Mark Compact GC)」前半

ガベージコレクションのアルゴリズムと実装

今日は第5章 前半を読みました。

• マークコンパクトGC
  • ルートから参照を辿ってマーク->ヒープ領域内で移動させてコンパクション
  • マークスイープ法とコピーGCの中間のような手法
  • コンパクションありなのでフラグメンテーションがない。しかし保守的GCとの相性は悪い
  • 領域毎コピーではなく同じ領域内のコンパクションなので空間利用効率は良い
  • マーク、forwardポインタ設定、ポインタ書き換え、コンパクションとオーバヘッドが大きい
• Two-Finger アルゴリズム
  • 前提として「全てのオブジェクトの大きさを揃えないといけない」CRuby は OK ですね
  • コンパクションは前に詰める方法ではなく、空きに刺し込むように移動する。これにより移動前のオブジェクト領域が保存されるので forwardポインタが不要。ヒープ領域のスキャンが2パスで済む
  • ヒープ領域をアドレスの上下から挟むようにスキャンしていく(それで Two-Finger か)
  • キャッシュヒット率のデメリットあり。サイズ統一の制限はBiBOP法と組み合わせることで克服できる
  • 個人的にはすごく賢いなーと思いました
• テーブルアルゴリズム
  • forward ポインタのかわりにGC中に別途テーブルを使って移動元オブジェクトの情報を管理する
  • ブレイクテーブルは移動で空いた領域に起くらしいけど、テーブル用のエントリ自体も移動しないといけないのでかなり複雑
  • オブジェクトの順序が保存されるのでキャッシュヒット効率的には優秀

まだまだありますよ。本当にGCにはいろんな工夫が (ry