monthly gimite

試験運用中。

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:これでもかなり端折ってますが。