さよならKnuth先生〜CRubyのGC編〜

振り返れば、もうそれは二年前のRubyKaigi…。
http://image.slidesharecdn.com/lazysweepgc-100827072707-phpapp01/95/slide-207-728.jpg

やるやる詐欺を続けていたマーク関数の再帰呼び出しを辞めるやつをコミットしました。

Knuthのスタック溢れ対策

オブジェクトのツリーをtraverseするときにマーク関数の再帰呼び出しを使ってたんですが、これだとオブジェクトが深ーい参照構造を持っていた時にマシンスタックを使いきってスタックオーバーフローしちゃうんですね。
それで、そういうのを回避するために『Art of Computer Programming Volume 1』の415ページ、アルゴリズムCを今まで使っていたわけです。
(もちろん、もってるでしょう?)

これはかなり初期の頃にコミットされています。おお、もう十年前ですね。

それは今回のコミットでばっさりと消しました。さよならさよなら。

マーク、再帰呼び出し辞めるってよ

基本的にはメール書いたことがほとんどなんですが、自前でCのヒープ上にスタック作ってそこを利用してマークするようにしました。

この辺の論文を参考にして、フロントにqueueを置いてキャッシュミスを少なくするみたいなこともやってみたんですが、あんまり早くならなくて…。がっかりでした。

たぶんスタックからキューへ入れ替えるときのコストがやっぱ高いんですよねぇ。

そう思って全部キューで書いてみたらすげー遅くなってさらにがっかり。

たぶん突っ込んだデータと取り出すデータが離れすぎるんで、全部キューだと遅くなっちゃうのかなぁ。

結局、フツーに作ったものをコミットしました。

なにがよくなるのか

深ーいツリー構造とかグラフを持つようなオブジェクトが作った場合にGCプレッシャーが少ないです。
あとFiberだと稀にGCでスタックオーバーフローすることがあったわけですが、それがなくなります。

さよなら、小津先生 DVD-BOX

さよなら、小津先生 DVD-BOX

以上、『We code』でした。