1月 19th, 2011 admin 

2011/01/16の第11回GC本読書会で2010/04/18から全11回でやってきたGC本読書会(ガベージコレクションのアルゴリズムと実装読書会)が終了しました。
最後に自分の言葉でGCについて確認し、8ヶ月の読書会のまとめとしたいと思います。
GCとは
GC(Garbage Collection)とは、プログラム中で使わなくなったメモリ領域を見つけ、開放するプログラムである。
GCが組み込まれている言語
Java,Python,Ruby,Perlなど
逆にない言語はC、C++など
メリット、デメリット
メリットはGCがあることでプログラマがメモリの確保、開放に気を使わなくてよいことである
(メモリの確保、開放が適切に行なえないとメモリリーク、オブジェクトの二重開放、無効なポインタという問題が発生する可能性がある。)
デメリットは、ガベージコレクションの処理によって処理が遅くなることである。
主なGCの種類
GCはマークスイープGC、参照カウント、コピーGCの3つのアルゴリズムが基本である。
マークスイープGC
GCをマークフェーズとスイープフェーズという2段階で行なうGC.マークフェーズででは生きているオブジェクトにマークをつけ、スイープフェーズでオブジェクトを回収するというアルゴリズム。
実装が単純で保守的GCとの相性がよい、ただしフラグメンテーションが起こりやすかったりする。
参照カウント
あるオブジェクトが何個のほかのオブジェクトから参照されるかということをカウントしておき、カウントが0のオブジェクトを開放するというアルゴリズム。
マークフェーズが不要なのでゴミの回収時間が早いが、カウンタを増減処理が必要になる。
コピーGC
使えるメモリ領域を2つのFrom空間とTo空間にわけ、最初はFrom空間をつかい、From空間がいっぱいになったら生きているオブジェクトだけをTo空間に移動しFrom空間を削除。From空間とTo空間を入れかれるというアルゴリズム。
死んでいるオブジェクトの探索がない分高速でオブジェクトの移動の際にメモリ領域が整理(コンパクション)されるのでフラグメンテーションが生じないが、ヒープ領域を分割しなければならなかったり、保守的GCとの相性が悪かったりする
そのほかの代表的な手法
上記の3つの組み合わせになります
マークコンパクトGC
マークスイープGCにコンパクションを加えたもの
保守的GC
ポインタと非ポインタとを識別できないGCのこと。
GCはポインタなのか非ポインタ(数値等)なのかわからない場合にはポインタとみなし安全に処理する。その反対にすべてのポインタを把握しているのが正確なGCである。
世代別GC
「多くのオブジェクトは若くして死ぬ」し「長生きしているオブジェクトはこれからも長生きする」という経験を元に効率UPを図ったGC
インクリメンタルGC
GCを徐々に行なうことでGCによる1回の停止時間を短くしたGC
まとめ
・GCについて学んでも(残念なことに)僕はnariさんほどは目が輝かない
・GCは基本のアルゴリズムは3つだが、結局環境や言語に応じて最適化する必要がある
・しったかしてたGCについて少し自信がもてるようになった
・実装編は著者はどんだけソースコードを読んだんだよと感心した
・第4回のときは著者のnariさんをお呼びできて感激だった(有難う御座いました)
・参加者でmallocとかをしたことがない高レベルな人間が僕だけで大変だった
・PythonやAndroidなどプログラムしたこともない言語のGCについて詳しくなった
宣伝
CSNagoyaでは新しいテーマ「入門自然言語処理読書会 」と「組込みOS自作本読書会 」もやっていますので是非どうぞ。
くわしくはこちらをクリック