l'essentiel est invisible pour les yeux

Monday, October 13, 2008

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
%

Thursday, October 09, 2008

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)