Brainfuck 実行環境を WebAssembly + Web Worker で高速かつ非同期に進化させた

with PureScript & tailwind

大変なことになってきました

URL

https://yukikurage.github.io/brainf__k/

たとえば http://esoteric.sange.fi/brainfuck/utils/mandelbrot/ から mandelbrot.b を持ってきて実行してみます。
僕の環境 (i9 12900, firefox) だと 830 ms 程度で実行できます！ ブラウザ上でここまで速く動いたら大成功なのではないでしょうか。

前回記事

https://zenn.dev/yukikurage/articles/e899c9bc14d73c

前回記事にて

今のところ観測範囲内でこれより速く，ブラウザ上かつ非同期で動くものは見つけられていません．もし見かけたらスーパーの値引きシステムでもっと高速化を頑張るので，コメント欄などに書き込んで頂けると幸いです

などと調子のボルテージを上げていたら、コメントにて kounoike さんが brainfuck を wasm にコンパイルする (しかもそのコンパイラもブラウザで動作可能) 速いライブラリを見つけてくださったので、これはやるしかないと、自分も wasm にコンパイルする機能を取り入れてみました。

変更点

以前までは JavaScript のコードにトランスパイルして、その生成した文字列そのものを Worker プロセスで走らせていました。

これを、 WebAssembly のバイナリにトランスパイルするように変更しました。そして、それをあらかじめ用意してある Worker に投げて、実行してもらう形にすることで大幅な速度改善に至りました。

間に PureScript もかませてあるので、正確にはこうです。

ユーザー入力 → PureScript が FFI を使って コードを Wasm にトランスパイル → できた Wasm バイナリをワーカープロセスに渡す → ワーカープロセスは渡された Wasm バイナリを実行する → 実行中に適宜アウトプットを更新

それぞれの箇所ではまった点や知見を書いていきます。

トランスパイルについては前回記事でループの部分以外は書いたので、今回は省きます。ループの最適化もいつか書きたいです。

WebAssembly 生成

これには binaryen.js というライブラリを使いました。

Top レベル await

早速詰まったのは PureScript の FFI は CommonJS のみ対応しているのに対し、binaryen.js は トップレベル await を行っていたためうまくバンドルできない所でした。 (なぜ CommonJS でトップレベル await が使えないのかはよく分かってません)

これは

const binaryenPromise = require("binaryen");

f = () => binaryenPromise.then(({ default: binaryen }) => { ...(binaryen を使った処理) } )

のように書いて、WebPack に

  experiments: {
    topLevelAwait: true,
  },

を追加すれば大丈夫でした。なぜ大丈夫になったかは、分かりません。

WebAssembly のメモリ仕様

これは WebAssembly というより、アセンブリ系の言語に触ったのが初めてだっために起こったのですが、メモリの 1 cell を 32 bit だと勘違いしていました。数字が i32 と i64 しかないのでセルサイズは 32 bit やろなぁと勝手に思ってしまったのが原因です。仕様を読みましょう。

実際には 8 bit なので、例えば i32 の数字を扱っているときは、 4 * i で配列の i 番目の要素にアクセスできます。また、通常の Brainfuck の仕様ではセルサイズが 8 bit ですが、そのような場合は store8、 load8_u などの 8 bit でメモリを読み書きする用のコマンドがあります。この場合は i で配列の i 番目にアクセスできます。

コピーコストなしで Worker に UintnArray を渡す

例えば、文字列 input、 Uint8Array の値 compiled を渡したいときは次のようにします。

worker.postMessage({ input, compiled }, compiled.buffer);

しかしこれで速くなった気があまりしないので、brainfuck のトランスパイル結果程度の Array では意味があまりないのかもしれません。

さいごに

まだ高速化の余地はあると思います。もし Web で動作するだろう Brainfuck の実行環境で、より速い場所があったら教えてください。　まだ頑張れます。