Zenn
🌊

【JavaScriptベンチマーク】pop ≒ shift >> push > unshift

に公開
4件
JavaScript
最適化
ベンチマーク
tech

タイトルの通りですが、JavaScriptのArray操作でpop / shift / push / unshiftを比較してどのような順番になるかを測ってみました。

  • pop ・・・ 配列の最後から要素を取り除き、取り除いた要素を返却
  • shift ・・・ 配列の最初から要素を取り除き、取り除いた要素を返却
  • unshift ・・・ 配列の最初に要素を追加し、要素数を返却
  • push ・・・ 配列の最後に要素を追加し、要素数を返却

ベンチマークテスト：ブラウザはChromeです。FirefoxとかSafariが好きな人がいたら流してみてください。僕はChrome（Brave）に骨をうずめるので確かめません。

その結果、

  • popとshiftは変わらなかった
    • StackOverflowとかを見ていると、shiftだと配列要素すべてをre-indexしないといけないため遅いと書いてあるが、JavaScriptは違う模様
    • popはendとlengthを更新、shiftはstartとlengthを更新、と考えると変わらないのも納得
  • popとshiftは、pushの6万倍くらい速い
    • つまり、配列は縮む分にはめっちゃ速い → 新しくメモリを確保しなくていいから
  • pushはunshiftの500倍くらい速い
    • 後ろに延ばす方がいいらしい。おそらくJavaScriptのメモリレイアウトがそうなのだろう。

ここまでやってみると、もう１つ気になるのが、事前に配列を確保しておいてから、中を埋めていく方法です。

ということでそれもベンチマークを取りました。

allocate and fillとは、以下のように先に配列を確保してから埋めていく方法です。

var array = Array(100000); // 配列を確保

for (var i=0,imax=array.length;i++) {
    array[i] = i;
}

結果、

  • allocate and fillはpushの3倍速い

ということがわかりました。

結論

pop ≒ shift >> allocate-fill > push > pop
  • スタックを作りたいときは、pushとpopで作った方が速い
  • キューを作りたいときは、shiftとpopで作った方が速い
  • 配列のサイズに予測が付くなら、pushとunshiftは使わないで実装すると速い

オマケ

JavaScriptで配列操作をする方法だと、もう少し最適化のテクニックがあります。

インデックスのJIT用の型ヒント

例えば、JITにインデックスの型のヒントを出すような書き方をすると速くなります。

let i = 0;
let array = Array(100000);
while (i < array.length) {
    i = (i + 1)|0; // 
}

論理和 |0をつけると整数型になるらしいです。（浮動小数点＝IEEE754より速い） 嘘です。BigIntの方が遅いです。当たり前でした。（コメントを参照）

JSの整数型じゃなくて、JITの内部実装（C++）の話のようです。恥ずかしい。

だったら、

let i = 0n

じゃだめなのだろうか。と思い測ってみた。

論理和 VS 宣言時指定

→ 前者の方が60倍くらい速かった

参考： JavaScriptのループはどれが一番高速なのか

キャッシュミス

※追記 JavaScriptの実装次第のようで、必ずしも以下の通りにはなりません。

以下に、３パターンでのパフォーマンス比較を置いておきます。

https://measurethat.net/Benchmarks/Show/34544/0/cpu-cache-test

--- 以下原文（JavaScript以外の言語では役に立つ知識かもしれないので一応残しておきます）

２次元配列にアクセスする時に、メモリが飛び飛びのアクセスになるとキャッシュミスが起きて遅くなります。

これは、CPUキャッシュのL1,L2,L3キャッシュの話です。

例えば、二次元配列のアクセスでパフォーマンスが変わります。

arr[j][i]

よりも、

arr[i][j]

の方が速いケースです。

もう少し説明すると、頭の中では、二次元配列に対してこういう表ができているわけで、

| 0,0 | 1,0 | 2,0 |
| 0,1 | 1,1 | 2,1 |
| 0,2 | 1,2 | 2,2 |　(i,j)

(1,0) と (1,1) は隣同士に思えますが、実際のメモリレイアウトは、

| 0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 |

となっているので、1,0と1,1は遠いです。

i++
j++

(0,0) (1,0) (2,0) (0,1) ...

とアクセスすれば連続ですが、

j++
i++

(0,0) (0,1) (0,2) (1,0)とアクセスすると飛び飛びになるのです。

キャッシュにメモリ範囲 (0,0) (1,0) (2,0) が入っている時、(0,1)にアクセスしようとするとキャッシュミスになるということです。

このキャッシュミスの話は、ゲーム開発で使われるECSの仕組みとも繋がるので、興味のある方は知っておいて損は無いです。

参考：「プログラマーですがなぜキャッシュメモリは早いのかといった物理的なことがネットで調べてもしっかり理解できまえせん」に関して

オマケの結論

  • なるべくメモリは静的に確保しよう
  • メモリアクセスはローカリティが高いほどいい（密集している方がいい、隣り合うとキャッシュミスが起きづらいから）
  • JITもできるだけ気にしよう

Discussion

ykyk

二次配列についてですが、キャッシュミスもそうかもしれませんが、最適化の問題だと思います。

最適化の結果、下記のようなコードとなり、dest,srcの一次元目の評価が省略されるため高速化に繋がります。

for(int i=0; i<1000000; i++){
    var dest_i=dest[i];
    var src_i=src[i];
    for(int j=0; j<1000000; j++){
        dest_i[j] = src_i[j];
    }
}

また、メモリレイアウトに関しても実装依存のため、L1-3キャッシュに乗るかどうかは何とも言えないと思います。

edaohedaoh

試してみましたが、i,jとj,iでなんと速さ変わらず、おっしゃられている最適化を事前にしたところ５倍くらい速くなりました...！！

https://measurethat.net/Benchmarks/Show/34544/0/cpu-cache-test

以前、node.jsで動かしたときはi,jが圧倒的だったので、検証サボってました。。。
勉強になりました。