「ガベージコレクション 自動的メモリ管理を構成する理論と実装」を読んだ
最近「おれってガベージコレクションを勉強するにあたってめちゃくちゃ恵まれた環境にあるのでは？」とふと思い立ち、ベージコレクションの勉強を始めました。
ガベージコレクションの勉強を始めるにあたって、とりあえず「The Garbage Collection Handbook (first edition)」の邦訳である「ガベージコレクション 自動的メモリ管理を構成する理論と実装」を読むことにしました。
この記事では、読み終わってうれしいので、雑に感想を書きなぐっています。表記が「GC」だったり「ガベージコレクション」だったりするのは雑に書いたからです。
前提知識
ガベージコレクションの事前知識はほとんど不要で、何をしてくれるものか大まかにわかっていれば良い程度だと思います。つまり、ヒープに確保した領域を明示的に解放しなくても、何かのアルゴリズムでいい感じにやってくれる仕組み、ということを知っていれば十分だと思います。自分もその程度の状態から読み始めました。逆にいえば、スタックとかヒープとかそういうのは知っている必要があるかもしれません。
ただ、必須ではないと思いますが、OSやCPUの勉強を全くしたことがないとピンとこない部分があるかもしれません。仮想メモリとかページテーブルの話とか、CPUのキャッシュメモリについてなんとなく知っていないと、その部分の説明がほとんどないので、もしかしたら難しい箇所があるかもしれません。自分の場合は、OSについては、大学の授業で勉強した範囲でなんとなくわかったのですが、CPUについてはあんまり知らなくて困ったのでラムダノートの「プログラマのためのCPU入門」を別途読みました。
各章について
ガベージコレクションの基本的なアルゴリズムには、マークスイープ、マークコンパクション、コピー、参照カウント、というのがあり、第5章まででそれらについて解説がされます(この分類が適切なのか、というのはもしかしたら様々な立場があるのかもしれませんが)。それぞれの方式についても色々なアルゴリズムがありますが、それらについて疑似コードを用いて詳細に解説してくれます。
第7章は、メモリ割り付けについてです。ガベージコレクションのアルゴリズムによって当然メモリ割り付けの方式も変わってきます。ここはまあ、それはそうだよねというか。そういう感じでした。
第8章から第11章までは、ヒープの分割というテーマについて解説されています。第9章では代表的なヒープ分割手法である、世代別GCについて一つの章が割かれています。前述の基本アルゴリズムと同じように、世代別GCについても疑似コードを用いた詳細な解説があり、比較的かんたんに読み進められると思います。個人的に問題は第10章だと思っています。この章では世代別GC以外の様々なヒープ分割手法について解説されていますが、一つずつの説明に割かれている文量が少なく、自分にとっては理解が難しかったです。そのうちいくつかは元の論文にあたってみましたが、英語の文章を読むのは大変なので、理解が浅いまま進みました。
第11章、第12章では、ランタイムインタフェースとプログラミング言語特有の機能について解説されています。ランタイムインタフェースの方はあまり興味がなかったので飛ばしながら読んでしまいましたが、プログラミング言語特有の機能については、自分が普段書いているJavaScriptとのつながりを感じられてよかったです。具体的にはFinalizationRegistryやWeakRefに該当する概念が紹介されていました。
第13章からは、並列GCや並行GCについての説明が始まります。第13章では、そのための準備として予備知識について説明されています。興味がわかなかったのでここも飛ばしつつ読みましたが、読み終わってから思えば、別に読まなくても良かったかもしれません。自分の並行並列プログラミング知識といえば、オライリーの「並行プログラミング入門」を半分くらい読んだ程度ですが、それで一応読み進めることができた(それが良書だというのもある)。
第14章は、並列GCについてです。世間一般的な用語なのかは知りませんが、この本では並列GCというのは、GCするときにストップザワールドしても良くて、ただコレクタスレッドが複数並列で実行されるような状況を指しています。個人的には、ここを理解するのはそんなに難しくなくて、一個の目的のためのタスクをスレッド間で共有し合うのにも色々な手法があるんですね、という感じでした。
第15章からは並行GCです。ここから難易度が一気に上がったように感じました。並行GCというのは、ミューテータとコレクタが並行して実行されるタイプのGCで、一回のGCサイクルのためにストップザワールドするのではなく、GCサイクルが終わるまでの間にミューテータが動きます。インクリメンタルGCのような、真に同時に動くわけではないものの、一回のGCサイクル中にミューテータが動きうるようなGCも、並行GCとして分類されるようです(本当に同時に動くタイプのものはオンザフライGCと呼ばれるそうです)。並行GCは、異なる目的を持つ複数のスレッド(実際にスレッドである必要はないが、概念上のスレッド)がお互いの状態を破壊しないように動作することになり、それが自分にとっては難しかったです。
第16~18章は、前述の基本的なGCアルゴリズムを並行に実行するための手法がそれぞれ紹介されます。第19章では、よりシビアなリアルタイムGCについてです。当然、ここもかなり難しく、全然理解できていません。
文献検索ウェブサイト
原著である「The Garbage Collection Handbook」のウェブサイトがとても優秀で、参照している(大量の)文献を検索できるシステムがあります。
前述のとおり、説明のための文量がかなり少ないアルゴリズムも紹介されているので、そういったものについてより深く理解した場合はここから探すと良いのだと思います。
まとめ
普通に難しかったです。自分の場合は、ガベージコレクションについて豊富な知識を持っている方にすぐ聞ける状態にあったので、なんとか一応最後まで読み進めることができましたが、そうでなければ挫折していたと思います。あと、何度か読み返すとわかるところが増えていく本だとも感じました。ある概念が説明なしで登場して、後の章で説明される、というようなことが何度かあった気がするので(ライト/リードバリアとかそうだった気がする)。内容が難しいのもそうですが、構成や文章的にもそんなに読みやすい本ではないと感じてしまいました。
自分はGCについて異常な興味がなぜか湧いていたので頑張って読みましたが、普通の職業ソフトウェアエンジニアがシュッと読む本ではない気がします。もちろん、自分の理解が単純に遅かったという気もするので、人によっては簡単に読めるかもしれないので、興味が出たら読んでみてください。
せっかくGCについてちょっとだけ詳しくなったので、実装もしてみたいと思っています。そのために最近は小さなLISPインタプリタを書いていて、まだGCは実装していませんが、一通り動くようになってきたので、色々なGCアルゴリズムを実装してみたいです。
あと、最近原著である「The Garbage Collection Handbook」の second edition が発売されたそうなので、読んでみたいです。
Discussion