ak備忘録

レガシーブログ

ガベージコレクションのアルゴリズム

こんばんは。
GW初日ですが今日は家に引きこもっていました。
普段やってない掃除とか、ちょっと模様替えとかしてなんかスッキリしていますw

ガベージコレクションの話。
この本を読みました。

ガベージコレクションのアルゴリズムと実装

ガベージコレクションのアルゴリズムと実装

日本語で書かれた最初のガベージコレクション本だそうです。
全部読んだわけではありませんが、大枠をパラパラと幅探索のごとく読みました。

最近よく思うのはアルゴリズムの勉強は不変なモノだなぁと思います。

使用する言語は時代の流れでどんどん変わっていきます。
なのでいくら勉強しても「これで終わり」ということはありません。
常に最新の言語なりSDKなりを勉強しなければいけません。

ただ、アルゴリズムの勉強は言語が変わっても通用します。
そういう意味では一生モノなのではないでしょうか。

というのを、先日空間分割のアルゴリズムを勉強していて思いました。

というわけで、話が戻りますがガベージコレクションについて勉強しました。
とはいえ、ガベージコレクションを作るぞ!というわけではなく、
どんな仕組みで動いているのかというアルゴリズム的な部分を
ちゃんと知っておきたかったというのが主な動機です。

(この本を読んだキッカケはジュンク堂でダラダラと本を漁っていたときに、
 なんか面白そうだったからですが)

以下、ホントに簡単にまとめです。
とても簡単に書いているので、詳しくは本を参照ください。

●マークスイープGC
マークフェーズ(生きている領域にチェックを入れる)と
スイープフェーズ(マークのついているものを有効なものとしてヒープ整理)
により行うガベージコレクション

複数フリーリスト(空き領域)
フリーリストのルートを複数持つことで、もっとも適した空き領域を効率的に探す。
(正直これが一番「あ、その手があったか」と思いました汗)

●参照カウント
自分自身が参照されている数を保持し、0になったら自動的に解放する。
循環参照は解放できないのが弱点。

●コピーGC
ヒープ領域を半分にして2つに分けたメモリ領域を使う。
GCを行うときに生きているメモリのみ、2つのうちもう片方のメモリにコピー。
GCが行われるたびに使用するメモリ領域を切り替える。
コンパクションが自動的に行われ、フラグメンテーションがおきない。
ただし、メモリ領域が半分しか使えないのとコピーコストが発生する。

●マークコンパクトGC
ベースはマークスイープGCで、コンパクション機能を有しているという違いだけ。
なんとか効率的に前に詰めようと頑張る。

●世代別GC
若いやつほど早く死ぬがモットー。
GCが行われるたびに生きているメモリが1歳年をとり、
ある程度年をとったら管理方法が変わる方式。
世代別GCの考えはこれだけで、
若いときと年をとったときのGCに何を使うかは自由。
若い時:コピーGC
老けたとき:マークコンパクトGC
がよくある構成っぽい。

●インクリメンタルGC
GCを数回に分けて実行できるようにするGC
GCに時間がかかりそのフレームだけガクッと処理落ちするのを避けたい場合に向く。


アルゴリズムではないが、GCにはベースとなる考えに
保守的GCと、正確なGCの2種類がある。

GCはスタックやグローバル領域などがルートとなり、
そこからヒープ領域をたどっていく。

この部分が最初何を言っているのかさっぱり分からなかったが、
ようはスタック領域やグローバル領域をガチで見る。
ポインタを使ってガチで解析する。

例えば、

void func()
{
	int a = 0;
	int* b = new int;
	・・処理・・
}

この場合は、aは非ポインタで、bはポインタである。
これはスタック領域にメモリが存在するが、このスタック領域をガチで解析する。

そして、bはポインタだということを突き止める。
そのbがさしている先が管理しているヒープ領域である場合、
GCを執行するという具合である。
(・・・と、しばらく考えて自分で納得しました。違っていたらご指摘ください!)

しかし、非ポインタとポインタを見分けるのは単純ではない。
というわけで、保守的GCと正確なGCに戻ると、

●保守的GC
非ポインタとポインタをある程度の条件を付けて分別する。
ポインタの疑いがちょっとでもある場合はポインタとみなす。安全策をとる。
ただし、ヘタをすると大きなメモリが解放されないままになる可能性もなくはない。

●正確なGC
非ポインタとポインタを確実に分別する。
非ポインタを1ビット左シフトし、最初の1ビット目をフラグとして使用するなど。
処理コストが大きい。

というわけで、アルゴリズムはよく分かったので満足しました。
にしてもGCは作りたいか、と言われたら作りたくないなぁ。

僕としてはshared_ptr最高なのです。(←結論)
※参照カウント方式のGC