情報科学実験II資料
一般教養としてのGarbage Collection

遠藤

1998年 12月 3日

1 What is Garbage Collection?

世の中のプログラミング環境をメモリ管理の方法に注目して 大きく2分すると、(1)手動のメモリ解放を必要とする場合、 (2)自動的なメモリ解放を行なってくれる場合、に分けられる。 C言語やC++, Pascalなどは普通の場合は前者であり、 SchemeやML, Javaなどは後者である。 Cではmalloc関数によってメモリ領域を確保(allocate)したら、使い終った後に free関数によって解放しなければならない。 一方、Schemeでconsやvectorで確保したメモリ領域は、使い終った後 ほうっておいても自動的に解放される。

今回のトピックである、garbage collection(GC)は、 自動メモリ管理方式のうち最も広く使われているものである。 今回の話の目的は、ユーザからは(えてして迷惑な)black boxとして扱われがちな garbage collectionがどう実装されているか、速度は何によって決まるか、 などを概観することである。

12は、allocate+手動freeと allocate+GCのそれぞれでユーザプログラム を動かした場合の時間と使用中メモリ量の関係のイメージ図である。 図の灰色の部分はメモリ管理のために使われる時間を示す。

Allocate+GCをallocate+手動freeと比べた場合 (注)、 以下のような短所が挙げられる。

  1. ユーザプログラムの停止時間が長くなる。 この理由は、手動freeと違ってGCは、不要なメモリ領域(ゴミ)の検出と ゴミの解放を一気に行なうためである。 これはGUIプログラムなどで特に問題となる。
  2. トータルの実行時間も、多くの場合、長くなる。
  3. まとめて解放を行なうため、使用中のメモリ領域が(特にGC直前) 多くなる。

1.の停止時間の問題と2.のトータル時間の問題は明確に区別しておく 必要がある。 ユーザプログラムの観点からすると、停止時間はGUIプログラムでは重要だが、 計算主体のプログラムではそれよりもトータル時間の方が重要である。 GCアルゴリズムの観点からすると例えば、停止時間を短縮するアルゴリズムも 存在するが(10章)、そのためにトータル時間が犠牲になることもある。

一方GCの最大の長所は、プログラマの手間を軽減することである。 Free忘れによるメモリリーク(メモリの無駄)や 早まったfreeなどによるバグを避けることができる。

4章以降では、GCのアルゴリズムの説明を通して、 GCの短所はどのように和らげられるのか、手間軽減のほかに長所はあるのか、 など触れる。 大まかな流れは[2]に沿っている。

   figure1
Figure 1: Allocate+手動freeの場合の時間とメモリ使用量の関係(イメージ図)。 Freeが行なわれた時点でその領域は再利用可能になる

   figure2
Figure 2: Allocate+GCの場合の時間とメモリ使用量の関係(イメージ図)。 GCが起こって初めて領域の再利用が可能になる

2 予備知識: メモリ構造と明示的なメモリ管理

  これからの物事を理解するために、プログラムが動いている時の メモリ領域の構造を図3に示す。 小さい四角はメモリオブジェクト、矢印はポインタを表す。 図は演習のSchemeコンパイラの場合を示す (注)> が、大まかには、C言語など他の言語も 似たような構造になる。

   figure3
Figure 3: プログラム動作中の典型的なメモリ構造

ここでは一度GCから離れて、allocate+手動freeの実装について軽く 触れておくことにする。

freeが行なうべき仕事は、指定されたメモリオブジェクトを 空き領域(=将来のallocateのために利用できる領域)にすることである。 C言語のfree関数にはメモリオブジェクトの先頭ポインタのみが知らされ、 オブジェクトの大きさは知らされない。 大きさを知るためには、最も単純には、allocateの時点でオブジェクトの 最初のワードの 前に余分に1ワード(このような余分な領域をヘッダと呼ぶ)とっておき、 そこに大きさを書いておけば良い。

飛び飛びのメモリオブジェクトがfreeされる状況を考えれば分かるように、 空き領域はヒープ上に通常は散らばってしまっている。 これらを将来再利用するために、リストにつないで管理(フリーリスト)するのが 一般的である。

allocateが行なうべき仕事は、様々な空き領域がつまったフリーリストから、 要求された大きさ以上の箇所を見つける、ということになる。

用語の説明をいくつか示す。

ところがこの単純な方式だと、allocateが(coalescingをまじめにやるならfreeも) 定数時間では終らない。最悪フリーリストの長さに比例した時間がかかる。 これを改善するための一つの方法は、フリーリストを空き領域サイズに 応じて複数用意すること(segregated free lists)である。一つのフリーリスト 中に同一サイズの領域しか入っていないのなら、allocateは定数時間で できる。

[5]は、メモリ管理方式のsurveyである。

3 Garbage Collectionの立場

  ちょっと先走って言っておくと、C言語におけるmalloc/free関数や 演習コンパイラの実数計算ルーチンがそうであるように、GCもまた ランタイムライブラリ(実行中にメモリに置かれ、呼ばれるのを待つ プログラムたち)である。

よって、気に入らなければすぐに取り替え可能なのが理想だが、 いくつかの理由によって、GCは他のランタイムライブラリよりも強く コンパイラに密着している。 一般には、GCは以下のような情報を知ることができる必要がある。

  1. GC起動時に各レジスタが生きているか否か、生きているならポインタか 否か分かる。
  2. GC起動時にスタックの範囲が分かる。
  3. 全ての大域変数はどこに格納されているか分かる。
  4. オブジェクトの途中を指しているかもしれないポインタがあるとき、 オブジェクトの先頭位置が分かる。
  5. オブジェクトを指すポインタがあるとき、そのサイズが分かる。
  6. オブジェクトやスタックに含まれる各ワードを見て、 それがポインタか否か分かる。

このうち5に関しては、allocate+手動freeにおいても必要だった。

一方、1〜6の全てがどうしても必要と言うわけではなく、1や6が分からない 状況、つまりC言語上でコンパイラの変更なしにGCを行なう処理系も存在する。 これについては11章で述べる。 多くの場合には、あらゆる値に型を示すタグがついているなどして、 GCに情報が提供されている。

4, 9, 10章に示すように、 GCアルゴリズムによっては更に以下の情報が必要なものもある。

  1. ユーザプログラムによるメモリオブジェクトへの書き込みが分かる。
  2. ユーザプログラムによるメモリオブジェクトの読み込みが分かる。

4 Reference Counting

  自動でメモリオブジェクトの解放をする素直な方法は、 それぞれのオブジェクトに対する参照数(reference count)を常に数えて おくことである。 参照数はオブジェクトのヘッダなどに記録しておく。 オブジェクトaに対する参照が0になったら、そのオブジェクトは解放可能 である。aが別のオブジェクトbを参照していたらbの参照数を 1減らす。

この方式の欠点は、以下のようになる。

このため、あまり広く使われていない。

ただし、長い停止時間がおこらないため(図2ではなく 図1のようになる)、トータルでの実行速度よりも 停止時間の短縮が重要な、GUI対応のスクリプト言語では使われている 場合もある(Pythonなど)。

5 探索型GC

GCの仕事は、ヒープ中のオブジェクトを「将来ユーザプログラムに 使われる可能性のあるオブジェクト(live object)」と 「使われる可能性のないオブジェクト(ゴミ)」に分類し、 ゴミオブジェクトの領域を解放することである。 多くのGCは、あるオブジェクトがliveかゴミかを、 「ユーザが現在直接さわれるオブジェクト(レジスタ、スタック、大域変数など で、これらをルートオブジェクトと呼ぶ) から、ポインタによって到達可能か否か」によって判断している。

よってGCは、ルートオブジェクトからポインタを再帰的に探索し、 発見したオブジェクトを全て何らかの方法で「区別」する。 そして探索が終った時点で発見されなかったオブジェクトをゴミと見なす。 探索には単純なallocate/free処理よりもずっと長い時間が 必要なため、図2のようにユーザプログラムを 止めてしまう (注)。 このような探索型GCの代表的なものは、mark and sweep GC (6章)と copying GC (7章)である。

3章で述べた条件(ルートの識別、ポインタか否かの判定、 オブジェクトサイズの知識など)は、この再帰探索を可能にするのが目的 である。

再帰探索のアルゴリズムを理解するためのモデルとして、tri-color abstraction というのが分かりやすい。 GC中のオブジェクトには、白、灰色、黒の3色のいずれかが塗られている。

詳細については田浦さんレジュメ3章を参照。

6 Mark and Sweep GC

  Javaの実装の一つであるKaffeや、C言語から利用できるGCであるBoehm GC で採用されている方法。

各オブジェクトに、1ビットのマークビットを割り当てる。 オブジェクトのヘッダに含めるのが簡単だが、 新しい処理系ではヒープの外にビットマップを用意する場合が多い。

ユーザプログラムがallocateを繰り返し、メモリが足りなくなったら GCを起動する。 一度のGC処理は、探索を行なうマークフェイズと、 ゴミ領域を解放するスイープフェイズからなりたつ。 GC開始時には全オブジェクトのマークビットは0である。 そしてルートオブジェクトから到達可能なオブジェクトのマークビットを、 次々に1にしていく。 GC処理のwave front(つまり灰色オブジェクト)を覚えるために、 マークスタックという データ構造を用いるのが一般的である (注)。

マークスタックを用いたmark and sweep GCのアルゴリズムの流れ は図4のように記述できる。 途中、マークビットが0であるか調べてから1にしている。 これによって、複数箇所から参照されているオブジェクトであっても、 正しく一度だけマークされる。

   figure78
Figure 4: 単純なmark and sweep GCのアルゴリズム

7 Copying GC

  多くのSchemeやML処理系で採用されている方法。 本演習でお勧めしてきた方法でもあります。

この方式の変わっているところは、ヒープを2等分して、 片方が埋まったところでGCを起動する点である(図5)。 そして到達可能なオブジェクトたちを、そっくりもう片方のヒープに 空きをつめながらコピーする。 コピー元のヒープをfromspace、コピー先のヒープをtospaceと呼ぶ。 コピーが終った時点ではすでにfromspaceにはlive objectの残骸と ゴミしか残っていないので用無しとなる。 GC終了後、ユーザプログラムはtospaceを用いて動作を続ける。 このように、2つのヒープの役割を交替しながらシステムは動作する。

概念的には分かりやすいが、基本アルゴリズムは少しややこしい。 例えばコピー後のグラフはtospace内で完結し、fromspaceにポインタが のびていてはいけない。 さらに気をつけることは、複数箇所から同オブジェクトが参照 されている場合である。図ではbcdを参照しているので、 tospaceにおいてもb'とc'は同オブジェクトを参照しなければならない。

アルゴリズムをtri-color abstractionを用いて考えると以下のようになる (注)

GC開始時に、ルートオブジェクトから直接参照されるオブジェクト(図ではaのみ) をtospaceにコピーする。この時点でaは灰色と考えられる。 以降、GCは再帰探索のためにtospaceを指す2つのポインタを用いる。

オブジェクトoを白から灰色にする動作はoをtospace中のunscannedへの コピーすることあり、灰色から黒にする動作は、 oが直接参照するオブジェクトのコピー(灰色化) + o中のポインタ書き換え、である。

同じオブジェクトへの複数参照に対応するためには、fromspace中のdを 見ただけで、それがすでにコピー済みであり、コピー先はd'であることが 分かる必要がある。 そのために、灰色化の時点でdforwarding tag (コピー済みであることを表す)、 forwarding pointer(コピー先を教えてくれる)を書き込んでおく。

   figure119
Figure 5: Copying GCの動作。Fromspace中の到達可能なオブジェクトを tospaceへコピーする。ただし正しくはfromspace中のオブジェクトa〜gも すきまなく並んでいるはず

>

7.1 Copying GCの性質

Copying GCの興味深い性質は、コピーするときにオブジェクトの空きを つめるため、fragmentationが発生しないということである。 よって手動freeを用いる場合(2章)や mark and sweep(6章)のような、フリーリストを 用いた複雑なallocationが必要ない。 代わりに、空き領域の先頭と、ヒープ境界を表すポインタを 管理しておけば充分である。

またオブジェクトの空きをつめるのは、GC以降のユーザプログラムの 局所性に良い影響を与える可能性がある。

演習コンパイラでは、「低コストなallocate」をインライン展開し (heapプリミティブ)、 さらにヒープ境界チェックをCPS関数の先頭にまとめて(live-reg疑似命令) 高速化を図っている。

8 Mark and Sweep v.s. Copying

ここでは主に実行時間に注目して、mark and sweep GCとcopying GCの 比較を行なう。持っていきたい結論は「古い教科書には``copyingの方が 優れている''と書かれているが、最近のアルゴリズムの工夫によって、 そう一概には言えなくなった」である。

以下の議論で、live objectの量をL, ヒープ全体の大きさをMとする。 まずmark and sweepの1回のGC時間を考える。 マークフェイズではlive objectを全てマークするので、時間は Lに比例する。 スイープフェイズではヒープの全オブジェクトのマークビットを 調べるのでMに比例する。 以上より、mark and sweepのGC時間はm L + s Mとなる。

一方copying GCの場合、live objectを全てコピーすれば終りなので、 時間はLのみに比例し、c Lとなる。

よって「Mに実行時間が依存するmark and sweepよりも、 Lだけに依存するcopyingの方が有利である」というのが 通説だったのだが、最近のmark and sweep GCの実装は lazy sweepingという改良が行なわれており、 一概には成り立たない。

Lazy sweepingとはアイデア的にはごく簡単で、マークフェイズが 終ったらもうユーザプログラムを再開してしまう。 その後、ユーザプログラムによるallocate要求がなされて初めて、 マークビットの検査を少しづつ行なっていく(そして空き領域を見つけた 時点でユーザに渡したり、フリーリストにつないだりする)。 Lazy sweepingによって、allocateのオーバヘッドが増えてしまうのだが、 (1)GCの停止時間が短くなり、m Lと考えることができる、 (2)一度に行なうスイープよりも局所性の面で優れている、という利点がある。

さてこの状況でもう一度、定数mcに注目しつつ、 mark and sweep GC(停止時間m L)とcopying GC(停止時間c L)を比べてみる。 Mark and sweep GCが一つのlive objectに 対して行なう仕事は、オブジェクト全体readが1回、 ビット変更(マークビット)、スタックへのpush/popが1回づつである。 一方、copying GCの場合は、オブジェクト全体readが2回、オブジェクト全体 writeが1回、さらにポインタ付け替えが加わる。 よってm ;SPMlt; cであり、停止時間についてはmark and sweepの方が有利と 考えられる(注)

大ざっぱにまとめると、

8.1 GC v.s. 手動free

まじめな比較ではないが、GC(話が簡単なcopying GC)と 明示的な(手動)freeを行なう場合の、効率の比較を行なってみる。

ここでは、メモリ解放のコストを、「解放のために費やした時間 / 解放した領域の大きさ」として定義して比較する。 手動freeの場合はこのコストはfreeにかかる時間であり、 簡単のために定数fとする。

Copying GCの場合は、c Lの時間をかけてM / 2 - Lの量を解放するので コストはとなる。

ここから、平均的にLが小さいユーザプログラムでは手動freeよりも GCの方が効率的に(停止時間でなくトータル実行時間が)なる場合があると言える。 Lが小さいというのは、大量にメモリオブジェクトが確保されても すぐに使い終り、生き残るものは少ないという状況である。 特に、SchemeやMLなどの関数型言語ではそういうプログラム はそれほど特別なものではない (注)

9 Generational GC

  メモリオブジェクトの寿命について、多くのプログラムで観測される ある傾向が知られている。それは「古くから生き残っているメモリオブジェクトは そのまま生き残りやすく、新しく確保されたメモリオブジェクトほど すぐにゴミになりやすい」という傾向である。 GCの実行効率は生き残るオブジェクトが少ないほどよいのだから、 古いオブジェクトはほうっておいて(無条件に生き残るとみなして) 新しいオブジェクトを重点的に探索することによって利益が得られそうである。

Generational GC (注) は、新しめのメモリオブジェクトのためのヒープと、 古めのメモリオブジェクトのためのヒープを別にとる。 図6のようになる。 Copying GCを基にする場合、新世代のヒープと旧世代のヒープの それぞれが2等分される。 オブジェクトはまず新世代ヒープに確保される。もしそれが長い間 (例えばGCがn回起こる間)生き残ったら、旧世代ヒープに移る(promote)。

メモリ不足が起こったら、ヒープ全体のGCを行なう代わりに、 新世代ヒープだけを対象としたGC(minor collection)を行なう。 その際に、旧世代のメモリオブジェクトは無条件に生き残るものとみなす。 具体的には、再帰探索で旧世代へのポインタが見つかったら 無視する。図ではオブジェクトb以降の探索は行なわない。 このため、大抵の場合はminor collectionは、ヒープ全体を探索するよりも 速く終了する。

Minor collectionだけでは充分にメモリ解放ができなくなったら はじめて、ヒープ全体を探索するGC(major collection)を 試みる。

Minor collectionにおいて注意が必要なのは旧→新のポインタである。 たとえばcdのポインタに気付かないと、 到達可能なメモリオブジェクトdを間違って解放してしまう。 この図の場合、新世代へのポインタを持っているceは特別扱い され、ルートに加えられる。

さて、Schemeにおいて、ユーザプログラムがconsやvectorのみを用いる 限り、旧→新のポインタは決して生まれない。 Set-car!などの破壊的代入を行なって初めて生じるものである。 コンパイラが、破壊的代入の際に必ずGCに知らせる(書き換えられるオブジェクトを GCに教える)ようにすれば、GCが旧→新のポインタ全てを手早く見つける ことができる。 このように、メモリオブジェクトへの書き込みの際に特別な処理を 行なう機構をwrite barrierという (注)

Generational GCによって良い効果が得られるプログラムは、 最初に述べた「新しいメモリオブジェクトほどすぐにゴミになりやすい」 という傾向が良く当てはまっている場合である。 こういう場合には、一度のGC時間が短くなりつつ、しかも解放できる メモリ量は単純なGCとあまり変わらないので、トータルな実行時間、 プログラムの停止時間の両方を改善できる。

   figure146
Figure 6: Generational GCのヒープ。New generationのみを 探索する場合、cd, efのポインタに注意する必要がある

10 Incremental GC

  Generational GCは単純なGCに比べれば、プログラムの停止時間を 短くすることができる。 しかしそれでも、その停止時間はGUIプログラムなどのリアルタイム性が 必要なプログラムにとっては長過ぎる場合があるし、そもそも major collectionが起こってしまえば単純なGCと同じくらい停止する。

Incremental GCはGC処理を細切れにしてユーザプログラムと 交互に動かすことによって、停止時間を短くするアプローチである。 交互で動かす単純な方法は、allocate処理を行なうときに、こっそり 少しづつGCの探索処理を行なうことである。

Incremental GCを実装するには、いくつか問題点をクリアしなければ ならない。

基本的には、incremental GCは停止時間を短くするのが目的であって、 GCの仕事の量を減らそうとするものではない (注)。このため、トータル 実行時間は短くはならないと考えられる。逆に仕事の切替えオーバヘッドや write barrierの分、遅くなるだろう。

   figure165
Figure 7: Incremental GCの場合の時間とメモリ使用量の関係(イメージ図)。 GC処理を少しづつ進め、一通り終った時に始めて領域が解放される

   figure171
Figure 8: Incremental GCにはwrite barrierが必要なことを示す図。 マークの途中で、ユーザプログラムがaからcのポインタを作り、 bからcへのポインタを消すと、そのままでは破綻する

11 C言語のためのGC

  これまで、GCは常にあらゆるメモリ内容の型(ポインタか否か)を 知ることができることを前提としていたが、C言語のように、実行時に 型が分からない環境でGCを行なう処理系も存在し、 Boehm GC[1]などが有名である。 これはC/C++プログラムから利用できるmark and sweep GCライブラリで、 このライブラリが提供するmalloc関数を呼ぶことによって GC機能を利用できる。

再帰探索中に見つけた値のポインタ判定をどうするかというと、 アイデアは簡単で、とりあえずポインタだと思ってみるという方針をとる (conservative GCと呼ばれる)。 そしてヒープ領域以外を指していたり、空き領域のはずの箇所を指している 場合は、明らかにポインタでないとして除外する。

もちろんこの方針を取る限り、ユーザプログラムがポインタのつもりで 使っていない値を、GCがポインタだと思ってしまう (false pointer)可能性は避けられない。 その場合でも、少しメモリ利用効率が落ちるだけで、プログラムの 続行にほぼ支障はない (注)

12 その他

MLの型推論を用いて、もっと違った方法で自動メモリ管理を 行なう処理系もある。

以下、GCに関連したWebページをいくつか:

References

1
Hans-Juergen Boehm and Mark Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience. 18(9):807-820, 1988.

2
Richard Jones and Rafael Lins. Garbage Collection, Algorithms for Automatic Dynamic Memory Management. Wiley & Sones, 1996.

3
Mads Tofte and Jean-Pierre Talpin. Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions. In Proceedings of the 21st ACM Symposium on Principles of Programming Languages. pages 188-201. ACM, 1994.

4
Paul R. Wilson. Uniprocessor garbage collection techniques. In Proceedings of the 1992 SIGPLAN International Workshop on Memory Management. volume 637 of Lecture Notes in Computer Science, 1992.

5
Paul R. Wilson, Mark S. Johnstone, Michael Neely and David Boles. Dynamic Storage Allocation: A Survey and Critical Review. In Proceedings of the 1995 SIGPLAN International Workshop on Memory Management. volume 986 of Lecture Notes in Computer Science, 1995.

...Allocate+GCをallocate+手動freeと比べた場合
ただし、C言語で標準でリンクされるような malloc/free関数は、相当遅いことに注意。この比較では、充分速いallocate/freeと、 充分速いがアルゴリズムは基本的なGCを比較する
...図は演習のSchemeコンパイラの場合を示す
実際にはヒープは2等分される(後述)
...止めてしまう
多くの処理系で、allocate試行 → メモリ不足 → GC起動 というタイミングでGCが起こるため、ユーザプログラムから見ると、 allocateにかかる時間が時々とても長くなるように見える
...データ構造を用いるのが一般的である
関数の再帰呼びだしなどで記述するより、ずっと(定数分の1だが) メモリ効率がよい
...abstractionを用いて考えると以下のようになる
コピー前とコピー後(例えばAA')のセットに対して、色が一つ 決まると考える
...考えられる
この傾向は、ヒープ中に大きいオブジェクトが多いと 顕著になる。Copy GCを改良し、大きいオブジェクトを(mark and sweep的に 管理される)第3のヒープに確保することによってこの問題を緩和することは できる
...GCの方が有利
Segregated free listを使ってさえ、copying GCのallocateに 勝つのは困難と考えられる
...はそれほど特別なものではない
もちろん、オブジェクトがほとんどゴミに ならない(M/2-Lがほとんどゼロ)プログラムもたくさんあり、 その場合にGCは悲惨なことになる
...GC
SML/NJなど、copying GCを基にしたものが多いようだが、 generationalの考え方はcopyingでもmark and sweepでも共通
...行なう機構をwrite barrierという
コンパイラの協力が得られない場合でもwrite barrierを 実現することは可能である。大抵のOSではメモリ領域のアクセス権限を 変えることができる(SunOSのmprotect()など)ので、旧世代ヒープを write不可にしておくことによって、writeをつかまえることができる
...のどちらかを実装すれば良い
個人的にはtri-color abstractionの不変条件を常に満たす、 前者の方が分かりやすいと思う
...GCの仕事の量を減らそうとするものではない
Incrementalかつgenerationalなものなら話は別
...続行にほぼ支障はない
ところで、型が分からない環境でcopying GCを実装するのは、 少なくともそのままでは無理である。Copying GCではメモリ内容の update(fromspaceを指すポインタがtospaceを指すように書き変わる)が あるためである。 非ポインタなのに勝手にGCに値を書き変えられてしまっては、 ユーザプログラムが正しく続行することができない

 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 16 May, 1999