SFX VM 命令コード作成とバイトコードのプリティプリントのメモ

Revision 37555時点で、106の命令コードが実装されていて、103の命令コードについてドキュメントがコメント形式で与えられている。

命令コードドキュメントの生成

% cd /path/to/WebKit/JavaScriptCore
% perl docs/make-bytecode-docs.pl VM/Machine.cpp docs/bytecode.html

バイトコードプリティプリント
DEBUGモードでビルドした時のみ、バイトコードを表示するための-dオプションが有効です。

date_test.js

var d = new Date();
print(d.getFullYear(), 1 + d.getMonth(), d.getDate());

% ./JavaScriptCore/build/Debug/jsc -d date_test.js
18 instructions; 388 bytes at 0x905b50; 1 parameter(s); 18 callee register(s)

[   0] enter
[   1] mov               r-14, r0
[   4] mov               r2, r0
[   7] resolve_global    r3, [object global], Date(@id0)
[  13] get_by_id         r4, r3, prototype(@id1)
[  21] construct         r-14, r3, r4, 5, 1, 14
[  28] construct_verify  r-14, r5
[  31] resolve_func      r2, r3, print(@id2)
[  35] get_by_id         r6, r-14, getFullYear(@id3)
[  43] call              r5, r6, r-14, 7, 1, 16
[  50] mov               r7, r1
[  53] get_by_id         r8, r-14, getMonth(@id4)
[  61] call              r9, r8, r-14, 9, 1, 18
[  68] add               r6, r7, r9
[  73] get_by_id         r8, r-14, getDate(@id5)
[  81] call              r7, r8, r-14, 9, 1, 18
[  88] call              r2, r3, r2, 4, 4, 16
[  95] end               r2

Identifiers:
  id0 = Date
  id1 = prototype
  id2 = print
  id3 = getFullYear
  id4 = getMonth
  id5 = getDate

Constants:
   r0 = undefined
   r1 = 1

StructureIDs:
  [   7] resolve_global: 0x0
  [  13] get_by_id: 0x0
  [  35] get_by_id: 0x0
  [  53] get_by_id: 0x0
  [  73] get_by_id: 0x0

2008 10 13
End: undefined
LEAK: 135 StructureID
%                                                                              

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)