« 論理演算2 | メイン | sha1.jsにおけるせこいテクニック »

分割してみる

論理演算2で現れた

・コード1

var x = 0;
for (var i = 0; i < 1000000; i++) {
    x += i;
}

の処理時間はFirefox(Fx)では1046(ここでは比率のみが焦点なので単位は考えない)でした.ちなみにIEでは141です(小さい方が速い).Fxはかなり分が悪いようです.

一見これ以上いじりようのない単純なコードをFxでどこまで速くできるのか少し詳しく考えてみます.前回見たように30bitを超えないようにxを二つの変数に分けてみましょう.

・コード2

/*
    [x[1]:x[0]] += [y[1]:y[0]]を求める.
    ここで[a:b]はa * (1<<30) + bを意味する(0 <= a, b < (1<<30)).
*/
function add(x, y)
{
    var t = x[0] += y[0];
    x[1] += y[1];
    if (t >= (1 << 30)) {
        x[0] -= 1 << 30;
        x[1]++;
    }
}
function test2()
{
    var x = new Array(2);
    var y = new Array(2);
    x[0] = x[1] = 0;
    y[0] = y[1] = 0;
    for (var i = 0; i < 1000000; i++) {
        y[0] = i;
        add(x, y);
    }
    document.write(" ax=[" + x[1] + ":" + x[0] + "]<br>");
    document.write("sum=" + ((x[1] * 1073741824) + x[0]) + "<br>");
}

関数add(x, y)は30bit進数加算を愚直に書き下したものです.
このコードの処理時間はFxでは1032でした.
コード1に比べてかなり複雑なのに実行時間はほぼ同じです.速くなる可能性がありそうです(IEでは3032とコードが増えた分遅くなってます).

さて,このループ内ではadd(x, y)のy[1]は常に0です.したがってそのコードを除去してみます.

・コード3

function add(x, y)
{
    var t = x[0] += y[0];
    if (t >= (1 << 30)) {
        x[0] -= 1 << 30;
        x[1]++;
    }
}

この処理時間は766となりました.3割ほど速くなっています.
ついでに関数をインライン展開してみましょう.

・コード4

function test()
{
    var xL, xH, yL, yH;
    xL = xH = yL = yH = 0;
    for (var i = 0; i < 1000000; i++) {
        yL = i;
        var t = xL += yL;
        if (t >= (1 << 30)) {
            xL -= 1 << 30;
            xH++;
        }
    }
    document.write("sum=" + ((xH * (1 << 30)) + xL) + "<br>");
}

処理時間は219.関数呼び出しはかなり重いことが分かりました.
更に無駄なyL = iの代入を止めてみます.

・コード5

function test()
{
    var xL, xH, yL, yH;
    xL = xH = yL = yH = 0;
    for (var i = 0; i < 1000000; i++) {
        var t = xL += i;
        if (t >= (1 << 30)) {
            xL -= 1 << 30;
            xH++;
        }
    }
    document.write("sum=" + ((xH * (1 << 30)) + xL) + "<br>");
}

なんと処理時間は172と6倍以上速くなりました.コード1におけるIEの141に匹敵する速度です.

もちろん上記のようにいつもうまくいくとは限りませんが,重たい計算をさせる場合には考慮する価値はあると思われます.

・まとめ
1) FirefoxはIEに比べて30bitを超える整数値の扱いが苦手である.場合によっては分割したほうがよいこともある.
2) 関数呼び出しは重たい.

コメント (4)

dsk:

自分で何も実験せずに勝手なことを言いますが、日記を読むとFirefoxではint <-> doubleの変換が遅いようですね。だから、単純なループで加算するだけなら、

var x = 0.0;
for (var i = 0.0; i < 1000000.0; i+= 1.0) {
 x += i;
}

という手はないですかね?
・int演算二回よりもdouble演算一回の方が高速かも?
・これだとdouble用のメモリ確保のinvokeは避けられる?
に期待。

へるみ:

実はそのあたりもいくつかやってみたのですが,うまくいきません(速くならない)でした.double1回だけmallocはできそうな気がするんですけどね.

dskさんの方法->変化無し

var x = 0;
var i = 0x80000000;
for (i = 0; i < 1000000; i++) {
x += i;
}
これも変わらず.

var x = 0x80000000;
var i = 0x80000000;
for (i = 0; i < 1000000; i++) {
x += i;
}
x -= 0x80000000;
も変わらず.

var x = 0;
for (var i = 0.5; i < 1000000 + 0.5; i++) {
x += i;
}
x -= 0.5 * 1000000;
なんてのも駄目でした.

dsk:

上記実験ですと、jsはインタープリタなので、
・リテラルの1000000に.0がないと、ループの度に(int) 1000000 -> (double) 1000000という変換が行われませんか?
・i += 1.0 じゃなくて i++ だと (int)1 -> (double)1 への変換の後、iに(double)1 が加えられませんか?
という心配があります。(FireFoxのソース読め、という話もありますが...)。

ちなみにSafariでやると、コード5はコード1の三倍くらいの時間がかかります。(IEと同じような内部処理なのか?)

へるみ:

>リテラルの1000000に.0がないと
その程度のことは事前に処理されていて影響無いです.x += i;をx += i + 0.0;にしたり,i++をi = 1.0 +2-2 +iとしても速度は殆ど変わりませんでした.

コメントを投稿

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