最近、 WebAssembly について、よく聞くようになってきました。実際に採用された例だと、 Amazon Prime Video で動画再生に WebAssembly を採用したという情報もあり、今注目を集めている技術なのではないかと思います。
WebAssembly を使うことにより、パフォーマンスを向上することができるということで、今回、数独を解くロジックを Rust + WebAssembly で実装してみて、 JavaScript (TypeScript) で実装した場合と、どれぐらいタイムに差が出るのかを検証してみました。
ちなみに、なぜ数独にしたのかというと、難易度的にサクッとアルゴリズムを実装できそうだというのと、なんとなく数独ソルバーを実装してみたくなったからですｗ
※ WebAssembly について詳しく知りたい方は下記の記事が参考になると思います。
実装方法
数独は、コンピュータ的にそこまで複雑なパズルではないので、単純で適当なアルゴリズムでも、それなりに速く解けたりします（とはいえ、あまりにも非効率な解き方をすると数十秒かかったりしますが）。
でもせっかく実装するからには、ある程度スピードにこだわりたいと思い、それぞれの環境において、最速のアルゴリズムを模索しました。
WebAssembly (以下、 Wasm) と JavaScript の実行速度を公平に比べるためには、同じアルゴリズムで実装すべきと考えるのが自然でしょう。僕も最初そう思っていました。しかし、1つ問題があります。それは、
Wasm と JavaScript では、それぞれ最適なアルゴリズムが異なる
のです。
具体的には、 Wasm でいろいろ試してみて最速だった bitboard を使用したアルゴリズムを、 JavaScript に移植すると、なぜかめっちゃ遅かったのです（実装方法が悪かった可能性はありますが）。 JavaScript の場合は、ボード表現は普通の配列にし、探索アルゴリズムに色々な工夫を加えることで速くなりました。
まあまあ頑張ったので、おそらく世界最速の数独ソルバーが完成したのではないかと勝手に思っていますｗ
というわけで、それぞれの環境で、どんなアルゴルズムを実装したのか、かんたんに紹介します。
Rust + Wasm
- bitboard を使ったアルゴリズムです。
- bitboard って何？って方は、この記事がわかりやすいです
- 1-9 それぞれの数字に対応する bitboard を準備します
- 1が入っている場所を管理する board、2が入ってる場所を管理する board...
- bitboard だと何が嬉しいかというと、重複判定がたった1回のビット演算でできることです
- 数独では、同じ行・列・ブロックに同じ数字が重複していないかを判定する必要があります
- 普通に実装すると、あるマスの重複判定をするために、最低20回ループを回す必要があります
- それが1発で判定できるので、高速というわけです
↓ ソースコード
↓ デプロイしたもの
JavaScript (TypeScript)
- ボード表現は普通に81個のマスの配列
- それぞれのマスに下記の情報を持たせることで高速化
- 影響を及ぼしうるマスへの参照（20マス）
- 入る可能性のある数字の候補
など
- 空きマスを、双方向連結リストで管理することにより、ループの回数を大幅に削減
- 候補数が少ないマスから優先的に探索することで高速化
↓ ロジック側のソースコード（勢い余って npmライブラリとして公開しちゃいましたｗ）
↓ アプリケーション側のソースコード
↓ デプロイしたもの
計測方法
performance.now() メソッドを使用します。
ソルブ前とソルブ後にこのメソッドを呼び出し、差分を表示するように実装しました。
数独のサンプルを2つ用意し、それぞれ繰り返し計測します。
- サンプル1 (Hard) 人間的にもコンピュータ的にも解くのが難しいサンプル
- サンプル2 (Easy) 簡単に解けるサンプル
また、ページロード後初回実行のタイムと、それ以降のタイムが大幅に異なる場合があるので、それらは別々に集計します。
6回（初回実行1回、2回目以降5回） x 10セット 実行し、それぞれ平均タイムを計算します。
計測結果
単位はms（ミリ秒）です。
PC (Macbook Pro / Google Chrome)
| サンプル1 (Hard) | サンプル2 (Easy) | |||
|---|---|---|---|---|
| 初回実行 | 2回目以降 | 初回実行 | 2回目以降 | |
| JavaScript | 15.68 | 6.11 | 2.74 | 0.72 |
| Wasm | 2.29 | 2.20 | 0.69 | 0.59 |
Wasm の圧勝となりました。サンプル1 (Hard) を平均2msで解けるのはエグいですね…
また、 JavaScript は初回実行時のタイムが大幅に遅くなる傾向が見られましたが、 Wasm は初回実行と2回目以降の実行に有意な差が見られませんでした。
スマホ (iPhone / Safari)
| サンプル1 (Hard) | サンプル2 (Easy) | |||
|---|---|---|---|---|
| 初回実行 | 2回目以降 | 初回実行 | 2回目以降 | |
| JavaScript | 20.10 | 14.94 | 5.10 | 2.22 |
| Wasm | 13.10 | 8.80 | 8.80 | 2.44 |
サンプル１ (Hard) にかんしては、 Wasm の圧勝でした。
しかし、サンプル2 (Easy) にかんしては、初回実行は JavaScript の勝利、2回目以降は同じぐらいでした。
またPCの場合と違い、 Wasm での初回実行が2回目以降の実行と比べて大幅に遅くなる現象が発生しました。
↓ 詳細な計測結果はこちら
デバイスによって結果が変わってくると思うので、みなさんもぜひスピードを測ってみてください ↓
感想
簡単な問題を解かせても大きな差は出ませんが、複雑な問題を解かせると、 Wasm のパフォーマンスの良さを引き出すことができるということがわかりました。
というわけで、めっちゃ面白かったので、これからも Wasm で色々なモノを作っていきたいなと思います。
直近だと、将棋AIを Wasm で実装してみると面白いかなと思ったりしています。