JavaScriptで巨大な静的配列を実装するときはswitchよりもarrayを使ったほうが普通にはやい

動機

JSで事前に値が決まっている巨大な静的配列を実装するときに、arrayじゃなくてswitchの方が早いと思ったのでベンチをとった。DenoでやったのでV8のベンチになる。

実験

ベンチマークを作るスクリプト。

await Deno.remove("array_switch.ts");
const Ns = [100, 1000, 10000];
for (const N of Ns) {
  const array_banch: string = `const arr${N} = [${Array.from(
    { length: N },
    (_, i) => i
  ).join(",")}];
const get_val_array${N} = (i: number) => {
    return arr${N}[i];
};
Deno.bench(
    "array_${N}",
    () => {
      for (let i = 0; i < 10000; i++) {
        get_val_array${N}(i);
      }
}
   )`;
  const switch_bench: string = `
const get_val_switch${N} = (i: number) => {
    switch (i) {
      ${Array.from({ length: N }, (_, i) => `case ${i}: return ${i};`).join(
        "\n"
      )}
    }}
Deno.bench(
      "switch_${N}",
      () => {
        for (let i = 0; i < 10000; i++) {
          get_val_switch${N}(i);
        }
    })
`;
  Deno.writeTextFile(`array_switch.ts`, array_banch, {
    append: true,
  });
  Deno.writeTextFile(`array_switch.ts`, switch_bench, {
    append: true,
  });
}

ベンチの実行結果

benchmark      time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------- ----------------------------- --------------------- --------------------------
array_100               4.8 µs       207,000 (  4.7 µs …   5.1 µs)   4.9 µs   5.1 µs   5.1 µs
switch_100             17.8 µs        56,030 (  8.2 µs … 322.9 µs)  16.3 µs  59.3 µs  76.8 µs
array_1000              5.0 µs       198,100 (  4.6 µs …   1.8 ms)   4.7 µs   8.4 µs  20.9 µs
switch_1000            60.5 µs        16,530 ( 55.5 µs … 437.3 µs)  57.7 µs 121.3 µs 149.7 µs
array_10000             4.6 µs       218,000 (  4.4 µs …   5.2 µs)   4.6 µs   5.2 µs   5.2 µs
switch_10000          257.6 µs         3,881 (202.7 µs …   3.0 ms) 257.3 µs 480.0 µs 585.6 µs

感想

動的なarrayよりも静的なswitchの方が早いと思ったが、結果は逆だった。arrayは定数時間で要素にアクセスできるのに対して、switchはほぼ要素数に比例してアクセス時間が伸びているように見える。