書評「ガベージコレクションのアルゴリズムと実装」
無限ではないメモリを有効に活用するために、メモリの開放を自動的にやってくれるガベージコレクション。これがなければ、どれだけメモリ不足のエラーが出てたでしょう。まさに縁の下の力持ち。そんなガベージコレクションに特化して書かれた、ちょっとめずらしい本です。
内容
アルゴリズム編
アルゴリズム編ではガベージコレクションについての基本的なアルゴリズムについて解説してくれます。それぞれのアルゴリズムは単独で使うのみでなく、組み合わせて使用するものもあります。
書籍では疑似コードを使っての説明になっています。Cのポインタのイメージが分からないと、ちょっとつらいかなと思います。
マークスイープGC
マークとスイープの2つのフェーズからなります。マークで生きているオブジェクトにフラグをつけ、スイープで使われてないオブジェクトを回収します。実装が容易ですが、フラグメンテーションが発生する等のデメリットが述べられています。
デメリットへの対応として、複数フリーリスト・BiBOP法・ビットマップマーキング・遅延スイープ法が紹介されています。
参照カウント
オブジェクトへの参照の数を管理して、誰からも参照されなくなったらメモリを解放する方法です。最大停止時間が短くなるのがメリットですが、カウンタの操作が必要等のデメリットが述べられています。
デメリットへの対応として、遅延参照カウント・Sticky参照カウント・マークスイープとの併用・1ビット参照カウント・部分マークスイープ法が紹介されています。
コピーGC
メモリ空間を分割し、生きているオブジェクトを全て別の空間にコピーした後、古い空間はバッサリと解放するアルゴリズムです。フラグメンテーションが発生しませんが、メモリの使用効率が悪い等のデメリットが述べられています。
デメリットへの対応として、CheneyのコピーGC、近似的深さ優先探索法・複数空間コピー法が紹介されています。
マークコンパクトGC
マークとコンパクトの2つのフェーズからなります。マークスイープGCとコピーGCを合わせたような手法です。メモリを有効に利用できますが、計算コストがかかる等のデメリットが述べられています。
デメリットへの対応として、Two-Fingerアルゴリズム・テーブルアルゴリズム・ImmixGCが紹介されています。
保守的GC
オブジェクトを正確に追跡できるか否かという観点で、GCを「保守的GC」と「正確なGC」に分類しての説明です。
MostlyCopyingGC・ブラックリストが紹介されています。
世代別GC
オブジェクトに新世代、旧世代といった「年齢」の概念を導入する考え方です。ライトバリア・メジャーGC・マイナーGCといった言葉が出てきます。スループットは改善されますが、プログラムによっては逆効果といったデメリットが述べられています。
カードマーキング・ページマーキング・複数世代管理GC・トレインGCが紹介されています。
インクリメンタルGC
少しずつGCを進めて、最大停止時間を短くする手法です。最大停止時間は短くなりますが、スループットが低下するなどのデメリットが述べられています。
Steeleのアルゴリズム・湯淺のアルゴリズムが紹介されています。
実装編
実装編では4つの環境について、実際のソースコードを追いかけながら解説してくれます。
Python
Python3.0.1のソースコードを使っての解説です。Pythonは参照カウントを採用し、アリーナ・プール・ブロックという単位でメモリを管理しているそうです。
DalvikVM
Androidに搭載されているDalvikVMのガベージコレクションについての解説です。Androidのアーキテクチャの説明から入ります。DalvikVMはマークスイープGCを採用しているそうです。
Rubinius
RubyでRubyを実装するRubiniusのガベージコレクションについての解説です。世代別GC（マイナー：コピーGC、メジャー：マークスイープGC・ImmixGC）を採用しているそうです。また「正確なGC」とのこと。
V8
GoogleのJavascriptエンジン、V8のガベージコレクションについての説明です。世代別GC（マイナー：コピーGC、メジャー：マークスイープGC・マークコンパクトGC）を採用していて、Rubiniusと同じく「正確なGC」だそうです。
感想
本書の監修者によると、ガベージコレクションについて書かれた本は、Lispに実装されてから37年後の1996年に出版された「Garbage Collection」という本が初めてだそうです。そして日本では本書が初めての本。かなり少ないですね。
読んでいて一番思ったのは「一長一短」。どのアルゴリズムもまさに一長一短で、完璧なものがない！あっちを取ればこっちが立たず。いや、ほんと焦ったい感じでした。各言語とも若干オリジナルなやり方の部分もありますが、基本的なアルゴリズムは確立されている印象でした。
そしてパフォーマンスの追求。CPUもかなり早くなったはずなのに、裏ではパフォーマンスのためにこんな苦労をしていたのかと驚きです。
いずれメモリの解放が不要になる程、メモリ量が豊富になる時代が来るのか、楽しみです。
