Rustのwasmでバブルソート

今回は流行り物のRustをやってみました。Web Assembly(以下wasm)を使うとweb上でも出来る！JavaScriptより速い！と巷で噂なのですが、実際のところどうなんだろうと言う話です。

お題はバブルソートで、JavaScriptで実施した場合と、wasmにしたRustで実施した場合の両方で時間を比較してみました。結果はこんな感じです(以下は画像ですが、動かしたい人はこちら。JavaScript+wasmなのでクライアント側で動きます)。

かかった時間が縦軸なので、あれあれ？JavaScriptの方が速い！というのが結論になってしまいました。原因は最後まで分からず、chromeのJavaScriptエンジンが速いだけなのかなぁと予想しています。以下では、調べた結果などを載せておきます。

目的

Rustで作成したwasmを使い、JavaScriptとバブルソートの速度を比較する

背景

重いJavaScriptを軽くしたいので、巷で速いと噂のRustとwasmを使った高速化の検証をしたい

実装

Rustでバブルソート

まずはnativeで動かして計測してみます。

use std::time::{Instant};
fn main() {
    let n = 50000;
    let mut v = (0..n).rev().collect::<Vec<u32>>();
    println!("{:?}",&v[0..10]);
    let start = Instant::now();
    for i in 0..v.len() - 1 {
        for j in i+1..v.len() {
            if v[i] > v[j] {
                v.swap(i,j);
            }
        }
    }
    println!("Elapsed time: {:.2?}", start.elapsed());
    println!("{:?}",&v[0..10]);
}

計測は10回行い、その中で最小のものを採用しています。

$ rustc --version
rustc 1.59.0 (9d1b2106e 2022-02-23)
$ rustc hoge.rs -C opt-level=3
$ ./hoge
[49999, 49998, 49997, 49996, 49995, 49994, 49993, 49992, 49991, 49990]
Elapsed time: 950.04ms
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
$

ついでにC++でバブルソート

#include <chrono>
#include <iostream>
#include <vector>
using namespace std;
using namespace std::chrono;
template<typename T, typename S> S& operator <<(S& s, const vector<T>& v) {
    s << "[";
    bool is_first = true;
    for (auto e: v) {
        if (is_first) {
            is_first = false;
        } else {
            s << ",";
        }
        s << e;
    }
    s << "]";
    return s;
}
int main() {
    const size_t n = 50000;
    vector<uint32_t> v(n);
    for (size_t i = 0; i < v.size(); ++i) v[i] = v.size() - i - 1;
    cout << decltype(v)(v.begin(), v.begin() + 10) << endl;
    auto start = high_resolution_clock::now();
    for (int i = 0; i < v.size() - 1; ++i) {
        for (int j = i + 1; j < v.size(); ++j) {
            if (v[i] > v[j]) {
                auto tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
            }
        }
    }
    cout << "Elapsed time: " << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << "ms" << endl;
    cout << decltype(v)(v.begin(), v.begin() + 10) << endl;
    return 0;
}
$ g++ --version
g++ (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ g++ -O3 hoge.cpp -o hoge
$ ./hoge 
[49999,49998,49997,49996,49995,49994,49993,49992,49991,49990]
Elapsed time: 883ms
[0,1,2,3,4,5,6,7,8,9]
$

C++の勝利！(僅かに)

wasmの作成

nativeでの確認も出来たので、次はこれをwasm上に持っていきます。

Rustによるwasmの作成は、以下を頼りに試行錯誤しました。

https://rustwasm.github.io/docs/book/

手順通りに進めると…まずはwasm-packのインストール

https://rustwasm.github.io/wasm-pack/installer/

で、新しいcrateを作ります。

$ wasm-pack --version
wasm-pack 0.10.2
$ wasm-pack new bubble-sort
...
$ cd bubble-sort
$

このcrateの設定を書き換えます。

[Cargo.toml]

[package]
name = "bubble-sort"
version = "0.1.0"
authors = ["secret"]
edition = "2018"
[lib]
crate-type = ["cdylib", "rlib"]
[features]
default = ["console_error_panic_hook"]
[dependencies]
wasm-bindgen = { version = "0.2.79", features = ["serde-serialize"] }
serde = { version = "1.0.136", features = ["derive"] }
console_error_panic_hook = { version = "0.1.7", optional = true }
wee_alloc = { version = "0.4.5", optional = true }
[dev-dependencies]
wasm-bindgen-test = "0.3.29"
[profile.release]
opt-level = 3

変更内容は、

  • バージョンをcargo-editでupgrade
  • serdeというシリアライズ用のcrateを追加
  • wasm-bindgenで受け渡しにserdeを使う用のfeatureを指定
  • 最適化レベルをサイズ優先から最大(3)に変更

この時点でもうビルドは出来ますが、続けてソースを修正してしまいます。

[src/lib.rs]

mod utils;
use wasm_bindgen::prelude::*;
#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
// #[wasm_bindgen(module="/www/log.js")]
// extern "C" {
//     fn console_log_now();
// }
#[wasm_bindgen]
pub fn sort(arg: &JsValue) -> JsValue {
    let mut v: Vec<u32> = arg.into_serde().unwrap();
    // console_log_now();
    for i in 0..v.len() - 1 {
        for j in i + 1..v.len() {
            if v[i] > v[j] {
                v.swap(i, j);
            }
        }
    }
    // console_log_now();
    JsValue::from_serde(&v).unwrap()
}

sort関数が実装され、引数で渡されたJavaScriptのArrayをserdeを使用してVec<u32>に移し替えています。Vecはnative版同様のコードでバブルソートされて、serdeでまたJavaScriptのオブジェクトに移し替えて返しています。

あと、src/utils.rsは今回使わなかったので、内容を空にしています。

あとはビルドするだけですね。

$ wasm-pack build

デフォルトで最適化されますが、Cargo.tomlの設定に従い、最適化レベル3で最適化され、中間結果はtargetに、最終成果物はpkgディレクトリにnode.jsのパッケージとして出来上がります。JavaScriptから直に使われるのはbubble_sort.jsで、sort関数の定義はbubble_sort_bg.jsに入っており、そこからwasm(bubble_sort_bg.wasm)内のsort関数が呼ばれる感じになります。*.tsはTypeScript用の定義です。

HTML+JavaScriptの作成

実装

今回は少しでも見通しを良くするためにTypeScriptは使いません。

では、まずはnode.jsのパッケージを作ります。

$ node --version
v14.15.3
$ npm --version
6.14.9
$ npm init wasm-app www
🦀 Rust + 🕸 Wasm = ❤
$ cd www
$ npm install
...
$

これで真新しいパッケージが出来たので、wasmを含むパッケージ(への依存関係)を追加します。(ついでにグラフ作成用のchart.jsも追加しています)

$ npm install ../pkg
...
$ npm install chart.js
...
$

実装準備が整ったので実装します。

[index.html]

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello wasm-pack!</title>
  </head>
  <body>
    <noscript>This page contains webassembly and javascript content, please enable javascript in your browser.</noscript>
    <div>
      N(array size)=<input id="array_size" type="number" value="1000">
       C(testing count)=<input id="testing_count" type="number" value="10">
    </div>
    <div style="width:80%;"><canvas id="canvas"></canvas></div>
    <button id="rerun">re-run</button>
    <script src="./bootstrap.js"></script>
  </body>
</html>

修正した部分はinput要素2つとcanvas要素とbutton要素の4つ追加だけ。Nに対応するinputで要素数を指定し、Cに対応するinputでテスト回数を指定する感じになり、canvasにグラフが描かれ、ボタンで再計測という感じのUIになります。

[index.js]

import {console_log} from "./log.js";
import * as wasm from "bubble-sort";
import Chart from './node_modules/chart.js/dist/chart.js';
const createSourceArray = (N) => [...Array(N)].map((_, i) => N - i);
const measure = (f) => {
    const s = performance.now();
    f();
    const e = performance.now();
    return e - s;
};
const standard_sort = (ary) => {
    ary.sort((left, right) => left - right);
    return ary;
}
const js_bubble_sort = (ary) => {
    const i_end = ary.length - 1;
    const j_end = ary.length;
    for (let i = 0; i < i_end; ++i) {
        for (let j = i + 1; j < j_end; ++j) {
            if (ary[i] - ary[j] > 0) {
                const tmp = ary[i];
                ary[i] = ary[j];
                ary[j] = tmp;
            }
        }
    }
    return ary;
}
const rust_bubble_sort = (ary) => wasm.sort(ary);
const tests = [
    { name: "standard_sort", fn: standard_sort },
    { name: "js_bubble_sort", fn: js_bubble_sort },
    { name: "rust_bubble_sort", fn: rust_bubble_sort },
];
const execute_tests = () => {
    const getNumberFromDocument = (id) => parseInt(document.getElementById(id).value, 10);
    const N = getNumberFromDocument('array_size');
    const C = getNumberFromDocument('testing_count');
    const src = createSourceArray(N);
    const result = [...Array(C)].map(() => {
        tests.forEach((e) => {
            const ar = [...src];
            e.time = measure(() => {
                e.answer = e.fn(ar);
            });
        });
        const ansjs = tests[1].answer;
        const ansrs = tests[2].answer;
        if (! tests[0].answer.reduce((b, e, i) => (b && ansjs[i] == e && ansrs[i] == e), true)) alert('error!');
        return tests.reduce((o, e) => {
            console_log("[" + e.name + "]:" + e.time + "ms");
            o[e.name] = e.time;
            return o;
        }, {});
    });
    const ctx = document.getElementById('canvas');
    let chart = Chart.getChart(ctx);
    if (! chart) {
        chart = new Chart(ctx, {
            type: 'line',
            data: {
                labels: result.map((_,i) => i + 1),
                datasets: [
                    {
                        label: 'JS Benchmark',
                        fill: false,
                        backgroundColor: '#ffccd7',
                        borderColor: '#ff6183',
                    },
                    {
                        label: 'RS Benchmark',
                        fill: false,
                        backgroundColor: '#d1eafa',
                        borderColor: '#37a3eb',
                    }
                ]
            },
            options: {
                responsive: true,
                title: {
                    display: true,
                    text: name
                },
                tooltips: {
                    mode: 'index',
                    intersect: false,
                },
                hover: {
                    mode: 'nearest',
                    intersect: true,
                },
                scales: {
                    x: {
                        display: true,
                        title: {
                            display: true,
                            text: 'Index'
                        }
                    },
                    y: {
                        display: true,
                        title: {
                            display: true,
                            text: 'ms'
                        },
                        min: 0
                    }
                }
            }
        });
    }
    chart.data.datasets[0].data = result.map(e => e["js_bubble_sort"]);
    chart.data.datasets[1].data = result.map(e => e["rust_bubble_sort"]);
    chart.update();
};
execute_tests();
document.getElementById('rerun').addEventListener('click', ()=>execute_tests());

散らかってはいるものの、取り立てて説明するまでもないコードです。C個の整数が降順に並んだ配列を、JavaScriptで実装されたjs_bubble_sort関数とRustで実装されてwasmになったものを呼び出すrust_bubble_sort関数で、時間計測しながら昇順ソートし、JavaScript組込みのsort関数の結果と照合して検証し、それらをN回行った時間をグラフにします。CやNはチェックしてないので、変なことをしたら動作は保証しません😆

[log.js](新規追加)

export function console_log(...args) {
    // console.log(...args);
}
export function console_log_now() {
    console_log(Date.now());
}

今回新しく作ったJavaScriptとRust両方から呼べるロギングを行う関数です。ロギングをこの関数に統一することでログ出力を一箇所で止める事ができます(現在は見ての通りコメントしてるのでログが出ない)。

ビルド

実装完了なのでデバッグ実行します。

$ npm run start
...

ブラウザから http://localhost:8080/ を開くと、動きが確認できます。確認が出来たらブラウザのタブを閉じ、npmの実行をCtrl+Cで止めます。

あとは時間計測用にproductionビルドします。webpack.config.jsの

...
mode: "development",
...

を

...
mode: "production",
...

に変更します(こうすることで、デバッグ用の情報がない、配備向けのファイルセットになります)。あとはビルドするだけです。

$ npm run build

これでdistディレクトリに配備向けのファイルセットが出来上がります。

配備

distに作成されたファイルセットをnginxWebサーバに配備します。といってもただの静的ファイルなので、置くだけなのですが・・・。ただ.wasmファイルはデフォルトだとMIME typeの設定がなく、サーバからダウンロードしてもContent-Typeがおかしいからと言って弾かれてしまいます。そのため、nginxに設定の追加が必要になります。

nginxにwasmのMIMEタイプを追加

docker-compose.ymlの分離

このサーバは現在こんな危うい運用をしてるわけですが、この設定のnginxを改修していきます。

今回編集する必要があるファイルはnginxコンテナの/etc/nginx/nginx.confにあるので、まずは動作中のコンテナから内容をコピーしておきます。

$ cd nginx
$ docker-compose exec nginx bash -c "cat /etc/nginx/nginx.conf" > nginx.conf

取得したnginx.confを以下のように編集します。

...
http {
    include       /etc/nginx/mime.types;
    types {
        application/wasm wasm;
    }
    default_type  application/octet-stream;
...

編集したファイルが反映されるように、今度はコンテナ側の設定を変更し、バインドマウントされるようにします。まずはコンテナを停止してから

$ docker-compose down

docker-compose.ymlを以下のように修正します。

version: "3"
services:
  nginx:
    image: nginx
...
    volumes:
      - ./nginx.conf:/etc/nginx/nginx.conf
      - ./../wordpress_fpm/wordpress:/var/www/html
...

これでwasmをapplication/wasmで送信できるようになったので、nginxを再度起動します。

$ docker-compose up -d

ファイルの配備

後は、静的コンテンツを置いてある場所に適切に作成したdist/以下のファイルを配備するだけです(略)。

計測

そうして出来上がったWeb画面が先のリンクの、

https://elephantcat.work/bubble_sort/index.html

になります。これをPC(AMD Ryzen 5 1400)のWindows10上のVirtualBox 6.1で動作するUbuntu20.04を使い、N=50000, C=10で計測したときの結果(最短時間)です。

言語/環境時間[ms]
C++(native)883
Rust(native)950
Rust(wasm) on chromium(99.0.4844.51 snap 64bit)2086
JavaScript on chromium(99.0.4844.51 snap 64bit)1645
Rust(wasm) on firefox(97.0.2 64bit)2526
JavaScript on firefox(97.0.2 64bit)5724

chromiumでのJavaScript性能がRust wasmを上回る傾向は、Windows10のChrome上でも同様に確認され、世界で最も使用されていると思われるブラウザで、JavaScriptがRust wasmを上回るという、巷の噂と異なる驚愕の結果となった。ただし、同じJavaScriptでもfirefoxでは全く事情が異なり、JavaScriptがRust wasmに大きく水をあけられている。全体的にfirefoxはchromiumよりはるかに遅い。

考察

chromiumでRust wasmがJavaScriptより遅い原因を調べるため、仮説として以下2つの要因を検討する。

  1. JavaScript<->Rust wasm間を繋ぐserdeなどデータ受け渡しが重い可能性(以下データ受け渡し要因)
  2. nativeとJavaScriptではSIMDだが、wasmだけSIMDでない可能性(以下SIMD要因)

データ受け渡し要因の検証

既に仕込みがあるので分かっているかもしれないが、以下のファイルを修正。

[www/log.js]

export function console_log(...args) {
    console.log(...args);
}
export function console_log_now() {
    console_log(Date.now());
}

[src/lib.rs]

mod utils;
use wasm_bindgen::prelude::*;
#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
#[wasm_bindgen(module="/www/log.js")]
extern "C" {
    fn console_log_now();
}
#[wasm_bindgen]
pub fn sort(arg: &JsValue) -> JsValue {
    let mut v: Vec<u32> = arg.into_serde().unwrap();
    console_log_now();
    for i in 0..v.len() - 1 {
        for j in i + 1..v.len() {
            if v[i] > v[j] {
                v.swap(i, j);
            }
        }
    }
    console_log_now();
    JsValue::from_serde(&v).unwrap()
}

再ビルド＆実行

$ wasm-pack build
...
$ cd www
$ npm run build
...
$ cd dist
$ npx http-server
...

chromiumで http://localhost:8080/ を開いてN=50000,C=10で測定し、console出力を確認し、Date.nowの差分と計測時間を比較

Date.now差分[ms]計測時間[ms]差分[ms]差分の割合
21242133.19.10.43%
22162224.78.70.39%
220022066.00.27%
22202226.76.70.30%
21922197.85.80.26%
21942201.57.50.34%
22802286.46.40.28%
22132219.86.80.31%
22282241.113.10.58%
22752284.19.10.40%

表中差分[ms]が実際にデータ受け渡しにかかっている時間なので、10回分の平均割合が0.36である以上、誤差程度であると判断する。

つまり、データ受け渡し要因ではない。

SIMD要因

Rust native

$ objdump -S hoge | less
0000000000007b20 <_ZN5hoge34main17h4da545b6c24d9852E>:
...
    7b49:       66 0f 6f 05 af 44 03    movdqa 0x344af(%rip),%xmm0        # 3c000 <_fini+0x1c>
...
   7c2a:       48 89 44 24 50          mov    %rax,0x50(%rsp)
    7c2f:       48 89 54 24 58          mov    %rdx,0x58(%rsp)
    7c34:       31 c0                   xor    %eax,%eax
    7c36:       eb 10                   jmp    7c48 <_ZN5hoge34main17h4da545b6c24d9852E+0x128>
    7c38:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
    7c3f:       00 
    7c40:       48 3d 4f c3 00 00       cmp    $0xc34f,%rax
    7c46:       74 44                   je     7c8c <_ZN5hoge34main17h4da545b6c24d9852E+0x16c>
    7c48:       48 89 c1                mov    %rax,%rcx
    7c4b:       48 83 c0 01             add    $0x1,%rax
    7c4f:       48 89 c2                mov    %rax,%rdx
    7c52:       eb 19                   jmp    7c6d <_ZN5hoge34main17h4da545b6c24d9852E+0x14d>
    7c54:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
    7c5b:       00 00 00 
    7c5e:       66 90                   xchg   %ax,%ax
    7c60:       48 83 c2 01             add    $0x1,%rdx
    7c64:       48 81 fa 50 c3 00 00    cmp    $0xc350,%rdx
    7c6b:       74 d3                   je     7c40 <_ZN5hoge34main17h4da545b6c24d9852E+0x120>
    7c6d:       48 81 fa 50 c3 00 00    cmp    $0xc350,%rdx
    7c74:       0f 84 e1 00 00 00       je     7d5b <_ZN5hoge34main17h4da545b6c24d9852E+0x23b>
    7c7a:       8b 34 8b                mov    (%rbx,%rcx,4),%esi
    7c7d:       8b 3c 93                mov    (%rbx,%rdx,4),%edi
    7c80:       39 fe                   cmp    %edi,%esi
    7c82:       76 dc                   jbe    7c60 <_ZN5hoge34main17h4da545b6c24d9852E+0x140>
    7c84:       89 3c 8b                mov    %edi,(%rbx,%rcx,4)
    7c87:       89 34 93                mov    %esi,(%rbx,%rdx,4)
    7c8a:       eb d4                   jmp    7c60 <_ZN5hoge34main17h4da545b6c24d9852E+0x140>

main関数内7b49にSIMD命令自体はあるので、有効になっているが、バブルソートのメインループ(7c2a～7c8a)からは外れている。つまり、Rust nativeはSIMD命令だから速くなっているわけではなく、従ってSIMD要因でもない。

結論

考察で立てた仮説、データ受け渡し要因、SIMD要因はいずれも否定され、Chrome系でJavaScript性能がRust wasmを上回る原因は不明。

いよいよChromeが速すぎる説が正しい気がしてきたという状況。

まとめ

JavaScriptよりRust wasmが常に速いわけでもない。今後も検証が必要。

未分類javascript,Rust,wasm

Posted by first_user