JavaScriptの正規表現のパフォーマンスに興味があったので調べてみました。 現時点での考察であり、JavaScriptの処理系による違いもありますし、将来的に最適化が進んだ場合は結果が変わることがあると思いますので、ご注意を。

まず、初めに見つけた記事が、これ。

http://stackoverflow.com/questions/9750338/dynamic-vs-inline-regexp-performance-in-javascript

簡単に言うと、

/[a-z]/.exec(str);

と

new RegExp('[a-z]').exec(str);

で、パフォーマンスが違うけど何で？という質問でした。 結論から言うと、これは等価ではありません。 前者は正規表現を一度しか評価しないのに対し、後者は毎回RegExpオブジェクトを作ります。

どうやら、次の3つ関数はほぼ等価のようです。

function func1(str) {
  return /[a-z]/.exec(str);
}

var re2 = /[a-z]/;
function func2(str) {
  return re2.exec(str);
}

var re3 = new RegExp('[a-z]');
function func3(str) {
  return re3.exec(str);
}

「ほぼ」というのは、実際に中身を見たわけではないからです。ただ、処理時間から推測しただけです。

さて、ここまでは理解できていたのですが、実はこの状態だと正規表現のコンパイルは行われていないようなのです。

どういうことかと言うと、

var re4 = new RegExp('[a-z]');
re4.compile();
function func4(str) {
  return re4.exec(str);
}

とすると、処理時間が短くなるケースがあるのです。 これはちょっと意外でした。正規表現のコンパイルというのは最適化の過程で勝手に行われるのかと思っていました。もしかしたら、最適化が行われるのはもっと長い時間処理が回っていないからなのかもしれませんが。

まずは、nodeでテストをしてみました。

https://gist.github.com/dai-shi/7394062

このベンチマークを走らせたら、一つの書き方だけ明らかに速くなりました。それが上記の書き方です。nodeのバージョンをv0.8, v0.10, v0.11と試しましたが、傾向はどれも同じです。

次にjsperfでも試しました。

http://jsperf.com/classname-check-regex-vs-indexof

ちょっと目的が違うのでindexOfとの比較が入っていますが、RegExpの方は大体同じです。 Chromeでの実行結果は、compile()を実行したケースがわずかに速くなりました。試している正規表現が違うので、コンパイルが効きにくいのかもしれません。 Firefoxでの実行結果も、compile()のケースが速くなりました。こちらは10%以上。しかも、全体的にChromeの実行結果より速い。ちょっと意外です。

さて、別のベンチマークも見てみましょう。

http://jsperf.com/javascript-compiled-regex/15

これは、globalマッチのテストケースも入っているのでちょっと分かりにくいですが、それを除けばやっぱりcompile()しているケースが速いです。Chromeで20%ほどアップ。Firefoxで30%ほどアップ。

ちなみに、globalマッチはChromeの場合は最速で、Firefoxの場合はもっとも遅いようです。これは使い方を悩みますね。

これらのベンチマーク結果を踏まえてどういう方針にするかですが、 まず、クライアントサイドのコードの場合は、10%～30%程度速くなることにどれくらい意味があるかですが、ばらつきもあるので、よほどパフォーマンスにシビアでなければ、inline型の正規表現でよいように思います。読みやすいといのが最大のメリットです。つまり、

/[a-z]/.exec(str);

こういう感じです。

一方、サーバサイドのコード、つまり、nodeの場合は、2倍近く速くなるケースもあり、また通常サーバサイドのコードはパフォーマンスを重視することから、現時点ではcompile型の正規表現を使うことに意味があるかもしれません。つまり、

var re = new RegExp('[a-z]');
re.compile();
function func() {
  return re.exec(str);
}

こういう感じです。関数の外で定義しないといけないので、場合によっては気をつける必要があります。変数名の衝突や、意図しない書き換えなど。

var func = (function() {
  var re = new RegExp('[a-z]');
  re.compile();
  return function() {
    return re.exec(str);
  };
})();

のようにする手もありますが、ますます読みにくくなっていきますね。

本来なら、re.compile()がなくてもコンパイルしてくれたらいいように思うのですが、コンパイルそのものにコストがかかるケースもあるので一回しか使わないような場合はコンパイルすべきじゃないということですね。JITなどの最適化はあまり詳しくないのですが、もしかしたら、次第にコンパイルされていくのかもしれません。

と、ここまで書いたところで見つけたのですが、

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Deprecated_and_obsolete_features

あれ、compile()は非推奨なのですね。ということは、やっぱり処理系が最適化の過程でコンパイルしていくのが筋ということですね。 非推奨のcompile()を使うとそれを強制的に動かせるのでベンチマークコードの場合は有利といったところでしょうか。

というわけで結論は、よほどの理由がなければ、inline型を使っておけばよいでしょう。new RegExp()を使ってもパフォーマンスが悪くなるわけではないので、場合によっては使ってもよいでしょう。

ぐるっと回って振り出しに戻った感じですが、個人的にはすっきりしました。

JavaScriptにはJavaで言うところのString.startsWithがないです。みんなどうやっているかというと、

if (str.indexOf('prefix') === 0) {
    console.log('prefix found');
}

みたいな感じのコードをよく見ます。AngularJSのソースでも見ました。でも、これって良く考えると無駄ですよね。indexOfというのは文字列を最初から最後までなめて、一致する位置を探すのです。見つかれば一発ですが、見つからなければ最後まで行って-1を返します。本来、prefixを判定するのなら最初だけ検査すればいいのです。

str.substring(0, 'prefix'.length) === 'prefix'

という書き方も見ますが、これもいまひとつです。substringは新たに文字列を作ってしまうので。結論としては、

str.lastIndexOf('prefix', 0) === 0

が一番いいと思います。lastIndexOfは文字列の後ろから検査するのですが、検査開始位置を0にしているので、判定するのは一回だけです。Javaの内部実装には詳しくないですが、String.startsWithも同じような実装でしょう。

さて、これが本当かを確かめるために、benchmark.jsでベンチマークを書こうかと思いました。いや、せっかくなのでjsperfで書いてみようと思って、書き始めたら、あれ、既に存在する。世の中同じこと考える人はいますね。

http://jsperf.com/string-startswith/3

最後の一つのテストケースは私が追加したものです。 想定通り、lastIndexOfが速いです。ん？しかし、Chromeだとcompiled regexの方が速い。いや、そんなはずは、、。compiled regexが速いのは事実ですが、lastIndexOfが遅いのです。こんな単純な関数でChromeがFirefoxより遅いのは想定外でした。

Chromeで遅いということは、v8が遅いのかと思って、node.jsでもテストしてみました。

https://gist.github.com/dai-shi/4950506

案の定、node.jsでも同様の結果です。 それでも、私はlastIndexOfを使うことをおすすめします。 v8で遅いのはv8が直るべきです。ところで、これはissueになっているのかな？

http://code.google.com/p/v8/issues/list

どうやらなっていないようです。ちょっとソースを覗いてみますか。v8はsubversionです。bleeding edgeブランチが最新のようです。

http://v8.googlecode.com/svn/branches/bleeding_edge/

checkoutしてStringLastIndexOfのソースコードを追ってみましたが、特に単純な問題があるようには見えません。久しぶりのCのソースで頭が疲れます。そりゃそうですよね、天下のGoogleが作っているものがそんな自明なバグを残しているわけないですよね。というわけで、しばらくは様子をみることにします。

ところで、jsperf.comにstring-startswithがあったのが悔しかったので、真似してstring-endswithを作ってみました。

http://jsperf.com/string-endswith

傾向はstartsWithと同様です。ここまで読んでくれたみなさん、suffixチェックするときに、間違ってもnaive indexOfのような書き方はしないように。

JavaScriptで配列を結合したいと思いました。配列の個数は分からず、任意の場合です。

var x = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [], [10]];

を、

var xx = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

に変換したいということです。 SchemeだとSRFI-1にconcatenateというのがあるのですが、JavaScriptはどうするとよいのかと思って調べました。

結論から言うと、

var xx = [].concat.apply([], x);

がよさそうです。

jsperfにベンチマークがありました。

http://jsperf.com/multi-array-concat/9

Safariでは別の書き方(push.applyをループする)の方がよいケースもあるようですが、コーディングの長さも考えると、上記の書き方がベストでしょう。

ついでに、結合する配列が2個に限定される場合のベンチマークも見つけました。

http://jsperf.com/concatperftest/13

この場合は、Array.concatを使うより、Array.push.applyを使うほうがよさそうです。

JavaScriptのお話です。node.jsに限らない話だと思いますが、node.jsでの動作を説明します。

一言で言うと、"g"オプションをつけたRegExpのtest()の呼び出しはループ(?)します。

説明するよりも、実際の動きを見てみましょう。

% node
> re = new RegExp('xyz', 'g');
/xyz/g
> s = 'aaaxyzbbbxyz';
'aaaxyzbbbxyz'
> re.test(s)
true
> re.lastIndex
6
> re.test(s)
true
> re.lastIndex
12
> re.test(s)
false
> re.lastIndex
0
> re.test(s)
true
> re.lastIndex
6

という感じで、re.lastIndexがマッチを開始するインデックスを保持しているようです。で、最後まで行ったら初めに戻ると。

"g"オプションをつけなければこんなことにはならず、lastIndexも常に0のままです。

---

ついでに、RegExp.test()とRegExp.exec()とString.match()とString.search()のベンチマークもしておきました。

一つは、node.js用。
https://gist.github.com/dai-shi/5169296

もう一つは、ブラウザ用。自分で作ろうかと思ったら、既にありました。
http://jsperf.com/regex-test-or-exec-or-string-search-or-match

やはり、正規表現のマッチを確認するだけなら、RegExp.test()が一番よさそうですね。

ちょっと面白い結果だったのはFirefoxのケースで、RegExp.test()とRegExp.exec()の速さがほとんど変わりませんでした。つまり、test()の内部でexec()を呼び出しちゃってる感じです。Chromeとnode.jsでは（どちらもv8だけど）差が出ているので、FirefoxのJavaScriptエンジンは改善の余地があるということでしょう。

前から思っていましたが、Chromeの正規表現の処理は速いですねぇ。Firefoxとは比べものにならないです。