読者です 読者をやめる 読者になる 読者になる

htsign's blog

ノンジャンルで書くつもりだけど技術系が多いんじゃないかと思います

ビット演算による小数の整数化

http://d.hatena.ne.jp/babydaemons/20110629/JavaScript_without_Math_floor_function を読んでなんとなくやりたくなったのでやります。

ご存知の通り、Javascriptでもビット演算はできます。
一般にビット演算は通常の四則演算よりも高速だと思われますので使えるところでは積極的に使っていきたいところであります。

よく知られている整数化の手法としては以下のようなものがあります。

// 論理積
var int = float&-1;

// 論理和
var int = float|0;

// 排他的論理和
var int = float^0;

// 2回の補数算出
var int = ~~float;

// 0回のビットシフト
var int = float<<0;

// Math.floor()
var int = Math.floor(float);

でもどの程度高速なのか、というのが分からないので簡単にベンチマークを取ってみました。
ベンチマークを行う上で使用したコードは以下の通り。

function calc(n) {
  var f = 3.141592;
  var tmp = 0;
  var start = new Date();
  for (var i=0; i<10000000; i++) {
    tmp = f&-1; // ここを少しずつ書き換えて判定しています。
  }
  var end = new Date();
  return end-start;
}
for (var i=0, ret=[], sum=0; i<100; i++) {
  ret[i] = calc(i);
  console.log(i+"回目: "+ret[i]+"ms");
  sum += ret[i];
}
console.log("100回の平均: "+sum/100+"ms");

これを Windows 7上のIE9, Firefox10, Chrome17 で実行しました。

実行環境マシンの大まかなスペックは以下の通り。

公平を期すため、すべてのブラウザにおいて about:blank を表示した上でコンソールから実行しました。

結果は以下のようになりました。

// IE9
論理積       : 9.88ms
論理和       : 9.9ms
排他的論理和 : 9.85ms
補数算出     : 113.24ms
ビットシフト : 9.92ms
Math.floor() : 2791ms

// Firefox10
論理積       : 37.94ms
論理和       : 37.13ms
排他的論理和 : 37.91ms
補数算出     : 38.25ms
ビットシフト : 38.19ms
Math.floor() : 5114.93ms

// Chrome17
論理積       : 10.05ms
論理和       : 10.06ms
排他的論理和 : 9.8ms
補数算出     : 9.98ms
ビットシフト : 9.9ms
Math.floor() : 9.95ms

なんとビット演算を直接叩いた時、IE9Chrome並に速いのでした。
ただし、IE9に関して言えば、100回の計算中、最初の2回はコンパイルされないらしくスコアがガクッと落ちています。*1
ですので上記のセットをもう一度行い、その結果を記入しています。

また、IE9ではクソ時間の掛かっていたMath.floor()による計算がChromeではほとんど他の演算法と変わらないところを見ると、内部でビット演算に置き換えているような気がいたします。
V8エンジンの中身を見ているわけではないので何とも言えませんが…。

あと、全体的にFirefoxが遅いです。
6週間ごとにメジャーバージョンアップしていますが、なにが高速化しているのかさっぱり分かりません。

1000万回演算しても1/100秒程度*2の世界なので、ぶっちゃけそこまで気にする必要ないですね。ということでした。
比較対象のMath.floor()が(Chrome以外では)あまりにも遅いので、使えるなら積極的にビット演算使っていった方がよさそうです…。

*1:意味が分からない方はご自分で上記コードを動かしてみれば分かります。

*2:IE9の補数算出以外