copying GCに対する改良

前回の記事ではcopying GCを取り上げた。今回はその続きとしてcopying GCに対する改良を2つ取り上げる。

2つはそれぞれcopying GCの短所、つまり「毎回全てのオブジェクトがコピーされること」「確保したメモリの半分しかプログラムで利用できないこと」に対応している。

大きい、または長命なオブジェクトの別扱い

copying GCは生き残るオブジェクトを毎回全てコピーするので、オブジェクトが短命でかつ小さい程都合がよい。裏を返すとオブジェクトが大きかったり長命だとコストが嵩む。

そこで、そのようなオブジェクトは別領域にとりmark & sweepで管理することにして、copying GCの対象からは外してしまう。

アルゴリズム

コンパクションの際に、ポインタがmark & sweepで管理されるオブジェクトを指す場合はマークも同時に行う。

ポインタのとりえる値は次の3種類に分けられる。

1. from-spaceにあるコピー前のオブジェクトを指す場合
2. from-spaceを指すがオブジェクトは既にコピーされていた場合
3. mark & sweepで管理するオブジェクトを指す場合

それぞれに応じて処理は次のようになる。

• from-space内のコピー前のオブジェクトを指す場合:
  1. to-spaceにコピー、freeポインタを進める
  2. forwarding pointerを記録
  3. ポインタを更新
• from-space内を指すがオブジェクトが既にコピー済の場合:
  1. ポインタを更新
• mark & sweep対象のオブジェクトを指す場合:
  1. そのオブジェクトをマークし、オブジェクト内のポインタを再帰的に処理。

ポインタの種類も3種類、ルートポインタ、to-spaceにコピーされたオブジェクト内のポインタ、markされたオブジェクト内のポインタ、とあるが、どの場合も処理は同じになる。

マークを兼ねたコンパクションが終わったら、mark & sweepの領域の回収処理を行う。

インクリメンタルなコンパクション

メモリの制約の厳しい環境では、確保できるメモリの半分しか一度に使用できないcopying GCは適用しづらい。そこで、コンパクションの効率を犠牲にしてメモリの利用効率を上げる方法が提案されている。

この手法では、ヒープを2つではなくn+1の部分空間に分割する。そのうちプログラムに使わせられないのは1つだけで、残りのn個の部分空間はプログラムが利用できる。

GCでは、とっておいたその部分空間をto-spaceとし、プログラムが使っていた部分空間のうち一つだけをfrom-spaceとしてcopying GCを行う。残りの(n-1)個の部分空間は「大きい、または長命なオブジェクトの別扱い」の場合のようにmark & sweepの対象とする。

GC前

GC後