SHA-1の高速化tips 2007/9/15 光成滋生@サイボウズ・ラボ

目次 前置き 初級編 中級編 マニアック編 地道に速度を稼ぐ 自己書換えによるお気軽ループ/インライン展開 Firefoxの特性を使った高速化

前置き 高速化 以上，すべてyesなら次へ 本当に必要? プロファイルした? アルゴリズムの見直しは? メンテ大変だけどコストに見合う? 小手先技術はすぐ廃れるけど覚悟はいい? 以上，すべてyesなら次へ

初級編（1/6） Blowfishの暗号化コアを例に コアのリファレンス実装 : 8byte入力, 8byte出力 IE 6 Fx2.0 encCore : function(inp) { var xL = inp[0]; var xR = inp[1]; var tmp; for (var i = 0; i < this.N; i++) { xL ^= this.P[i]; xR ^= this.F(xL); tmp = xL; xL = xR; xR = tmp; } xR = xR ^ this.P[this.N]; xL = xL ^ this.P[this.N + 1]; if (xL < 0) xL += 4294967296; if (xR < 0) xR += 4294967296; return [xL, xR]; IE 6 Fx2.0 処理時間 134 162 高速化率 100% @PentiumD2.8GHz

初級編（2/6） 入出力を同一に function (inp) { return out; } → function(inout); encCore : function(inout) { var xL = inout[0]; var xR = inout[1]; var tmp; for (var i = 0; i < this.N; i++) { xL ^= this.P[i]; xR ^= this.F(xL); tmp = xL; xL = xR; xR = tmp; } xR = xR ^ this.P[this.N]; xL = xL ^ this.P[this.N + 1]; if (xL < 0) xL += 4294967296; if (xR < 0) xR += 4294967296; inout[0] = xL; inout[1] = xR; IE 6 Fx2.0 処理時間 134 155 高速化率 100% 104%

初級編（3/6） thisのalias作成 this.N → Nなど IE 6 Fx2.0 処理時間 128 155 高速化率 104% encCore : function(inout) { var xL = inout[0]; var xR = inout[1]; var tmp; var N = this.N, P = this.P; for (var i = 0; i < N; i++) { xL ^= P[i]; xR ^= this.F(xL); tmp = xL; xL = xR; xR = tmp; } xR = xR ^ P[N]; xL = xL ^ P[N + 1]; if (xL < 0) xL += 4294967296; if (xR < 0) xR += 4294967296; inout[0] = xL; inout[1] = xR; IE 6 Fx2.0 処理時間 128 155 高速化率 104%

初級編（4/6） 1回unloopによるswapの除去 block暗号化における常套手段 IE 6 Fx2.0 処理時間 126 153 encCore : function(inout) { var xL = inout[0]; var xR = inout[1]; var tmp; var N = this.N, P = this.P; for (var i = 0; i < N; i += 2) { xL ^= P[i]; xR ^= this.F(xL); xR ^= P[i + 1]; xL ^= this.F(xR); } xL = xL ^ P[N]; xR = xR ^ P[N + 1]; if (xL < 0) xL += 4294967296; if (xR < 0) xR += 4294967296; inout[0] = xR; inout[1] = xL; IE 6 Fx2.0 処理時間 126 153 高速化率 106%

初級編（5/6） 関数呼び出しを止める 速いけど汚い IE 6 Fx2.0 処理時間 73 129 高速化率 183% 125% for (var i = 0; i < N; i += 2) { var a, b, c, d, x, y; xL ^= P[i]; x = xL; d = x & 255; x >>>= 8; c = x & 255; x >>>= 8; b = x & 255; x >>>= 8; a = x & 255; y = ((S0[a] + S1[b]) ^ S2[c]) + S3[d]; xR ^= y; xR ^= P[i + 1]; x = xR; d = x & 255; x >>>= 8; xL ^= y; } IE 6 Fx2.0 処理時間 73 129 高速化率 183% 125%

初級編（6/6） ループ展開し，変数伝搬も修正 速いけど読めない でもどうしても速度が欲しいならありかも IE 6 Fx2.0 処理時間 var a, b, c, d, x, y; x = xL ^= P[9]; d = x & 255; x >>>= 8; c = x & 255; x >>>= 8; b = x & 255; x >>>= 8; a = x & 255; xR ^= ((S0[a] + S1[b]) ^ S2[c]) + S3[d]; x = xR ^= P[8]; xL ^= ((S0[a] + S1[b]) ^ S2[c]) + S3[d]; x = xL ^= P[7]; x = xR ^= P[6]; (中略) x = xR ^= P[4]; x = xL ^= P[3]; x = xR ^= P[2]; IE 6 Fx2.0 処理時間 53 103 高速化率 252% 157%

中級編（1/3） JavaScriptは関数もobject なら実行前に書き換えてみよう オリジナルアイデアは奥さん@labs.cybozu.co.jp var f = targetFunction.toString().split('\n'); 与えられた関数をtoString()で文字列にする 文字列を解析し書き換える eval()を使って関数を定義し直す これらを起動時に一度呼ぶ

中級編（2/3） 作ってみた これらを起動時に一度呼ぶ まじめなJavaScriptパーサは大変なので超限定版 unrollLoop(出力関数, 入力関数); 与えられた関数内のforループを展開する関数 forceInline(出力関数, 入力関数, 展開関数); 与えられた関数が呼び出す関数を展開する関数 これらを起動時に一度呼ぶ optimize()

中級編（3/3） ベンチマーク 下記コードに1行加えるだけ optimize('encCore2', encCore, 'this.F'); encCore : function(inout) { var xL = inout[0]; var xR = inout[1]; var tmp; var N = this.N, P = this.P; for (var i = 0; i < N; i += 2) { xL ^= P[i]; xR ^= this.F(xL); xR ^= P[i + 1]; xL ^= this.F(xR); } xL = xL ^ P[N]; xR = xR ^ P[N + 1]; if (xL < 0) xL += 4294967296; if (xR < 0) xR += 4294967296; inout[0] = xR; inout[1] = xL; IE 6 Fx2.0 処理時間 126 153 手動最速 53 103 IE 6 Fx2.0 処理時間 73 101 いい線 互角

マニアック編（1/3） ところでFxはIEの50～70%の速度しか出ない? 現象 block暗号，ハッシュ関数系の処理では似た傾向 countが小さいときはFxも速い var x = 0; var count = 1000000; for (var i = 0; i < count; i++) { x += i; }

マニアック編（2/3） 原因はFxのSTORE_INT()の実装にあり 絶対値が2^30-1を超える数値にはメモリ確保が伴う 大抵のLLの実装では整数を効率よく扱うために32bitのうち1bitを判別フラグに利用している IEは違うようだ if (INT_FITS_IN_JSVAL(i)) { v_ = INT_TO_JSVAL(i); } else { ok = js_NewDoubleValue(cx, (jsdouble)(i), &v_); if (!ok) goto out; }

マニアック編（3/3） 解決方法 例（x ^ y） 詳細は 32bit変数を16bit x 2として扱い， 最大値が2^30にならないように実装する これでFxでSHA-1をIEなみの速度にもっていける ただしコードは本当に読めない(^^; 例（x ^ y） x = [xH:xL], y = [yH:yL] として xH ^ yH, xL ^ yL を計算する 詳細は http://labs.cybozu.co.jp/blog/mitsunari/