HotRubyがC Rubyより速い本当の理由は?
JavaScriptが速くて、Rubyが遅い理由というエントリがあったのですが、コメントやトラックバック、追記などを読むと
- 実用上HotRubyがC Rubyより速いというわけではまったくない
- プリミティブ型の有無が原因という話はどうやら間違い
のようです。
とはいえ「↓のベンチマークでHotRubyがC Rubyより速い」というのは事実です。これがなぜなのかちょっと気になったので考えてみました。
startTime = Time.new.to_f sum = "" 50000.times{|e| sum += e.to_s} endTime = Time.new.to_f puts (endTime - startTime).to_s + ' sec'
これについてはRubyが遅いのは本当にBoxingのせいか?が参考になります。まず、C Rubyではベンチマークの += を << に書き換えるとめっちゃ(手元の1.9では約84倍)速くなります。これはなぜかというと、
- += では毎回新しいStringオブジェクトを作って文字列全体をコピーする。ので、文字列長が長くなるほど時間がかかり、全体の計算量はO(N^2)になる。
- << では既存のStringオブジェクトの後ろに文字列をくっつけるだけなので、全体のコピーは起こらない。たまにバッファが足りなくなったときは全体のコピーが必要だが、バッファを倍々で伸ばせば全体ではO(N)になる。
インスタンスの生成も減りますが、それよりO(N^2)がO(N)になったのが大きいです。上の記事の+=版でだんだん時間がかかってるのはこのせいですね。
そうなると上の記事の最後の記述、「HotRuby版では+=でも時間が一定になった」というのが気になります。JavaScriptでは+=を使っても上のコードはO(N)になるということです。これが上のベンチマークでHotRubyがC Rubyより速くなった理由のようです。しかし、どうやってるのでしょう…?
まず「JavaScriptの+=はRubyの<<相当の実装になってるのではないか」と思ったのですが、HotRuby上で a += b を実行すると、JavaScript上では単なる+=ではなく、以下のようなコードが実行されます*1。
function stringPlus(a, b) { var c = a.__native + b.__native; return {__native: c}; } a = stringPlus(a, b);
これを破壊的な連結(Rubyでいう<<)で実装するのはかなり難しそうです。 d = stringPlus(a, b); だったら破壊的に連結してはまずいですからね。
次に考えたのが、JavaScriptの文字列の連結はこんな感じになってるのではないか、というものです。
つまり、a.__nativeのバッファに余裕があったら、そこに詰めてしまう。ただし、個々の変数は文字列の始点と終点を保持してるので、これによってa.__nativeの内容が変わることはない、というもの。この実装ならRubyの<<版と同じで、上のベンチマークはO(N)になります。
これは単なる想像で、実際こうなってるのかは調べていません(知ってる人かFirefoxなどのソースを見た人がいたら教えてください…)が、JavaScriptではRubyのString#<<相当がなく、+=を多用しがちなことを考えると、この手の工夫にはそれなりの効果があるのかもしれません。
2008/8/2追記: shinhさんがFirefoxの(だと思う)ソースから該当箇所を見つけてくれました。どうも上の想像は当たっていたみたいです。
2008/8/4追記: id:bosconoさんによるとWebKitも似たようなことをやってるようです。
*1:これでもかなり端折ってますが。