«前の日記(2004年02月04日) 最新 次の日記(2004年02月06日)» 編集

Matzにっき


2004年02月05日 [長年日記]

_ [言語]既存のGC手法の長所と課題

まず、スクリプト言語におけるGCの要求を復習すると以下の通り。

1. 拡張ライブラリが書きやすい(明示的なprotectが不要)
2. 移植性が(そこそこ)高い
3. native threadと相性が良い
4. さまざまな状況でも落ちない
5. 普段の性能を維持しつつ、大量のlive objectに対応できる

Rubyの採用しているconservative mark and sweep手法は、1,2,4はクリアしているが、3,5が苦手。 以前にも書いたようにpthreadはスタックアドレスを得るAPIがないので、 conservativeの特徴であるCスタックのスキャンができない。 また、生きているオブジェクトを全部スキャンするのでlive objectが多くなると極端に遅くなる可能性がある。

一方、PerlやPythonの使っているreference count手法は、2,4,5をクリアしている。 一般的にreference countは応答性がよく、 特にオブジェクトが参照されなくなった時にすぐに解放されるのでlive objectが増えても問題は発生しない。 しかし、代入が発生するたびに参照数(reference count)を増減させる必要があるため、 拡張ライブラリのメモリ管理が面倒だ。また、参照数管理を間違えると面倒なバグの原因になる。 代入のたびの参照数管理はトータルの性能低下の原因になる。 特にthread環境下ではあらゆる代入のためにmutex_lockが必要になるので、 性能上の問題が発生する可能性がある。

それと、reference countにはサイクル(間接的に自分を参照すること)が発生すると、 誰からも参照されなくなってもオブジェクトが解放されないという欠点があるので、 多くの処理系ではmark and sweepのようなスキャンを行う他のGC手法と組み合わされている。

こういうのを見ていると結局、大量オブジェクト対策とthread対応が大きな課題であることがわかる。

大量オブジェクト対策としては、generational GC(世代別GC)が有名だ。 これは、ほとんどのオブジェクトの寿命は短いが、 中には長く生き残るオブジェクトがいて、そういうオブジェクトはあまり変化しないという性質を利用している。 新しく作られたオブジェクトは「若い世代」として頻繁にスキャンされ、 長く生き残ったオブジェクトは「殿堂入り」してたまにしかスキャンしない。 これで無駄なスキャンによる性能低下を避けることができる。

thread対応は難しい。CスタックをスキャンするconservativeなGCでpthreadにうまく対応した手法はあまりないからだ。

QSchemeというScheme処理系とBoehm GCはスレッド対応として

  • スレッド生成関数をフックしてスタックの先頭アドレスを保存
  • GC時に各スレッドにシグナルを送ってハンドラでスタックトップのアドレスを取得

という方法を使っている。しかし、pthreadとシグナルは鬼門で移植性に問題がある(Boehm GCはプラットフォームごとにスレッド対応のコードを持つ、QSchemeはLinuxのみ対応)。

スレッド対応で移植性のある唯一のGC手法はKSMというScheme処理系で採用されているものだ。 これは「ある関数内で生成されたオブジェクトはregistryと呼ばれるスレッドごとのテーブルに登録され、スキャンの対象になる」というルールによって実現されている。まあ、確かにこの方法ならまだ参照されている可能性のあるオブジェクトを解放してしまうことはないわな。

だが、これはあまりにも「保守的」すぎて、関数の実行が終了しない限り、 参照されなくなったオブジェクトも後生大事にとっておくので性能上の問題がある。 ある関数の中で大量のオブジェクトを作って捨てて、としているとあっという間にメモリを使い切ってしまう。 が、発想としては面白い。

で、これらを組み合わせて理想の技法を作り出そうというわけだ(まだ引っ張るらしい)。

追記

pthread_attr_setstackaddrで事前にスレッド用のスタックを用意しとくのでは駄目なんですか」という質問がありました。

完全に駄目というわけではないのですが、

  • スレッドライブラリはpthreadだけではない
  • pthread_attr_setstackaddrを使ったGC処理系はなぜか存在しない(私が知らないだけかも)
  • pthread_attr_setstackaddrはスレッド生成前にしか使えないので、 外部で生成されたスレッドに対応できない

などの理由で、満足できてません。


«前の日記(2004年02月04日) 最新 次の日記(2004年02月06日)» 編集