JavaScript 膨大なcase数のswitch文を高速化する

2021/09/09 22:45

JavaScript で書いたツールをプロファイリングしていたところ、膨大な数の case の switch 文で処理時間を食っている事が分かり、以下の記事で JavaScript の switch の速度について簡単な検証をしました。

https://puarts.com/?pid=1700

詳しくはこちらの記事を見ていただきたいのですが、switch は FirefoxでもChromeでも2021年9月現在の最新バージョンではcase数に応じて線形に処理が増加する事が分かりました(ifと変わらない)。

これをどうにか高速化できたので、こちらの記事に記録しておきます。

元のコードは以下です。単純にconst変数ベースでswitchしてるだけです。

const a0 = 0;
const a1 = 1;
const a2 = 2;
..

switch(value) {
case a0: x++; break;
case a1: x++; break;
case a2: x++; break;
..
}

そして、以下が高速化後のコードです。

const a0 = 0;
const a1 = 1;
const a2 = 2;
..

const funcDict = {};
funcDict[a0] = () => { x++; };
funcDict[a1] = () => { x++; };
funcDict[a2] = () => { x++; };
..

let valueFunc = funcDict[value];
if (valueFunc) {
    valueFunc();
}

誰でも思いつくとは思いますが、分岐処理の関数をすべて事前に辞書に登録しておき、辞書から実行する処理を選ぶようにするのを試してみました。線形探索が二分探索になるので、膨大な数の分岐でも高速に該当の処理に飛ぶことができるようになるはず。もちろん、辞書を初期化する固定コストはかかるので、辞書の初期化は最初に済ませておく必要はあります。

処理時間を測ってみると、このswitchを1万回実行するのに、Firefox では 10 ms 程かかっていた処理が 0.9 ms 程に、Chrome では 4 ms 程かかっていた処理が 0.2 ms 程に短縮しました。(辞書の初期化は除く処理時間での比較です)

1000個の case があった場合だと、10倍から20倍高速になったことになりますね。これだけ速ければ私のスクリプトが遅い問題も大分緩和できそうです。

ちなみに辞書の初期化も毎回行うと Chrome で 10 ms 程だった処理が 200 ms 程に処理時間が増加します。辞書は最初に初期化しておかなければならないという点は要注意です。

とは言え、私のスクリプトは既に大量の switch で実装してあるので、既存のコードをこの方法に置き換えるのは骨が折れそうです。あと、処理に渡さなければらない引数もあるので、それらもうまく辞書に登録する関数に渡す調整が必要です。この方法に切り替えると確実にメンテナンス性は悪くなります。

でも、処理時間が劇的に速くなるのはとても魅力。なんとか文字列置換とかで一括置き換えできないか模索してみようと思います。

追記

実際に問題になっていたスクリプトをこの方法に置き換えて処理時間を計測してみました。

Chrome では、もともと 130 ms 程かかっていた処理が 60 ms 程に短縮、Firefox では、もともと 230 ms 程かかっていた処理が 70 ms 程に短縮しました。小さいと思われるかもしれんが、1000回とか繰り返す処理なので分レベルでの短縮になります。

ちなみに jest 上で実行した場合は処理時間に変化はありませんでした。おそらく、jest では switch 文の評価が case 数に依存しない命令にコンパイルされているのだと思われます。

この最適化が有効かどうかは JavaScript のコンパイラ依存という事になるので、本当に有効かどうかは事前に確認するよう注意した方が良いですね。


  このエントリーをはてなブックマークに追加  

<<「Web 開発」の記事一覧に戻る

関連記事