ガベージコレクション（GC）
tl;dr
ガベージコレクション（GC）についてサーベイしたので、メモを残す。
- 作者: 中村成洋,相川光,竹内郁雄
- 出版社/メーカー: 秀和システム
- 発売日: 2010/03/17
- メディア: 単行本
- 購入: 25人 クリック: 810回
- この商品を含むブログ (94件) を見る
本文中の多くの記述は、上記の書籍を参考にした。筆者は素人なので、詳細な記述や実装については参考文献を参照されたい。
Introduction
プログラムを書く上では、例えば入力長が分からない入力を受け取るためなどでメモリを動的に確保したい場合がある。その際ヒープ領域とよばれる領域にメモリを確保するが、使い終わった際には解放しなければ、確保しているが使われない領域が生じるメモリリークが発生してしまう。
しかし一般に、その解放を手動で管理することは面倒である。プログラマがどの時点で確保した領域が不要となるか、その全てのオブジェクトに対して追跡することは厄介である。そのために言語処理系やライブラリでメモリ解放の手間を肩代わりするような機能が実装されている。これがガベージコレクションである。
確保したメモリ領域を手動でfreeする場合に比べて、ガベコレのある言語を用いると実装が楽になる一方、GCが起きる条件を制御できず、また多くの実装で無視できない停止時間が存在するといった問題点はあるが、小さいオブジェクトが大量に死ぬような場合ではある種のGCのほうが有利であり、どちらを選択するのが良いかは時と場合による。
GCの評価基準
スループット（単位時間当たりの処理能力）とレイテンシ（要は最大で停止している時間）はトレードオフにあり、GCの種類によりどちらにより重きを置くかは変わる。またヒープの使用効率を向上させる（例えばコピーGCで、断片化を防ぐために生存しているオブジェクトをつめるような実装がある）ことが必要となる場合もある。
C, C++では
Cでは基本的にはGCはない。mallocしたヒープ領域は自分でfreeしなければならない。 C++でもnewした領域はdeleteしなければならないが、スマートポインタというものがあり、boostに実装されているほかC++11では以下のものがある。スマートポインタは、確保したメモリ空間を、スコープから外れたときに自動で開放してくれるポインタである。
- unique_ptr, shared_ptr, weak_ptr unique_ptrはメモリの所有権をそこに限定するもの。shared_ptrは所有権を参照カウンタによって管理し、共有することが可能である。
参照カウンタ
そのポインタを参照するごとにカウンタをインクリメントしていき、参照しなくなるとデクリメントする。カウンタが0になるとそのカウンタはどこからも参照されないということになり、安全に回収することができる。
このときの問題点として、循環的にオブジェクトを参照したいときにshared_ptrでは、その領域が解放されなくなってしまう。これを防ぐためにweak_ptrが用いられる。弱い参照と呼ばれるが、これは所有権を持たずにメモリを参照できるポインタである。例えば木構造で親子の双方向にポインタを持ちたい場合などに、これを用いることが可能である。
その他、利点として最大停止時間が短いこと、ポインタを走査するという手順が必要ないこと、逆に欠点としてカウンタの処理や実装が煩雑となることがあげられる。
- Boehm-GC
スマートポインタでなくともmallocのかわりの関数を呼ぶと、自動でfreeしてくれるGCは古くから提案されている。このときGCする対象となるオブジェクトを知りたいが、どのオブジェクトが参照されているかを知るためには、そのオブジェクトをさすポインタがあるかどうかで区別するしかない。しかしながら、入っている値が単なる数値なのかポインタなどのかは区別することができないので、全ての値をポインタと見なしてオブジェクトを辿り、辿れないオブジェクトをゴミとして回収する。このような仕組みで動くGCを保守的GCと呼ぶ。
従って、もしスタックに載った値がたまたまオブジェクトを指すポインタになってしまうような場合は、そのポインタの先がゴミであっても回収されず、データセットによっては大きいスペースリークが発生してしまうことが考えられる。32bitのマシンでは、このようなコリジョンが発生してしまうことは可能性としてそれほど低くないが、64bitのマシンでは場合にもよるが無視できるレベルだろう。
APGAS型の並列計算言語であるX10も、C++にトランスパイルした場合はこのGCによってヒープは管理される。
少し注意しなければならないというか、当たり前のことであるが、参照を外さないとGCで回収されない。逆に言えば参照が外れてしまうとGCで回収されてしまう可能性がある。例えば双方向連結リストでメモリ空間を節約するために、左右のポインタのxorを持っておくという方法があるが、そのような方法で管理しているポインタはこうしたGCでは辿ることができないので、オブジェクトが破棄されてしまうおそれがある。
Haskell
コピーGCをベースに、Cheneyのアルゴリズムや世代別GCを取り入れている。以下のスライドをもとに詳説を試みる。
https://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf
Haskellでは、RTS（Runtime-System）がネイティブスレッドやGCについて司る。
コピーGC
生きているオブジェクトを別領域に全てコピーし、もとの領域を全て解放するようなGC。
- Stop the World
- 実行系は全て停まってガベコレのスレッドだけが動く
コピーGCはゴミを捨てるのにほとんどコストがかからないために生きているオブジェクトが少ないほど有利であり、また別領域に詰め込むことでヒープのフラグメンテーションが起きないことが利点である。そして、GCの途中で参照関係にあるオブジェクトが近接するようになるので、GCに有利である。
デメリットとしては、ヒープ領域の使用効率が悪化すること、保守的GCとの相性が悪いことがある。これは、コピーGCでヒープの値のアドレスが変わってしまうと、それをさすアドレスも書き換えなければならないが、保守的GCをしたいような場合には、スタックなどに積まれている値がアドレスであるか値であるか分からないため、書き換えられるか分からないということがあるためである。
世代別GC
少しの長生きしたオブジェクトは長生きするが、残りのオブジェクトは量が多く、すぐ破棄されるという経験的な性質をもとに、アロケートされたオブジェクトは第一世代に属し、Haskellの場合では生きているオブジェクトが少ないときに有利なコピーGCで回収し、ある程度長生きしたオブジェクトは第二世代に移行し、一般にはそこでは回収しないか、低頻度でコピーGCやMark & Sweepで回収するという仕組みである。
これを組み合わせ世代別コピーGCは、JVMの実装でもみられるが、全く書き換えられないオブジェクトが何度もコピーされるのを防ぐことができる。ここでは高頻度でガベコレされる領域Nurseryと、長生きする領域Generation0, step1とGeneration1を分ける。Nurseryは高頻度にガベコレされる（Minor GC）が、一定以上長生きしたオブジェクトはstep1に移行し、Generation1へと昇格し、それほど高頻度にガベコレされなくなる（Major GC）。
ところで、JVMでもこうしたフィーチャーは実装されているが、Javaのような言語ではthisがあるせいで、Generation1に相当するオブジェクトがNurseryへのポインタを持つことがしばしば起こる。このとき、Nurseryを注意深くガベコレしなければSeg4が起こるため、Nurseryの高速なガベコレを妨げる。これに対してHaskellではmutationがrareであること、またIORefで触るような場合はどのみち遅いことから、一般の場合でそれによるオーバーヘッドはそれほど大きくならない。
また更にmajor GCにおいてはParallel GCが可能である。これはGCのスレッドが複数あり、そのそれぞれがコピーGCを行うが、複数のスレッドが同じオブジェクトをコピーしようとすることがある。しかしそうであったととしても、immutableな小さいオブジェクトであるならば複数コピーされることによるオーバーヘッドはそれほど大きくないため、ロックせずにガベコレを並列で走らせることができる。これで純粋関数であることで柔軟さを得ることが可能となる。
このように、ハイスループットなGCをHaskellのRTSでは実現している。
Go
Go1.5〜でのGCはレイテンシの短縮にフォーカスしている。
Mark & Sweep
- Mark
- ポインタを辿り、オブジェクトにマークする
- Sweep
- マークが付けられていないオブジェクトは捨てて良い
しかしこの場合、GC実行中にプログラムが動作してポイントの様態が変化してしまうと、本来捨てるべきでない領域をSweepしてしまうかもしれない。こういった問題を防ぐために、一般にはSTWで実行系は全て停まってガベコレのスレッドだけが動くようにしている。しかし当然、STWの間は実行系が動けず、そのレイテンシはヒープ使用量が大きいほど増大することが見込まれる。
また一般に、Mark & Sweepの特性として、以下のものがある。
- 保守的GCとの相性が良い
- CopyGCに比べて、フラグメンテーションが起きやすい。また開放されたメモリ空間も非連続になりがち。
Go1.5〜では、Tri-color markingとよばれるオブジェクトを3分類し、コンカレントGCでほとんどSTWを起こさずにGCすることが可能となっている。これはインクリメンタルGCの一種である。
Rust
Rustでは生存時間が型レベルで管理されており、生ポインタを触ることは一般に忌避される。そこで何らかの型でラッピングしてポインタにアクセスする必要がある。
Rustではヒープ領域を確保する方法はBox, Rc, Arcがある。Boxはunique_ptrに対応するようなもの、Rc、Arcはshared_ptrに対応するようなものだと認識している。例えば再帰的データ構造を定義する際、Haskellではそれが参照であることを明示する必要はないが、RustではBoxで明示的にヒープを確保していることを示す必要がある。またRcとArcの違いは、それがスレッド間で共有されるかどうかという点である。
ところが、BoxやRcで指す先の値をmutableにしたいという要請がある。これを一般化するとimmutableなオブジェクトの内部に、mutableなオブジェクトを持つ要請であり、こうした要請に対してRefCell、Cellが用いられる。Cellは単純な型ぐらいに対してしか使えないので、参照型を持つ場合ではRefCellを使うことが多く、Rcと組み合わせてRc<RefCell<T>>のようになる。更に更に、スレッド間でmutableなオブジェクトを共有したい場合はMutexを用い、Arcと組み合わせてArc<Mutex<T>>のようになる。
困ること
ところで、こうした参照カウント方式ではDAGならともかく、循環リストや双方向連結リストのようなグラフ構造を持つことができない。
これに対してTyped Arenaという方法があるが、領域を開放するためのインターフェースとして実装されているのは、全て捨てるということしかできない。つまり参照しなくなったオブジェクトがArena内にあったとしてもそれをガベコレすることができない。参照しなくなる要素が増える場合、メモリリークが大量に発生することになってしまう。
これに対応する方法としては2つであり、1つはfreeListを作り、そこに削除した要素を登録し、次にnewする際にその要素を用いるようにする。ただしその場合は削除した要素が飛び飛びになっている場合、近接して確保したい領域が離れて確保される懸念がある。もう1つの方法としてはある程度使われない要素が増えた時にもう1つArena領域を取り、参照されている要素を走査し詰め込んだ後、元のArenaを全て捨てるというさながらコピーGCのような実装をするかである。
どちらにしてもTyped ArenaはArena内部に持つ要素の型と生存時間が管理されることは利点であるが、参照しなくなった領域に対するメモリリークに対する解決策ではないように思われる。
その他調べたこと
- RubyはMRubyではマーク＆スイープ、Ruby2.1からは世代別GCを取り入れている。
- Pythonは参照カウントで管理。循環参照GCは世代別GCで管理している。
- JavascriptのV8は世代別GCで、マイナーGCはコピーGC、メジャーGCはマーク＆スイープGC。
まとめ
きわめておおざっぱな分類は以下。
| 言語 | 種類 | 特徴 | 詳細 |
|---|---|---|---|
| C | 基本的にはなし | Malloc, freeで管理 | |
| C++11 | 参照カウンタ | unique_ptr, shared_ptr, weak | |
| C,C++(Boehm-GC) | Mark & Sweep | 保守的GC,STW | ライブラリを導入 |
| X10 | Mark & Sweep | 保守的GC,STW | C++にトランスパイルするとBoehmGCが使われる |
| Haskell | コピーGC | STW | Cheneyのアルゴリズム＋世代別GCなど |
| Go1.4 | Mark & Sweep | parallel STW | |
| Go1.5〜 | Mark & Sweep | Concurrent/Incremental | |
| Rust | 参照カウンタ | 生存時間で管理 | Rc, Arc, Arena |
参考
www.slideshare.net
http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf
