CTFE再起動 - Outlandish Watch

　dmdのソースがgithubで管理されるようになったり、

GitHub - dlang/dmd: dmd D Programming Language compiler

TwitterでD言語er（発音はディーゲンガーか？）の方々をたくさん見かけたりして、またCTFEにはまり込む気分になってきた。

d:id:outland_karasu:20081031

　過去のソースを拾ってきて最新版のdmd2 ver2.052でコンパイルを行ったが、やはりCTFEがメモリを食いすぎてOut of memoryが発生した。
　2年前はここで諦めてしまったけれど、また、2年も経つのにこの辺改善されてないのかと呆然としたけれど、今回は手元にdmdのソースが全て揃っている。これを修正してどうにか動かしてしまおうと思った。

原因の特定

　まずgithubから取って来たソースをざっと眺める。ソースの拡張子は.cだが言語はC++だ。interpret.cといういかにもCTFEでインタープリタしてそうなソースがあり、覗いてみるとやはりその通りだった。
　コンパイル時に生成されたASTのノード（ExpressionやFuncDeclarationといったクラス）に実装されているメンバ関数interpretを再帰的に呼び出してCTFEを実現している。で、ざっと見た限りnewをたくさん呼んでいるけれど、deleteしている箇所がない。
　GCとか何か特殊なメモリ管理をしているのかな、と基本クラスのExpressionやObjectを覗いてみるが、それらしい箇所は見つからない。grepしてroot/rmem.cという箇所でoperator newがオーバーロードされている*1のを見つけたが、単にmalloc/freeしているだけだった。なぜ再定義したし……。
　どうも本来はGCを使ってメモリ管理したかったらしく、中身が空のmark関数やfullCollect関数が散見される。おそらく移植性等の問題で未実装になっているのだろう。
　そして、コンパイラの実装コードの方だけGC前提の書き方になってしまっているのだ。

対策の検討

　newしっぱなしのオブジェクトをなんとか回収しなければならない。考えた対策は2つ。

メモリプールで確保し、CTFE終了時には一括で解放する。
GCを組み込む。

　2のハードルが明らかに高そうなので、最初は1で行こうと考えていた。Expression辺りのoperator new/deleteをオーバーロードし、CTFEの時だけ専用のメモリプールを使って領域確保して、後で一括解放できるようにすれば良いのだ。
　しかし調べてみると、interpretはoptimize（つまり最適化の処理か）という関数から呼ばれていて、この関数がnewされたExpressionを返していて、その返したExpressionをいつ解放して良いのか、呼び出し元までさかのぼって戻り値の使用状況を見ないと分からない。呼び出し元は全ソースで数十箇所あり、それぞれ全部確認してメモリプールの確保・解放を仕込むのは面倒だなあ、と思った。
　何か方法はないかなあ、とdmcのドキュメントを眺めていると、なんとgc.hというライブラリがあるではないか。中身はBoehm GCらしい。これそのまま組み込めるんじゃね？　と思い、グローバルなnew/deleteのあるroot/rmem.cを改造してみることにした。

対策の実施

　Boehm GCの使い方は昔「Binary Hacks」という素晴らしい本で読んだ事があって、単にGC_INIT()した後でmalloc/freeをGC_MALLOC/GC_FREEで置き換えるだけという素晴らしいものだ。これだけで、明示的にfreeしなくてもメモリが足りなくなると勝手にGCされるようになる。しかもdmcのライブラリのおかげで、gc.hをincludeするだけで使える。（libもgc.h内部でpragmaにより指定済み）
　後は出来たdmdと同じディレクトリにdmc付属のgc.dllをコピーして実行すれば、GC付きdmdが動作する。
　試してみると、dmdが落ちてしまう。どうもmallocしたものをdeleteしてみたりとかしているらしく、operator deleteをGC_FREEで実装するとどうやっても落ちる。しかし、よく考えたらGCなのだから、わざわざfreeする必要はなかった。operator deleteの中身をコメントアウトして空の関数にしたら、落ちずに動作するようになった。

対策の結果

　2年前のCTFE時PEGパーサを実行したところ、メモリ消費量が20MBほどで安定し、時間は数分掛かるが正常終了するようになった。ちゃんとASTのダンプも出力されたので、たぶん大丈夫だろう。今までGB単位でメモリを食っていたのに、GCの力は偉大だ。
　今回処理させているソース（Shift_JISとUnicodeの対応表）も、8000行/300KB程度で、ASTノード数ばかり多いタイプのものだったので、もっと普通のソースならそれなりの速度で動くかもしれない。

今後

　というわけで、CTFEでコンパイルタイムにコンパイラ・コンパイラを動かしてコンパイラを作る準備が整った。
しかし、他人にコンパイラを修正させてまでライブラリを使ってもらうわけにはいかず、今回のCTFEライブラリはまだ外には出せない。
　実行方法を修正すればまだ速度やメモリ効率を改善できるかもしれないし、2年前と比べてD言語も進歩しているので、また新たに書き直してみようと思う。