GCアルゴリズム詳細解説 - GC/extend/TreadmillGC(Barker 1992)

TreadmillGC(Barker 1992)

Copyingに似たnon-movingなインクリメンタルGC

アルゴリズム

このアルゴリズムは双方向リンクを利用し,Copyingと似た動きをする.
つまりMark&Sweepは行わない.
Copyingのようにルートからたどったオブジェクトを移動させるアルゴリズムである.

移動の際,単純なChenyCopyingGCだとオブジェクトを物理的に移動するが,このアルゴリズムの場合,双方向リンクを付け替える事で移動とする.

このアルゴリズムではGCの際に4つのセグメントに分かれる.
  • Free 解放済み,もしくは未使用のオブジェクトが所属する空間
  • New スキャン中に割り当てたオブジェクトが所属する空間
  • To Fromから生きているオブジェクトの移動する先の空間
  • From スキャン対象のオブジェクトが所属する空間

またその区別の為,4つのポインタをもつ.
  • top To空間との境目に位置
  • bottom Free空間との境目に位置
  • scan スキャン対象のオブジェクトを指す
  • free 次のオブジェクト割り当て対象を指す

初期状態は以下の様な位置関係にある.
  • scanとfreeは隣同士に位置
  • topとbottomとscanは隣同士に位置

freeからオブジェクトを割り当てると,topとbottomの間に位置づける.
そうすると自然とFrom空間は肥大化し,Freeは少なくなる.

Freeが残り半分程になるとGCを開始する.手順は以下である.
  1. ルートを探索し,見つかったオブジェクトをscanとtopの間に移動する.ここにTo空間が生まれる.
  2. ルートを探索し終えると,scanポインタをtop方向にずらし,オブジェクトをスキャンする.
  3. 見つかったオブジェクトは同様にscanの右に移動する.
  4. 一つの木を探索し終えると,いったんGCを中断する.
  5. オブジェクトの割り当て要求がある場合,freeをbottom方向にずらす.この際free-scan間はNew空間になる.
  6. またGCを再開.
  7. これを繰り返しscanがtopに到達すると,bottomをtop方向にオブジェクトを解放しながら動かす.
  8. bottomがtopに到達すると,From空間がまるまるFree空間に変わる.
  9. その後,scanをfreeの横に,topをscanの横に移動する事でTo空間がFrom空間に変わる.
  10. GC終了.

私的にはしくみを知ったときに一番感銘を受けたアルゴリズム.
美しいですよね.

利点

  1. インクリメンタル
  2. non-movingなCopyingGCのようなものを作成できる

欠点

  1. CopyingGCとは違いコンパクションされない。フラグメンテーションが発生する。

実コードを見たい場合


  1. Io(id:keisukefukudaさんより)