JavaScriptのループはどれが一番高速なのか #JavaScript

JavaScriptで画像処理などの重い計算をしているとどうしても気になるのがループの部分。実際の処理に加えてループの部分でのロスが気になり始めたので実際にどのループ方法が速いのか試してみました。

概要

0~9999999の長さ1000万の配列のすべてを足し合わせるという単純な計算を行います
配列は、各ループの前で常に初期化を行います。
ループはforまたはwhileを用います。foreachやforinは使いません。
v8（Node.js）、Chrome、Firefox、Safariで実験を行います
筆者が噂で聞いた５つのポイント（後述）を加味した計32種類のコードを自動生成し、実行します。
各プラットフォームで５回実行し、平均をとります。
ウェブブラウザではWebWorkerを用いて実行します。
結果は実行環境に左右されている可能性があります

環境

MacBook Air (11-inch, Mid 2012)
プロセッサ：2 GHz Intel Core i7
メモリ: 8 GB 1600 MHz DDR3

ポイント１：Array.prototype.length

JavaScript the Goodpartsなどで言われている、forの条件文のところで配列のlengthにアクセスしてはいけない、という説です。JavaScriptの配列のlengthは遅いのでループ中に呼ぶと遅くなるということですが、どうなのでしょうか。

// which is faster?
for (var i = 0; i < arr.length; i++){}
for (var i = 0, max = arr.length; i < max; i++){}

ポイント２：for vs while

通常数値のループならfor文を使うことが多いと思いますが、実際はforでもwhileでも問題は無いわけで、この２つに速度の差は無いのでしょうか？


// which is faster?
for (...) {}
while(...) {}

ポイント３：インクリメント vs デクリメント

筆者が聞いた「配列は前から後ろに走査したほうが速い」「数値は--した方が速い」という対立する２つの噂のどちらが正しいのかを検証します。


// which is faster?
for (var i = 0; i < arr.length; i++) {}
for (var i = 0; i < arr.length; i--) {}

ポイント４：i++ vs i = i+1

これも筆者が聞いたi++が速い説とi=i+1が速い説（もしくは--,-1）を検証します。

// which is faster?
for (var i = 0; i < arr.length; i++) {}
for (var i = 0; i < arr.length; i=(i+1) {}

ポイント５：|0

|0とは、Googleの中の人が言っていた「jsのJITコンパイラに型を認識させる裏技」です。

プログラミング言語の講義資料を作っていて行列積の速度を比較してみたのだが、C言語＝1.8秒、Java＝1.9秒、Python＝18分、ChromeのJavaScript＝3.6秒。型無しの言語仕様でここまでがんばるJavaScriptはすごい。ブラウザ間の熾烈な速度競争の結果。
— Kentaro Hara (@xharaken) 2015, 7月 3

（ただ正式にJavaScriptに型が導入されるまでは、処理系に型を理解させて高速化させるために、for (i=0; i<n; i++) を for (i=0; i<n|0; i=(i+1)|0) と書く必要があったりするなどの事情は伏せておこうｗ）
— Kentaro Hara (@xharaken) 2015, 7月 3

type

var hoge = 1;
var fuga = hoge|0;

こうすることでfugaも数値型だと認識されるので計算が速くなるらしいです。
これも検証します。

// which is faster?
for (var i = 0; i < arr.length; i=i+1) {}
for (var i = 0; i < arr.length; i=(i+1)|0) {}

ソースコード

https://github.com/keroxp/JS-FastestEnumeration

結果

@riocampos さんからのテーブルのo/xが分かりづらいとご指摘を受けました。
対応は、以下になります。

// for
for (...) {}  // o
while(...) {} // x

// length
for (var i = 0; i < arr.length; i++) {}            // o
for (var i = 0, max = arr.length; i < max; i++) {} // x

// increment
for (var i = 0; i < arr.length; i++) {}    // o
for (var i = arr.length-1; -1 < i; i--) {} // x

// i++
for (var i = 0; i < arr.length; i++) {}     // o
for (var i = 0; i < arr.length; i=(i+1)) {} // x

// typed
for (var i = 0; i < arr.length; i=(i+1)|0) {} // o
for (var i = 0; i < arr.length; i=i+1) {}     // x

Chrome

for	length	increment	i++	typed	Average
x	x	x	x	x	121.8
o	x	x	x	x	111.2
x	o	x	x	x	109.2
o	o	x	x	x	109.2
x	x	o	x	x	118.6
o	x	o	x	x	108.4
x	o	o	x	x	112.4
o	o	o	x	x	117.2
x	x	x	o	x	126
o	x	x	o	x	112
x	o	x	o	x	109.4
o	o	x	o	x	109.8
x	x	o	o	x	117
o	x	o	o	x	109.2
x	o	o	o	x	105.4
o	o	o	o	x	106.6
x	x	x	x	o	36
o	x	x	x	o	38.8
x	o	x	x	o	35.2
o	o	x	x	o	37.4
x	x	o	x	o	38
o	x	o	x	o	39.4
x	o	o	x	o	33.4
o	o	o	x	o	37.8
x	x	x	o	o	112
o	x	x	o	o	111.6
x	o	x	o	o	105.8
o	o	x	o	o	110.6
x	x	o	o	o	112.6
o	x	o	o	o	111.4
x	o	o	o	o	106.4
o	o	o	o	o	106.4

最速コード 33.4ms


i = 0;
sum = 0;
while(i < arr.length) {
    sum = (sum+arr[i])|0;
    i=(i+1)|0;
}

最遅コード 126ms


i = arr.length-1;
sum = 0;
while(-1 < i) {
    sum += arr[i];
    i--;
}

firefox

for	length	increment	i++	typed	Average
x	x	x	x	x	264.2
o	x	x	x	x	271.8
x	o	x	x	x	144
o	o	x	x	x	283.2
x	x	o	x	x	276.2
o	x	o	x	x	214.6
x	o	o	x	x	220.8
o	o	o	x	x	285.2
x	x	x	o	x	264.8
o	x	x	o	x	155.2
x	o	x	o	x	245.4
o	o	x	o	x	267.8
x	x	o	o	x	226.2
o	x	o	o	x	229.6
x	o	o	o	x	275.8
o	o	o	o	x	268.8
x	x	x	x	o	133.4
o	x	x	x	o	241.6
x	o	x	x	o	234.6
o	o	x	x	o	178.6
x	x	o	x	o	185.4
o	x	o	x	o	273
x	o	o	x	o	216.2
o	o	o	x	o	168.6
x	x	x	o	o	251.6
o	x	x	o	o	253
x	o	x	o	o	251.6
o	o	x	o	o	163.4
x	x	o	o	o	291
o	x	o	o	o	267.2
x	o	o	o	o	193.8
o	o	o	o	o	255.4

最速コード 133.4ms


i = arr.length-1;
sum = 0;
while(-1 < i) {
    sum = (sum+arr[i])|0;
    i=(i-1)|0;
}

最遅コード 291ms


i = 0;
sum = 0;
max = arr.length;
while(i < max) {
    sum += arr[i]|0;
    i++|0;
}

safari

for	length	increment	i++	typed	Average
x	x	x	x	x	59.8
o	x	x	x	x	52.8
x	o	x	x	x	59.4
o	o	x	x	x	64
x	x	o	x	x	57.4
o	x	o	x	x	53.2
x	o	o	x	x	53.8
o	o	o	x	x	55.4
x	x	x	o	x	52.2
o	x	x	o	x	54.6
x	o	x	o	x	53.6
o	o	x	o	x	62.4
x	x	o	o	x	58.2
o	x	o	o	x	62.4
x	o	o	o	x	64.4
o	o	o	o	x	65.4
x	x	x	x	o	44.2
o	x	x	x	o	52.6
x	o	x	x	o	140.6
o	o	x	x	o	47
x	x	o	x	o	51.2
o	x	o	x	o	58.2
x	o	o	x	o	41.8
o	o	o	x	o	52
x	x	x	o	o	80.2
o	x	x	o	o	62.4
x	o	x	o	o	58.6
o	o	x	o	o	66.8
x	x	o	o	o	61.4
o	x	o	o	o	73.8
x	o	o	o	o	54.6
o	o	o	o	o	60.6

最速コード 41.8ms


i = 0;
sum = 0;
while(i < arr.length) {
    sum = (sum+arr[i])|0;
    i=(i+1)|0;
}

最遅コード 140.6ms

i = arr.length-1;
sum = 0;
while(-1 < i) {
    sum = (sum+arr[i])|0;
    i=(i-1)|0;
}

Node.js

for	length	increment	i++	typed	Average
x	x	x	x	x	127.6
o	x	x	x	x	109.8
x	o	x	x	x	111.8
o	o	x	x	x	109.2
x	x	o	x	x	121
o	x	o	x	x	106.8
x	o	o	x	x	109.6
o	o	o	x	x	112.6
x	x	x	o	x	115.2
o	x	x	o	x	105.8
x	o	x	o	x	105.8
o	o	x	o	x	109.2
x	x	o	o	x	121.4
o	x	o	o	x	110.8
x	o	o	o	x	110
o	o	o	o	x	108.6
x	x	x	x	o	35.6
o	x	x	x	o	39.4
x	o	x	x	o	35.8
o	o	x	x	o	37.6
x	x	o	x	o	35.8
o	x	o	x	o	37.6
x	o	o	x	o	34.6
o	o	o	x	o	38.8
x	x	x	o	o	94.8
o	x	x	o	o	120.4
x	o	x	o	o	111
o	o	x	o	o	119.6
x	x	o	o	o	109
o	x	o	o	o	124
x	o	o	o	o	108.4
o	o	o	o	o	113.4

最速コード 34.6ms

i = 0;
sum = 0;
while(i < arr.length) {
    sum = (sum+arr[i])|0;
    i=(i+1)|0;
}

最遅コード 127.6ms

i = arr.length-1;
sum = 0;
while(-1 < i) {
    sum = sum + arr[i];
    i=(i-1);
}

結果

これらの結果から色々わかることがあるのですが、プラットフォームごとの違いはさすがに追い切れないと思うので、ポイントについてまとめてみます

1. Array.prototype.length

おどろくべきことに、Chrome, Safari, Node.js（v8）では、コードのイテレーションにlengthを用いたものが最速でしたが、使わなかったものとの差は3~10msほどでした。

しかし、Firefoxでは異なり、最速コードの当該ポイントをlengthに変えたものとの差は約100ms、1.75倍の違いがありました。

これらから以下の結果が分かりました。

Array.ptotototype.lengthは、WebKit由来のブラウザとNode.jsでは十分速いが、それ以外だと遅いブラウザもある

2. forとwhile

すべてのプラットフォームでwhileが最速でした。
しかし、たとえばNode.jsでは最速コードのforを使ったverとの差はわずか4msでした。
この結果から、以下の事がわかります。

forとwhileにほとんど差はないが、若干whileの方が速い

3 インクリメントとデクリメント

WebKit由来のブラウザでは、インクリメントとデクリメントの差はないようです。
Firefoxでは、デクリメントとインクリメントで50msほどの差がありました。

インクリメントとデクリメントの差がある場合とない場合がある。差がある場合、デクリメントの方が速い場合がある

4. i++ vs i = i+1

すべてのブラウザで、i = i+1 / i = i-1が最速でした。
それどころか、最速コードを++/--にしたコードは、約３倍遅いことが分かりました。

++/--は非常に遅い

5. |0

すべてのブラウザで、|0でtypedを施したコードが最速でした。
最速コードとの比較では、使わない場合２〜３倍の差が出るようです。

|0 で型を認識させることは重要

これが最速のループ文だ！（？）

...を書こうと思ったのですが、FirefoxとWebKit系で振る舞いが違いすぎる結果を受け、IEとかどうなるのかも分からなくなったので、書くことは控えさせていただきます。が、インクリメントする部分は以下のように書くといいのは確かなようです。

i=(i+1)|0

注意

この記事の結果は、筆者のパソコン、ブラウザ、CPU、メモリなどの実行環境によって左右されている可能性があります。鵜呑みにしないでください。