最近、仕事で大量の配列操作を行う必要がある処理を記述することになった。
具体的にどういった処理かを書くことはできないが、その処理は非常に時間がかかるものだった。
大まかな説明をすると、あらかじめ用意された配列(重複あり)を時系列に並び替えて最適な並び順を求めるといったものだ。
動作環境はChrome(Chromium)で動作、開発はTypeScript(Remix)で行っていた。また、デプロイ環境はCloudRunでNode.jsを使っていた。

ブラウザへの淡い期待

最初は、特に何も考えずにブラウザ上でその計算を実行させようと考えたが、すぐに問題にぶつかった。
いつまでたっても処理が終わらないのである。
そればかりか、一晩中動かしていても終わらないどころかメモリ不足でブラウザのタブがクラッシュしてしまった。
私の開発マシンはメモリが128GBあり、通常の開発時で最大70GB程度までしか使われていないのにクラッシュしてしまっていた。
最初は拡張機能が悪さをしているのかと思ったが、それは違った。 開発のデバッグ時には拡張が何も入っていないプロファイルを使っていた。
PCのメモリが不足しているとは思えない状況だった。

クラッシュした状態でF12を押してインスペクタツールを開いてみても何もわからない。
out of memoryじゃないよ。もっと詳細を教えてよ…。

調べていくとChrome、V8にはタブごとのメモリ上限があるようだった。
Increasing the memory limit on Chrome v104
最近のChromeではこれらの値を変更することができないようだった。
ただ、よくよく考えてみると操作対象の配列が巨大すぎる気がしていた。
配列の順列を操作していたが、その数が膨大すぎるのだ。
計算してみたところ (1+3)! * (1+5)! * 16! 要素の配列の操作を行おうとしていた。
要素1つあたりのメモリ使用量が1byteとしても、数千PBものメモリが必要になる計算だった。
終わるわけがないし、メモリが足りるわけがない。

サービスワーカーへの期待

そこで、まずは望みは薄いがServiceWorkerに切り出すことにした。
ServiceWorkerはブラウザのバックグラウンドで動作するため、メインスレッドの処理をブロックしない。
しかし、ServiceWorkerもJavaScriptで書かれているため、シングルスレッドで動作する。
UIスレッドをブロックしないだけで、処理速度が向上するわけではない。
結局メモリ不足でクラッシュしてしまった。
困った……。

Wasmへの希望

どうしたもんか………と悩んでいたところ、C++に next_permutation という関数があったことを思いだした。
これは、順列を生成する関数で、引数に渡した配列を次の順列に変更してくれる。
これを使えば、配列の順列を生成することができる。
これを使って、WebAssembly (Wasm) に順列生成部分を移植して高速化することにした。
事前にWasmで実装しても配列操作などはそこまで速くならないといった情報を見たことがあったが、順列の生成は高速化できると思った。
これはそもそも作成する順列の数が減るためで、新しくWasmに記述した順列生成では (1+3)! * (1+5)! * 16! ではなく、 (1+3)! / (3)! * (1+5)! / (5)! * 16! だけの順列を生成することになる。これは同じ重複した要素の並び替えのため、生成する順列の数が減る。(ABBC を並び替えたときのBBAC, BBACは同じといったようなことと同じ)

Wasmに移植した処理は、大幅に高速化された。
当初は無限大の時間がかかると思われていたが、12時間まで短縮することができた。
これでもまだ遅い。これでは1回処理を実行してボタンを押すだけでPCを12時間放置することになる。
しかも、ブラウザを閉じてはいけないしブラウザが意図せずクラッシュするとやり直しだ…
それはまずい。

並列処理へ

そこで、処理を並列で動かせるようにすることを考えた。
並列処理を行えるようにするためのアプローチとしては、今まで一連の処理として実行していた物をチャンクに分割できると考えた。
チャンクに分割した処理はブラウザの手を離れ、サーバー側へ並列処理として委譲することができる。
やったね。これで処理を高速化できる。
これで最初のブラウザで処理を行っていたものが、サーバー側で並列処理を行うことができるようになった。
ユーザーのせいぜい数コアのCPUから解放されて無限の計算リソースで処理を行うことができるようになった。
無限っていいよね。

適度にチャンクに分割して、適度に並列で投げることにした。
イイカンジの案配が見つかり、50処理づつ、24並列で投げることにした。
これで、12時間かかっていた処理が、4時間まで短縮された。

Bun is faster

今まではNode.jsで動作していた処理をBunに変更してみることにした。
Bunは、Node.jsと互換性があり、より高速に動作するランタイムだ。
最近よく耳にするようになった。
最初はBunに変更するだけで高速化できるとは思えなかったが、試してみることにした。
公式のベンチマークみたいな物は大抵その速度がでるような有利な条件で行われているだろうという考えだった。
しかし、自分の処理をBunに変更してみると、4時間かかっていた処理が、わずか1.5時間で完了するようになった。
これは予想以上の速度だった。
Node.jsをBunに変更するだけで、こんなに変わる！？？？って感じだった。
これはすごい。

まとめ

なにをまとめるというのかはよくわからないが、こういったブログという物は大抵まとめという物があるので書いておこう。
タイトルには∞倍速くしたと記述したが、実際には∞倍速くしたわけではない。
そもそも最初は動作しなかったので、速い以前で動作していなかったという……。
しかし、最初の12時間かかっていた処理が1.5時間まで短縮されたので、∞倍速くしたという表現は許してほしい。 具体的には、12時間が1.5時間になったので、12時間/1.5時間 = 8倍速くなったということになる。
800%高速化といえば結構だろう。

今回は処理にどれくらいの時間がかかるか、どれくらいのメモリが必要かを事前に計算していなかった。
次からは、事前に計算しておくことを心がけよう。
計算量も最初に考慮しておこう。

あと、Bunはかなり速い。おすすめ。

まとめではないが、ブログのスタイルがあまりに雑だったので少し手直しした。 文字サイズとかフォントとか、マージンとか。