GCアルゴリズム詳細解説

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さんより）