メイン

JavaScript アーカイブ

2007年07月20日

論理演算1

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

2007年07月24日

md5.js

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倍程度高速に計算されていることが分かります.

sha1.js

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: CryptographyJavaScript でハッシュアルゴリズムで公開されているライブラリです.

環境: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倍程度高速に計算されていることが分かります.

2007年07月26日

論理演算2

高速化のために,いくつかの基本的演算のベンチマークを取っていて驚くのは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
    }
}
abcd
IE110110110110
Fx7878125890

(注意) 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)は -230-1<=j<=230-1なら真のマクロ.

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

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

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

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

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

2007年07月31日

sha1.jsにおけるせこいテクニック

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

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

・32bitラップアラウンド

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

function MD5_number(n) {
  while (n < 0)
    n += 4294967296;
  while (n > 4294967295)
    n -= 4294967296;
  return n;
}
他のwebページでも似たコードを見かけました. もしかしたら昔の処理系に対応したものの名残が広まっているのかもしれませんが, 0とorして正しく32bit整数になる処理系にとっては殆ど無意味です. もし入力値に負数を許容するとしても
function round(x)
{
    x |= 0;
    if (x < 0) x += 4294967296;
    return x;
}
で十分でしょう. ただし, SHA-1で定数値に負数を含まないようにしておけばif()は不要です. ついでにsha1.jsなどではA + B + Cをround(round(A + B) + C)のように演算ごとにroundを呼ぶ必要もありません. 削れるところは削りましょう.

・32 = 16 + 16?

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

function rotL5(x)
{
    return (x << 5) | (x >>> 27);
}
ですから, 16bit x 2のバージョンではxを上位16bitのxH, 下位16bitのxLとに分割すると,
    var t = ((xL << 5) & 0xffff) | ((xH >>> 11);
    xH = ((xH << 5) & 0xffff) | (xL >>> 11);
    xL = t;
となります. しかし, ここを 32 = 5 + 27 (xHが上位5bit, xLが下位27bit)と分ければどうなるでしょうか.
    var t = xH | ((xL & 0x3fffff) << 5);
    xH = xL >>> 22;
    tL = t;
となり, 論理演算が8回から4回と半分に減りました. もちろん5 + 27に分けても1bit右回転は論理演算が8回必要ですが, 片方が半分になるだけでもうれしいです. なお, 逆に32 = 1 + 31に分けるのもあるのか? と思われるかもしれませんが, もともと30bit整数未満にしたかったわけですからその選択はありません.

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

・16bit整数のnot

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

今回はこんなところで.

2007年09月15日

出張Shibuya.js 24の発表資料

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

内容の詳細は後日.

2007年09月16日

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

出張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で終わってないといけないなど.

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

2008年09月09日

google ChromeでSHA-1のベンチマーク

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への対応が簡単になると思いますがいかがでしょう.






my SHA-1pajhomeJavaScriptでハッシュアルゴリズム
IE60.94msec10.47msec6.25msec
Firefox 3.0.10.63msec2msec1.39msec
Chrome0.55msec0.44msec0.65msec

About JavaScript

ブログ「mitsunari@cybozu labs」のカテゴリ「JavaScript」に投稿されたすべてのエントリーのアーカイブのページです。過去のものから新しいものへ順番に並んでいます。

前のカテゴリはC++です。

次のカテゴリはMD5です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。