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

2021/09/09 22:45
(この記事の文字数: 1300)

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

詳しくはこちらの記事を見ていただきたいのですが、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 で実装してあるので、既存のコードをこの方法に置き換えるのは骨が折れそうです。あと、処理に渡さなければらない引数もあるので、それらもうまく辞書に登録する関数に渡す調整が必要です。この方法に切り替えると確実にメンテナンス性は悪くなります。

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