もっと速くするために(スコープ解決コストと正規表現オブジェクトの置き場所)

js 高速化

正規表現オブジェクトをどのように配置すれば効率的なのか調べました。

配置パターン

A. ループ内にべた書き

function job(expr, n) {
  var i = 0, match;

  for (var i = 0; i < n; ++i) {
    match = /regexp1/.exec(expr);
    match = /regexp2/.exec(expr);
  }
}

B. スコープ内(ループの外)に配置

function job(expr, n) {
  var i = 0, match,
      REX1 = /regexp1/,
      REX2 = /regexp2/;

  for (var i = 0; i < n; ++i) {
    match = REX1.exec(expr);
    match = REX2.exec(expr);
  }
}

C. 5つ外側のスコープに配置

(function() {
var _REX1 = /regexp1/,
    _REX2 = /regexp2/;

 (function() {
   (function() {
     (function() {
       (function() {
         (function() {
           function job(expr, n) {
             var i = 0, match;

             for (var i = 0; i < n; ++i) {
               match = _REX1.exec(expr);
               match = _REX2.exec(expr);
             }
           }
         })();
       })();
     })();
   })();
 })();
})();

D. 5つ外側のスコープに配置し、関数内に export する(スコープ解決用に変数/定数の Alias を作成する)

(function() {
var _REX1 = /regexp1/,
    _REX2 = /regexp2/;

 (function() {
   (function() {
     (function() {
       (function() {
         (function() {
           function job(expr, n) {
             var i = 0, match,
                 REX1 = _REX1, REX2 = _REX2; // alias

             for (var i = 0; i < n; ++i) {
               match = REX1.exec(expr);
               match = REX2.exec(expr);
             }
           }
         })();
       })();
     })();
   })();
 })();
})();

実際にはもうちょっと色々とあるけど、興味深いスコアが出たのが上の4つ。

普通に考えると「A は遅そう、B は速そう。C は B より遅そうで、D は効果がありそうだけど、良く判らない」って感じですかね。

テスト方法

1. job を 100000回呼び出す, n = 1
2. job を 1000回呼び出す, n = 100
3. job を 1回呼び出す, n = 100000

どのテスト方法でも、各正規表現オブジェクトは、計10万回評価されます。

ポイントは

  • 正規表現オブジェクトはキャッシュされるのか?
  • ネストしたスコープの名前解決コストはどれぐらいなのか?
  • 関数呼び出しにより正規表現オブジェクトのキャッシュがどうなるか?
    • ガベージが遅いブラウザ(IE6, IE7)でキャッシュが破棄される場合にスコアがどうなるか
  • クロスブラウザかつ万能な記述方法は存在するのか、状況に応じてコードの書き方を変化させるべきか?

といった感じです

結果

IE6 と IE7 はそれぞれ別の PC で測定しています(IE6 は ASPIRE ONE)
IE8 とその他のブラウザは同じ PC で測定しています。

IE6
＼ A B C D C と D の速度比較
1 6266 6172 4896 4890 とんとん
2 5516 3333 3938 3307 D が +16%
3 5541 3338 3953 3297 D が +16%
  • A と B はループ内で正規表現オブジェクトをそのつど生成してるので遅い(関数が呼ばれるたびに、正規表現オブジェクトを生成する)
  • D-2, D-3 は C-2, C-3 と違い名前を解決してあるため、16% 高速

ちなみに、C や D は 匿名関数で5重にネストしてますが、これが1重になると、D-1, C-1 で 約430ms 速くなります(4890 ⇒ 4459)。
10万回 job 関数を呼び出すと、スコープを5つ上までさかのぼって名前を解決するのに 430ms 掛かるってことですね。

IE7
＼ A B C D C と D の速度比較
1 3005 3037 2169 2246 D が -2%
2 2637 1612 1799 1612 D が +9%
3 2662 1591 1794 1597 D が +9%
IE8
＼ A B C D C と D の速度比較
1 2677 2672 2047 2073 D が -1%
2 2580 1776 1927 1745 D が +9%
3 2547 1740 1922 1740 D が +9%
Firefox 2.0
＼ A B C D C と D の速度比較
1 2113 2150 5922 6053 D が -2%
2 2069 2072 3714 2078 D が +44%
3 2052 1995 3562 1969 D が +44%
  • C-1 や D-1 が A-1 や B-1 の 3倍遅い
    • Firefox 2 に限り、呼び出し回数の多い関数の中では、外部の名前を解決しなくても済むような特別な工夫が必要です。
      • たとえば、関数の外側でループさせているのを、関数の内側でループさせるように書き換えるとか。
    • Firefox 2 では、ループコストや正規表現の評価コストよりも、スコープ解決コストが高速化の鍵になりそうです。
Firefox 3.0
＼ A B C D C と D の速度比較
1 - 1306 1469 1373 D が +6%
2 - 1246 1305 1242 D が +5%
3 - 1336 1520 1337 D が +12%
  • A-1, A-2, A-3 のデータは取ってません。
Firefox 3.5 (JIT 有効)
＼ A B C D C と D の速度比較
1 1005 990 1257 1288 D が -2%
2 - 988 998 1010 D が -1%
3 - 1025 972 990 D が -1%
  • A-2, A-3 のデータは取ってません。
Opera 10.0
＼ A B C D C と D の速度比較
1 1864 1855 1912 1901 とんとん
2 1777 1776 1865 1782 D が +4%
3 1781 1780 1844 1792 D が +3%
  • Opera 9.5, Opera 9.6 はベンチマークが完走しないため(CPUを食いつぶした後に遮断される)、スコアがありません。
Safari 4.0(530.17)
＼ A B C D C と D の速度比較
1 645 651 426 452 誤差
2 - 545 425 418 誤差
3 - 568 429 412 誤差
Google Chrome 4β(4.0.203.2)
＼ A B C D C と D の速度比較
1 178 181 177 182 誤差
2 - - - - -
3 190 179 182 179 誤差

まとめ

D は C よりも速く、遅いブラウザ(IE6, IE7) などでは、B よりも D のほうが速いという結果がでました(Firefox2 は一捻り必要そうですが)。

トリミング用の正規表現( replace(/^\s+|\s+$/, "") )などのように、複数の関数から利用される正規表現オブジェクトをループ内で多用する場合は、スコープ解決用のaliasを作ってやると、軽くできるかもしれませんね。

(function() {
var _REX1 = /regexp1/,
    _REX2 = /regexp2/,
    _hoge = {},
    _huga = [];

 (function() {
   (function() {
     (function() {
       (function() {
         (function() {
           function job(expr, n) {
             var i = 0, match,
                 REX1 = _REX1, REX2 = _REX2; // alias

             for (var i = 0; i < n; ++i) {
               match = REX1.exec(expr);
               match = REX2.exec(expr);
             }
           }
         })();
       })();
     })();
   })();
 })();
})();

alias は、PHP の global にも似てますね。

IE(とSafari) では関数が呼ばれる度に正規表現オブジェクトが構築されます。面倒でも大外で定義したオブジェクトを利用したほうが良い結果になりそうです。

これ(↓)でもいいけど

function job(expr, n) {
  var REX1 = /regexp1/;
  ... 色々 ...
}

こっち(↓)だと、関数呼び出しの度にオブジェクトの生成と破棄が発生しない ⇒ ガベージレス ⇒ CPU/メモリ負荷が軽い ⇒ UIが軽くなる

var _REX1 = /regexp1/;

function job(expr, n) {
  var REX1 = _REX1
  ... 色々 ...
}

追記

「5重もネストさせるようなコード普通は書かないよ〜大げさだなぁ」と、感じる方もいるかと思いますが、jQuery とかのライブラリは、jQuery(...).width() とか呼ぶだけで、10重とか関数呼び出しがネストしてるもんですよー。

深いネストも問題ですが、ネストの深部で即値(そこで使うためにそこで作る値とかオブジェクト)を多用すると、旧式のブラウザではどうあがいても速くなりません(ガベージが発生してUIがシャックリする)。が…このエントリで紹介したように、スコープを解決する方法を取り入れると、多少は改善できるかもしれません。

div>div>div>div>div>... などのように、ギチギチに多重ネストしてるDOM 要素を、チラツキ無しでスムーズにドラッグ＆ドロップできないのと一緒ですよー(嘘

裏を返せば… ネストが浅くなるように jQuery を書き直すと、今よりもっと速くなると思いますよ。トレードオフとしてコード量が1.5〜2倍ぐらいに膨らみそうですけどね。
# 誰かチャレンジしないかな。なかなか面白いと思うんだけど。