tl;dr
- C++のツールをWebAssemblyを使ってWebに移植した
- WebAssemblyへコンパイルする言語としてRustを, JS-WebAssembly間のバインディングにwasm-bindgenを採用した
- 乱数計算処理をWebAssemblyで実装することで, C++実装と比べて0.2〜0.7倍, JS実装と比べて1〜13倍の性能が出た
はじめに
枠だけ確保してずっと放置していた去年のAdvent Calendarの記事がようやく書けたと思ったら, もう少しで今年のAdvent Calendarがやってくる季節になってしまいました. この記事は Pokémon RNG Advent Calendar 2017 23日目の記事です.
皆さんは「乱数調整」という言葉を知っているでしょうか? 乱数調整とは簡単に言うと計算機によってゲームのランダムな事象を予測し, 狙った結果を引き起こす行為のことです. 例えば, 乱数調整を行うことで珍しいアイテムや強いキャラを狙って入手したり, 貴重なイベントを狙って発生させたりできるようになります.
この Pokemon RNG Advent Calendar はポケモンにおける乱数調整についての記事を書く Advent Calendar です. 今回はAdvent Calendarのネタとして7世代の孵化乱数*1に関するツールを作ったので, その紹介をします.
背景
計算機によってゲームのランダムな事象を予測するためには, 現在の乱数生成器の状態を特定することが不可欠です. 現在でいくつかの特定手法が確立されており, その内の1つに乱数生成器の初期化方法に注目して初期Seedを特定する方法があります. これは乱数生成器が32bitの初期Seedで初期化されていることを利用して, 32bit値の総当たりにより初期Seedを特定するものです.
これを利用した初期Seed特定ツールがおだんぽよ氏開発の search-tinymt-seed です. search-tinymt-seed では乱数生成器の初期化直後に生成された8つのタマゴの個体の性格を元に, 初期Seedを 2^32 通り総当たりで検索して初期Seedを特定します.
しかしこのツールはC++によって実装されており, 公式サイトで配布されているビルド済みバイナリが動かない場合はユーザが自力でビルドしなければなりません. そこで今回はWebAssemblyを使って search-tinymt-seed をWebへと移植し, ブラウザさえあれば誰でも簡単に利用できるようにしてみました.
ツールの紹介
以下のリンクからアクセスできます.
search-tinymt-seed-for-web.netlify.com
乱数生成器の初期化直後に生成された8つのタマゴの個体の性格を入力すると, その条件にマッチする初期Seedを出力してくれます. また計算方式としてJavaScriptとより高速に計算が可能なWebAssemblyの2種類の方式が選べます. デフォルトの入力 [れいせい, きまぐれ, のんき, おっとり, すなお, おだやか, まじめ, てれや] では初期Seed候補として [0x0B76DDAF, 0x261C6F52] が出力されるようになっています.
技術面について
ツールのコアとなる乱数計算処理にWebAssemblyを使用することで, Webツールでありながら高速で, (WebAssemblyをサポートする) ブラウザがインストールされたあらゆる環境から利用できるというポータビリティを実現しています. PC版のChromeやSafari, Firefoxに加え, モバイルのChromeやSafariなどでも動くはずです *2.
WebAssemblyへとコンパイルできる言語には C/C++/Rust/AssemblyScript などがありますが, 今回はRustを採用しました. エコシステムの枯れ具合を考慮するとC/C++でも良いですが, 最近になってRust/WebAssembly周りのエコシステムが充実してきたため, 素振りがてらRustを使ってみることにしました.
WebAssemblyを使って開発する際にまず問題になるのはJS-WebAssembly間でのデータの受け渡しです. 現在のWebAssemblyの仕様では整数やIEEE754準拠の浮動小数点数などの基本的な値しか直接JS-WebAssembly間で受け渡しできないため, 構造体や文字列といったデータを受け渡す際は一工夫必要です. こうしたデータバインディングをWebAssemblyの仕様として取り入れる Host Bindings という Proposal も出ていますが, 現在仕様策定中でまだまだブラウザで利用できるような状況ではありません. そこで今回は Host Bindings のポリフィル的な位置づけにあるwasm-bindgenを使用し, データバインディングを実現しています.
例えばツールでは以下のようにRust側からJavaScript側でexportされた関数を呼び出して, 進捗の表示を実装しています.
// /src/worker/worker.ts // `foundSeeds` の型として `number[]` の代わりに `Uint32Array` を使い, // Rust側から見えるようにexportする export function postProgressAction (foundSeeds: Uint32Array, seed: number) { // UI スレッドに進捗を送信 postMessage({ type: 'PROGRESS', payload: { foundSeeds: Array.from(foundSeeds), calculatingSeed: seed, }, } as Progress) }
// /src/wasm/lib.rs // wasm_bindgen アトリビュートで wasm-bindgen による // データバインディングを利用することを宣言し, // 合せてimportしたいJavaScriptの関数のシグネチャと // その関数が宣言されている場所 (JavaScriptのモジュール) を指定する #[wasm_bindgen(module = "../worker/worker")] extern { // `&[u32]` と `Uint32Array`, `u32` と `number` が // それぞれ wasm-bindgen によって対応付けられる fn postProgressAction(foundSeeds: &[u32], seed: u32); } #[wasm_bindgen] pub fn search_tinymt_seed(natures: &[u32], has_shiny_charm: bool) -> Vec<u32> { let mut found_seeds: Vec<u32> = Vec::new(); let param = tinymt32::Param { mat1: 0x8F7011EE, mat2: 0xFC78FF1F, tmat: 0x3793FDFF, }; each_u32!(seed => { let mut rng = tinymt32::from_seed(param, seed); let found = natures .iter() .all(|&nature| nature == get_egg_nature(&mut rng, has_shiny_charm)); if seed % 0x0100_0000 == 0 && seed != 0 { // 通常のRustの関数と同じように呼び出す postProgressAction(found_seeds.as_slice(), seed); } if found { found_seeds.push(seed); postProgressAction(found_seeds.as_slice(), seed); } }); found_seeds }
またツールでは初期Seed検索中にUIスレッドがブロックされるのを防ぐため, 初期Seed検索処理をWebWorker上で実行しています. Safariなどの一部のブラウザには一定期間UIスレッドがブロックされるとブロックの原因になっているスクリプトを停止する機構が備わっているため, 「どうせ計算ボタン1つしかないツールだしUIスレッドくらいブロックされても困らないでしょ」という気持ちでWebWorker無しで雑に実装すると, 計算が途中で停止してしまいます. WebWorkerの導入はその対策にもなっている訳です.
計算時間の比較
移植元のC++実装はマルチスレッドで並列化されているため, JS/WebAssembly実装と同じシングルスレッド構成になるよう改変したものの結果を載せています. 環境やブラウザによりますがWebAssembly実装はC++実装と比べて0.2〜0.7倍, JS実装と比べて1〜13倍と, 十分ツールとしては実用的なレベルの性能が出ています. ちなみにこの計算時間はシングルスレッドでの計測値なので, マルチスレッドにより乱数計算処理を並列化すればさらなる性能の向上が見込めます.
困ったこと
Webpack で WebWorker 上から wasm を Dynamic Import できない
現状 worker-loader を使ってWebWorkerをバンドルしているプロジェクトにて, wasm-bindgen で生成されたスクリプトを WebWorker 上から Dynamic import すると実行時エラーになります.
例えば次のようなコードが実行時エラーになります.
// /app.js import Worker from './worker.js' const worker = new Worker() worker.onmessage = (event) => { console.log(event.data) // expected: 3 }
// /worker.js import('./lib.js').then((module) => { const result = module.add(1, 2) postMessage(result) })
// /lib.rs extern crate wasm_bindgen; use wasm_bindgen::prelude::*; #[wasm_bindgen] pub fn add(a: i32, b: i32) -> i32 { a + b }
// /webpack.config.js const { resolve } = require('path') const HtmlWebpackPlugin = require('html-webpack-plugin') const rootPath = resolve(__dirname, '.') const distPath = resolve(rootPath, './dist') module.exports = { entry: { app: resolve(rootPath, './app.js'), }, output: { path: distPath, filename: '[name].[hash].js', // WebWorkerの実行コンテキストでは `window` グローバルオブジェクトが無いので, // 代わりに `this` でグローバルオブジェクトを参照するようにする globalObject: 'this', }, resolve: { extensions: ['.js', '.wasm'], }, module: { rules: [ { test: /worker\.js$/, loader: 'worker-loader' }, ], }, plugins: [ new HtmlWebpackPlugin(), ], }
この問題はWebpackのBootstrapコード *3 の一部がエントリポイントだけに埋め込まれてしまい, WebWorker 内には埋め込まれないことに起因しています. WebWorkerとそれ以外のモジュールの実行コンテキストは分かれているので, 片方だけにBootstrapコードが埋め込まれているともう片方からそのコードを参照することが出来ず, エラーとなるという訳です. WebpackのWebWorker/WebAssemblyサポートはまだまだ未熟なため, こうしたエッジケースに嵌まることが度々あります.
今回はIssueのコメントにもあるように, worker-loaderに頼らず webpack.config.js で WebWorker を明示的に別のエントリポイントとして分けることで問題を回避しました. こうすることで Webpack が WebWorker とそれ以外のモジュールの実行コンテキストが分かれていることを正しく認識し, WebWorker にも初期化コードを埋め込んでくれるようになります.
// /webpack.config.js const { resolve } = require('path') const webpack = require('webpack') const HtmlWebpackPlugin = require('html-webpack-plugin') const webpackMerge = require('webpack-merge') const rootPath = resolve(__dirname, '.') const distPath = resolve(rootPath, './dist') const WORKER_PATH = '/worker.js' // ビルド後のworkerのパス const baseConfig = { resolve: { extensions: ['.js', '.wasm'], }, plugins: [ new webpack.DefinePlugin({ WORKER_PATH: JSON.stringify(WORKER_PATH), }), ], } // app用にentry/outputフィールドをカスタマイズした設定 const appConfig = webpackMerge(baseConfig, { entry: { app: resolve(rootPath, './app.js'), }, output: { path: distPath, filename: '[name].[hash].js', }, plugins: [ new HtmlWebpackPlugin(), ], }) // worker用にtarget/entry/outputフィールドをカスタマイズした設定 const workerConfig = webpackMerge(baseConfig, { target: 'webworker', entry: { 'worker': resolve(rootPath, './worker.js'), }, output: { path: distPath, filename: 'worker.js', // target フィールドで WebWorker 用に `globalObject` フィールドが // 自動で書き換えられているので, `globalObject` フィールドを手動で指定する必要はない // globalObject: 'this', }, }) module.exports = [appConfig, workerConfig]
// /app.js const worker = new Worker(WORKER_PATH) worker.onmessage = (event) => { console.log(event.data) // 3 }
おわりに
WebAssemblyを使ってC++の乱数調整ツールをWebに移植することで, ブラウザさえあれば誰でも簡単に利用できるポータビリティと, (ブラウザにより多少差はあるものの) 十分ツールとしては実用的なレベルの性能を実現することができました. 個人的にはもっと低い性能が出ると思っていたので, C++実装とそれほど大差のない性能が出た時は驚きました. WebAssemblyスゴイ.
また記事では触れていませんでしたが, 実はRustを使って型安全性/メモリ安全性のあるDXの良いWebアプリケーション開発環境の構築に挑戦する, というのも今回の開発で掲げたテーマの1つだったりします. リポジトリをよく見ると, ちゃっかりTypeScriptを導入していたり, JS/Rustの自動コンパイルやNetlifyによるpush駆動deployを実現していたりします. ですから今回の開発で小さいプロジェクトながらもそうした開発環境を構築できることが分かったのは大きな成果だったと思います. 今度はもっとガッツリRust/WebAssemblyを使って大きなものを作ってみたいですね. 最近は wasm-bindgen 以外にも js-sys や web-sys といったRustからJavaScript APIやWeb APIを直接利用できるcrateが登場しているので, 合せてそちらも触っていけると良さそうです.
*1:育て屋から貰えるタマゴの生成に関する乱数調整を対象とする分野のことです.
*2:ちなみに手元のEdge for Windowsでは動きませんでした
*3:参考: https://github.com/webpack/webpack/blob/a4e5f63d9d370b191bb9586570bc22bf2947e390/lib/MainTemplate.js
