カスタマーレビュー

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

星5つ:		(2)
星4つ:		(1)
星3つ:		(0)
星2つ:		(1)
星1つ:		(0)

 

 

Garbage Collection (GC) は、Javaなどのインタープリターにおけるメモリ管理以外にも、ファイルシステムのデフラグや LogStructured File System の本質の部分(ZFSやWAFLなどの派生ファイルシステムも含む)、DBMSのコンパクション処理など、そのアルゴリズムはものすごく広範に応用されている。また、まだまだ応用出来るジャンルは沢山ある。しかし、英語と日本語の資料に関する限り、ある程度網羅的で入門的な本は、1996年に出た Garbage Collection: Algorithms for Automatic Dynamic Memory Management だけ。しかも翻訳されていない。

この本は、GCに関する日本語初の入門書。基本になるアルゴリズムが、網羅的に説明されていて非常によい。もし、GCの基礎が知りたければこの一冊があればよい。アルゴリズムはそれぞれ多くの図で説明されており、動作は非常に追いやすい。

大きな問題点はひとつだけ(これを問題点と言うかどうかは異論があろうが)。
Compaction が GC の一部とみなされており、独立した章を与えられていないのが残念でならない。Table of Contents を経由させることで、Garbage Collection を実装しなくても Compaction は実装する事ができる。そして Compaction の実施はキャッシュヒット率に大きな影響を与えるのだ。Compaction は独立させられるだけの内容を持っている。Compaction大好きな私としてはここが大いに不満だ。

小さな問題点はいくつもある。擬似コードに結構小さなバグが… p.44 List.3 line.4 *ptr=objは ptr=&obj じゃなかろうかとか…(なので擬似コードのシンタックスそのものが不足してないか?)
インデンテーションを python 風にしているのもいただけない。長めのコードになると、どことどこの高さが一致しているのか、ガイド線無しに判別するのが難しい。
しかし、そんなものは些細なことだ。擬似コードなんか読まなくてもわかるし ;p

というわけで大お勧め。
次は是非、RealTime GC など「微に入り細に入った」もうどう考えてもマニア中のマニアしか読まねーだろうがそれは、的な解説書を書いて欲しい。日本にはそういう技術的な解説書がマジで不足しているんだ。

ガベージコレクタに焦点を当てた本という時点で、十分貴重な本ではありますが、読み進めていくうちにメモリアロケータの総括本も出して欲しいと感じました。
著者のGC好きは凄く伝わってくるものがあり、好感が持てますし、それだけに読み進めるのも楽しめ、資料として後から読み返す価値も感じます。

本書では、他の方も指摘されているよう、純粋なガベージコレクトのみならず、コンパクションにも言及されています。
ガベージコレクトを志す方の多くが、コンパクションに興味を持たれるのは必然だと思いますし、ある意味セットであるとも言えます。

ただ、もっと遡って言及すると、ガベージコレクトの必要性、コンパクションの必要性は、アドレスの連続性、固定性に繋がる部分であり、
そこからrealloc(恐らく最初に出るのは積極的に再配置を行うべきかどうかの議題)、そしてさらにmallocへと話題が繋がって行く、
非常に奥深い話題が眠っているはずで、さらなる挑戦としてメモリアロケータを総括した考察、そしてその結果を出版してくれたら、
GC好きやallocator好きの行き過ぎな好事家が(きっと沢山います)必ず評価してくれると思います。

アルゴリズムに関する部分は理解しやすく、綺麗にまとめられていて良かったです。 実装に関する部分は自分にとっては難しかったですが、実際に実装する際にどのような工夫がされているのかがわかり、勉強になりました。

私は言語処理の実装に興味があり、メモリ管理の技術要素として重要なガベージコレクションの入門書として本書を購入しました。 前半ではガベージコレクションの基本的なアルゴリズムについて述べ、後半では CPython (Python 処理系) や Dalvik VM (Android の Java 仮想マシン)、Rubinius (Ruby 処理系)、そして V8 (JavaScript エンジン) を取り上げ、これらの処理系の中でどのようにガベージコレクションが実装されているかが述べられています。

前半のアルゴリズムの部分は、図が多く使われていることもあり、ガベージコレクションに興味をもつような人にとっては苦もなく読み進められると思います。 他のレビューに書かれているようにサンプルコードに問題がありますが、サンプルコードを読まずとも内容はすぐに理解できますので、特に問題はないでしょう。 ガベージコレクションについて綺麗にまとめられていて読みやすかったです。
後半の実装に関する部分は、実際のコードを追いながら理解して読み進めていくのがなかなか難しかったです。 ガベージコレクションの理論だけ知りたい、という人は実装に関する部分は読まなくてもいいかと思います。 ただ、実際に実装するにあたってどのような工夫がなされているのか、ということを知ることができ、勉強にはなると思います。

ガベージコレクションに興味がある、という人におすすめの 1 冊です。
(おすすめもなにもこれ以外の選択肢はないようですが...)

先にも書かれている通り、擬似コードにバグがちらほら
擬似コードを真面目に理解して読み進めようとすると変な所で躓くので擬似コードはバグありのコードとして見て真面目に読まない方が良いかも