Zenn
Open9

wasm-pack で regex を使う時のビルドサイズとパフォーマンスの調査

Rust
#
wasmpack
#
regex
mizchimizchi

tl;dr

  • regex crate のサイズが重い(700k)
  • wasm-pack 環境で単純な正規表現のユースケースなら js-sys::RegExp を使う方が速度/サイズ両面で有利

なぜ調査するか

wasm で軽量プログラミング言語を作りたいと思い、rust のパーサジェネレータを調べていた。

nom でサンプルの #ff00cc みたいなカラーコードをパースする example を wasm ビルドすると、16kb程度なのに対し、lalrpop で簡単な構文で生成した wasm binary が 697kb になってしまった。

追ってみると lalrpop は構文定義の grammar.lalrpop から grammar.rs を生成する precompile 処理と、その後のランタイム処理で使われる lalrpop-util がある。

この lalrpop-util は regex の crate を依存に持っており、 regex 実装が全て入っている。特に、unicode table 関連の定義が多い模様

https://github.com/rust-lang/regex#crate-features

色々ビルドオプションを工夫して小さくすることを試してみる。最悪 wasm 実装なので js 側の regex を借用するのもベンチ取りつつ検討する

mizchimizchi

元々のコード

src/lib.rs
#[macro_use] extern crate lalrpop_util;

use wasm_bindgen::prelude::*;

lalrpop_mod!(pub grammar); // synthesized by LALRPOP

#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

#[wasm_bindgen]
pub fn parseable(input: &str) -> i32 {
    match grammar::TermParser::new().parse(input) {
        Ok(_) => Ok(1),
        Err(_) => Err(-1),
    }
}
src/grammar.lalrpop
use std::str::FromStr;

grammar;

pub Term: i32 = {
    <n:Num> => n,
    "(" <t:Term> ")" => t,
};

Num: i32 = <s:"1"> => i32::from_str(s).unwrap();
Cargo.toml
[package]
name = "mizl_lalrpop_parser"
version = "0.1.0"
authors = ["mizchi <miz404@gmail.com>"]
edition = "2021"
build = "build.rs" # LALRPOP preprocessing

[profile.release]
# Tell `rustc` to optimize for small code size.
opt-level = "s"

[dependencies]
serde = { version = "1.0", features = ["derive"] }
lalrpop-util = "0.19.7"
regex = "1"
wasm-bindgen = { version = "0.2.63", features = ["serde-serialize"] }
wee_alloc = { version = "0.4.5", optional = true }
console_error_panic_hook = { version = "0.1.6", optional = true }

[build-dependencies]
lalrpop = "0.19.7"

これを wasm-pack build --out-name mod --target web -- --features wee_alloc でビルドすると 697kb

mizchimizchi

regex を単体でビルドしてみる

use wasm_bindgen::prelude::*;

#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

use regex::RegexSet;

#[wasm_bindgen]
pub fn regex_match(input: &str) -> Vec<i32> {
    #[cfg(feature = "console_error_panic_hook")]
    console_error_panic_hook::set_once();

    let set = RegexSet::new(&[
        r"\w+",
        r"\d+",
        r"\pL+",
        r"foo",
        r"bar",
        r"barfoo",
        r"foobar",
    ]).unwrap();
    let matches: Vec<i32> = set.matches(input).into_iter().map(|m| m as i32).collect();
    matches.to_vec()
}

#[cfg(test)]
mod tests {
    use super::*;
    use wasm_bindgen_test::wasm_bindgen_test;
    #[wasm_bindgen_test]
    fn pass() {
        let x = regex_match("foobar");
        println!("{:?}", x);
        // assert_eq!(regex_match("foo"), vec![1, 2, 3]);
    }
}

[package]
name = "mizl_wasm"
version = "0.1.0"
authors = ["mizchi <miz404@gmail.com>"]
edition = "2021"
publish = false

[lib]
crate-type = ["cdylib"]

[dependencies]
wasm-bindgen = { version = "0.2.63", features = ["serde-serialize"] }
serde = { version = "1.0", features = ["derive"] }
wee_alloc = { version = "0.4.5", optional = true }
console_error_panic_hook = { version = "0.1.6", optional = true }
once_cell = "1.9.0"

[dependencies.regex]
version = "1.5"

[dev-dependencies]
wasm-bindgen-test = "0.3.13"

[profile.release]
opt-level = "s"

675K: mod_bg.wasm

つまり、lalrpop の 697k ほとんどのサイズが regex 由来なことがわかる。

regex のオプションをいじってビルドする

[package]
name = "mizl_wasm"
version = "0.1.0"
authors = ["mizchi <miz404@gmail.com>"]
edition = "2021"
publish = false

[lib]
crate-type = ["cdylib"]

[dependencies]
wasm-bindgen = { version = "0.2.63", features = ["serde-serialize"] }
serde = { version = "1.0", features = ["derive"] }
wee_alloc = { version = "0.4.5", optional = true }
console_error_panic_hook = { version = "0.1.6", optional = true }

[dependencies.regex]
version = "1.5"
default-features = false
# regex currently requires the standard library, you must re-enable it.
features = ["std"]

[dev-dependencies]
wasm-bindgen-test = "0.3.13"

[profile.release]
opt-level = "s"
src/lib.rs
use wasm_bindgen::prelude::*;

#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

use regex::RegexSet;

#[wasm_bindgen]
pub fn regex_match(input: &str) -> Vec<i32> {
    #[cfg(feature = "console_error_panic_hook")]
    console_error_panic_hook::set_once();

    let set = RegexSet::new(&[
        // r"\w+",
        // r"\d+",
        // r"\pL+",
        r"foo",
        r"bar",
        r"barfoo",
        r"foobar",
    ]).unwrap();
    let matches: Vec<i32> = set.matches(input).into_iter().map(|m| m as i32).collect();
    matches.to_vec()
}

#[cfg(test)]
mod tests {
    use super::*;
    use wasm_bindgen_test::wasm_bindgen_test;
    #[wasm_bindgen_test]
    fn pass() {
        let x = regex_match("foobar");
        println!("{:?}", x);
    }
}

ビルドサイズは 257kまで落ちるが、コメントアウトした3つが動かなくなる。

        // r"\w+",
        // r"\d+",
        // r"\pL+",

---- mizl_wasm::tests::pass output ----
    error output:
        panicked at 'called `Result::unwrap()` on an `Err` value: Syntax(
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        regex parse error:
            \w+
            ^^
        error: Unicode-aware Perl class not found (make sure the unicode-perl feature is enabled)
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        )', crates/wasm/src/lib.rs:22:8

Unicode-aware Perl class を有効にする必要があるらしい。

mizchimizchi

これだと \w+ が通る

[dependencies.regex]
version = "1.5"
default-features = false
features = ["std", "unicode-perl"]

    let set = RegexSet::new(&[
        r"\w+",
        r"\d+",
        // r"\pL+",
        r"foo",
        r"bar",
        r"barfoo",
        r"foobar",
    ]).unwrap();

283K で +26K 増える。

\L を動かすには unicode-gencat が必要

features = ["std", "unicode-perl", "unicode-gencat"]

    let set = RegexSet::new(&[
        r"\w+",
        r"\d+",
        r"\pL+",
        r"foo",
        r"bar",
        r"barfoo",
        r"foobar",
    ]).unwrap();

332K.

この時点で r"あ" も通るようになる。

mizchimizchi

ここから実行速度を計測する。

unicode 系を落として、perf を有効にしてみる。

[dependencies.regex]
version = "1.5"
default-features = false
features = ["std", "perf"]

389K。速度出すには +110K が必要

mizchimizchi

ちょっと趣向を変えて js-sys を使ってみる。ビルドサイズ自体はこちらが最小のはず。

use wasm_bindgen::prelude::*;

#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

use js_sys::RegExp;

#[wasm_bindgen]
pub fn regex_exec(input: &str) -> bool {
    #[cfg(feature = "console_error_panic_hook")]
    console_error_panic_hook::set_once();
    let expr = RegExp::new(r"\w+", "u");
    expr.test(input)
}

#[cfg(test)]
mod tests {
    use super::*;
    use wasm_bindgen_test::wasm_bindgen_test;
    #[wasm_bindgen_test]
    fn pass() {
        assert_eq!(regex_exec("foobar"), true);
    }
}

JS 側から RegExp を借用したので、当たり前だがビルドサイズはものすごく小さい。

4.8K  mod.js
3.3K  mod_bg.wasm

パフォーマンスは呼び出しのたびにブリッジコストがかかるのであまり良くないはず。

mizchimizchi

ここから regex, regex(perf), RegExp(js-sys) で比較していく。

use wasm_bindgen::prelude::*;

#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

use js_sys::RegExp;

use once_cell::sync::Lazy;

static REGEX_EXPR: Lazy<regex::Regex> = Lazy::new(|| {
    regex::Regex::new("\\w+").unwrap()
});

#[wasm_bindgen]
pub fn js_sys_regexp_test(input: &str) -> bool {
    #[cfg(feature = "console_error_panic_hook")]
    console_error_panic_hook::set_once();
    let expr = RegExp::new(r"(\d{4})-(\d{2})-(\d{2})", "u");
    expr.test(input)
}

#[wasm_bindgen]
pub fn regex_test(input: &str) -> bool {
    #[cfg(feature = "console_error_panic_hook")]
    console_error_panic_hook::set_once();
    REGEX_EXPR.is_match(input)
}

#[cfg(test)]
mod tests {
    use wasm_bindgen_test::wasm_bindgen_test;
    use crate::{js_sys_regexp_test, regex_test};

    #[wasm_bindgen_test]
    fn perf_js_sys_regexp() {
        let now  = js_sys::Date::now();
        let text = "2012-03-14, 2013-01-01 and 2014-07-05";
        println!("time: {:?}", now);
        for (_, _) in (0..100000).enumerate() {
            let result = js_sys_regexp_test(text);
            assert!(result);
        }
        let end  = js_sys::Date::now();
        println!("time: {:?}", end - now);
        assert_eq!(end - now, 0.0);
    }
    #[wasm_bindgen_test]
    fn perf_regex_test() {
        let now  = js_sys::Date::now();
        let text = "2012-03-14, 2013-01-01 and 2014-07-05";
        println!("time: {:?}", now);
        for (_, _) in (0..1000000).enumerate() {
            let result = regex_test(text);
            assert!(result);
        }
        let end  = js_sys::Date::now();
        println!("time: {:?}", end - now);
        assert_eq!(end - now, 0.0);
    }
}

wasm-pack test で println がうまく出力できなかったので、assert で値を見た。本来 cargo test -- --nocapture とか色々ハックがあるらしいが、wasm-pack 越しだとちゃんと動かなかった…。

同じ入力を大量に突っ込んでるのでおよそまともなベンチではないのだが、 rust で fake やその他のユーティリティが使えないのと、ブリッジコストを測りたかったので、これで良いとする。

  • perf_js_sys_regexp: 378ms
  • perf_regex_test(perf): 754ms
  • perf_regex_test(no perf): 6757ms

perf でも JS の方が 2倍近く速い。v8 jit が効いてるからか？

このコードを書く前に、regex を static にせずに毎回評価してると、ベンチマーク不可になるぐらい遅かった。

mizchimizchi

js側から使う時のブリッジコストを確認する。

  1. web-sys 実装の wasm 関数を js から呼ぶ
  2. regex crate の wasm 関数を js から呼ぶ
  3. js の RegExp を js から呼ぶ
// deno test --allow-read run.test.ts
import { assert } from "https://deno.land/std@0.126.0/testing/asserts.ts";
import ready, { regex_test, js_sys_regexp_test } from "./pkg/mod.js";

await ready();

Deno.test("js => wasm (rust regex)", () => {
  console.time("regex_test");
  for (let i = 0; i < 100000; i++) {
    assert(regex_test("2012-03-14, 2013-01-01 and 2014-07-05"));
  }
  console.timeEnd("regex_test");
});

Deno.test("js => wasm => js", () => {
  console.time("js_sys_regexp_test");
  for (let i = 0; i < 100000; i++) {
    assert(js_sys_regexp_test("2012-03-14, 2013-01-01 and 2014-07-05"));
  }
  console.timeEnd("js_sys_regexp_test");
});

Deno.test("js => js", () => {
  const re = /(\d{4})-(\d{2})-(\d{2})/u;
  console.time("RegExp");
  for (let i = 0; i < 100000; i++) {
    assert(re.test("2012-03-14, 2013-01-01 and 2014-07-05"));
  }
  console.timeEnd("RegExp");
});

js => wasm (rust regex) ...regex_test: 22ms
js => wasm => js ...js_sys_regexp_test: 529ms
js => js ...RegExp: 4ms

実行速度は RegExp > Rust regex 実装 >>>> js_sys 実装という感じ

mizchimizchi

まとめ

  • regex crate のビルドサイズはどう頑張っても重い
    • full で 700k
    • 全部落として 256k
    • 現実的な選択肢 features=["std", "perf", "unicode-perl"] で 450k ぐらい
  • wasm-bindgen から js-sys の呼び出しはそこまで大きくないので、ビルドサイズが第一なら検討したほうがいい
    • ただしJS から呼ぶ回数が多くなると js-sys のオーバーヘッドが顕著
    • 重いのは wasm_bindgen js-sys::RegExp に渡す際に string encoder 通ってるからな気はする

実際は rust のいろんなパッケージが regex のインターフェースであることを期待してるので置き換えるケースは少ないだろうが、同じインターフェースの実装を作ることができれば、js-sys::RegExp はかなり有効な選択肢になる。

で、lalrpop の実装を考えると、regex package を差し替えて同等の機能を web-sys::RegExp に差し替えるのが検討できる。lexer 差し替え機能があるのでそこを頑張る感じか