JavaScriptにおけるビット演算と剰余の速度比較

jsbnというJavaScriptの暗号用多倍長整数演算ライブラリをHaxeへ移植するという作業をしている関係で多倍長整数演算ライブラリについて調べていると、JavaScriptは他のプログラム言語に比べて多倍長整数演算ライブラリの実装がこの世にたくさん存在するということが明かになった。例えば次のようなものがある。

• http://silentmatt.com/biginteger/
• http://blog.livedoor.jp/dankogai/archives/51516961.html
• https://github.com/peterolson/BigInteger.js/tree/master

多倍長整数演算は内部で配列を使って、一要素を一桁として大きな数を表現するのが一般的だが、問題は一桁をどれだけの大きさにするか、つまり 基数 をいくつにするかが重要である。既にスタンダードが存在すると考えていたが、どうも実装によって色々な基数が存在するということがあきらかになった。それも、2の補数ではない10の$n$乗といった数を基数にしている実装もあった。
しかし、$10^n$乗を基数にして多倍長整数演算を実装すると、剰余を使った計算が必要になる。$2^n$を基数にした場合はビット演算で済む。僕みたいな素人の考えでは、どう考えても「剰余 vs ビット演算」ではビット演算が勝つと考えてしまうが、もしかしたらもしかするかもしれないので、とりあえずは検証してみることにした。ただし全てのビット演算を試すのは面倒だったので、ここではビットシフトを代表として使うことにした。

検証環境

ハードウェア

CPU

Intel Core i7 2.7GHz

メモリ

8GB

OS

Mac OS X Yosemite

ブラウザのバージョン

Firefox	Chrome	Safari
36.0.1	41.0.2272.76	8.0.3

実験内容

次のようなコードでベンチマークをとった。（参考：http://d.hatena.ne.jp/mindcat/20091119/1258651717）

function perf_test1(val) {
	var cnt = 1000000000;
	var tm1 = (new Date).getTime();
	while (cnt-- > 0) {
		val % 10
	}
	var tm2 = (new Date).getTime();
	console.log("modulo time=" + (tm2 - tm1));
}

function perf_test2(val) {
	var cnt = 1000000000;
	var tm1 = (new Date).getTime();
	while (cnt-- > 0) {
		1 << val;
	}
	var tm2 = (new Date).getTime();
	console.log("bit-shift time=" + (tm2 - tm1));
}

perf_test1(10);
perf_test2(10);

結果

次のような結果になった。

	Firefox	Chrome	Safari
modulo	915	1340	9804
bit-shift	914	1343	7791

FirefoxとChromeでは差がほとんどなく、Safariではそれなりに差が出た。ただ冷静に考えてみたら、これは%に与えるvalが小さすぎた可能性があるとして、valを2147483647（特に意味はないが一応$2^{31} - 1$）にして再度実験した。ビットシフトの方はそのままvalに10を用いる。

	Firefox	Chrome	Safari
modulo	940	1355	9804
bit-shift	944	1372	7790

同じような結果となった。

考察

JavaScriptは数値をDoubleで持っているが、ビット演算は32bit整数で表現されている。ということは、ビット演算するたびに暗黙的にDoubleで保持していた数値を何かの関数で32bit整数へと変換している。その関数はECMAScript262で定義されていて、要約すると次のようになる。

1. ゼロに近い整数へまとめる（floor）
2. $2^{32}$との 剰余 をとる

つまり、ビット演算を行うと中で自動的に剰余が行われているので、たいしてパフォーマンスに差がでなかったのではないかと思う。ビットシフト以外の他のビット演算についても恐らく同じと思われる。
そうすると、どうしてSafariでは速度に差が生じたのか謎。

結論

結局この実験だけでは、多倍長整数演算ライブラリの基数に$10^n$か$2^n$かどちらがよいのかを直ちに結論付けることはできなかった。
ただ、MacのSafariではビット演算（今回の実験で試したのはビットシフトだけだが）の方が剰余よりも早い可能性があるので、今すぐパフォーマンスが欲しい場合は$2^n$を基数にした実装を選ぶべきかもしれない。（微妙）