copying GCでウェブを検索すると真っ先に東大のコンパイラ演習の資料*が出てくるが、恥ずかしながらこれを読んでもいまひとつはっきりしたイメージが湧かず、うまくいくという確信がなかった。 最近ようやく腑に落ちたのでまとめてみようと思う。
copying GCではヒープを2つの部分空間に分け、 プログラムはその片方だけを利用して動作する。そこに空きがなくなるとGCが起動する。 GCは使われている部分空間(from-space)の中の到達可能なオブジェクトを全てもう一方の部分空間(to-space)にコピーする。GCが終了するとプログラムは今度はto-spaceを使って動作を継続する。2つの部分空間の役割はGCのたびに入れ替わる。
まずはmark and sweep方式をおさらい。その後、 copying GCの説明に先立ちmark-compact方式を説明する。
mark and sweep 方式
mark and sweep方式のGCは大略次のような動作をする。
1. グローバル変数やCPUのレジスタ、マシンスタックなどの既知のポインタ(纏めてルートセットという)が指すオブジェクトをマークする。
2. 既にマークされたオブジェクトからポイントされているオブジェクトを再帰的に全てマークする。
マークされたオブジェクトはまだ使われているオブジェクトなので生き残る。マークされなかったオブジェクトは最早プログラムから参照不可能となったものなので回収される。
3. ヒープの全オブジェクトを走査。マークされたオブジェクトはマークを解除し、マークされなかったオブジェクトは回収する。回収されたメモリはリストで管理され、次にアロケートする際に再利用される。
mark and sweep方式の性質
マークと、マークの解除及び回収という、2パスの手順からなる。
オブジェクトが移動されないので、ヒープの断片化という問題が生じる。このため空間利用効率が下がり、局所性も低下する。効率よくメモリを割り当てようとするとアロケータも複雑になる。
mark-compact方式
copying GCに進む前にmark-compact方式を説明する。その方が格段に理解が容易になる。
mark and sweep方式ではヒープの断片化が問題となった。 mark-compact方式ではそれを解決するため、 mark and sweep方式と同様に到達可能オブジェクトをマークした後、 それらのオブジェクトを移動させてヒープの隙間を詰める。これをコンパクションという。
空き領域が一つの大きなかたまりにまとまるため、アロケータは簡単になる。
two fingerアルゴリズム
ヒープの上の方にいるオブジェクトを空いているところに下から順に詰め込む。教室の後ろの方に座っている学生を一番前から順に座らせるようなものか。
- コンパクション
freeポインタとliveポインタという2つのポインタをヒープの下と上から出発させる。freeポインタは空きスロットを、liveポインタは生き残ったオブジェクトを探す。
liveポインタが生きているオブジェクトを発見するとそれをfreeポインタが指す空きスロットにコピーする。元の場所にはコピー先を記録する。これをforwarding pointerと呼ぶ。 freeポインタは次の空きスロットに進む。
freeポインタとliveポインタが出会ったらコンパクション完了。
- ポインタ修正
次に、オブジェクトの移動前の位置を指していたポインタを移動先を指すように書き換える。 移動したオブジェクトの元の位置に残されているforwarding pointerでポインタを更新する。
ポインタが指していたオブジェクトが移動されたかどうかは、liveポインタと比較して大小をみれば判る。
two fingerアルゴリズムの性質
このアルゴリズムはシンプルで速度もそこそこだが、同じ大きさのオブジェクトのみの場合に限定されること、また移動によってオブジェクトの順序がばらばらになり局所性を低下させるといった欠点がある。
Lisp2アルゴリズム
ヒープの先頭から順に隙間を詰めるように移動させる。最も素朴なコンパクション方法。
- 移動先の計算
オブジェクトを移動させる前に、移動先だけ計算してしまう。
freeポインタとliveポインタの2つのポインタを使う点はtwo fingerアルゴリズムと同じだが、どちらもヒープの下から出発させる。
liveポインタが生きているオブジェクトを発見すると移動先のアドレスを計算してオブジェクトに余分に持たせているforwarding pointerに記録する。 freeポインタもオブジェクトの大きさだけ進める。
- ポインタの修正
次に生きているオブジェクトを指す全てのポインタをforwarding pointerに従って更新する。
- コンパクション
最後にオブジェクトを実際に移動させる。
Lisp2アルゴリズムの性質
大きさの異なるオブジェクトが混在するヒープを扱えて、オブジェクトの順序も保たれる。two fingerアルゴリズムが持つ問題点を解消している。
一方、3パス(マークも含めたGC全体では4パス)もかかること、オブジェクトごとにforwarding pointerのための余分なスペースを要するという短所もある。
そしてcopying GCへ
mark-compact方式を睨んでもう一つ二つ工夫を加えるとcopying GCが出来上がる。
まずはmark-compact方式のポイントを考えてみよう。
- ポインタ修正のためにオブジェクトのコピー先を示すforwarding pointerを記録する。
- アルゴリズムによってはコンパクションが別のオブジェクトの移動元を上書きしてしまう。
Lisp2方式でforwarding pointer専用に余分なスペースが必要になったのは、オブジェクトのコピー元が別のオブジェクトのコピーにより上書きされる可能性があり、移動後の残骸にforwarding pointerを記録することができないためだった。
copying GCではヒープを2つの部分空間に分け、一回のGCではfrom-spaceからto-spaceへのみコピーする。だからコンパクションによる上書きは起こらない。従ってforwarding pointerは移動元にそのまま上書きできる。
更に、コンパクションがオブジェクトの探索を兼ねることができれば、マークのフェーズをなくすことができる。
mark and sweep方式やmark-compact方式では一般にスタックを利用して到達可能なオブジェクトを探索しマークをつける。つまり深さ優先探索する。
一方、探索はキューを用いた幅優先探索でも行える。 幅優先探索では、キューの先頭からオブジェクトを一つ取り出してそのオブジェクトの持つポインタをチェックする。ポインタが新しいオブジェクトを指していればそれをキューの末尾に追加する。
copying GCではto-spaceがまさにそのキューの役割を果たす。to-spaceへのコピーはそのままキューへの追加とみることができる。
copying GCのアルゴリズム
copying GCではfreeポインタとscanポインタの2つのポインタを使う。freeポインタをto-spaceの下から出発させる。移動されるオブジェクトはfreeポインタが指すアドレスにコピーされ、freeポインタがそのオブジェクトの大きさだけ進められる。
まず、ルートセットから指されるオブジェクトをto-spaceに全てコピーする。コピー元にはforwarding pointerを記録する。
それが済んだらscanポインタをto-spaceの下から出発させる。scanポインタは探索キューの先頭を意味する。scanポインタより下は既に処理が済んだもの、scanポインタより上はまだ処理されていないものとなる。
scanポインタが指すオブジェクトの持つポインタを調べる。 ポインタが指すオブジェクトがまだ移動されていなければそのオブジェクトをto-spaceにコピーし、forwarding pointerを元の位置に記録する。既に移動済なら記録されているforwarding pointerを使ってポインタの修正だけをする。 全てのポインタを処理したら、scanポインタを進める。
オブジェクトAの処理前
処理後
上図ではオブジェクトAは3つのポインタを持ち、それぞれB、C、Dを指している。このうちBは既にto-spaceにコピーされているのでforwarding pointerでポインタの修正だけ行う。C、Dは新たに発見したオブジェクトなのでto-spaceへのコピーとforwarding pointerの記録を伴う。
scanポインタがfreeポインタに追い付いたら、to-spaceの全てのオブジェクトが処理済となりGCは完了。コピーされなかったオブジェクトは破棄される。
copying GCの性質
オブジェクトの探索・コンパクション・ポインタ修正が全て一回の走査で完了する。これがcopying GCの大きな特長であるように思える。コンパクションを行うのでmark-compact方式と同様のアロケータの単純さなどの長所も維持する。
短所はなんといってもメモリの半分しかプログラムで利用できない点だろう。ただし、mark and sweep方式(やmark-compact方式)の側にもマークスタックの大きさを定数で押さえにくいという問題がある。マークスタックの深さは最悪の場合、全到達可能オブジェクトの半数程度になるのではなかろうか。
リンク
John Wiley & Sons Ltd (Import) (1996/07/12)
売り上げランキング: 3600
よくまとまっていて分かりやすい