Hatena::ブログ(Diary)

ぼちぼち日記

2012-07-13

Googleが示すJavaScriptを350倍高速化する秘訣

1. はじめに、

今年も Google I/O が開催されました。一度も現地に行って参加したことはないのですが、毎年セッションの内容は技術的に高度なものばかりでいつも注目しています。今年の一つ興味深いセッションで、

Google I/O 2012 - Breaking the JavaScript Speed Limit with V8 (Daniel Clifford)スライド ,ビデオ

というのがありました。(ビデオ・資料をすぐ公開してもらえるのはホントありがたいです。)

ご存じの通り V8 は Chrome に搭載されているばかっ速い JavaScript エンジンで Node.js でも採用されています。このセッションは、 V8 の内部実装の解説を元にどう JavaScript の実行速度がパフォーマンスチューニングができるかという内容で、もうこれは必見で見逃せないものです。

最初、資料だけ公開されたのでパラパラと内容を見たところ、

  • 「サンプルコードの比較で現状JavaScriptはC++より5倍遅い。これをどこまで速くできるのか?」
  • 「JavaScriptは、C++ より60%速くなった!
  • 「最終結果: JavaScript が当初より350倍以上速くなった!

などが書いてあるのが読めて、もう驚いて
f:id:jovi0608:20120713031710p:image
なことをツィートしました。でも改めてビデオと資料を見直したところ、
「ごめんなさい、間違ってました。(_o_)」
完全に釣りネタの数字にひっかかってしまいました。別にプレゼンが悪いわけではなく、中身をちゃんと読まずに早とちりした私が悪いのです。
ということで反省の代わりに、この釣りネタ数字に関する解説記事を書いてみたいと思います。
なお、本筋のV8の最適化手法 Hidden Class/Inline Cache/Profiling 等々のネタはこれはこれで非常に貴重な情報です。でも一つ一つがとても重い内容なのでまたの機会にできたらと思います。

2. セッションの内容

セッションでは具体的なJavaScriptの性能向上させる例として、

お題:25,000番目の素数を計算しなさい

が取り上げられました。これを JavaScript と C++ で実装した場合の実行速度の比較を解説しています。(実際のコードは、このスライド )
話の流れとしては、

  1. 最初 C++: 3秒、JS:15.5秒で C++ は JavaScript の5倍早い。これをどこまで速くできるかやってみよう。
  2. V8の内部実装とそれに関連する様々な最適化の手法の説明。
  3. C++: 3秒、JS:1.8秒で JavaScript は C++ よりの60%速くなった
  4. 最終的に JS:0.04秒になり350倍以上の性能向上を達成した!

というものでした。これじゃ
「V8の最適化で350倍の性能向上、すげぇ〜!」
って誤解しますよねw
次にそれぞれの速度向上要因の理由を書いてみます。

2.1 JavaScript が C++ より5倍遅かった理由

なんと! JavaScriptコードのバグによるもの。for 文で回すインデックスの最後の条件が間違っています。既に計算された素数の個数分(this.prime_count) 回すのですが、素数が格納されている配列のインデックスは this.prime_count-1 までです。なのに this.prime_count まで1個余分に回しています。

for (var i = 1; i <= this.prime_count; ++i) {
    if (candidate % this.primes[i] == 0) return true;
}

正解は、

for (var i = 1; i < this.prime_count; ++i) {
    if (candidate % this.primes[i] == 0) return true;
}

これでバグ入りの方は最後の要素が undefined になり、「ループの回数が余分 + candidate/undefined(=NaN)の計算」分だけオーバヘッドがかかるため結果的に C++ より5倍遅くなっています。
セッションではこのバグをプロファイラーを使って見つられるというストーリになっています。

2.2 JavaScript が C++ より 60% 速かった理由

これを見た時「JavaScriptがC++のネイティブコードの実行より速くなることがあるのか!」って普通不思議に思いますよね。 その理由は、C++コードをコンパイルするときに最適化オプションを付けていなかったためでした。(要は C++ の最適化が足りなかった。) -O3 オプションを付けてコンパイルすると C++ の実行速度が倍近く速くなり、結果 JavaScriptの実行速度は C++ より17%遅くなりました。(実は JS と C++ で17%しか性能が違わないという方が凄いと思うけど)

2.3 JavaScript が 350倍性能向上した理由

単純明快計算ロジックを変えたためでした。素数候補の整数の割り算を平方根の値で打ち切るロジックを組み込みました。ある整数がある素数の2乗の値だったとわかるまでが一番計算量が多いわけですからね。

for (var i = 1; i < this.prime_count; ++i) {
  var current_prime = this.primes[i]; 
  if (current_prime * current_prime > candidate) { return false; }
  if ((candidate % current_prime) == 0) return true;
}

実際、このアルゴリズムの変更が大きく効いて、割り算までたどり着くループの回数が 1/100 まで減少してます。こりゃ数百倍高速になるわけだ。

3. まとめ

以上をまとめると以下の通りです。

性能評価理由
JavaScript が C++ より5倍遅いJavaScriptコードのバグ
JavaScript が C++ より 60% 速いC++の最適化コンパイルオプションの付け忘れ
JavaScript が 350倍性能向上したアルゴリズムの変更で計算量が1/100に減少

ということで V8 に特化したチューニングでもなんでもなかったというわけです。ちゃんと読めば書いてあるし、プレゼンで間違ったことは話されていません。
でも、実はこのプレゼンで Googler が言いたかったことは、
「お前ら細かい技術的なテクニックに期待する前にバグ修正やアルゴリズムの見直しをきちんとやれ。そうしたら JavaScript のコードが 350倍 にも高速になるぞ!」
というオチだったんじゃないかと思ったりします。

4. さらなる独自解析を行うと、

やっぱりこれで終わっちゃったらちょっと物足りないので、「JavaScript が C++ より5倍遅い」ケースをもう少し独自に何パターンかで解析してみます。

4.1 NaN演算を避ける

このスクリプトでよくある undefined を除く条件を if文の頭に入れてみたらどうなるでしょうか? この手当をすると NaN の演算を避けることができます。

for (var i = 1; i <= this.prime_count; ++i) {
    if (this.primes[i] && candidate % this.primes[i] == 0) return true;
}
4.2 配列要素の型をそろえる

そして配列評価の最後が undefined になっているのをあえて 0 を入れてみます。これだと評価される配列は全て整数でそろいます。

this.primes[this.prime_count] = 0;
for (var i = 1; i <= this.prime_count; ++i) {
    if (this.primes[i] && candidate % this.primes[i] == 0) return true;
}
4.3 別の型の配列要素が混じったらどうなる?

4.2の反対で、これは文字列を最後に入れた場合との比較でどこまで性能が落ちるのかを見てみます。

this.primes[this.prime_count] = '0';
for (var i = 1; i <= this.prime_count; ++i) {
    if (this.primes[i] && candidate % this.primes[i] == 0) return true;
}
4.4 結果

上記の実行結果は以下の通りになります。


ケース実行結果[sec]
バグ有14.46
NaN演算を避けた場合4.48
整数配列に全部そろえた場合2.51
配列の最後を文字列('0')にした場合3.94
バグフィックス版2.03

この結果からわかるのは、

  • NaN 計算を避けると高い性能向上が見込まれる
  • 配列の要素をすべて整数(というか同じ型のプリミティブ)にすると性能向上する

ということです。やっと本来の性能向上ネタにもどることができました。

このセッションでは、V8の実装に特化した最適化手法がいくつか述べられていますが、多くは JavaScript の動的型付けの「ゆるさ」から来ているものです。
静的型付けな形を意識してJSのコード書くとJSらしさはなくなりますが、実は結果的にV8の最適化に近いものになり、ひいてはV8固有じゃなくて他の実装でもそこそこ最適化されたコードになるんじゃないかと思ったりもします。
それなら、と Dart や JSX に行っちゃうのもわかりますね。

su--18820su--18820 2012/07/14 02:06 アルゴリズムを改良した計算をC言語でも行って比較すると、より誤解が少なくなります。

twittertwitter 2014/04/21 13:43 >ある整数がある素数の2乗の値だったとわかるまでが一番計算量が多いわけですからね。
これは間違いで、nが素数であることを確認するためには√n以下の素数で試し割りするだけで十分だからです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証