ガベージコレクションのアルゴリズムと実装
なぜ読む
大学時代に研究してたわけでもなくGCについての知識がほぼないので単純に知りたかった
どんな本
お馴染みのマークスイープGCからV8などでも使われている世代別GCなど主要なGCをその手法とメリット/デメリット、さらに発展させた改良版に分けて解説してくれる。これがアルゴリズム編。後半はPython/DalvikVM/Rubinis/V8の(当時の)GCを実際のコードを交えて解説してくれている。これが実装編。大きく分けてこの2編で構成されている。
学部レベル1,2年程度のC言語/低レイヤーのアーキテクチャに関する知識があればGCについて何もわからなくても読み進められる
感想
GCはいくつもの手法がありそれぞれにメリットとデメリットがある。各種GCのデメリットを補うための発展系のGC手法はあるがそれもまた別のメリットを犠牲にすることとなる。よってGCもACID特性のように全ての要件を満たすような銀の弾丸がない。だからこそトレードオフを考慮していくつかのGCを特定の場所で使い分けながら採用されている。GC、泥臭くて深い...。
John McCarthy、Marvin L. Minsky、Dijkstraなどコンピューターサイエンスの歴史に名を刻む人物が続々登場するのでGCの深さを感じた(GC誕生からもう60年なのでそれはそう...)
メモ
通常の仮想記憶が空間方向にメモリを拡大する技術ならば、GCは時間方向にメモリを拡大する仮想記憶の一種 by 竹内郁雄 レビュアーたちがふざけてて序文から結構面白いw 昔の空気感を持ったギークたちだ。
アルゴリズム編と実装編に分かれている
GCの歴史めっちゃ古い。1960年にJohn McCarthy(Lispの父)によって発表された。
GC色々
マークスイープGC(John McCarthy)
参照カウンタ
コピーGC(Marvin L. Minsky: 人工知能の父)
等々
万能なGCはない、全て時と場合による。トレードオフ。
GC = ヒープ領域に配置されたオブジェクトの管理を行う仕組み
GCの評価指標
スループット: HEAP_SIZE / GCにかかる時間。この値が大きい方が性能が良い。
最大停止時間: 各GC時に停止する時間の中の最大値
ヒープ領域の使用効率
参照の局所性
ルート
レジスタ/コールスタック/グローバル変数
ミューテータ
状態を変更させるやつ。アプリケーションとかいわゆる使う側のあれ。
マークフェーズ: 全ての生きているオブジェクトに対して再帰的にマークする。O(N)。
スイープフェーズ: ヒープを全てスキャン。マークフェーズでマークがつけられなかったオブジェクトはフリーリスト(後ほど空いてる領域のチャンクリスト)に加える。チャンクの合体もこのフェーズでやる。O(N)。
アロケーション: フリーリストから欲しいサイズ以上のチャンクをみつけて割り当てる
メリット: 実装がシンプル
デメリット: フラグメンテーションが発生しやすい
参照カウント
オブジェクトへの参照カウンタを持つようにする。生きているオブジェクトはchunkメモリ確保時に+1される。
ポインタ更新時に参照カウンタの値が0ならゴミと見做して処理する。マークスイープGCのようにスイープフェーズを専用で設けない。
メリット: ゴミになったら(参照カウンタが0になったら)すぐ回収される / 最大実行時間が短い / ポインタを辿るフェーズがないs
デメリット: ポインタの値の更新が頻発する(この処理が結構重い) / カウンタ用に多くのビット(メモリ)が必要になる / 循環参照がごみにできない
1ビットでカウンタ足りなくない?とおもったが「ほとんどのオブジェクトは共有されることはなくすぐ回収可能」という観測結果から1ビットを参照数が1つか複数かの判別だけに使う。ヒューリスティックで頭いい。
コピーGC
生きてるオブジェクトを別の領域にコピーして、残りを全部削除しちゃう大胆なやつ
メリット: 速い / フリーのchunkを返すのが速い(フリーリストを使わないので) / フラグメンテーションが起きない(startとendをガバッとやるため) / キャッシュ効率が良い(ガバッと領域に展開されるのでアドレスが近い)
デメリット: ヒープの使用効率が悪い(実質半分しか使えないので) / 再帰関数呼び出し / 保守的GC(使用中っぽいオブジェクトは無理に回収しないやつ)と相性悪い
複数空間GC: 2等分じゃなくてもっと細かい領域に分けてコピーGCをするやつ。2等分よりも効率が良い。これもマークスイープGCを組み合わせる。困ったらマークスイープGCみたいなところがあるな...
マークコンパクト
マークスイープGCとコピーGCの組み合わせ。コピーGCで発生してたヒープを半分しか使えない問題が解決されてるのでヒープの利用効率が上がってる。ただしそれを実現するためのコンパクションのフェーズにヒープの走査が何回か走るので重い。
保守的GC <=> 正確なGC
不明瞭なルート(レジスタ/コールスタック/グローバル変数ではintやdoubleのような非ポインタとvoid*のようなポインタが混在してる
保守的GCでは不明瞭なルートをチェックしてある程度の精度でポインタを識別する
非ポインタがたまたまポインタっぽい値と同じだと間違ってGCされちゃうとかその逆も困る
保守的GCはこういう生きてるか怪しいオブジェクトはポインタだと見做して安全に処理するという手法
世代別GC
オブジェクトに世代の概念を導入。ごみになりやすいオブジェクトを旧世代・新世代と分け、新世代を優先的にGCする。旧世代は新世代よりGCの回数を減らす。
ライトバリア
ミューテーターとGCの切り替えタイミングなどに起因して本来灰色や黒に塗られなければいけなかった生きているオブジェクトが白色のままになってしまいゴミとしてスイープされてしまう可能性がある。
ライトバリアはこれを防ぐために新たに参照されるオブジェクトが白色であればすぐ灰色に変えちゃう仕組み
しかしライトバリアはオーバーヘッドがデカくてスループットの低下を引き起こす
メリット: スループットが改善
デメリット: マイナーGC or メジャーGCに偏りがあると逆効果
インクリメンタルGC
少しずつGCを進める手法
3色マーキング(Tri-color marking。作者ダイクストラだ...)
未探索のオブジェクト・ルートから辿れるオブジェクト・マーク済みのオブジェクトの3つに分ける
ライトバリア
メリット: GC実行中にミューテータが完全にストップしてしまう停止型GCに対してインクリメンタルGCだと最大停止時間を小さくできる
デメリット: オーバーヘッドがでかいのでスループットが低い
Rubinius(RubyでのRuby実装)のGCだけ気になるのでちゃんと見るか。基本世代別GCでマイナーGCがコピーGC、メジャーGCにマークスイープGCとImmixGC(マークコンパクトGC)を使った正確なGC。
関連リソース