GC本(ガベージコレクションのアルゴリズムと実装)の発売を祝して、昨年末に Ruby の GC にちょっとした改造を加えてみた顛末を記します。
[2010/07/14 追記]いまさらですが、GC本を読んで、この内容は6章最後の「ブラックリスト」という手法の劣化版だとわかりました。おはずかしい……。考えつくようなことはたいてい既にやられてしまっているものですね。[追記終わり]
解説するのも野暮ですがタイトルは「女には向かない職業1 (創元ライブラリ)」のオマージュなので中身を正しく表現しておりませんので悪しからず。
最初に言い訳してしまいますが、この実験は業務で「Rubyのプロセスがメモリ使いすぎて落ちるからなんとかせよ」という指令を受けて調査の途上で行なったので、パッチや実験結果が会社にしかなく、手元に具体的なコードやデータがありません。いずれプライベートで追試しようと思いつつできてないので、説得力に欠けますが公開してしまいます。
さて、GC のアルゴリズムについて詳しくは GC本を読んでいただくとして、保守的GCには「本当はゴミなのに解放されないオブジェクトが残ることがある」という欠点があります。
Ruby(CRuby)の GC は保守的な Mark&Sweep GC なので、やはりゴミが残ることがあります。具体的にはマシンスタックやレジスタの値は、ポインタかどうかわからないので、Slot(まとめて確保されるオブジェクトの配列)の領域へのポインタっぽい値だったらポインタ(VALUE 型)と見做してマークしてしまいます。
特に 1.8 は Ruby のメソッドの呼び出しでマシンスタックもひとつ積まれるということと、C言語での実装が自動変数が多くてスタックを使いがち*1であるということがあって、1.9 に比べて保守的GCの弊害が現れやすいように感じます。
特にデーモンとして動作するプロセスを Ruby で実装するケースで問題になるのが、イベントループやソケットの待ち受けをしている Thread がずっと動き続けていて、その Thread のループしているメソッドの呼び元のスタックフレーム部分に誤検出される値があるケースです。このような Thread はほぼプロセスが動いている限りループを回り続けるので、その上のスタックフレームの値は変更されることがありません。そうなると、ある Slot は一度オブジェクトを割り当てたが最後終了時までずっと解放されないことがほぼ確定してしまう、ということが起きてしまうことがあります。
さて、タイトルにある保守的GCと相性のよくないデータ構造についてですが、要するに子(孫、ひ孫……)をたくさん持つオブジェクトは、それ1つがたまたま誤ってマークされても子孫全体がマークされて残ってしまうので、ヒープを圧迫してしまいます。
木構造とかそういうのですね。さらに循環参照してたりすると、どれがひとつが誤マークされるだけで全体が残ってしまうのでもっとたちが悪いです。こういう構造と、ずっと解放されない Slot の問題が組み合わさると、かなりやっかいなメモリ使用量への悪影響が出てしまうようです。
ちょっと手元で実験してみました。こんな二分木の構造と、終了しない Thread を組合せてみます。GCされていないオブジェクトは ObjectSpace.each_object(klass) で数えることができます。
class BinTree def initialize(lev) if lev > 0 @child = (0..1).map{ BinTree.new(lev-1) } end end end def deep_call(lev) if lev == 0 sleep else deep_call(lev - 1) end end def fork_threads(num) (0...num).map do |i| Thread.start do deep_call(10) end end end a = BinTree.new(12) p(ObjectSpace.each_object(BinTree){|o|}) a = nil GC.start p(ObjectSpace.each_object(BinTree){|o|}) a = BinTree.new(12) p(ObjectSpace.each_object(BinTree){|o|}) thrs = fork_threads(200) a = nil GC.start p(ObjectSpace.each_object(BinTree){|o|})
実行結果
$ /usr/bin/ruby -v gc_test.rb ruby 1.8.7 (2008-08-11 patchlevel 72) [universal-darwin10.0] 8191 8191 16382 16382 $ ruby-1.9.2 -v gc_test.rb ruby 1.9.2dev (2009-07-18) [i386-darwin10.0.0] 8191 0 8191 0
あれ……1.8 は Mac OS X(Snow Leopard) の標準添付の ruby なのですが、これGCちゃんと動いてるのかな。Linux でやった時はここまで極端ではなかったと思うのですが。1.9 は優秀です。Linux でも優秀でした。マシンスタックあまり消費しないからではないかと思います。
さて、実はここからが本題です。この「決して解放されない Slot に参照をたくさん持つオブジェクトが割り当てられてしまう」という問題の影響を軽減するために、GCFiller というクラスを導入して、Ruby が新しい Slot*2を確保する度に、その時点で既に誤マークされているところに GCFiller オブジェクトを詰めておくようにしてみました。
実装は heaps に新しい heap を確保したらまず GCFiller のオブジェクトで全て埋めてしまって、全 Thread のスタックとレジスタという不確実なルートからのマークをその heap について実行します。確保したばかりの heap なので、そこへの参照のようにみえるものは実際には全てポインタ(VALUE 型)ではない、誤マークの原因になるものです。こうしてマークされた GCFiller オブジェクトはそのまま残し、それ以外の slot を free list に繋げます。
GCFiller はインスタンス変数を持たないただの Object を継承しただけのクラスなので、これが誤マークされても被害は struct RVALUE の slot がひとつ潰れるだけで済みます。あからさまに危険な slot にうっかりツリーの根が入ってしまうのを防げるので、GC が有効に働いて結果としてメモリ使用量の低減が期待できるのではないか、と考えました。
ただし heap を確保した後で誤マークされるようになった slot は救えないので、完全な対策ではありません。あきらかに危いところを避けるようにしているだけです。
それで結果なのですが、すみませんデータが手元にないので具体的な数値が出せません。
おおまかな印象としては、GCFiller の導入だけではあまり効果が顕著ではなくて、さらに heap の1度に確保するサイズをあまり大きくしすぎないようにする修正も一緒にしないといけませんでした。おそらくイベントループの Thread を起動する前に大きな heap を確保してしまうので GCFiller による回避の効果が出なかったのだと思います。heap の確保をもっと小刻みにするようにしてみたところでは、問題のデーモンでは確か2割くらいのメモリ使用量の低減があったと思います。
けど実は 1.9 で動くようにしてみたら、それだけでメモリ使用量が半分以下になってしまったというオチがつきました。
結論→早く1.9に移行しよう。
