Figure 1: Allocate+手動freeの場合の時間とメモリ使用量の関係(イメージ図)。 Freeが行なわれた時点でその領域は再利用可能になる
遠藤
1998年 12月 3日
世の中のプログラミング環境をメモリ管理の方法に注目して 大きく2分すると、(1)手動のメモリ解放を必要とする場合、 (2)自動的なメモリ解放を行なってくれる場合、に分けられる。 C言語やC++, Pascalなどは普通の場合は前者であり、 SchemeやML, Javaなどは後者である。 Cではmalloc関数によってメモリ領域を確保(allocate)したら、使い終った後に free関数によって解放しなければならない。 一方、Schemeでconsやvectorで確保したメモリ領域は、使い終った後 ほうっておいても自動的に解放される。
今回のトピックである、garbage collection(GC)は、 自動メモリ管理方式のうち最も広く使われているものである。 今回の話の目的は、ユーザからは(えてして迷惑な)black boxとして扱われがちな garbage collectionがどう実装されているか、速度は何によって決まるか、 などを概観することである。
図1、2は、allocate+手動freeと allocate+GCのそれぞれでユーザプログラム を動かした場合の時間と使用中メモリ量の関係のイメージ図である。 図の灰色の部分はメモリ管理のために使われる時間を示す。
Allocate+GCをallocate+手動freeと比べた場合 （注）、 以下のような短所が挙げられる。
1.の停止時間の問題と2.のトータル時間の問題は明確に区別しておく 必要がある。 ユーザプログラムの観点からすると、停止時間はGUIプログラムでは重要だが、 計算主体のプログラムではそれよりもトータル時間の方が重要である。 GCアルゴリズムの観点からすると例えば、停止時間を短縮するアルゴリズムも 存在するが(10章)、そのためにトータル時間が犠牲になることもある。
一方GCの最大の長所は、プログラマの手間を軽減することである。 Free忘れによるメモリリーク(メモリの無駄)や 早まったfreeなどによるバグを避けることができる。
4章以降では、GCのアルゴリズムの説明を通して、 GCの短所はどのように和らげられるのか、手間軽減のほかに長所はあるのか、 など触れる。 大まかな流れは[2]に沿っている。
Figure 1: Allocate+手動freeの場合の時間とメモリ使用量の関係(イメージ図)。
Freeが行なわれた時点でその領域は再利用可能になる
Figure 2: Allocate+GCの場合の時間とメモリ使用量の関係(イメージ図)。
GCが起こって初めて領域の再利用が可能になる
これからの物事を理解するために、プログラムが動いている時の メモリ領域の構造を図3に示す。 小さい四角はメモリオブジェクト、矢印はポインタを表す。 図は演習のSchemeコンパイラの場合を示す （注）> が、大まかには、C言語など他の言語も 似たような構造になる。
ここでは一度GCから離れて、allocate+手動freeの実装について軽く 触れておくことにする。
freeが行なうべき仕事は、指定されたメモリオブジェクトを 空き領域(=将来のallocateのために利用できる領域)にすることである。 C言語のfree関数にはメモリオブジェクトの先頭ポインタのみが知らされ、 オブジェクトの大きさは知らされない。 大きさを知るためには、最も単純には、allocateの時点でオブジェクトの 最初のワードの 前に余分に1ワード(このような余分な領域をヘッダと呼ぶ)とっておき、 そこに大きさを書いておけば良い。
飛び飛びのメモリオブジェクトがfreeされる状況を考えれば分かるように、 空き領域はヒープ上に通常は散らばってしまっている。 これらを将来再利用するために、リストにつないで管理(フリーリスト)するのが 一般的である。
allocateが行なうべき仕事は、様々な空き領域がつまったフリーリストから、 要求された大きさ以上の箇所を見つける、ということになる。
用語の説明をいくつか示す。
ところがこの単純な方式だと、allocateが(coalescingをまじめにやるならfreeも) 定数時間では終らない。最悪フリーリストの長さに比例した時間がかかる。 これを改善するための一つの方法は、フリーリストを空き領域サイズに 応じて複数用意すること(segregated free lists)である。一つのフリーリスト 中に同一サイズの領域しか入っていないのなら、allocateは定数時間で できる。
[5]は、メモリ管理方式のsurveyである。
ちょっと先走って言っておくと、C言語におけるmalloc/free関数や 演習コンパイラの実数計算ルーチンがそうであるように、GCもまた ランタイムライブラリ(実行中にメモリに置かれ、呼ばれるのを待つ プログラムたち)である。
よって、気に入らなければすぐに取り替え可能なのが理想だが、 いくつかの理由によって、GCは他のランタイムライブラリよりも強く コンパイラに密着している。 一般には、GCは以下のような情報を知ることができる必要がある。
このうち5に関しては、allocate+手動freeにおいても必要だった。
一方、1〜6の全てがどうしても必要と言うわけではなく、1や6が分からない 状況、つまりC言語上でコンパイラの変更なしにGCを行なう処理系も存在する。 これについては11章で述べる。 多くの場合には、あらゆる値に型を示すタグがついているなどして、 GCに情報が提供されている。
4, 9, 10章に示すように、 GCアルゴリズムによっては更に以下の情報が必要なものもある。
自動でメモリオブジェクトの解放をする素直な方法は、 それぞれのオブジェクトに対する参照数(reference count)を常に数えて おくことである。 参照数はオブジェクトのヘッダなどに記録しておく。 オブジェクトaに対する参照が0になったら、そのオブジェクトは解放可能 である。aが別のオブジェクトbを参照していたらbの参照数を 1減らす。
この方式の欠点は、以下のようになる。
ただし、長い停止時間がおこらないため(図2ではなく 図1のようになる)、トータルでの実行速度よりも 停止時間の短縮が重要な、GUI対応のスクリプト言語では使われている 場合もある(Pythonなど)。
GCの仕事は、ヒープ中のオブジェクトを「将来ユーザプログラムに 使われる可能性のあるオブジェクト(live object)」と 「使われる可能性のないオブジェクト(ゴミ)」に分類し、 ゴミオブジェクトの領域を解放することである。 多くのGCは、あるオブジェクトがliveかゴミかを、 「ユーザが現在直接さわれるオブジェクト(レジスタ、スタック、大域変数など で、これらをルートオブジェクトと呼ぶ) から、ポインタによって到達可能か否か」によって判断している。
よってGCは、ルートオブジェクトからポインタを再帰的に探索し、 発見したオブジェクトを全て何らかの方法で「区別」する。 そして探索が終った時点で発見されなかったオブジェクトをゴミと見なす。 探索には単純なallocate/free処理よりもずっと長い時間が 必要なため、図2のようにユーザプログラムを 止めてしまう （注）。 このような探索型GCの代表的なものは、mark and sweep GC (6章)と copying GC (7章)である。
3章で述べた条件(ルートの識別、ポインタか否かの判定、 オブジェクトサイズの知識など)は、この再帰探索を可能にするのが目的 である。
再帰探索のアルゴリズムを理解するためのモデルとして、tri-color abstraction というのが分かりやすい。 GC中のオブジェクトには、白、灰色、黒の3色のいずれかが塗られている。
Javaの実装の一つであるKaffeや、C言語から利用できるGCであるBoehm GC で採用されている方法。
各オブジェクトに、1ビットのマークビットを割り当てる。 オブジェクトのヘッダに含めるのが簡単だが、 新しい処理系ではヒープの外にビットマップを用意する場合が多い。
ユーザプログラムがallocateを繰り返し、メモリが足りなくなったら GCを起動する。 一度のGC処理は、探索を行なうマークフェイズと、 ゴミ領域を解放するスイープフェイズからなりたつ。 GC開始時には全オブジェクトのマークビットは0である。 そしてルートオブジェクトから到達可能なオブジェクトのマークビットを、 次々に1にしていく。 GC処理のwave front(つまり灰色オブジェクト)を覚えるために、 マークスタックという データ構造を用いるのが一般的である （注）。
マークスタックを用いたmark and sweep GCのアルゴリズムの流れ は図4のように記述できる。 途中、マークビットが0であるか調べてから1にしている。 これによって、複数箇所から参照されているオブジェクトであっても、 正しく一度だけマークされる。
Figure 4: 単純なmark and sweep GCのアルゴリズム
多くのSchemeやML処理系で採用されている方法。 本演習でお勧めしてきた方法でもあります。
この方式の変わっているところは、ヒープを2等分して、 片方が埋まったところでGCを起動する点である(図5)。 そして到達可能なオブジェクトたちを、そっくりもう片方のヒープに 空きをつめながらコピーする。 コピー元のヒープをfromspace、コピー先のヒープをtospaceと呼ぶ。 コピーが終った時点ではすでにfromspaceにはlive objectの残骸と ゴミしか残っていないので用無しとなる。 GC終了後、ユーザプログラムはtospaceを用いて動作を続ける。 このように、2つのヒープの役割を交替しながらシステムは動作する。
概念的には分かりやすいが、基本アルゴリズムは少しややこしい。 例えばコピー後のグラフはtospace内で完結し、fromspaceにポインタが のびていてはいけない。 さらに気をつけることは、複数箇所から同オブジェクトが参照 されている場合である。図ではbとcがdを参照しているので、 tospaceにおいてもb'とc'は同オブジェクトを参照しなければならない。
アルゴリズムをtri-color abstractionを用いて考えると以下のようになる （注）。
GC開始時に、ルートオブジェクトから直接参照されるオブジェクト(図ではaのみ) をtospaceにコピーする。この時点でaは灰色と考えられる。 以降、GCは再帰探索のためにtospaceを指す2つのポインタを用いる。
オブジェクトoを白から灰色にする動作はoをtospace中のunscannedへの コピーすることあり、灰色から黒にする動作は、 oが直接参照するオブジェクトのコピー(灰色化) + o中のポインタ書き換え、である。
同じオブジェクトへの複数参照に対応するためには、fromspace中のdを 見ただけで、それがすでにコピー済みであり、コピー先はd'であることが 分かる必要がある。 そのために、灰色化の時点でdにforwarding tag (コピー済みであることを表す)、 forwarding pointer(コピー先を教えてくれる)を書き込んでおく。
Figure 5: Copying GCの動作。Fromspace中の到達可能なオブジェクトを
tospaceへコピーする。ただし正しくはfromspace中のオブジェクトa〜gも
すきまなく並んでいるはず
>
Copying GCの興味深い性質は、コピーするときにオブジェクトの空きを つめるため、fragmentationが発生しないということである。 よって手動freeを用いる場合(2章)や mark and sweep(6章)のような、フリーリストを 用いた複雑なallocationが必要ない。 代わりに、空き領域の先頭と、ヒープ境界を表すポインタを 管理しておけば充分である。
またオブジェクトの空きをつめるのは、GC以降のユーザプログラムの 局所性に良い影響を与える可能性がある。
演習コンパイラでは、「低コストなallocate」をインライン展開し (heapプリミティブ)、 さらにヒープ境界チェックをCPS関数の先頭にまとめて(live-reg疑似命令) 高速化を図っている。
ここでは主に実行時間に注目して、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)一度に行なうスイープよりも局所性の面で優れている、という利点がある。
さてこの状況でもう一度、定数mとcに注目しつつ、 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の方が有利と 考えられる（注）。
大ざっぱにまとめると、
まじめな比較ではないが、GC(話が簡単なcopying GC)と 明示的な(手動)freeを行なう場合の、効率の比較を行なってみる。
ここでは、メモリ解放のコストを、「解放のために費やした時間 / 解放した領域の大きさ」として定義して比較する。 手動freeの場合はこのコストはfreeにかかる時間であり、 簡単のために定数fとする。
Copying GCの場合は、c Lの時間をかけてM / 2 - Lの量を解放するので コストはとなる。
ここから、平均的にLが小さいユーザプログラムでは手動freeよりも GCの方が効率的に(停止時間でなくトータル実行時間が)なる場合があると言える。 Lが小さいというのは、大量にメモリオブジェクトが確保されても すぐに使い終り、生き残るものは少ないという状況である。 特に、SchemeやMLなどの関数型言語ではそういうプログラム はそれほど特別なものではない （注）。
メモリオブジェクトの寿命について、多くのプログラムで観測される ある傾向が知られている。それは「古くから生き残っているメモリオブジェクトは そのまま生き残りやすく、新しく確保されたメモリオブジェクトほど すぐにゴミになりやすい」という傾向である。 GCの実行効率は生き残るオブジェクトが少ないほどよいのだから、 古いオブジェクトはほうっておいて(無条件に生き残るとみなして) 新しいオブジェクトを重点的に探索することによって利益が得られそうである。
Generational GC （注） は、新しめのメモリオブジェクトのためのヒープと、 古めのメモリオブジェクトのためのヒープを別にとる。 図6のようになる。 Copying GCを基にする場合、新世代のヒープと旧世代のヒープの それぞれが2等分される。 オブジェクトはまず新世代ヒープに確保される。もしそれが長い間 (例えばGCがn回起こる間)生き残ったら、旧世代ヒープに移る(promote)。
メモリ不足が起こったら、ヒープ全体のGCを行なう代わりに、 新世代ヒープだけを対象としたGC(minor collection)を行なう。 その際に、旧世代のメモリオブジェクトは無条件に生き残るものとみなす。 具体的には、再帰探索で旧世代へのポインタが見つかったら 無視する。図ではオブジェクトb以降の探索は行なわない。 このため、大抵の場合はminor collectionは、ヒープ全体を探索するよりも 速く終了する。
Minor collectionだけでは充分にメモリ解放ができなくなったら はじめて、ヒープ全体を探索するGC(major collection)を 試みる。
Minor collectionにおいて注意が必要なのは旧→新のポインタである。 たとえばc→dのポインタに気付かないと、 到達可能なメモリオブジェクトdを間違って解放してしまう。 この図の場合、新世代へのポインタを持っているcとeは特別扱い され、ルートに加えられる。
さて、Schemeにおいて、ユーザプログラムがconsやvectorのみを用いる 限り、旧→新のポインタは決して生まれない。 Set-car!などの破壊的代入を行なって初めて生じるものである。 コンパイラが、破壊的代入の際に必ずGCに知らせる(書き換えられるオブジェクトを GCに教える)ようにすれば、GCが旧→新のポインタ全てを手早く見つける ことができる。 このように、メモリオブジェクトへの書き込みの際に特別な処理を 行なう機構をwrite barrierという （注）。
Generational GCによって良い効果が得られるプログラムは、 最初に述べた「新しいメモリオブジェクトほどすぐにゴミになりやすい」 という傾向が良く当てはまっている場合である。 こういう場合には、一度のGC時間が短くなりつつ、しかも解放できる メモリ量は単純なGCとあまり変わらないので、トータルな実行時間、 プログラムの停止時間の両方を改善できる。
Figure 6: Generational GCのヒープ。New generationのみを
探索する場合、c→d, e→fのポインタに注意する必要がある
Generational GCは単純なGCに比べれば、プログラムの停止時間を 短くすることができる。 しかしそれでも、その停止時間はGUIプログラムなどのリアルタイム性が 必要なプログラムにとっては長過ぎる場合があるし、そもそも major collectionが起こってしまえば単純なGCと同じくらい停止する。
Incremental GCはGC処理を細切れにしてユーザプログラムと 交互に動かすことによって、停止時間を短くするアプローチである。 交互で動かす単純な方法は、allocate処理を行なうときに、こっそり 少しづつGCの探索処理を行なうことである。
Incremental GCを実装するには、いくつか問題点をクリアしなければ ならない。
このような状況を防ぐためには、ユーザプログラムがオブジェクトを 書き換えたことをGCが知る必要がある。 流儀は大きく2つあって、
基本的には、incremental GCは停止時間を短くするのが目的であって、 GCの仕事の量を減らそうとするものではない （注）。このため、トータル 実行時間は短くはならないと考えられる。逆に仕事の切替えオーバヘッドや write barrierの分、遅くなるだろう。
Figure 7: Incremental GCの場合の時間とメモリ使用量の関係(イメージ図)。
GC処理を少しづつ進め、一通り終った時に始めて領域が解放される
Figure 8: Incremental GCにはwrite barrierが必要なことを示す図。
マークの途中で、ユーザプログラムがaからcのポインタを作り、
bからcへのポインタを消すと、そのままでは破綻する
これまで、GCは常にあらゆるメモリ内容の型(ポインタか否か)を 知ることができることを前提としていたが、C言語のように、実行時に 型が分からない環境でGCを行なう処理系も存在し、 Boehm GC[1]などが有名である。 これはC/C++プログラムから利用できるmark and sweep GCライブラリで、 このライブラリが提供するmalloc関数を呼ぶことによって GC機能を利用できる。
再帰探索中に見つけた値のポインタ判定をどうするかというと、 アイデアは簡単で、とりあえずポインタだと思ってみるという方針をとる (conservative GCと呼ばれる)。 そしてヒープ領域以外を指していたり、空き領域のはずの箇所を指している 場合は、明らかにポインタでないとして除外する。
もちろんこの方針を取る限り、ユーザプログラムがポインタのつもりで 使っていない値を、GCがポインタだと思ってしまう (false pointer)可能性は避けられない。 その場合でも、少しメモリ利用効率が落ちるだけで、プログラムの 続行にほぼ支障はない （注）。
MLの型推論を用いて、もっと違った方法で自動メモリ管理を 行なう処理系もある。
以下、GCに関連したWebページをいくつか:
〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
Last updated on 16 May, 1999
