FIFO/LIFO trial

これは何

rubyでスタック・キューを作る実装をbddで進める課題の練習

せっかくふるまいを定義したので、c拡張とpure rubyで同じものを作成し、ベンチマークをとった

課題についてはbdd-stackを参照

benchmark

$ ruby bench/bench.rb

1. スタック

	user	system	total	real
LIFO (c ext)	0.150330	0.002457	0.152787	0.153376
LIFO (ruby)	0.044496	0.001956	0.046452	0.046825

2. キュー

	user	system	total	real
FIFO (c ext)	0.152509	0.002391	0.154900	0.155512
FIFO (ruby)	0.050082	0.000594	0.050676	0.051421

データ挿入と取り出しをそれぞれ100,000回連続で行い比較した

• スピードはrubyの方が約３〜４倍速い

• ソースの行数はcが90〜100行に対して、rubyは35行〜50行で半分以下。

rubyが圧倒的にコンパクトに書ける。しかも雑につくったcより全然速い。

結論

＿人人人人人人人人人人人人人＿
＞　C Launguage is dead 　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣

敗因と今後の予定

• cからrubyオブジェクトを生成・操作しているだけなので、C言語の良さが全く生きない

• リストを持つのにクラスをつくるのではなく、VALUEのアドレスを保持するような素の構造体を使うと早くなる（ような気がする）

• これをやるとGCにVALUEを持っていかれそうな気がするので、もうちょっと挙動を理解したい 　 　

---

　

（後日談）リベンジしました

rubyのオブジェクトを生成・操作するコストがボトルネックだろうと踏んで、ネイティブなc構造体で実装してみた。

３番目がc構造体による実装結果。

	user	system	total	real
LIFO (c ext)	0.150330	0.002457	0.152787	0.153376
LIFO (ruby)	0.044496	0.001956	0.046452	0.046825
LIFO (c struct)	0.027673	0.002248	0.029921	0.030232

かろうじて２倍弱のパフォーマンスが出ました。

＿人人人人人人人人人人人人人＿
＞　C Launguage is alive  ＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣

この程度だとJITが入ったら大差なくなるのではという予感...

なお、以下のように実戦には耐えない残念な仕様です。

• グローバル変数。全てのインスタンスが１つのスタックを指している

• rubyオブジェクトをスタックに積む時に、GC対策として一応マーキングした。（pop時にアンマークできるかわからないがたぶんメモリリークする）

• スレッドセーフかどうかなんて1mmも考慮されてない 　 　

---

　

苦労したところ

• 頑張ってvimだけで開発してみたが開発時間と脳ミソの半分をvimに捧げることになった

• コンパイルが通るまで時間がかかった。init_xxxx の関数名と extconf.rb の指定の不一致（大文字・小文字の違い）でハマる

• queueを単方向リストで表現するのはちょっと面倒。双方向リストの方がよかったか

Special Thanks

そもそもスタックを書いてみようという気になったのは@yalab師のお導きによります。 また資料としては、たまたま取り組んでいた神資料を盛大に読み返しました。 これがなかったら不可能でした（心で合掌）

c拡張時のお作法全般については、こちらを、GCについてはこちらやこちらなどを参照しました。