はじめに
こちらの記事を読んで、 forEach が速いことが意外だったので、自分でも検証してみました。
検証結果
コード
検証コード
{
const fill = n => Array.from({ length: n }, (_, i) => i);
const arrays = [
fill(100000),
fill(10000000),
fill(2 ** 25),
fill(2 ** 25 + 1),
fill(2 ** 26),
];
arrays.forEach(arr => {
console.log('-------');
console.time(`for : ${arr.length}`);
for (let i = 0; i < arr.length; i++) { const v = arr[i]; }
console.timeEnd(`for : ${arr.length}`);
console.time(`for (cached): ${arr.length}`);
const len = arr.length;
for (let i = 0; i < len; i++) { const v = arr[i]; }
console.timeEnd(`for (cached): ${arr.length}`);
console.time(`for of : ${arr.length}`);
for (const v of arr) { }
console.timeEnd(`for of : ${arr.length}`);
console.time(`forEach : ${arr.length}`);
arr.forEach((v, i) => { v; });
console.timeEnd(`forEach : ${arr.length}`);
});
}
実行結果
表
グラフ
実行結果(画像の表と同じです)
-------
for : 100000: 2.464ms
for (cached): 100000: 2.212ms
for of : 100000: 4.849ms
forEach : 100000: 1.801ms
-------
for : 10000000: 13.398ms
for (cached): 10000000: 2.842ms
for of : 10000000: 5.92ms
forEach : 10000000: 3.019ms
-------
for : 20000000: 5.608ms
for (cached): 20000000: 5.674ms
for of : 20000000: 11.461ms
forEach : 20000000: 5.732ms
-------
for : 33554432: 9.434ms
for (cached): 33554432: 9.397ms
for of : 33554432: 19.094ms
forEach : 33554432: 10.009ms
-------
for : 33554433: 33.497ms
for (cached): 33554433: 26.946ms
for of : 33554433: 642.979ms
forEach : 33554433: 283.816ms
-------
for : 67108864: 59.199ms
for (cached): 67108864: 49.539ms
for of : 67108864: 847.556ms
forEach : 67108864: 537.941ms
要素数が33,554,432を超えると突然遅くなる
確かに要素数が少ないうちは forEach は速いのですが、要素数が 33,554,432 から 33,554,433 になった瞬間、明らかに遅くなってます。
どのループ方法でも、突然遅くなっていますが、特に著しくパフォーマンスが悪化したのは、 for of と forEach で 約30倍に増加 しています。
for と比べても約10倍で、一緒に走っていたはずなのに突然見捨てられてしまいました。
for 文の変化がわかりにくいので拡大すると、
for 文であっても、突然3倍ぐらいの時間がかかっています。
ただ、 for 文の速度であれば、遅くなったとはいえ許容範囲内だと思います。
ちなみに for in は遅すぎたので検証から外しました。
なぜ遅くなるのか
なぜ遅くなるのかという点については、調べていません。
メモリを連続的に確保できなくて最適化できなくなる…とかそんな感じだと勝手に思ってます。
その他のメソッドでの検証
コード
検証コード
{
const fill = n => Array.from({ length: n }, (_, i) => i);
const arrays = [
fill(100000),
fill(10000000),
fill(2 ** 25),
fill(2 ** 25 + 1),
fill(2 ** 26),
];
arrays.forEach(arr => {
console.log('-------');
console.time(`for : ${arr.length}`);
for (let i = 0; i < arr.length; i++) { const v = arr[i]; }
console.timeEnd(`for : ${arr.length}`);
console.time(`for (cached): ${arr.length}`);
const len = arr.length;
for (let i = 0; i < len; i++) { const v = arr[i]; }
console.timeEnd(`for (cached): ${arr.length}`);
console.time(`for of : ${arr.length}`);
for (const v of arr) { }
console.timeEnd(`for of : ${arr.length}`);
console.time(`forEach : ${arr.length}`);
arr.forEach((v, i) => { v; });
console.timeEnd(`forEach : ${arr.length}`);
// some
let label = `some : ${arr.length}`;
console.time(label);
arr.some((v, i) => { });
console.timeEnd(label);
// every
label = `every : ${arr.length}`;
console.time(label);
arr.every((v, i) => true);
console.timeEnd(label);
// reduce
label = `reduce : ${arr.length}`;
console.time(label);
arr.reduce((acc, v, i) => { }, 0);
console.timeEnd(label);
// filter
label = `filter : ${arr.length}`;
console.time(label);
arr.filter((v, i) => true);
console.timeEnd(label);
// map
label = `map : ${arr.length}`;
console.time(label);
arr.map((v, i) => v);
console.timeEnd(label);
// find
label = `find : ${arr.length}`;
console.time(label);
arr.find((v, i) => false);
console.timeEnd(label);
// indexOf
label = `indexOf : ${arr.length}`;
console.time(label);
arr.indexOf(Infinity);
console.timeEnd(label);
// slice
label = `slice : ${arr.length}`;
console.time(label);
arr.slice();
console.timeEnd(label);
});
}
検証結果
表
グラフ
検証結果(表と同じです)
-------
for : 100000: 1.917ms
for (cached): 100000: 2.196ms
for of : 100000: 5.423ms
forEach : 100000: 1.906ms
some : 100000: 2.12ms
every : 100000: 1.765ms
reduce : 100000: 1.598ms
filter : 100000: 55.721ms
map : 100000: 2.207ms
find : 100000: 1.68ms
indexOf : 100000: 0.151ms
slice : 100000: 0.697ms
-------
for : 10000000: 20.499ms
for (cached): 10000000: 2.878ms
for of : 10000000: 5.614ms
forEach : 10000000: 2.827ms
some : 10000000: 2.806ms
every : 10000000: 3.048ms
reduce : 10000000: 10.281ms
filter : 10000000: 249.985ms
map : 10000000: 65.648ms
find : 10000000: 3.047ms
indexOf : 10000000: 0.002ms
slice : 10000000: 41.558ms
-------
for : 33554432: 9.721ms
for (cached): 33554432: 9.502ms
for of : 33554432: 19.155ms
forEach : 33554432: 9.626ms
some : 33554432: 9.41ms
every : 33554432: 19.198ms
reduce : 33554432: 24.619ms
filter : 33554432: 785.836ms
map : 33554432: 499.55ms
find : 33554432: 310.616ms
indexOf : 33554432: 42.842ms
slice : 33554432: 249.602ms
-------
for : 33554433: 69.343ms
for (cached): 33554433: 34.429ms
for of : 33554433: 427.38ms
forEach : 33554433: 267.396ms
some : 33554433: 326.967ms
every : 33554433: 338.672ms
reduce : 33554433: 298.681ms
filter : 33554433: 1.219s
map : 33554433: 501.959ms
find : 33554433: 307.183ms
indexOf : 33554433: 42.954ms
slice : 33554433: 142.439ms
-------
for : 67108864: 68.643ms
for (cached): 67108864: 55.465ms
for of : 67108864: 836.494ms
forEach : 67108864: 530.984ms
some : 67108864: 643.041ms
every : 67108864: 668.004ms
reduce : 67108864: 587.057ms
filter : 67108864: 2.236s
map : 67108864: 978.112ms
find : 67108864: 610.472ms
indexOf : 67108864: 84.211ms
slice : 67108864: 285.489ms
その他のメソッドでも、似たような傾向ですが、一部要素数に比例しているものもあります。
わかりにくいので遅いグループと速いグループに分けてみます。
速いグループ
速いグループでは、 indexOf が直線的に増加しているのがわかります。
なぜなのかわかりませんが、 indexOf は要素数に関係なく速度を維持できるようです。
遅いグループ
遅いグループでは、 filter 以外 が直線的に増加しています。
filter の場合は、最初から速度が遅いのに、 33554433 から1.5倍ほど時間がかかっています。
新しい配列を生成するからと言うのであれば、 map や slice も同様の現象が発生しそうですが、そうではありません。
find も条件を見て要素を返すか返さないかという点ではほとんど同じですが、パフォーマンスが明らかに違います。
もしかすると、 map や slice は関数呼び出しの時点で、確保する要素数が確定しているため、最適化しやすいのかもしれません。
filter は、コールバック関数の戻り値によって、配列のlengthが可変なので、動的にメモリ確保することになり最適化しづらいのかと思いました。
結論
結論としては、大きな配列を扱う可能性がある場合、極力純粋な for 文でループを回すか、大きな配列を作らないように分割して処理するなどの注意が必要になるということですね。
あとがき
おそらくですが、この現象はJavaScriptに限った話ではないと思います。
今後は少ないデータを扱う場合と、大量のデータを扱う場合とではセオリーが変わるかもしれない、ということを念頭に置いておこうと思いました。
Discussion
要素数を見るに途中からV8の配列に対する操作が変わってそうですね
こんな記事が出てきました