« 出張Shibuya.js 24の発表資料 | メイン | Xbyakで始めるx86(IA-32)入門 »

実行時のインライン+ループ展開による高速化例

出張Shibuya.js 24の発表資料の中の,JavaScriptで実行時に関数を書き換えることで高速化する例を紹介します.オリジナルアイデアはokuさんで,JavaScriptの勉強のために私もやってみました.

ここでは二つの関数unrollLoop()とforceInline()を作ってみました.たとえば,

add3 : function(y) {
    return y + 3;
}

addF : function(x) {
    var z = 2;
    for (var i = 0; i < 3; i++) {
        z += this.add3(i);
    }
    return z;
}

という関数があるとします.
addF()に対してblowfish.js(仮実装なので実用性はまだありません)にあるunrollLoop()を適用すると,addF()が書き換えられて

function(x) {
    var z = 2;
        z += this.add3(0);
        z += this.add3(1);
        z += this.add3(2);
    return z;
}

とループ展開されます.更にforceInline()を適用すると,

function(x) {
    var z = 2;
    {
        var _y = 0; z+=(_y + 3);
    }
    {
        var _y = 1; z+=(_y + 3);
    }
    {
        var _y = 2; z+=(_y + 3);
    }
    return z;
}

とインライン展開されます.
ここではBlowfish暗号化のコア部分の最適化を各種方法で試した速度比較をするデモ(JavaScriptを有効にしてください)を用意しました.
比較対象はoriginal(リファレンス実装),自動インライン展開,自動ループ展開,自動インライン展開 + ループ展開,手動最適化の五つです.それらの処理時間を測定し,オリジナルに対する速度比を表示します.

自動インライン,ループ展開による速度向上率の比較
originalforceInlineunrollLoopunrollLoop + forceInline手動最適化(参考)
IE1.01.031.641.732.20
Fx1.01.131.281.411.46

上記のようにIE6で1.73倍,Fxで1.41倍高速化されました.特にFxでは手動最適化にかなり近い値となっています.オリジナルコードに1, 2行追加するだけこの速度向上を得たわけですから,このような手法が有効であることがわかりました.

なお,これらの関数は暫定版なので,複雑な式だとうまく展開できません(ソースをみればわかりますがかなりの手抜きです).

# 引き数を一つしかとれない.'{}'の対応をチェックをきちんとしていない.returnで終わってないといけないなど.

しかし,比較的効率よく高速化されることが分かりましたのでライブラリとして完成度をあげてみるのも面白いかと思います.

コメント (6)

dsk:

自動出力コードの閉括弧「}」が2つほど少ないせいで、当方のSafariだとevalの行でParse Errorとなります。

あとdocument.write()はデバッグ的に極悪なので例えば<div id='out'></div>としておいて(タグの開閉は全角になってます)、onLoad()とかで
document.getElementById('out').innerHTML += 内容;
としてもらえると、デバッグしやすいです。
(onLoadだととりあえずはHTMLが全部読み込まれてから実行、document.writeはHTMLのパーズ中に実行するので、他の要素を付け足しにくいです。

へるみ:

>当方のSafariだとevalの行でParse Errorとなります。
少し見てみました.
Safariでは
function() {
var s = 0;
for (var i = 0; i < 3; i++) {
s += i;
}
}
という関数をalert()するとfor()のvarが消滅してparseに失敗してるようです.対処はあとで考えてみますが,不思議ですね.

dsk:

確かにforのvarはありませんが、その場合はparseErrorではなくてiが定義されていない、というエラーになります。今回のエラーはそれ以前の問題で、
this.encCore2 = function (inOut)
{
var xL = inOut[0];
var xR = inOut[1];
var P = this.P;
var S0 = this.S0, S1 = this.S1, S2 = this.S2, S3 = this.S3;
var F = this.F;
var x;
for (i = 0; i < this.N; i += 2)
{
x = xL ^= P[i];
{
var _x = x;
{
var a, b, c, d, y;
d = _x & 255;
_x >>= 8;
c = _x & 255;
_x >>= 8;
b = _x & 255;
_x >>= 8;
a = _x & 255;
y = this.S0[a]+this.S1[b] ^ this.S2[c]+this.S3[d];
xR^=(y);
}
x = xR ^= P[i+1];
{
var _x = x;
{
var a, b, c, d, y;
d = _x & 255;
_x >>= 8;
c = _x & 255;
_x >>= 8;
b = _x & 255;
_x >>= 8;
a = _x & 255;
y = this.S0[a]+this.S1[b] ^ this.S2[c]+this.S3[d];
xL^=(y);
}
}
xL = xL ^ P[16];
xR = xR ^ P[17];
if (xL < 0)
xL += 4294967296;
if (xR < 0)
xR += 4294967296;
inOut[0] = xR;
inOut[1] = xL;
}
→この行でparseエラーが出る。
という感じです。247-248行目を
out = destName + ' = ' + out;
out += (destName.substr(0,destName.length-1) == 'this.encCore')? '}}': '';
eval(out);
とすると、parseErrorはなくなりました。というかきちんとblowfishを計算しているようです。

関係ないですが、
forceInline('name', func, applyFunctionName)として、
eval('destname = ' + out);
とするより、
name = forceInline(func, applyFUnctionName)として、
return eval(out);
とする方がforceInline()の中から参照できない変数にも結果を代入できて便利?だと思います。

dsk:

1点勘違いです。
for(i = 0; i <3; ++i)のようにvarがないのがparseErrorにならないのはEcma262のfor文のSyntaxで
for( ExpressionNoIn_opt; Expression; Expression) ....
というのがあり、i = 0はExpressionNoIn_optになり得るから正しいのですが、実はRuntimeErrorにもならずに、グローバルのiがその場で作られて代入されますね。本件の場合、最初に必ずi=0されて中身もiのスコープによって差異の出る記述がないので結果に差異はないです。一般的には差異が出ると思うのでvarを勝手に消すのはおかしいと思いますが。
Ecma262の仕様だとtoString()はスペースや改行、コメント、省略可能なセミコロンなどの扱いは実装依存だそうです。すなわち勝手に改行したりセミコロンを省いたり補ったりは自由。

へるみ:

コメントが遅くなって申し訳ありません.
>一般的には差異が出ると思うのでvarを勝手に消すのはおかしいと思いますが。
そうですね.私もvarがなくなるとglobalかそうでないのかわからなくなるのでおかしいと思いました.
toString()の結果が,本来なら改行などに依存すべきでないのも承知していますが,手を抜いています.
動的とは言え,結果は静的なので別にJSでやらなくても別のLLなどによるプリプロセッサが簡単でしょうね.

単なるループ展開で速くなるということはJSの演算最適化という観点からはあまり面白いものではなく,そういったプリプロセッサに走るのが妥当かなと.JSは8bit時代の機械語(まともな最適化コンパイラも無いということも含む)という印象ですね.
Google Web Toolkitは正しい方向だなあと.

dsk:

2点。
■Function.prototype.toString()について
勝手にvarがなくなっているのはSafari内蔵のJSのバグですが、そもそも、クロージャのことを考えると、Function.toString()というのが無理があるんですよね。すなわち、
var x, y, z, p, q;
functioin a() {
var b = 5;
x = function() { return b; }
}
y = x.toString();
p = x();
functioin c() {
var b = 10;
x = function() { return b; }
}
z = x.toString();
q = x();

という例で、yとzに代入される文字列は(通常)同じものになりますが、
pとqの値は異なりますよね。toString()ではクロージャで言う「環境」までは表現できない訳です。ならば、ソースを覚えておいてそれを出力するということで良いのか?となると、
var x, y;
function twice(f) {
return function(a) { return f(f(a)); };
}
var g = twice;
x = g.toString();
g = g(g(g));
y = g.toString();

の場合、xやyに代入されるべき文字列は何でしょうか?
xは "function twice(f){ return function(a) { return f(f(a); }; }"で、yは "function(a) { return f(f(a)); }"である、というのも一つの答えですね(上記ソースを保存する方式を貫くとこんな感じかと、f = twice(twice)であれば正しい訳ですから)。

このあたりも含めてECMA262の定義(15.3.4.2参照)を見ると、
・functionを定義する文法形式を出力する
・対象となるオブジェクトである関数を表現(represent)する
こと以外は処理系依存である、となっていて曖昧ですね。

■ECMA262(JS)について
某所でも何度か主張していたのですが、ECMAScriptはLisp(scheme)に似ているのではないかと。http://www.json.org/js.html にも私と同じ主張が書かれていて、The Little LISPer.という有名なLISPの入門書(お勧め、私もこれで入門しました)をもじった、The Little JavaScripter.というコンテンツへのリンクがあったりします。

コメントを投稿

(いままで、ここでコメントしたことがないときは、コメントを表示する前にこのブログのオーナーの承認が必要になることがあります。承認されるまではコメントは表示されません。そのときはしばらく待ってください。)