Garbage Collectionの教科書

この本はほぼ唯一といっていいgarbage collectionの教科書。初歩的なアルゴリズムから並列GCまで幅広く、複数のアルゴリズムがあるものはそれぞれ解説して利点欠点も比較している。

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

posted with amazlet on 07.04.04

Richard Jones Rafael Lins
John Wiley & Sons Ltd (Import) (1996/07/12)
売り上げランキング: 3600

おすすめ度の平均:

よくまとまっていて分かりやすい

Amazon.co.jp で詳細を見る

米Amazon.comのページを見たい方はこちら。当然ながらカスタマーレビューが日本のアマゾンより多い。

なまじ良く書かれているだけに、Amazonの太っ腹機能「なか見!検索」(検索した単語のある周辺のページを立ち読みさせてくれる)がかなり便利に使える。アルゴリズム名などで検索するのがお勧め。検索して出てきたところから2〜3ぺージも読めば用が足りることも多い。

例えば、マルチスレッド・プログラム用のGC (concurrent GC)としてTreadmillという方式がある。 これで検索すると p.188, p.218, p.219, p.220, p.221, p.225 が出てくる。これはもう明らかに、p.218〜221辺りを読めばいいわけだ。案の定、p.218をクリックすると、そこから「8.8 Baker's Treadmill collector」という節が始まっている。

目次も詳しい。そのおかげで、検索のアタリをつけるのも簡単。いいんだか悪いんだか。

※目次などを除いて、「なか見!検索」で出てきた本文中のページを立ち読みするにはアマゾンのアカウントでログインしていることが必要。ページをクリックして「この機能は利用できません」のように表示されたら、おそらくアカウントでログインしていないことが原因です。

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 Garbage Collector

copying GCでウェブを検索すると真っ先に東大のコンパイラ演習の資料^*が出てくるが、恥ずかしながらこれを読んでもいまひとつはっきりしたイメージが湧かず、うまくいくという確信がなかった。 最近ようやく腑に落ちたのでまとめてみようと思う。

copying GCではヒープを2つの部分空間に分け、 プログラムはその片方だけを利用して動作する。そこに空きがなくなるとGCが起動する。 GCは使われている部分空間(from-space)の中の到達可能なオブジェクトを全てもう一方の部分空間(to-space)にコピーする。GCが終了するとプログラムは今度はto-spaceを使って動作を継続する。2つの部分空間の役割はGCのたびに入れ替わる。

GC前

GC後

まずはmark and sweep方式をおさらい。その後、 copying GCの説明に先立ちmark-compact方式を説明する。

続きを読む