Every Byte is Sacred - 書評 - ガベージコレクションのアルゴリズムと実装

著者より献本御礼。

ガベージコレクションの
アルゴリズムと実装
中村成洋 / 相川光 / 竹内郁雄監

これほど地味かつ即実務に役立たない、しかし確実にプログラマーの滋養になる本が出版される日本の出版界に乾杯!世界で二番目(著者調べ)、国内で初のGC本は、実に滋味豊かだ。

とはいえ、本書はこの話題に関してMECEというわけでもない。というわけで本entryでは本書に何が書いていないかを主に紹介していく。何が書いてあるかは本書で確認すればよいのだから。

本書「ガベージコレクションのアルゴリズムと実装」は、コンピューターの資源管理の技術の一つ、ガベージコレクション(以下GC)についてまるまる一冊を費やして考察した本。

目次 - 「ガベージコレクションのアルゴリズムと実装」という本を書きました。 - I am Cruby!より

監修者まえがき はじめに 謝辞 序章 GCとは GCの恩恵 GCの歴史 なぜ今GCなのか 読者対象 本書の表記 アルゴリズム編 第1章 GCを学ぶ前に 1.1 オブジェクト/ヘッダ/フィールド 1.2 ポインタ 1.3 ミューテータ 1.4 ヒープ領域 1.5 生きている/死んでいるオブジェクト 1.6 アロケーション 1.7 チャンク 1.8 ルート 1.9 評価項目 第2章 マークスイープGC（Mark Sweep GC） 2.1 マークスイープGCとは 2.2 メリット 2.3 デメリット 2.4 複数フリーリスト（Multiple free-list） 2.5 BiBOP法（Big Bag Of Pages） 2.6 ビットマップマーキング（Bitmap Marking） 2.7 遅延スイープ法（Lazy Sweep） 第3章 参照カウント（Reference Counting） 3.1 参照カウントのアルゴリズム 3.2 メリット 3.3 デメリット 3.4 遅延参照カウント法（Deferred Reference Counting） 3.5 Sticky参照カウント法 3.6 1ビット参照カウント（1bit Reference Counting） 3.7 部分マークスイープ法（Partial Mark & Sweep） 第4章 コピーGC（Copying GC） 4.1 コピーGCとは 4.2 メリット 4.3 デメリット 4.4 CheneyのコピーGC 4.5 近似的深さ優先探索法 4.6 複数空間コピー法 第5章 マークコンパクトGC（Mark Compact GC） 5.1 マークコンパクトGCとは 5.2 メリット 5.3 デメリット 5.4 Two-Fingerアルゴリズム 5.5 テーブルアルゴリズム 5.6 ImmixGC 第6章 保守的GC（Conservative GC） 6.1 保守的GCとは 6.2 メリット 6.3 デメリット 6.4 正確なGC（Exact GC） 6.5 間接参照 6.6 MostlyCopyingGC 6.7 ブラックリスト 第7章 世代別GC（Generational GC） 7.1 世代別GCとは 7.2 Ungarの世代別GC 7.3 メリット 7.4 デメリット 7.5 世代間の参照を記録する方法 7.6 複数世代管理GC（Multi-generational GC） 7.7 トレインGC（Train GC） 第8章 インクリメンタルGC（Incremental GC） 8.1 インクリメンタルGCとは 8.2 メリット・デメリット 8.3 Steele のアルゴリズム 8.4 湯淺のアルゴリズム 8.5 各ライトバリアの比較

実装編 第9章 PythonのGC 9.1 はじめに 9.2 オブジェクト管理 9.3 Python のメモリアロケータ 9.4 第0層汎用的な基礎アロケータ 9.5 第1層Python低レベルメモリアロケータ 9.6 第2層Pythonオブジェクトアロケータ 9.7 第3層オブジェクト特有アロケータ 9.8 参照カウント 9.9 参照の所有権 9.10 循環参照をもつゴミオブジェクトへの対応 9.11 パフォーマンスチューニングのヒント 第10章 DalvikVMのGC 10.1 はじめに 10.2 mmap再入門 10.3 DalvikVMのソースコード 10.4 DalvikVMのGCアルゴリズム 10.5 オブジェクト管理 10.6 マークフェーズ 10.7 スイープフェーズ 10.8 Q&A 第11章 RubiniusのGC 11.1 はじめに 11.2 RubiniusのGCアルゴリズム 11.3 オブジェクト管理 11.4 正確なGCへの道 11.5 コピーGC 11.6 Q&A 第12章 V8のGC 12.1 はじめに 12.2 V8のGCアルゴリズム 12.3 オブジェクト管理 12.4 正確なGCへの道（V8 編） 12.5 マークコンパクトGC 12.6 マークフェーズ 12.7 コンパクションフェーズ 12.8 Q&A 補遺 補遺A 簡単言語入門： Python編 補遺B 簡単言語入門： Java編 補遺C 簡単言語入門： Ruby編 補遺D 簡単言語入門： JavaScript編 補遺E 参考文献 本書のレビューを終えて あとがき 索引

「技術の一つ」とあえて書いた。別の言い方をすると、それ以外の資源管理法に関しては本書に書かれていないということになる。本書の性格を考慮すれば書く必要はないのだけど、それでも序章で紹介はしておいて欲しかったところ。

たとえば、スタック。あらかじめ使用する資源量がわかっていれば、実は全てスタックにのせてしまえばGCは不要である。そうしたプログラムは少なくなく、C言語の初心者本のサンプルはたいていそういうプログラムである。別の言い方をすれば、malloc()を使わずに済むプログラムにGCはいらない。

しかし実際のプログラミングにおいて、このやり方は無駄が多い。なぜならプログラマーは考えうる最大の資源を確保せざるを得ないからだ。実際に使う時にはたとえ1Byteで済む場合でも、1MBになる可能性があれば、問答無用で1MBをあらかじめ用意しておかなければならない。

The C Programmming Lanugage
K&R

これを防ぐには、必要な時に、必要なだけ、動的に資源を確保すればよい。それがmalloc()だ。これをどうやるのかは、実は本を一冊書けるネタでもあるのだが、簡単な実装例であればK&Rにも載っている。

そして使った後は、free()で返す…のだが、この返し忘れによるバグが後を経たない。資源のポイ捨ては地球にもコンピューターにもやさしくないので慎むべきではあるが、しかし環境の方でよきに計らってくれたら楽なのに。

その願いをかなえてくれるのが、

オビ by まつもとゆきひろ

古からの魔法ガベージコレクション

というわけだ。ずいぶん長い前置きになってしまったが、序章でここまでは書いておいて欲しかったというのが正直な感想だ。その代わりというわけではないが、「初めての人のためのLISP」の著者でもある監修者が、すばらしい序文を寄せている

実は、GCは仮想記憶なのです。通常の仮想記憶は、実メモリは大きくないのに、それを二次記憶を使って「仮想的に」アドレス空間一杯あるかのごとく見せる技術です。つまり、空間方向にメモリを拡大する技術なので、私はこれを空間的仮想記憶と呼んでいます。とするとGCは使い捨てメモリを永久に与え続けてくれる時間軸方向の、時間的仮想記憶ということになります。

本書が扱っているのは、その時間的仮想記憶が実際にどうなっているか、である。

やり方はいくつもある。そしてそれぞれに一長一短がある。Mark & Sweep は確実だが遅い。参照カウンターは速いが循環参照を回収できない…保守的(conservative)GCは「ゴミでないものを捨てる」危険が少ないが、ゴミを確実に捨てられない。厳格(exact)--本書では「正確」なGCは、ゴミを100%回収できるが、そのかわり「ゴミ袋」がかさばる…。

こうした苦労を、ふつうのプログラマーは知る必要はない。我々が清掃業者のことを知らなくても日々生活できるように。しかし知っているのと知らないのとでは、プログラムの質に格段の差が出るはずだ。特に必要な資源と確保できる資源の差が少ない環境ではそうである。本書を薦めるゆえんだ。

とはいえ、細かい点で気になるところは少なくない。たとえば本書で用いている疑似コード。関数は{}でくくるのにifはインデントというのはいささか面食らう。参照カウンターをせっかく取り上げているのに weak reference に関する言及がない(Perlが有名だが、Pythonにもちゃんとある)…しかしこれだけ多彩なアルゴリズムを実装とともに図解した本は今までなかった。こうした不備不満は、保守的GCで回収しきれなかったゴミとみなすべきだろう。むしろ不満があった方が読解が進むぐらいに思った方がいい。

とはいえ、「空間的仮想記憶」の方にも多少は言及があってもよかったのではと感じる。こういっては何だが、アプリケーションの場合、GCに瑕疵があっても終了してしまえばそれでよい。しかしOSからしてみれば、プロセス即オブジェクト。これをきちんと回収しなければすぐにコンピューターはゴミ屋敷になってしまう。実際そういうOSは今だって少なくない。

BSDカーネルの設計と実装
Marshall McKusick(著)
歌代 和正(訳)

それとて再起動してしまえばきれいさっぱりにはなるのだが、それは再起動できる場合であって、端末はとにかくサーバーはそういうわけに行かない。実際何年にもわたって再起動なしで稼働しているコンピューターは少なくない。

そんなわけで、本書で「時間的仮想記憶」を学んだ後は、ぜひ「BSDカーネルの設計と実装」を。それこそが、おそらく

序文

多くの読者にGCの重要さを納得していただければ、GCがハードウェアやOSによってサポートされた真の時間的仮想記憶に発展することがあり得るでしょう。ワツィが前書きで述べたかった本音はこれです

の「実装」に相当するはずなのだから。

Dan the Sloppy Garbage Collector

Comments

エントリーの内容の具体的なことはよくわかりませんが、知識という資源も当然有限で、取り扱うには相応のコストがかかるという道理はわかります。

知識の生態学や知識の衛生学や知識の病理学や知識の疫学もこれから整備されていくのだろうと思います。

そういう知識が充実するうちに、知識や時間をみんなが粗末な扱いをしないようになるのだろうとも思います。

Posted by h7bb6xg3 at 2010年03月20日 12:47