読み飛ばしポイント
どうも、限界派遣SESです。
ひとりアドカレ20日目も遅刻です。
今回はBrainf**k(以下BF)のインタプリタをWasmで作ってみました。
Wasmとは？
WebAssemblyの略で、Webブラウザ上で動作するバイナリ形式のプログラムを実行するための技術です。
これを生成するためには、C/C++やRustなどの言語を使ってコンパイルする必要があります。
コンパイルされるってことは最適化されるってことなので、JavaScriptよりも高速に動作することが期待できます。
「見せてもらおうか、そのコンパイラによって最適化されたWasmの速さを！」
ということで、Brainf**kのインタプリタを作っていきます。
BFインタプリタを作っていく
過去にはTuringCompleteというゲームでBFインタプリタを作っていたことがありますが、今回はWasmで作ってみます。
BFはその難解な構文で知られますが、インタプリタやコンパイラは最小限の機能で実装できるためこういった遊びには最適です。
開発環境など
- Rust
- wasm-pack
- Python3
インストールはせずDevContainerを使って環境構築をしていきます。
公式がイメージを用意してくれているのでポチポチっとするだけで環境構築が完了します。
仮想環境が開いたら、wasm-packをインストールします。
curl https://rustwasm.github.io/wasm-pack/installer/init.sh -sSf | sh
後ほどの確認用にPython3もインストールしておきます。
apt-get update
apt-get install python3
これはpython3 -m http.serverでローカルサーバを立てるためです。
代替手段としては、VSCodeのLive Serverを使うこともできます。
真面目にこれらの環境を整える際は.devcontainerフォルダを用意してDockerfileとdevcontainer.jsonを用意しておくと良いです。
Dockerfileに必要なパッケージを記述しておけば、毎回同じ環境を構築できます。
RustでBFインタプリタを作る
wasm-packのテンプレートを使って、Wasmプロジェクトを作成します。
wasm-pack new bf-wasm
lib.rsにBFのインタプリタを書いていきます。
なお、最適化などは考慮せず、愚直な実装を行います。
use wasm_bindgen::prelude::*;
fn bf_interpreter(code: &str) -> Result<String, String> {
let mut tape = vec![0u8; 30000];
let mut ptr = 0;
let mut code_ptr = 0;
let code = code.as_bytes();
let mut loop_stack = Vec::new();
let mut result = String::new();
while code_ptr < code.len() {
match code[code_ptr] {
b'>' => {
ptr += 1;
if ptr >= tape.len() {
tape.resize(tape.len() * 2, 0);
}
}
b'<' => {
if ptr == 0 {
return Err("Pointer out of bounds".to_string());
}
ptr -= 1;
}
b'+' => {
tape[ptr] = tape[ptr].wrapping_add(1);
}
b'-' => {
tape[ptr] = tape[ptr].wrapping_sub(1);
}
b'.' => {
result.push(tape[ptr] as char);
}
b',' => {
// 標準入力は実装しない
}
b'[' => {
if tape[ptr] == 0 {
let mut loop_count = 1;
while loop_count > 0 {
code_ptr += 1;
if code_ptr >= code.len() {
return Err("Unmatched [".to_string());
}
if code[code_ptr] == b'[' {
loop_count += 1;
} else if code[code_ptr] == b']' {
loop_count -= 1;
}
}
} else {
loop_stack.push(code_ptr);
}
}
b']' => {
if let Some(&start) = loop_stack.last() {
if tape[ptr] == 0 {
loop_stack.pop();
} else {
code_ptr = start;
}
} else {
return Err("Unmatched ]".to_string());
}
}
_ => {}
}
code_ptr += 1;
}
Ok(result)
}
// ここがJSから呼び出される関数
#[wasm_bindgen]
pub fn run_bf(code: &str) -> Result<String, JsValue> {
bf_interpreter(code)
.map(|result| result)
.map_err(|err| JsValue::from_str(&format!("Error: {}", err)))
}
JSから呼び出す関数はrun_bfです。
この関数はBFのコードを受け取り、実行結果を返します。
あとはビルドするだけです。
wasm-pack build --target web
ビルドが成功すると、pkgディレクトリが生成されます。
比較用にJSでBFインタプリタを作る
今回のターゲットはWeb上で動作するWasmですが、比較のためにJSでBFのインタプリタを作っておきます。
なお、生成AIに対して「BFインタプリタをJSにコンバートして」のように指示して生成しています。
便利ですね。
export function bf_run(code) {
let tape = new Uint8Array(30000);
let ptr = 0;
let code_ptr = 0;
let loop_stack = [];
let result = '';
while (code_ptr < code.length) {
switch (code[code_ptr]) {
case '>':
ptr += 1;
if (ptr >= tape.length) {
let newTape = new Uint8Array(tape.length * 2);
newTape.set(tape);
tape = newTape;
}
break;
case '<':
if (ptr === 0) {
throw new Error("Pointer out of bounds");
}
ptr -= 1;
break;
case '+':
tape[ptr] = (tape[ptr] + 1) & 0xFF;
break;
case '-':
tape[ptr] = (tape[ptr] - 1) & 0xFF;
break;
case '.':
result += String.fromCharCode(tape[ptr]);
break;
case ',':
// 標準入力は実装しない
break;
case '[':
if (tape[ptr] === 0) {
let loop_count = 1;
while (loop_count > 0) {
code_ptr += 1;
if (code_ptr >= code.length) {
throw new Error("Unmatched [");
}
if (code[code_ptr] === '[') {
loop_count += 1;
} else if (code[code_ptr] === ']') {
loop_count -= 1;
}
}
} else {
loop_stack.push(code_ptr);
}
break;
case ']':
if (loop_stack.length === 0) {
throw new Error("Unmatched ]");
}
if (tape[ptr] !== 0) {
code_ptr = loop_stack[loop_stack.length - 1];
} else {
loop_stack.pop();
}
break;
default:
break;
}
code_ptr += 1;
}
return result;
}
HTMLで動作確認
それぞれのインタプリタをHTMLで動作確認してみます。
今回はラジオボタンでJSとWasmを切り替えられるようにしています。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>Wasm BF</title>
</head>
<body>
<h1>Wasm BF</h1>
<textarea id="code" rows="10" cols="80"></textarea>
<!-- ラジオボタンでJSネイティブとWasmを切り替える -->
<h2>Language</h2>
<input type="radio" name="lang" value="js" checked>JS Native
<input type="radio" name="lang" value="wasm">Wasm
<br>
<button id="run">Run</button>
<!-- 結果の表示 -->
<h2>Output</h2>
<p id="info">Time:</p>
<textarea id="output" rows="10" cols="80" readonly></textarea>
<script type="module">
// Wasmのインポート
import init, { run_bf } from './pkg/wasm_bf.js';
import { bf_run as js_bf_run } from './bf.js';
function get_code() {
return document.getElementById('code').value;
}
async function wasm_bf_run() {
// Wasmの初期化
await init();
// Wasmの関数を呼び出す
let result = run_bf(get_code());
return result;
}
function js_bf_run_wrapper() {
return js_bf_run(get_code());
}
document.getElementById('run').addEventListener('click', async () => {
let start = performance.now();
let output;
if (document.querySelector('input[name="lang"]:checked').value === 'js') {
output = js_bf_run_wrapper();
} else {
output = await wasm_bf_run();
}
let end = performance.now();
document.getElementById('output').value = output;
document.getElementById('info').textContent = `Time: ${end - start}ms`;
});
</script>
</body>
</html>
Wasm側の関数を呼び出す際は、init関数を呼び出して初期化を行います。
初期化が終わったら、run_bf関数を呼び出すことができます。
jsコードでやり取りが出来る点で、Wasmはjsとの連携がしやすいですね。
動作確認
ローカルサーバを立てて、動作確認を行います。
python3 -m http.server
ブラウザでhttp://localhost:8000にアクセスして、コードを入力して実行してみます。
実行できていそうですね。
実行速度の比較
それぞれの実行速度を検証するためにマンデルブロ集合を描画するBFプログラムを実行してみます。
なお、筆者のPCのスペックは以下の通りです。
- CPU: Intel Core i5-13600KF
- RAM: 64GB
- OS: Windows 11
- ブラウザ: Vivaldi 7.0.3495.27
jsで実行
先にJSで実行してみましょう。JSはそれ自体がインタプリタなので、実行速度には期待できません。
おお、すごい。ちゃんと描画されていますね。
実行時間は76941msほどかかりました。
Wasmで実行
本命のWasmで実行してみます。
Wasmは最適化されているはずなので、JSよりも高速に動作することが期待できます。
13171msで実行できました！早い！
ついでにネイティブRustで実行
せっかくなので、ネイティブのRustで実行してみます。
main.rsを作って、コードを実行してみます。
mod lib;
use lib::bf_interpreter;
fn main() {
// コマンドライン引数からBFのコードを取得
let args: Vec<String> = std::env::args().collect();
if args.len() != 2 {
eprintln!("Usage: bf <code>");
std::process::exit(1);
}
let code = &args[1];
let start = std::time::Instant::now();
// BFコードを実行
let result = bf_interpreter(&code);
let end = std::time::Instant::now();
println!("Time: {}ms", (end - start).as_millis());
println!("{}", result.unwrap());
}
実行する際は、cargo run --releaseでリリースビルドを行います。
また、コマンドライン引数にBFのコードを渡して実行します。
# mandelbrot.bfにBFのコードを記述している
cargo run --release "$(cat mandelbrot.bf)"
実行時間は10756msでした。
速度のまとめ
実行時間をまとめると以下の通りです。
| 言語 | 実行時間 |
|---|---|
| JS | 76941ms |
| Wasm | 13171ms |
| Rust | 10756ms |
WasmとネイティブRustの速度差は2415msほどでした。
ネイティブと比べると遅いですが、それでもJSの速度を考えると実用的な速度で実行できているかと思います。
まとめ
実をいうとこの記事を書こうとしたのはQiita Engineer Festa 2024で投稿しようとしていた内容で、1度同じようなことをやっていたのですが、その時はWasmのほうが遅くない？という結果になってしまいました。
なので、記事冒頭のフリは「おそいやないかーい！」とツッコミを入れるつもりで書いていたのですが、今回はWasmのほうが速かったですね。
もしかしたらブラウザがWasmコードを最適化してくれるようになったのかもしれません。
ということで、Rustを書くモチベーションが上がったので、また何か作ってみたいと思います。
それでは！