miura1729の日記

配列の高速化を実装しました

21:17 |

yarv2llvmはデータマイニングやグラフィックスなど速度が必要なプログラムで、Hot spotになっているところを高速化するという感じで使うことを考えています。このような場合、行列計算など配列の操作が多いのではないかなと思います。

これまで配列の参照(opt_aref)はrb_ary_entryを呼び出すことで行っていたのですが、この場合は関数呼び出しとインデックスの範囲チェックの分オーバヘッドを生じます。そこで、インデックスの範囲チェックを行うか否かを指定するコンパイルオプションを作りました。オプションで、範囲チェックをしないとすると、rb_ary_entryを呼び出す代わりに配列の構造体を直接アクセスするコードが生成されます。

ただし、この機能には問題があってほとんど実用になりません。というのは、Rubyの最新版では配列は要素数が4以上と未満でデータ構造が異なるからです。アクセス時に場合分けすればいいのですが、そうすると速度低下してしまいます(それより面倒ってのが大きい)。配列の操作で高速化したいのは要素数が多い配列でしょうから場合分けするより、配列の要素は４以上だと決めてしまった方がいいと判断しました。そういうことで、範囲チェックしないオプションを指定すると、テスト(test/test_compile.rb)が失敗して、Segmentation Faultが出ます。

そういうリスク一杯の機能ですが、eを約10000桁求めてみると(http://d.hatena.ne.jp/miura1729/20081116/1226837201)こんな感じでちょっと効果があります。

範囲チェックあり(これまで)
real	0m2.676s
user	0m1.904s
sys	0m0.654s

範囲チェック無し
real	0m2.085s
user	0m1.622s
sys	0m0.498s

Ruby 1.9.0で実行した場合
time ruby19 -r sample/e-aux.rb -e 'compute_e'
real	0m13.151s
user	0m13.061s
sys	0m0.124s