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

プログラムが深刻な問題を抱える時、動的メモリの管理に関するものが多い。メモリ系のバグが厄介なのは、バグが埋め込まれる箇所と、それが顕在化するタイミングが大きくズレていることにある。かつて、必要なデータ領域の確保と解放の問題は、プログラマの責任とされた。今でも、そうなんだろうけど...
整数型や文字型などプリミティブなデータ型を扱う分には、それほど目くじらを立てることもあるまい。だが、大量のデータ領域、あるいは、クラス型や構造体といった抽象化データを扱う場合には注意がいる。メモリ空間を相対アドレスで管理すれば、複雑なデータ構造にもアクセスしやすい。物理的には、参照という形で間接アドレッシングの構造を持つことになる。あの忌み嫌われるポインタってやつだ。こいつの危険性は、参照値をちょいと間違えたり改竄するだけで不正領域を指すことができることで、セキュリティ上の問題となる。あるいは、malloc/free, new/delete といった御呪いを疎かにするだけで、ヒープ領域には文字通りゴミが山積みされる。メモリ資源が豊富になればなるほどコードは複雑化し、バグの頻度が高まるは必定。不要になったゴミは長い間メモリ空間に居座り、メモリリークやらで他のプログラムと衝突したり、コールスタックに矛盾が紛れ込んでシステムを不安定にさせたり、最悪の場合メモリを喰い潰してシステムをダウンさせる。
そこで登場するのがゴミ収集係、そう、ガベージコレクションだ。人間社会においても、ゴミ清掃システムが破綻すると都市は崩壊する。地味な存在こそが、真の意味でシステムを支えている。本来、論理性だけに傾注したいプログラマとって、低水準な構造を意識させられることは思考の足かせとなる。動的空間を意識せずに済むというだけで、情報のゴミに翻弄される酔っ払いは幸せよ...

しかしながら、自動化という言葉は、心地よい響きがするだけに迷信となりやすい。厄介な機能を隠してくれるということは、その危険性までも隠蔽することになる。
近年、ポインタの概念を排除した多くの高水準言語を見かける。だが、むろんポインタがなくなったわけではなく、隠しているに過ぎない。トリッキーなキャストを要求するようなデータ定義が危険なことに変わりはない。ゴミ収集の仕掛けや癖を知っておくだけでも、危険なデータ構造を定義するリスクを避けることができよう。
ちなみに、おいらはプログラマではないが、メモリ管理やデータ構造の考え方はハードウェア設計でも参考になる。FIFO構造やスタック構造など物理構造の制限に因われなければ、思考も広がるだろう。おまけに、アルゴリズムを読むのが好きときた。コンパクトでエレガントに書かれる分野だけに、数学的で無味乾燥的なものと思われがちだが、そこには作者の思考物語が埋め込まれている。それが読み取れた時、感動を禁じ得ない...

本書に共感を覚えるのは、実装の解説をデータ型から始めてくれることである。おいらは、データ型やクラス型や構造体などの定義が、コンパクトな仕様書のようなものだと考えている。静的なデータ型を一通り定義するだけで、大方のプログラムイメージが出来上がっている。型の適切な定義は、そのプログラムが何をするものかについて、かなりの事を物語ってくれるはずだ。
実装編では、Python, DalvikVM(Android), Rubinius(Ruby), V8(JavaScript)におけるものが紹介され、言語システムを違った視点から眺められるのも興味深い。ただ、アルゴリズムではやや意外な印象を与える。それは、この技術分野が思ったより推論的で、確率論的であること。人間社会的とも言えようか。自分で明示的にやった方がマシかもしれない、と思わせるところもある。もう少しきちんと管理してくれると思ったのだが、保険の機能ぐらいに思った方がよさそうである。
ガベージコレクションは、大まかに「保守的GC」と「正確なGC」の二つに分類される。保守的GCとは、「ポインタと非ポインタとを識別できないGC」のことだという。正確なGCとは、言うまでもなく確実にポインタを識別すること。それがポインタなのかも正確に判断できないとなれば、データ領域を勝手に移動すると本来の参照関係が崩れることになる。よって、フラグメーテーションの問題がつきまとう。
しかしながら、ポインタの識別は構文解析と関わり、言語処理系の支援なしで完璧な判別は困難となる。処理も重そうだし、本筋のプログラムが遅くなったり停止するのでは本末転倒。保守的GCを選択する方が、実用的なようである。
さらに、アルゴリズムが言語処理系に対して独立して設計できるかどうかも、実用性の指標となろう。結局、現実味のある実装は、互いのアルゴリズムの欠点を補い合うような複合的な用い方になる。いまや実用的の代名詞となった、妥協、適当、微妙... ってのが、この世にマッチしているのかもしれん。どうせ世界は不完全だし。現代社会は、何事も面倒なことを覆い隠し、利便性や自動化に邁進していくが、自動化に頼り過ぎる感は否めない。本書は、これを問うているようにも映る。プログラミングが庶民化すると、低品質のソフトウェアが大量に出回る。少なくとも、システムプログラムとアプリケーションプログラムでは、プログラマの意識にも雲泥の差が生じるだろう。高水準という基準も曖昧になっていく。かつて、C言語も高水準言語と呼ばれた。そりゃ、アセンブラ言語に比べれば、見た目からして高級だ。アセンブラ言語だって機械語に比べれば、はるかに抽象度が高い。所詮、相対的な価値観の問題か。今日、高水準と呼ばれるプログラミング言語の一つの指標として、言語システムが動的メモリを自動で管理してくれるかどうか、という見方はできそうである...

1. ガベージコレクションの世界と三つの基本アルゴリズム
1995年、Javaの発表以来、ガベージコレクション技術の有り難さが広く認知されるようになった。しかし、その歴史は古く、1959年、Lispの設計で、D.Edwards が実装したという。
本書は、基本的なアルゴリズムに、「マークスイープGC」、「参照カウント」、「コピーGC」の三つを挙げ、他は派生型や組合せとしている。マークスイープGCは1960年、John McCarthy が発表... 参照カウントは1960年、George E. Collins が発表... コピーGCは1963年、Marvin L. Minsky が発表... と、この分野の基礎技術は半世紀前にほぼ確立しているようである。いずれにせよ、完璧なガベージコレクションの方法はない。マシン、言語、アプリケーションなどの設計思想に応じて、アルゴリズムの組合せや用い方も変わる。
全般的な印象として気になるのが、GCの起動タイミングが先送りなところである。具体的には、メモリアロケーションに失敗した時。おいらは、ゴミが発生したら即掃除しないと気が済まないタチだ。もちろん、先駆けてメモリ状態を健全に保とうとするアルゴリズムもあるが...
また、同じソフトウェア業界でありながら、用語のニュアンスもだいぶ違うようである。
例えば...
「オブジェクト」とは、オブジェクト指向で言うところの属性や振る舞いを持ったサービス群という意味合いでなく、データの塊を意味するという。ガベージコレクションは、この塊を基本単位とし、メモリ上での移動や破棄といった操作を行う。
「ミューテータ(mutator)」という用語も紹介してくれる。Dijkstra によって考案された用語だそうで、「変化させるもの」という意味。オブジェクト指向的なオブジェクトへのアクセスメソッドは、基本的に set/get 系で済むと思っているが、ガベージコレクションでは参照関係を重視するため、ゴミ収集ではミューテータのタイミングが鍵となりそうだ。つまり、参照関係は時間とともに変化するが、その監視の手がかりになるというわけである。
「チャンク(chunk)」という用語も聞き慣れない。「かたまり」という意味で、将来的にオブジェクトを利用するための空き領域のこと。ガベージコレクションは、死んだオブジェクトを回収して、チャンクとして次に備える。
... こうした用語がデータ構造にだけ着目している点に、いかにもゴミ収集の世界という印象を与える。要するに、問題は死んだオブジェクトをいかに判別するかということ。過去の実績や栄光などに構っちゃいない。そして、ガベージコレクションの役割は、死んだオブジェクトを本当の意味で葬り去ることにある。

2. マークスイープGC(Mark Sweep GC)
保守的GCの代表的な存在のようで、その名のとおり、マークフェーズとスイープフェーズからなる。マークフェーズは、生きているオブジェクトにマークをつけるステップ。スイープフェーズは、マークのついていないオブジェクトを回収するステップ。その機構は極めて単純で、ルートから階層的に参照関係を再帰的に辿ってマークすれば、すべてのオブジェクトがマークできるという発想。
オブジェクト探索には、その階層から「深さ優先探索」と、その広がりから「幅優先探索」とが考えられる。GCはすべてを探索する必要があるので、どちらを優先しても探索するステップ数はあまり変わらない。だが、メモリ消費量を比較すると、深さ優先探索の方が少なく抑えられる傾向にあるという。アロケーションのタイミングは、ミューテータからチャンクが要求されると、その適切なサイズのチャンクを返す。
チャンクには、「First-fit, Best-fit, Worst-fit」の三つの戦略があるという。First-fit は要求されたサイズを返す。Best-fit は要求サイズ以上で最小のチャンクを返す。Worst-fit は最大のチャンクを見つけ、要求されたサイズとその残りに分割する。戦略によっては、細かなチャンクが多くなってしまう問題がある。そこで、連続したチャンクをつないでおいて、フリーリストとして持っておく手もある。
また、マークスイープGCは、Copy-On-Write との相性が悪いという。Copy-On-Write とは、unix系の仮想記憶で使用されている高速化手法で、プロセスのコピー(fork)を行う時など、大半のメモリ領域でコピーしたふりをして、実際にはメモリを共有するといった仕掛けである。だが、書き込みが発生した場合、他のプロセスとの不整合が生じるため、共有メモリを勝手に書き換えるわけにはいかない。書き込む場合は私有領域にコピーしておき、その領域上でデータ操作を行えばいいのだけど。マークスイープGCは、生きている可能性のあるオブジェクトすべてにマークビットを立ててしまうため、本来発生しないコピーが頻発してメモリを圧迫するという。確かに、マークビットを立てるだけで、オブジェクトに書き換えが生じたと勘違いされては困る。この問題に対処する方法が、「ビットマップマーキング」だという。ガベージコレクション用のヘッダをビットマップテーブルとして別管理するわけか...

3. 参照カウント
すべてのオブジェクトに参照の数を記憶させるという考え方で、各オブジェクトは自分の人気度を知っていて、人気がなければ自然消滅させる。マークスイープGCでは、チャンクがなくなった時にミューテータがGCに空き領域を要求するが、参照カウントでは、ミューテータが明示的にGCを起動することはなく、ミューテータの処理とともにカウンタの増減を行う。カウンタの増減のタイミングは、ミューテータが新たなオブジェクトを生成する時やポインタの参照状態を更新した時で、カウンタ値がゼロになると破棄される。参照カウントは、メモリ管理をミューテータと並行して行うという特徴がある。しかしながら、カウンタ値のビット幅が大きくなり、処理が重たそう。
また、循環参照が回収できないという大きな欠点を抱えているという。カウンタのビット幅を減らす方法では、「Sticky参照カウント法」を紹介してくれる。その極端な例では、1bitしか割り当てない「1ビット参照カウント」という方法もあるという。すぐにオーバーフローするわけで、簡易的な判別ぐらいにしか使えないような...
カウンタの増減処理を軽減する方法では、「遅延参照カウント法」という改良版が紹介される。
さらに、循環参照が回収できるように、マークスイープGCと組み合わせた「部分マークスイープ法」を紹介してくれる。循環参照が回収できないのは、参照カウントの特有の問題とすれば、通常は参照カウントをやっておき、必要な時にマークスイープGCを呼び出すという戦略である。しかし、効率が悪いようだ。一般的に、循環参照をもつゴミは滅多に生じないのだとか。循環参照を持つかもしれないオブジェクト群に対してのみ、マークスイープGCを適用するとなると、循環参照であるかもしれないという推定が必要になる。再帰的にアロケーションを試すといった機構が必要か。これはこれで、オーバーヘッドが大きそうである。滅多に生じないのであれば、最初のキューが空かどうかだけでも、かなりの判別ができそうな気もする。

4. コピーGC(Copying GC)
生きているオブジェクトだけを集めて別の領域にコピーし、連続した領域を確保するという考え方。むかーし、メインフレームでコンデンスによる最適化といった処理を明示的にやっていたような... おっと、年齡がバレそう！ユーザが明示的にデフラグをやる某OSの思想もどうか？と思うが...
それはさおき、コピーGCはフラグメンテーションの抑止に非常に良く、メモリ状態を常に健全に保てるという特徴がある。全領域をコピーするので、保守的GCと相反する。参照関係にあるオブジェクト同士が隣り合わせにあるので、キャッシュメモリの恩恵を受けやすい。しかし、ヒープ領域を常に二等分して、片方をバックアップ用に開けておく必要があるため、メモリの使用効率が悪い。
また、再帰的関数の呼び出しでは、子オブジェクトが再帰的にコピーを行うため、オーバーヘッドが大きいという。再帰的コピーの対処では、固有の反復コピー関数で置き換える「CheneyのコピーGC」を紹介してくれる。キャッシュとの相性を犠牲にするが...
あるいは、全体を二等分するのではなく、細かく空間を分けて、マークスイープGCなどの他のアルゴリズムに割り当てる「複数空間コピー法」も紹介してくれる。フラグメンテーションの問題が再浮上するけど...

5. 世代別GC(Generational GC)
三つのアルゴリズムとは、ちと違う視点だが、考え方としては興味深い。注意したいのは、このアルゴリズムは単独なものではなく、他のGCと組み合わせることである。
ほとんどのオブジェクトは生成されてすぐゴミになり、長く生き残るのは稀、という研究報告があるそうな。そこで、オブジェクトに年齡の概念を導入する。GCを一回経て、生き残ったオブジェクトは、1歳となる。そして、オブジェクトを世代別に分類し、一定の年齡を超えると旧世代オブジェクトとし、新世代オブジェクトを重点的にGCの対象とすることで時間を短縮する。
とはいえ、旧世代から新世代への参照を考慮する必要がある。その対処では、記憶集合(Remembered set)を使って、新世代への参照を効率よく見つけることができるという。そして、「ライトバリア」という旧世代から新世代への参照を記録するための機構を紹介してくれる。ヒープ領域が圧迫された時の非常手段として、旧世代オブジェクトから排除するというのはありかもしれん。楢山節考やなぁ...

6. Python
Python のメモリ確保は、単純に malloc/free を使うだけでなく、その上に３階層の独自レイヤを重ねて、効率的なアロケーションを行う戦略をとっているという。

  レイヤ3: PyList_New(), PyTuplet_New(), PyDict_New(),...
  レイヤ2: PyObject_GC_New(), PyObject_Malloc(), ...
  レイヤ1: new_arena()
  レイヤ0: malloc()

しかも、オブジェクトの生成時に、割り当てるメモリのサイズによって、アロケーション方法を変えている。要求サイズが 256byte を超えると素直に malloc を呼び、それ以下だとレイヤ順に登っていく。オブジェクトのほとんどが、256byte 以下で、しかも、すぐに捨てられる傾向にある。例えば、forループ文では一時的な文字列や数値列を大量に使い捨てるので、malloc/free 構造を使うのはあまりにも酷。
その構造は、細かい方からブロック、プール、アリーナの3階層になっているという。アリーナオブジェクトはプールで分割され、プールサイズは 4Kbyte 固定。このサイズは、大抵のOSの仮想メモリのページサイズ 4K と合う。OSがプール単位でメモリ管理してくれることを期待してのことか。それで、OSとの相性が良くなるかは知らんが...
また、アルゴリズムは参照カウントをベースとし、「参照の所有権」という構造を紹介してくれる。所有権はオブジェクトに対するものではなく、参照に対してのもの。尚、オブジェクト自体には所有権はない。参照の所有権は、関数の戻り値と引数に大きな意味を持つという。関数側は、呼び出し側に戻り値と一緒に参照の所有権を渡す。参照の所有権を持つものが、同時に破棄する権利を持つという考え方か。他から参照ができるのは、参照の所有権を借りている状態とするわけだが、借り手が勝手に破棄するわけにはいかない。ただ、カウンタをデクリメントする権利はある。貸出時にインクリメントして、返却時にデクリメントするという仕掛けか。まるで図書館の仕組み。しかし、すべてのデータのやりとりにおいて、参照の所有権がつきまとうとなれば、言語処理系に仕様変更や機能追加をする度に、GCの構造に振り回されそう。
また、参照カウントの欠点である循環参照の問題は、マークスイープGCの改良版との組合せで対処しているという。循環参照は、すべてのオブジェクトで起こるのではなく、コンテナオブジェクトによって引き起こされるという。コンテナオブジェクトとは、他のオブジェクトへの参照を保持することが可能なオブジェクトのこと。尚、Pythonのオブジェクト構造には、リスト型、タプル型、辞書型といったコンテナオブジェクトが用意されている。
なんと！コンテナオブジェクトは三世代あって、世代別コンテナオブジェクト構造だという。言語設計者は、こんなデータ構造までも考慮しながら設計しなければならんのかぁ... 足を向けて寝られん！

7. DalvikVM
DalvikVM は、Androidプラットフォームに搭載される仮想マシン。Android のアーキテクチャは、Linuxカーネルやそのライブラリ(libc, SQlite, ...)で構成されるが、その上位階層に位置づけられる。尚、Dalvik(谷間の入江) という名は、開発者Dan Bornstein の祖先が住んだアイスランドのフィヨルドにある漁村に因んでいるそうな。
Androidを起動すると、最初に Zygote というプロセスが立ち上がるという。Zygote はすべての親プロセスとなる。アプリケーションを立ち上げる際は、Zygote から fork してプロセスを作る。Zygote は多くのライブラリを抱えるために起動は遅いが、その後の子プロセスは起動が高速に行える。また、子プロセスは親プロセスの共有メモリ領域を使用するため、メモリ消費量も軽減できるという。
ちなみに、Android には、bionic という独自のCライブラリが搭載されているという。bionic は、glibc malloc から派生した独自の dlmalloc を持っているとか。glibc が大きすぎるということか。BSD libc を改良したものらしい...
共有メモリ用のデバイスには、ashmem(Anonymous Shared Memory Subsystem) というものが組み込まれているという。こいつが、mmap の機構を持っているらしい。mmap とは unix系のシステムコールで、ファイルのランダムアクセスなどを可能にするライブラリ。通常のアロケーションには、brk というシステムコールを使うという。これは、Cのヒープ領域を拡張するシステムコールだとか。だが、Cのヒープ領域はプロセスによってサイズの上限が決まっていて、mmap は、brk より制限が少なく、大きなメモリサイズを取得できる。ただし、mmap はページサイズ 4KByte 単位でしか割り当てない。
dlmalloc のアロケーションは、小さなサイズには brk を、大きなサイズには mmap を使うという。mmap 機構からして、Copy-On-Write との相性が良さそうだが、DalvikVMでは、これを苦手とするマークスイープGCを採用しているという。もっとも、この問題に対処したビットマップマーキングのようだが...
ところで、仮想マシンの世界は、大まかにレジスタマシンとスタックマシンの二つに分類される。スタックマシンは、レジスタを使わずにスタックを使って計算し、結果をスタックに積み上げる。一方、レジスタマシンは、数値を固有のレジスタにロードして、計算結果をレジスタに格納する。CPUの設計経験を持つおいらには、後者の方がイメージしやすい。それも古代人の感覚かもしれん。実際、固有レジスタで機能を差別化するよりも、スタックだけで抽象化した方がすっきりしている。スタックマシンのメリットは、オブジェクトコードのコンパクト化、コンパイルの単純さなどが挙げられるが、なによりもプロセッサの状態数が少なくて済む。ただ、メモリ参照をスタックで管理すればアクセスがそこに集中するわけだし、GCにとっては辛そうな気もするけど...
多くの JVM(Java Virtual Machine )でスタックマシンが採用される。しかし、DalvikVM はレジスタマシンを採用しているという。それも、Android 特有の事情があるようだ。Android端末のプロセッサが、レジスタマシンアーキテクチャだからであろう。ハードウェア思想をそのまま受け継いで、最大限の高速化を狙っているのだろう。これを仮想マシンと言うのか？は知らん。実際、ARMに特化したアセンブラコードもたくさん置かれているらしい。Androidマシンには、ARMが採用され、Android-x86 も進行中という事情もある。

8. Rubinius
Rubyの処理系で有名なのは、C言語で記述される CRuby の方だが、本書はあえて Rubinius を扱っている。Rubiniusは、Evan Phoenix を中心に進められ、その象徴的なポリシーに「Ruby で Ruby を実装」というのがあるそうな。思想では、Rubinius の方がエレガントに映るが、実用性では、CRuby の方であろうか。Rubinius が興味深いのは、本書で扱われる数少ない「正確なGC」の事例だということ。尚、CRuby の方は「保守的GC」だという。
Rubinius は世代別GCを採用し、マイナーGCとメジャーGCの二段階で構成されるという。マイナーGCでは、コピーGC(CheneyのコピーGC)を、メジャーGCでは、マークスイープGCとマークコンパクトGC(ImmixGC)を。メモリ空間も、それぞれ三つの領域に割り当てられる。シーケンスは、閾値を超える大きなサイズの場合はマークスイープGCアロケータを呼び出し、閾値を越えない場合は、コピーGC空間用に割り当て可能な場合はコピーGCアロケータを呼び出し、それ以外はマークコンパクトGC用アロケータを呼び出すといった具合。コピーGCでは、ライトバリアが実装されているようだ。
やはり、Rubiniusも、CRuby用に書かれたC拡張ライブラリをサポートしているようだ。では、Cのコールスタックやレジスタをどうやって走査するのか？保守的GCであれば、オブジェクトへのポインタがC拡張ライブラリのコールスタックやレジスタに漏れたとしても、とりあえず生きているオブジェクトとみなす。しかし、正確なGCではそうはいかない。その対処として、C拡張ライブラリに渡すすべてのオブジェクトへのポインタをハンドラに格納し、ルートで扱うという。そして、参照カウントに似た形でハンドラの生死を管理するとか。こりゃ、いくらなんでも Ruby じゃ書けんやろ。どうやら、C++ で書いてギャップを埋めているようだ。あれ、ポリシーに反しないのか？
保守的GCのメリットは、ミューテータでGCを意識する必要がない。デメリットは、使用できるGCアルゴリズムが制限される。対して、正確なGCのメリットは、GCアルゴリズムが制限されない。デメリットは、ミューテータを意識する必要がある。保守的なGCを採用している CRuby は、驚くほど簡単にC拡張ライブラリを記述することができるという。対して、正確なGCを採用している Rubinius は、アルゴリズムの制限がないために、比較的簡単にGCを改良することができるという。GCの作りやすさを優先しているという見方もできそうか...

9. V8
Google Chrome の特徴は、Google社が独自に開発した高速な JavaScript エンジンを搭載していること。そう、V8 JavaScript Enjine ってやつだ。名前の由来は、V型8気筒エンジンからきているらしい。高速なパワフルエンジンの代名詞だとか。コードは、80%以上が C++でグルグルしそうだけど...
V8 は正確なGCが採用され、世代別GCが使用されるという。構成は、Rubinius のGCに似ていて、これも正確なGCの事例。マイナーGCでは、コピーGC(CheneyのコピーGC)を、メジャーGCでは、マークスイープGCとマークコンパクトGCを採用している。ハンドラでリストを持つという考え方も、Rubinius と同じか。もっとも、こちらは最初から C++ で書こうとしているので、なんでもありだけど...
そもそも、GCをどう位置づけるか？システムプログラムなのだから、わざわざスクリプト言語で書く必要があるのか？あるいは、言語システムはアプリケーションプログラムなのか？OSの境界も曖昧になっている。ユーザの立場では、ポインタから解放してくれることはありがたい。だからといって、ポインタの概念を知らなくて、本当にいいのか？将来はガベージコレクションも独り一人歩きを始めるのかもしれん...
ところで、むかーしから、ファイナライザってやつの意義がよく分かっていない。ソフト屋さんに、いろいろ説明してもらうのだけど、いまいちしっくりこない。ファイナライズとは、オブジェクトの解放処理にフックをかけて、何らかの処理をする機能である。何らかの処理というのが微妙で、メッセージを発行するぐらいしか思いつかない。デバッグの手がかりにはなりそうだが、パフォーマンスを落とすだけのような気もする。GCを装備していない言語システムでは、直接デストラクタをやればいいだろう。だが、自動化システムではファイナライザにオブジェクトの解放まで期待していいのか？
案の定、V8 にはファイナライザがないという。ファイナライザに関する問題は、GCの実装において厄介なものらしい。もしかして、いらねぇってかぁ？変に操作をやると怖いから、触らぬ神に祟りなし！