出張やらなにやらどたばたしている間に届いていた論文誌を読む。
ささだくんの論文「Ruby用仮想マシンYARVにおける並列実行スレッドの実装」が 掲載されている。私と前田敦司先生、並木先生も共著者に名前が載っている。
で、前から読んでいたこの論文はおいといて、 発表概要だけで論文掲載にいたらなかった「世代管理を保守的に行う世代別GCアルゴリズムの提案およびRubyへの実装と評価」というのが非常に気になる。
アブストラクトによれば、
本発表のアルゴリズムの特徴として、ライトバリアが必要ない、 メジャーコレクションとマイナーコレクションが一体化している、 および生きているオブジェクトの移動を必要としない ことなどがあげられる。
のだそうだ。うーむ、どうやって実現しているのだろう。 アブストラクト中でのヒントはこれだけ。
先頭側の領域をold領域、末尾側の領域をnew領域に分断し、 old領域に属しているオブジェクトはすべて古いオブジェクトと見なす 新しい世代別GCアルゴリズムを提案する。 本発表のアルゴリズムでは、old領域ではnew領域へのポインタが存在するかを検査し、 new領域ではGCを行う
のだそうだ。うーん、オブジェクトの移動を伴わないのに どうやってnew領域とold領域を分断するのかな。
そうか、アレか。木山版みたいにリンクリストで世代を管理してるのかな。 で、old領域のオブジェクトにはマークビットを立てたままにしておけば、 old領域のそれぞれのオブジェクトから 再帰マークするだけでold領域からnew領域のリファレンスを検出できるよな。 後は普通にルートから再帰マークを行い、 new領域に属するオブジェクトだけをスイープすればよい。
メジャーコレクションしたい場合には事前にold領域のマークビットをクリアしてから GCすればよいことになる。 もちろん、メジャーとマイナーの切り替え戦略とか、 検討すべき点はいくつかあるだろうけど、そんなに悪くないアイディアのように思える。 意味があるかどうかわからないけど、複数世代への拡張も可能だし。
では、このアイディアが論文掲載に至らなかった理由はなんだろうか。
まあ、GC時間が30%近く改善されたらすごいと思うけどな。 もっとも、ここで示した方法では「メジャーコレクションとマイナーコレクションが一体化」は 達成できていないような気がするので、また違うアルゴリズムなのかもしれない。
とか書いてると、作者からコンタクトがあるかも。 神奈川工科大の五百蔵(いおろい)さ〜ん、見てますかぁ？
さらに考えてみた。
あるGC時点で存在するすべてのオブジェクトの総数をm、 old領域に所属するオブジェクト数をo、 new領域に所属するオブジェクト数をnとした時、
m = o + n
であるが、ここで、old領域で「生きている」オブジェクト数をoL 「ゴミになった」オブジェクト数をoGとする。 new領域でも同様にnL、nGがある。
o = oL + oG n = nL + nG m = (oL + oG) + (nL + nG)
さて、ここでマークフェーズとスイープフェーズのコストを考える。 従来のGC方式ではマークのコストは、生きているオブジェクト数に依存するので
oL + nL
になる。また、スイープは全部のオブジェクトをスキャンするのでコストは
m (= o + n)
である。
この「世代別」方式でのマークのコストは、 (old→new参照を検出するため)旧世代オブジェクトから全部マークした上、 主にnew領域を対象に通常のマークを行うので、
o + nL
となる。スイープのコストはnew領域のオブジェクトのみになるので
n (= nL + nG)
である。
さて、これを元に旧方式と新方式のコストを比較すると、 マーク時のコストは
旧方式: oL + nL 新方式: oL + oG + nL
で、oGぶんだけ新方式の方が増加している。 経験則からoGは小さいことが期待されるとは言え、 マークコストの増加は痛い。
一方、スイープ時のコストは
旧方式: o + n 新方式: n
で、old領域をスキャンしなくてもよい新方式の方が優れている。
スイープはnew領域だけスキャンすればよいという点で、 有利だが、実はスイープは一気にやらず遅延するテクニックがあるので、 それを使えば差はほとんどなくなるかもしれない。
正確に結果を知るためには、実装して測定してみるのが一番だけど、 こうやって机上で考える範囲内では期待するほど有効じゃないかもな。
世の中甘くない。
550行のCで実装されたTclサブセット。
Tclってのは小さな言語だが、550行ってのはすごい。 先日の(圧縮された)lisp500とちがってまともなコードで550行ということである。
勉強になる、かも。Tclが変な言語であることは置いておくとして。
picolのページには「Rubyなどで書いたら200行以下で実装できるだろう」とあるが、 Haskellで書いたTclサブセット(hiccup)は 250行だそうだ。
とうとう出た。
自分で最終的な判断をするのは、これからGPLv3がどういう意味と影響を持つのか 見極めてから。それまでは、引き続きRubyのライセンスは独自とGPLv2のデュアル。
今の計画では、
のいずれかを考えている。最後のものは最終手段として、できれば避けたいものだ。
Xtalではインスタンス変数は配列として持ち、オフセットで管理される。 一方、RubyやPythonではハッシュテーブルとして持ち、名前で管理される。
これは純粋にトレードオフで、 配列の方がアクセスは高速だし、インスタンス変数のタイプミスがコンパイル時にわかる というメリットもある。しかし、名前によるアクセスも 動的にインスタンス変数が追加できるので、 オープンクラスや特異メソッドに対応しやすいという利点がある。
で、リンク先のエントリでは、XtalとRubyとPythonでベンチマークを取っている。 インスタンス変数に対して加算するという単純なものだが、 結果は
で、配列方式を取るXtalが一番高速であることがわかる。 っていうか、Ruby 1.8遅いな。
ま、配列アクセスの方がずっと高速だからね。
...と、言いたいが話には続きがある。 実はこの同じベンチマークをYARV(1.9)で実行したら、
となった。つまり、どういうことかというと、 (少なくともこのベンチマークでは)インスタンス変数のアクセスコストは支配的な要因ではない、 ということだ。
パフォーマンスに必要以上に注目してしまうことも、 適切でないベンチマークを選んでしまうことも、 私も含めて多くの技術者が陥りやすい罠だ。
ベンチマークは奥が深い。