のどあめ

ググってもなかなか出てこなかった情報を垂れ流すブログ。

【Rust×WebAssembly】木構造グラフの描画でWebAssemblyの処理速度を検証

概要

  • 力学的モデルを使った木構造グラフの描画を対象に
    JavaScriptとWebAssembly(WASM)の処理速度比較をした
  • ノード数が大きいグラフの描画ではWebAssemblyのほうが1.7倍くらい早かった。

やりたいこと

過去に何人かの方がWebAssemblyとJavaScriptの処理速度をされています。

彼らによると、フィボナッチ数列やループ処理などのベンチマーク的なスクリプトは、WebAssemblyのほうが数倍程度早いそうです。

今回は、WebAssemblyが実際に使われそうな例で処理時間の比較を行いたいと思います。

検証対象

数倍の処理速度向上で恩恵を受ける例として描画計算があります。

今回は、グラフ描画アルゴリズムの一つである力学的モデルを用いた 木構造グラフの描画時間を、JavaScriptとWebAssemblyで比較したいと思います。

アルゴリズム参考:力学モデル (グラフ描画アルゴリズム) - Wikipedia

検証に用いたスクリプト

github.com

f:id:ykicisk:20170514184326p:plain

ざっくりした使い方

  1. num_nodesに木構造グラフをのノード数を入力する
  2. [Init Graph]を押下してグラフのノード位置を初期化する
  3. [Update by JavaScript]または[Update by WASM]を押下して、力学モデルを使ってノード位置を更新する
  4. 実行にかかった時間がtimeに表示される

※ animation flagをOFFにした場合は、ノード位置が収束するまで描画しない。

実装概要

dist/index.html

https://github.com/ykicisk/wasm_graph/blob/master/dist/index.html

  • 諸々に利用するjQuery, 描画に利用するjCanvasをロードします。
  • dist/wasm/*dist/js/bundle.jsの順番にスクリプトをロードします。

src/js/main.js

https://github.com/ykicisk/wasm_graph/blob/master/src/js/main.js

※実際はBabelでdist/js/bundle.jsにトランスパイルされます。

  • 指定されたノード数で木構造グラフを生成します。
    • 描画に利用するノード・エッジの情報はWebAssemblyで利用しやすいように、ArrayではなくFloat32ArrayやInt32Arrayで定義します。
  • グラフ初期化関数・グラフ描画関数を定義します。
  • index.htmlにグラフ操作用のIF要素を追加します。
    • 指定したノード数のグラフを生成します。
    • 後述のGraphUpadaterを使ってグラフのノード位置を更新します。

src/js/GraphUpdater.js

https://github.com/ykicisk/wasm_graph/blob/master/src/js/main.js

※実際はBabelでdist/js/bundle.jsにトランスパイルされます。

  • グラフのノード位置を更新するGraphUpadaterクラス。
    • GraphUpdaterBase: 共通部分を実装した基底クラス
      • 共通で利用するノードの速度を格納するFloat32Arrayの確保
      • animation_flagによる処理切り替え
      • _update_loop()関数でイテレーション1回分の更新を行う。
    • JavaScriptGraphUpdater: JavaScriptでグラフ更新するクラス
    • RustGraphUpdater: WASMでグラフ更新するクラス
JavaScriptのグラフ更新関数

ノードの座標{x,y}_list、速度{vx,vy}_listを更新して、 ノードの運動エネルギー合計を返します。

スクリプト内で使われている変数は以下の通り

  • COULOMB, BOUNCE, ATTENUATION: 定数
  • {x,y}_list: 現在のノードのx, y座標(Float32Array)
  • {fx,fy}_list: ノードにかかる力のx, y成分(Float32Array)
  • {vx,vy}_list: ノードの速度のx, y成分(Float32Array)
  • tmp_{x,y}_list: 前ステップのノードのx, y座標(Float32Array)
  • edge_list: エッジ情報(i+1番目のノードとedge_list[i]番目のノードにエッジが貼ってある)(Int32Array)
_update_loop() {
    // init
    this.tmp_x_list.set(this.x_list);
    this.tmp_y_list.set(this.y_list);
    this.fx_list.fill(0.0);
    this.fy_list.fill(0.0);

    let energy = 0.0;
    for (let idx1 = 0; idx1 < this.num_nodes-1; idx1++){
        for (let idx2 = idx1 + 1; idx2 < this.num_nodes; idx2++){
            let dist_x = this.tmp_x_list[idx1] - this.tmp_x_list[idx2];
            let dist_y = this.tmp_y_list[idx1] - this.tmp_y_list[idx2];
            let rsq = Math.pow(dist_x, 2) + Math.pow(dist_y, 2);
            this.fx_list[idx1] += this.COULOMB * dist_x / rsq;
            this.fy_list[idx1] += this.COULOMB * dist_y / rsq;
            this.fx_list[idx2] -= this.COULOMB * dist_x / rsq;
            this.fy_list[idx2] -= this.COULOMB * dist_y / rsq;
        }
    }
    for (var i = 0; i < (this.num_nodes - 1);i++) {
        let idx1 = this.edge_list[i];
        let idx2 = i+1;

        let dist_x = this.tmp_x_list[idx2] - this.tmp_x_list[idx1];
        let dist_y = this.tmp_y_list[idx2] - this.tmp_y_list[idx1];

        this.fx_list[idx1] += this.BOUNCE * dist_x;
        this.fy_list[idx1] += this.BOUNCE * dist_y;
        this.fx_list[idx2] -= this.BOUNCE * dist_x;
        this.fy_list[idx2] -= this.BOUNCE * dist_y;
    }
    for (let idx = 0; idx < this.num_nodes; idx++){
        this.vx_list[idx] = (this.vx_list[idx] + this.fx_list[idx]) * this.ATTENUATION;
        this.vy_list[idx] = (this.vy_list[idx] + this.fy_list[idx]) * this.ATTENUATION;
        this.x_list[idx] += this.vx_list[idx];
        this.y_list[idx] += this.vy_list[idx];
        energy += Math.pow(this.vx_list[idx], 2) * Math.pow(this.vy_list[idx], 2);
    }
    return energy;
}
WASMのグラフ更新関数

処理をWebAssemblyに委任します。

constructor() {
    ...
    this.wasm_update_loop = Module.cwrap('wasm_update_loop',
                                            'number',
                                            ['number', 'number',
                                             'number', 'number',
                                             'number', 'number']);
    ...
}
_update_loop() {
    return this.wasm_update_loop(this.num_nodes, this.edge_list.byteOffset,
                                 this.x_list.byteOffset, this.y_list.byteOffset,
                                 this.vx_list.byteOffset, this.vy_list.byteOffset);
}

src/main.rs(WebAssembly)の実装はほぼJavaScriptと同じです。

#[no_mangle]
pub extern "C" fn wasm_update_loop(num_nodes_i32: i32,
                                   edge_list_ptr: *const i32,
                                   x_list_ptr: *mut f32,
                                   y_list_ptr: *mut f32,
                                   vx_list_ptr: *mut f32,
                                   vy_list_ptr: *mut f32)
                                   -> f32 {
    let mut energy: f32 = 0.0;

    unsafe {
        let num_nodes = num_nodes_i32 as usize;
        let mut x_list: &mut [f32] = std::slice::from_raw_parts_mut(x_list_ptr, num_nodes);
        let mut y_list: &mut [f32] = std::slice::from_raw_parts_mut(y_list_ptr, num_nodes);
        let mut vx_list: &mut [f32] = std::slice::from_raw_parts_mut(vx_list_ptr, num_nodes);
        let mut vy_list: &mut [f32] = std::slice::from_raw_parts_mut(vy_list_ptr, num_nodes);
        let edge_list: &[i32] = std::slice::from_raw_parts(edge_list_ptr, num_nodes - 1);
        let mut fx_list = vec![0.0; num_nodes];
        let mut fy_list = vec![0.0; num_nodes];
        let mut tmp_x_list = vec![0.0; num_nodes];
        let mut tmp_y_list = vec![0.0; num_nodes];
        tmp_x_list.clone_from_slice(x_list);
        tmp_y_list.clone_from_slice(y_list);
        for idx1 in 0..num_nodes - 1 {
            for idx2 in idx1 + 1..num_nodes {
                let dist_x = x_list[idx1] - tmp_x_list[idx2];
                let dist_y = y_list[idx1] - tmp_y_list[idx2];
                let rsq = dist_x * dist_x + dist_y * dist_y;
                fx_list[idx1] += COULOMB * dist_x / rsq;
                fy_list[idx1] += COULOMB * dist_y / rsq;
                fx_list[idx2] -= COULOMB * dist_x / rsq;
                fy_list[idx2] -= COULOMB * dist_y / rsq;
            }
        }
        for i in 0..num_nodes - 1 {
            let idx1 = edge_list[i] as usize;
            let idx2 = i + 1;

            let dist_x = tmp_x_list[idx2] - tmp_x_list[idx1];
            let dist_y = tmp_y_list[idx2] - tmp_y_list[idx1];

            fx_list[idx1] += BOUNCE * dist_x;
            fy_list[idx1] += BOUNCE * dist_y;
            fx_list[idx2] -= BOUNCE * dist_x;
            fy_list[idx2] -= BOUNCE * dist_y;
        }
        for idx in 0..num_nodes {
            vx_list[idx] = (vx_list[idx] + fx_list[idx]) * ATTENUATION;
            vy_list[idx] = (vy_list[idx] + fy_list[idx]) * ATTENUATION;
            x_list[idx] += vx_list[idx];
            y_list[idx] += vy_list[idx];
            energy += vx_list[idx].powf(2.0) * vy_list[idx].powf(2.0);
        }
    }
    energy
}

検証方法

ノード位置をランダムに初期化した木構造グラフに対して力学的モデルを適用します。 ノード数が同じグラフを3個生成して、ノード位置が収束して描画が完了するまでの時間の平均を比較します。

先のスクリプトのanimation flagはOFFで比較します。

検証結果

結果は下表です。 WebAssemblyを使うことで、ノード数が大きいときの処理時間が60%程度に抑えられることが読み取れます。

f:id:ykicisk:20170514192228p:plain

力学的モデルを利用した木構造グラフの描画においても、 WebAssemblyを用いることで計算時間短縮の恩恵を得られることがわかりました。

感想

  • WebAssemblyを使っても処理が数倍早い程度なので、応用先は考える必要がありそう。
  • WebAssemblyはまだまだ安定していないようにみえる。
    • 不具合があったときに、エラー文でググっても出てこない
    • 再起動すると動くようになる謎バグとかが多い
  • 当たり前だがJavaScriptmallocの相性が悪い。例えばClassにDestructorがないのでメモリ管理が大変。
  • WebAssemblyに状態をもたせるより、JavaScriptで状態を一元管理してWebAssemblyに引数で必要な情報だけ渡したほうが良さそう。
  • Rustの実装がunsafeのオンパレードになるなら、普通にCやC++で実装したほうがわかりやすそう。

参考ページ