mitsunari@cybozu labs

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整数値を二つの数値型変数に分けて入れることでそれに対応しました．

前回の結論のように, 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です.

今回はこんなところで.

Shibuya.JSで発表したppt資料を置きました．
ppt

内容の詳細は後日．

出張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(リファレンス実装)，自動インライン展開，自動ループ展開，自動インライン展開 + ループ展開，手動最適化の五つです．それらの処理時間を測定し，オリジナルに対する速度比を表示します．

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

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

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

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

1年ほど前に作ったsha1.jsをgoogle Chrome上でベンチマークをとってみました(Win Xp@Core2Dup 2.6GHz)．
結果はpajhomeさんの実装では20倍以上もの凄まじい速度向上がありましたが，もともと最適化していた私ものものはあまり速くなっていません．
これはループアンロールなどの(つまらない)努力は不要になるということで，すばらしいことです．
ただ数値計算に限っては，もともと十分に最適化されていればIE6と大きく変わるものでもないとも言えます．
ちなみにC++でのSHA-1では0.0056msecでした．まだ100倍ほどの開きはあるようです．

ところでchromeのJIT部分で使ってるassembler-ia32.ccなんかみるとxbyak使ってほしいなとか思ったり．x86-64への対応が簡単になると思いますがいかがでしょう．