2007-10-10

Boehm GC

言語

今だに読み方が判らない。ぼえーむ？ささださんによると「べーむ」らしい。
私も使っているGarbage Collectionのライブラリ。様々なアーキテクチャに移植されているので汎用性が高く、GCJやGaucheなどの言語実装に採用されている。基本的にはCで書かれていて、C++から使うことも考慮されている。
GCの手法としては保守的マーク＆スイープ法を採用している。マーク＆スイープというのは

GC対象のメモリ全てをリストアップ
スタックなどをルートとして登録
既に登録されているものから参照されているメモリを登録
全ての参照先が解決するまで3を再帰的に繰り返し
それでも参照されていないメモリはゴミなので回収

という感じだ。保守的というのは3で「その値の型がポインタでなくてもポインタをキャストしたものの可能性があるので念のため参照されているとみなす」という意味だ。欠点としてはGC中は動作が停止するため、リアルタイム性が要求される分野に弱いことがある。世代別GCなど、停止時間を短くする進化が続けられている。
この保守的というのはC,C++のように整数値からポインタへのキャストが許されている言語を前提とした話だ。実際にjavaのような整数値からポインタへのキャストが許されていない言語では保守的である必要がない。でもgcjは保守的にしているのだよな。gcjが遅い理由の一つはそこにあるのではなかろうか。
マーク＆スイープ法と対照的なのは参照カウント法か。こちらはメモリ毎に参照カウントというものを用意して、参照される度に+1、参照が外される度に-1と操作して、参照カウントが0になったらゴミなので回収という方法だ。実装例はBoostのshared_ptrなどがある。自己参照や循環参照があると参照カウントが0にならないため本来はゴミになっているメモリが回収されないという欠点がある。
ちなみにrubyはマーク＆スイープ法(独自実装)を使っている。pythonは参照カウント法(独自実装)なのだが、循環参照検出機構も実装することで上記の欠点を克服している。単体で見るとpythonの方が優れているように思う。しかし、拡張ライブラリを書こうとするとpythonは参照カウントの操作が難しく、rubyの方が楽だとも思う。緩いrubyと厳しいpythonという傾向がここでも表れているのかも。

2007-10-10

shared_ptr

言語

で、boostのshared_ptrなのだが。循環参照を解決できる超スマートなポインタは作れないのだろうか。まあ、簡単に作れたらboostに入っているだろうけども。
RTTIを駆使する場合を考える。例えば、

#include <iostream>
class Base {
public:
  virtual ~Base() {}
}
class Sub: public Base {
}
int main() {
  Base* p = new Sub();
  std::cout << typeid(*p).name() << std::endl;
}

の出力は「3Sub」だった(gcc3.3.3)。しかし、

#include <iostream>
class Base {
public:
  ~Base() {}
}
class Sub: public Base {
}
int main() {
  Base* p = new Sub();
  std::cout << typeid(*p).name() << std::endl;
}

の出力は「4Base」だった(同じくgcc3.3.3)。
http://ray.sakura.ne.jp/tips/rtti.htmlによるとVC++の場合には仮想関数テーブルを持つ場合はその要素として型情報を持ち、仮想関数テーブルを持たない場合は静的型から型情報を決定するらしい。gccでも似たような振舞いを見せているし、同様の機構なのだと思う。ここから推察するにRTTIは仮想関数テーブルを持つ場合にしか使えない。つまり、RTTIで超スマートポインタを作るのは無理。
実行時の型情報だけで足りないのならコンパイル時の型情報をどうにか分けてもらえば良いのではなかろうか。これには自作のプリプロセッサを通すのが簡単だが、ちょっとC++の範囲を逸脱している気がする。
一歩譲って中身の型情報が判ったとしてもその型情報からメンバの内容を割り出さなくてはならない。アーキテクチャに依存して良いなら出来ないこともなさそうな気がするがどうだろう。
結局、判らなかったということで……。