「ガベージコレクションのアルゴリズムと実装」を読んだ 〜実装編〜

ガベージコレクションのアルゴリズムと実装」を読了。前半の「アルゴリズム編」で GC の基本アルゴリズムを網羅的に解説し、後半の「実装編」では実際の処理系のソースを追いながら GC の実装を見てみるという構成で、非常に面白かった。

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

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

以下、読みながら思ったこと、メモしたことなどをまとめてみる。主に後半の「実装編」から。本書の中で解説されているバージョンは1年以上前のものなので、最新の実装にはあてはまらないかも。

Python

採用されているアルゴリズム

  • 参照カウント
  • マークスイープGC(循環参照したゴミの回収用)

記述言語:

  • C

Python のエンドユーザーのレベルでは GC の恩恵でメモリについては何も考えなくていいのに、C のレベル(Python自体の実装のレベル)だと参照カウントを意識しつつのプログラミングになってプログラマの負担が結構大きいなという印象。プログラマがメモリ管理している感がありあり。

特に参照を受け渡す境界部分で、参照の「所有権」を「渡す」のか「貸す」のか「乗っ取る」のかという判断。多分、参照の所有権の扱いについては紳士協定というか、規約のようなものがあって、この場合は「渡し」て、あの場合は「貸す」、それ以外は「乗っ取る」んだ、みたいなことが決まっていて、どこかにちゃんと文書化されていると思うんだが、勝手がわからないと簡単にメモリをリークさせそうな気がする。

DalvikVM

採用されているアルゴリズム

  • マークスイープGC
  • ビットマップマーキング

記述言語:

  • C

マークビットマップのビットでイテレートするのでマーク関数を再帰的に呼び出す必要がない点と、

オブジェクトビットマップとマークビットマップの差分を XOR で取って死んだオブジェクトをイテレートして回収する辺りは、なかなか巧妙な仕掛けになっていて面白いなと思った。

ただちょっと気になったのは、CLZ のような、先頭からのゼロビットの数を数えるための機械語命令の存在を前提としたアルゴリズムになっている点。

  • Android端末の CPU は ARM と決まっているのでこれでいい
  • この手の命令は大体どんなプロセッサにもあるのでこれでいい

ということなんだろうか。この辺りまで低レベルになってくると不勉強で知識が足りなくて困る。勉強しないと。*1

後、ちょっと気になったこととして、C のマクロ(複数行にわたる比較的大きなもの)が読み難かったというのがある。特に、引数以外に呼出側のローカル変数などが使われているもの。これをやられるとマクロを抽象化された手続きとして読めないので、慣れていないとちょっと戸惑う。

Rubinius

採用されているアルゴリズム

  • 世代別GC
    • マイナー:コピーGC
    • メジャー1:ImmixGC
    • メジャー2:マークスイープGC
  • 正確な GC

記述言語:

世代別GC を採用しており、使用するアルゴリズムとヒープ領域が多段構成。確保したいメモリのサイズによって割り当て時に使用するヒープを切り替えるなど、構造が複雑な印象。

が、ミューテータは ObjectMemory という抽象的なインターフェース(Facade)を介してメモリの割り当てと解放を行うので、使用する GCアルゴリズムについては関知する必要がない。よって、GC部分の実装をいじるのでなければ、記述言語である C++ のレベルでは GC の恩恵の元に開発が行える。その点、参照カウントの Python より開発者の(メモリ管理の)負担が小さい。

一方、正確な GC であることと、C の拡張ライブラリとの相性は悪く、拡張ライブラリからの参照をハンドラで別途管理するなどの苦心が見られる。(この辺は CRuby用に C で書かれた拡張ライブラリに対応したいという Rubinius特有の事情)

組み込みクラスのメンバ変数のアクセサ関数をプリプロセッサマクロで生成しているのが面白い。C/C++メタプログラミング的なことをしようとするとこうなるんだっていう驚きが。と同時に、このマクロで生成するセッターにライトバリアを仕込む辺り、うまいなと思った。

他にも一部のメソッドを Ruby によるテキスト処理でコード生成しているとのこと。

プリプロセスにおけるテキスト処理でコード生成、本当の意味で「メタ」プログラミングじゃねーか、という新鮮な驚きがあった。

本書で解説されているのはコピーGC の部分だけ。世代別GC の全容を把握するには実際のソースをさらに読んでみる必要がある。特に ImmixGC の実装と、大きなサイズのオブジェクトをマークスイープでどう扱っているのか見てみたい。

V8

採用されているアルゴリズム

  • 世代別GC
    • マイナー:コピーGC
    • メジャー1:マークコンパクトGC
    • メジャー2:マークスイープGC
  • 正確な GC

記述言語:

ヒープの構造が複雑でぱっと見で挫けそうになった(笑)

メモリをどう割り当てるかによってクラス階層の大元を分けるという構成。インスタンスをヒープに割り当てるものはすべて HeapObject を継承する、といった具合。これは、オブジェクトシステムの設計(クラス階層の構成など)とメモリ管理戦略の設計が不可分であるということであり、相当慎重に設計しないと後々いろいろ破綻をきたすと思う。

ハンドルスコープではコンストラクタ/デストラクタが呼び出される仕組みをうまく使ってコールスタックとハンドルスコープを同期させている。この辺もうまい。コンパイラが仕込んでくれるイベントフックというわけ。

フィールド制御。なんとハックなやり方。コンパイラ任せにできないとなるとこういう工夫が必要になるのか。コンパイラから制御を奪いとって自分でフィールドを配置するという。やはり言語処理系を作るともなれば、この手の逸脱行為は往々にして必要になってくるのか。

後、Rubinius 同様、やはりアクセサ関数はプリプロセッサマクロで生成していた。この辺は定石なのか。DRY原則重要がここにも。

本書で解説されているのはマークコンパクトGC の部分だけ。世代別GC の全容を把握するには実際のソースをさらに読んでみる必要がある。

EncodeForwardingAddresses() 以降はちょっと待てよと思った。そこまでやんのかと。ここで使われているテクニックのミソは要は相対アドレッシングで、アドレスをどこかに設定した基準からのオフセットとして表現すれば、アドレスの表現に必要なビット数を減らせるというもの。それ自体はへーなるほどなーって感じなんだけど……

そこまでしないといけないのかっ! という驚き。すべてのオブジェクトに 4バイトのフィールド、これが許容されない世界なんだなあと。ミューテータが生成するオブジェクトの数を考えたらまあ納得なんだけれども、まあなんとも泥臭い世界だ。

まとめ

「実装編」を読み終えて思うことは、やっぱり実際の処理系の GC は複雑で大掛かりで、実装上の工夫は総じて泥臭いということ。うまいなあ、なるほどなー、巧妙な仕掛けだなー、と思わされることはたくさんあるが、エレガントとか、美しいとか、そういうのとはちょっと方向性が違う。世代別ともなれば、ほんとにもう色々ごちゃごちゃしていて、本当に参ったという感じになる。

けれど、ソースコードを丹念に読んでいけば、ひとつひとつの処理は「探索」「マーク」「走査」「コピー」といったことに還元されていくわけで、GC は地道に愚直な処理をせっせとやっている、とても複雑で、巧妙な仕掛け、メカニズムだ。

それが動いて機能をなす、というのがなんとも面白い。

自分で GC を実装するのは、きっと面白いだろう。どんなアルゴリズムを採用しようかとか、ヒープの構成どうしようかとか、ちょっと考えただけでもなんだかワクワクしてくる。バグで生きているはずのオブジェクトを消し去ったりなんかした日には!

はやくそこまで行きたい。

*1:と言ってなかなかやらないわけですけど……