5倍速いSquirrelFish Extremeの正規表現エンジンWREC

「recursive callを得意とするV8が、recursive callに比重をおいた、V8 Benchmark Suiteで速い!速い!と語られるのはフェアではない」

今回、正規表現のみに焦点を当ててJavaScriptエンジンを比較してみた。

環境

• SpiderMonkey - 1.7.0 2007-10-03
• SFX - Revision: 37445
• v8 - Revision: 389

SFX(SquirrerlFish Extreme)に新しく搭載されたWREC("the WebKit Regular Expression Compiler")、Safari 3に搭載されているJavaScript Coreに比べて、なんと5倍も速い。正規表現の実行が占める実行時間が、Webアプリケーション全体の実行時間の3%ほどだとすれば、WRECは、2.4%ほどの高速化に貢献している。

V8, SFX, SpiderMonkey, Safari 3でregexp-dna.htmlをベースに作成したベンチマークスクリプトでベンチマークを計測した。スループット(1分間の実行回数)を算出しているので、グラフが大きい方が高性能。(5回測定した結果の中央値を利用)



SFXが、Safari 3の6.44倍も速いという結果がでた!!公式に発表されている結果では、5倍だからそれよりも速い!が、String.prototype.replaceメソッドの実装に差があるため、この結果はフェアではない。regex-dna.jsを修正し、実行した結果は次の通り。

実行結果


公式の発表に近い、Safari 3の5.19倍速いという結果がでたので、概ね正しそうだ。

regexp-dna.jsの修正内容は、次のとおり。

<  dnaInput = dnaInput.replace(k, subs[k], "g")
---
>  dnaInput = dnaInput.replace(new RegExp(k, 'g'), subs[k]);

String.prototype.replaceの実装の差
ECMAScript262によるString.prototype.replace(searchValue, replaceValue)の定義では、第三引数は受付けないが、MozillaのSpiderMonkeyでは、第一引数に文字列が渡された場合に、第三引数に正規表現フラグを指定できるように拡張している。

もうひとつ。SpiderMonkey(js), SFX(jsc), v8(v8-shell)でString.prototype.replace関数の比較をすると、SFXの実装だけ明らかに他の2つとは異なることがわかる。

% js
js> 'aaaaa'.replace('a', '_$&_', 'g') # SpiderMonkeyでは、gフラグが有効
_a__a__a__a__a_

% v8-shell
V8 version 0.2.5
> 'aaaaa'.replace('a', '_$&_', 'g') # v8では、gフラグは無効
_a_aaaa

% jsc
> 'aaaaa'.replace('a', '_$&_', 'g') # SFXでも、gフラグは無効
_$&_aaaa
>'aaaaa'.replace(/a/, '_$&_', 'g')
_a_aaaa

WRECでは、第一引数が通常の文字列の場合は、通常の文字列置換が行われ、第二引数の置換テキスト($&)が展開されない。SFX中では、"WebKit/JavaScriptCore/kjs/StringPrototype.cpp"にString.prototype.replaceの実装があるが、文字列を探索して、マッチした以前の部分、置換する文字列、マッチした後の文字列を連結して返している。

WebKit/JavaScriptCore/kjs/StringPrototype.cpp

JSValue* stringProtoFuncReplace(ExecState* exec, JSObject*, JSValue* thisValue, const ArgList& args)
{
   // 引数の処理
   if (pattern->isObject(&RegExpObject::info)) {
     // 第一引数がRegExpオブジェクトのケースの処理
   }
   // 第一引数が文字列の場合
    // First arg is a string
    UString patternString = pattern->toString(exec);
    int matchPos = source.find(patternString);
    int matchLen = patternString.size();
    // Do the replacement
    if (matchPos == -1)
        return sourceVal;

    if (callType != CallTypeNone) {
        ArgList args;
        args.append(jsSubstring(exec, source, matchPos, matchLen));
        args.append(jsNumber(exec, matchPos));
        args.append(sourceVal);

        replacementString = call(exec, replacement, callType, callData, exec->globalThisValue(), args)->toString(exec);
    }

    return jsString(exec, source.substr(0, matchPos) + replacementString + source.substr(matchPos + matchLen));
}

String.prototype.replaceの第一引数が文字列の場合に、単純な文字列置換をおこないパフォーマンスを向上する最適化は、SpiderMonkeyでもとりこまれる予定だ。(See Bug 432525)

WRECでは、グルーピングは未実装
シンプル!軽量!速い!と3拍子そろったWRECだけど、グルーピングの機能は実装しておらず、グルーピング付きのパターンが指定された時は、PCREに処理を任せることになるため、実行速度が低下する。

bool WRECParser::parseParentheses(JmpSrcVector&)
{
    // FIXME: We don't currently backtrack correctly within parentheses in cases such as
    // "c".match(/(.*)c/) so we fall back to PCRE for any regexp containing parentheses.

    m_err = TempError_unsupportedParentheses;
    return false;
}

regepx-dna.htmlのベンチマークでグルーピングありとなしを比べると実行速度の差が明らかになる。実行時間が変更前の140%になったSpiderMonkeyに比べて、SFXは、680%もの増加となった。

変更前

>  dnaInput = dnaInput.replace(/g*t/g, subs[k]);

% jsc regexp-dna.js
285 (msec)

% js regepx-dna.js
1789 (msec)

変更後 (SFXでは、680%の速度低下)

>  dnaInput = dnaInput.replace(/(g*)t/g, subs[k]);

% jsc regexp-dna.js
1942 (msec)

% js regexp-dna.js
2501 (msec)