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日目の記事です.
adventar.org
皆さんは「乱数調整」という言葉を知っているでしょうか? 乱数調整とは簡単に言うと計算機によってゲームのランダムな事象を予測し, 狙った結果を引き起こす行為のことです. 例えば, 乱数調整を行うことで珍しいアイテムや強いキャラを狙って入手したり, 貴重なイベントを狙って発生させたりできるようになります.
www.mizdra.net
この 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
github.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を使ってみることにしました.
www.mizdra.net
WebAssemblyを使って開発する際にまず問題になるのはJS-WebAssembly間でのデータの受け渡しです. 現在のWebAssemblyの仕様では整数やIEEE754準拠の浮動小数点数などの基本的な値しか直接JS-WebAssembly間で受け渡しできないため, 構造体や文字列といったデータを受け渡す際は一工夫必要です. こうしたデータバインディングをWebAssemblyの仕様として取り入れる Host Bindings という Proposal も出ていますが, 現在仕様策定中でまだまだブラウザで利用できるような状況ではありません. そこで今回は Host Bindings のポリフィル的な位置づけにあるwasm-bindgen を使用し, データバインディングを実現しています.
hacks.mozilla.org
例えばツールでは以下のようにRust側からJavaScript側でexportされた関数を呼び出して, 進捗の表示を実装しています.
export function postProgressAction ( foundSeeds: Uint32Array , seed: number ) {
postMessage( {
type : 'PROGRESS' ,
payload: {
foundSeeds: Array .from( foundSeeds),
calculatingSeed: seed,
} ,
} as Progress)
}
#[wasm_bindgen(module = "../worker/worker" )]
extern {
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 {
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の導入はその対策にもなっている訳です.
スレッドと計算の流れを示したアーキテクチャの図
計算時間の比較
計測時間の比較. MacOS/Android/iOSごとに違うデバイスで測定. 異なるデバイス間の値は単純に比較できないので注意.
移植元の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 すると実行時エラーになります.
github.com
例えば次のようなコードが実行時エラーになります.
import Worker from './worker.js'
const worker = new Worker()
worker.onmessage = (event ) => {
console.log(event .data)
}
import ('./lib.js' ).then((module) => {
const result = module.add(1, 2)
postMessage(result)
} )
extern crate wasm_bindgen ;
use wasm_bindgen :: prelude :: * ;
#[wasm_bindgen]
pub fn add (a: i32 , b: i32 ) -> i32 {
a + b
}
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' ,
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 にも初期化コードを埋め込んでくれるようになります.
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'
const baseConfig = {
resolve: {
extensions: [ '.js' , '.wasm' ] ,
} ,
plugins: [
new webpack.DefinePlugin({
WORKER_PATH: JSON.stringify(WORKER_PATH),
} ),
] ,
}
const appConfig = webpackMerge(baseConfig, {
entry: {
app: resolve(rootPath, './app.js' ),
} ,
output: {
path: distPath,
filename: '[name].[hash].js' ,
} ,
plugins: [
new HtmlWebpackPlugin(),
] ,
} )
const workerConfig = webpackMerge(baseConfig, {
target: 'webworker' ,
entry: {
'worker' : resolve(rootPath, './worker.js' ),
} ,
output: {
path: distPath,
filename: 'worker.js' ,
} ,
} )
module.exports = [ appConfig, workerConfig]
const worker = new Worker(WORKER_PATH)
worker.onmessage = (event ) => {
console.log(event .data)
}
おわりに
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が登場しているので, 合せてそちらも触っていけると良さそうです.
id:mizdra
id:miki_bene
id:hogashi
id:motemen
id:YaaMaa
id:hitode909
id:onk
id:swimy1113
id:Pasta-K
id:gazimum
