mitsunari@cybozu labs

今月からサイボウズ・ラボで働くことになりました．
non-富豪的(=しみったれ)プログラミングが身に染みついて離れない生粋のC/C++/asmプログラマですが，ゆるゆると新しいことに挑戦したいと思います．
まずはJavaScriptから始めます．

JavaScript(JS)の勉強を始めて最初にひっかかったのは整数の挙動です．
JSでは整数は内部64bit浮動小数として扱われますが，論理演算をするときに限り符号つき32bit整数に変換されます．
C++プログラマからすると，「符号つき」が曲者です．
たとえばJSでは
x = 0xee6b28004;/* =4e9 */
は正の整数
x == 4000000000であるため，uint32相当と思いがちです．しかしその場合，
x &= 0xffffffff;
とした瞬間にxは「符号つき」と扱われ，
x == -294967296;
と負の整数になってしまうことを忘れてしまうかもしれません．

また，JSで厳密に扱える整数の最大値は
0x20000000000000 = 9007199254740992;
ですが，これを1 << 53として作ろうとすると，32bitでラップアラウンドするため，
1 << 53 = 1 << (53 - 32) = 1 << 20 = 1048576;
になります．

x | 0やx >> 0など，通常変化しないと思ってしまいがちな処理でも符号つき32bit整数への変換が行われるため，注意が必要です．
#(4000000000 | 0) < 0

なお，特別な値NaNについては
NaN | 0 == 0
NaN >> 0 == 0
となるため，0として扱われるようです．

cf.
http://developer.mozilla.org/ja/docs/Core_JavaScript_1.5_Guide:Operators:Bitwise_Operators

JavaScriptでMD5を計算するライブラリを作りました．

○特長
webでよく見られるいくつかの同種のライブラリに比べて3～7倍ほど高速に計算します．

○ダウンロード(download)
md5.js

○仕様
ASCII文字列を渡すとそのMD5を計算して16進数文字列で返します．
文字列に漢字などが含まれている場合は二つ目の引数にCybozuLabs.MD5.BY_UTF16を指定してください．UTF16として処理します．

○使い方1
var str = CybozuLabs.MD5.calc("abc");
if (str == "900150983cd24fb0d6963f7d28e17f72") {
...
}
○使い方2
var str = CybozuLabs.MD5.calc("あ", CybozuLabs.MD5.BY_UTF16);

○ライセンス
修正BSDライセンスにしたがいます．

○動作環境
Windows Xp + IE6, Firefox, Mac OS X + Safariで動作確認をしています．

○ベンチマーク
var msg = "MD5abZRVSXZVRcasdfasdddddddddddddddds+BNRJFSLKJFN+SEONBBJFJXLKCJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wuraddddddasdfasdfd";
という文字列に対してMD5の計算を100回ループしたときの処理時間を測定しました．
比較対象は高度な JavaScript 技集とJavaScript でハッシュアルゴリズムで公開されているライブラリです．

環境:Windows Xp Sp2 Core2Duo 2.66GHz 2GB memory
IE6:
test1 my lib
time = 0.79msec
test 2 高度な JavaScript 技集
time = 5.31msec
test 3 JavaScript でハッシュアルゴリズム
time = 3.28msec

Firefox:
test1 my lib
time = 0.94msec
test 2 高度な JavaScript 技集
time = 7.03msec
test 3 JavaScript でハッシュアルゴリズム
time = 7.5msec

幅はありますが4～8倍程度高速に計算されていることが分かります．

JavaScriptでSHA-1を計算するライブラリを作りました．

○特長
webでよく見られるいくつかの同種のライブラリに比べて4～6倍ほど高速に計算します．

○ダウンロード(download)
sha1.js

○仕様
ASCII文字列を渡すとそのSHA-1を計算して16進数文字列で返します．
文字列に漢字などが含まれている場合は二つ目の引数にCybozuLabs.SHA1.BY_UTF16を指定してください．UTF16として処理します．

○使い方1
var str = CybozuLabs.SHA1.calc("abc");
if (str == "a9993e364706816aba3e25717850c26c9cd0d89d") {
...
}
○使い方2
var str = CybozuLabs.SHA1.calc("あ", CybozuLabs.SHA1.BY_UTF16);

○ライセンス
修正BSDライセンスにしたがいます．

○動作環境
Windows Xp + IE6, Firefox, Mac OS X + Safariで動作確認をしています．

○ベンチマーク
var msg = "MD5abZRVSXZVRcasdfasdddddddddddddddds+BNRJFSLKJFN+SEONBBJFJXLKCJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wuraddddddasdfasdfd";
という文字列に対してSHA-1の計算を100回ループしたときの処理時間を測定しました．
比較対象はPaj's Home: CryptographyとJavaScript でハッシュアルゴリズムで公開されているライブラリです．

環境:Windows Xp Sp2 Core2Duo 2.66GHz 2GB memory
IE6:
test1 my lib
time = 0.94msec
test 2 pajhome
time = 9.22msec
test 3 JavaScript でハッシュアルゴリズム
time = 6.1msec

Firefox:
test 1 my lib
time = 2.19msec
test 2 pajhome
time = 11.87msec
test 3 JavaScript でハッシュアルゴリズム
time = 9.22msec

幅はありますが4～6倍程度高速に計算されていることが分かります．

高速化のために，いくつかの基本的演算のベンチマークを取っていて驚くのはFirefox(Fx)での結果です．

function test()
{
    var x;
    for (var i = 0; i < 1000000; i++) {
        x = 1 >> 1; // a
//        x = 1 >>> 1; // b
//        x = (-1) >> 1;  // c
//        x = (-1) >>> 1; // d
    }
}

(注意) 1 >> 1をi >> 1や (-i) >> 1に変えてもほぼ同じ．

どれもほぼ一定のIEに比べてFxで(-1)>>>1がやたら遅いのはどうしてでしょうか．

FxのSTORE_INT()のコードを見ると

if (INT_FITS_IN_JSVAL(i)) {                                           \
    v_ = INT_TO_JSVAL(i);                                             \
} else {                                                                    \
    ok = js_NewDoubleValue(cx, (jsdouble)(i), &v_);              \
    if (!ok)                                                                 \
        goto out;                                                          \
}

となっています．

#INT_FITS_IN_JSVAL(j)は -2³⁰-1<=j<=2³⁰-1なら真のマクロ．

つまり，xの値がその範囲を超えるとdouble型に移行し，その値を保存するためにメモリ確保関数が呼び出されます．

これが他に比べて10倍以上遅い原因となっています．
同様に

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

もFxはIEに比べて8倍近く遅くなります．SHA-1の演算では
2³⁰ - 1 < x < 2 ³²の整数は大量に出てくるわけですからこのペナルティは無視できません．

sha1.jsなどでは32bit整数値を二つの数値型変数に分けて入れることでそれに対応しました．

論理演算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) 関数呼び出しは重たい．

前回の結論のように, JavaScriptにおいては計算の重たい部分を展開したもの勝ちです. 一昔前のCコンパイラに対するようなものですね.
無論, やり過ぎたら読みにくいしメンテしづらいですが変わることのないライブラリなら許容範囲は広いでしょう.

ここではsha1.jsで使われている展開以外のテクニック(?)をあげてみます.

・32bitラップアラウンド

高度な JavaScript 技集では次のコードが使われていました.

function MD5_number(n) {
  while (n < 0)
    n += 4294967296;
  while (n > 4294967295)
    n -= 4294967296;
  return n;
}

function round(x)
{
    x |= 0;
    if (x < 0) x += 4294967296;
    return x;
}

・32 = 16 + 16?

分割してみるで述べたようにFxでは32bit整数を分割するほうが高速に動作する可能性があります.
素直に実装するならここは二つの16bit整数のペアとするでしょう.
もちろんそれで全然問題ありませんが, SHA-1には5bit右回転と1bit右回転がたくさんでてきます.
5bit右回転は

function rotL5(x)
{
    return (x << 5) | (x >>> 27);
}

    var t = ((xL << 5) & 0xffff) | ((xH >>> 11);
    xH = ((xH << 5) & 0xffff) | (xL >>> 11);
    xL = t;

    var t = xH | ((xL & 0x3fffff) << 5);
    xH = xL >>> 22;
    tL = t;

またSHA-1の演算の中で5回連続足し算がでてきますが, 27bit整数の場合は8回加算しても2³⁰を超えませんから問題ありません(この文の意図は解りにくいかな).

・16bit整数のnot

単に~xとしてしまうと上位16bitに1が立ってしまいます. ~x & 0xffffとしてもよいですが, 入力値が65536未満であることを利用すれば 65535 - x でOKです.

今回はこんなところで.