Go Fuzzing beta を go-yaml/yaml.v3 で試してみた

Go の fuzzing のプロポーザルについてツイートしていたら,Kaoriya さんに

と教えてもらったので,早速 Go 標準で利用可能になる fuzzing 機能(現在は beta 扱い)を使ってみました.

blog.golang.org

セットアップ

上記のブログ記事に書いてあるやり方で問題なくセットアップできました.

$ git clone https://github.com/go-yaml/yaml.git -b v3
$ cd yaml
$ go get golang.org/dl/gotip  # gotip 入れる
$ gotip download dev.fuzz  # dev.fuzz ブランチの Go をビルドしてインストール
$ gotip version
go version devel go1.17-5542c10fbf Fri Jun 4 03:07:33 2021 +0000 darwin/amd64

使ってみる

gofuzz を使ったことがあるので使い方について困ることは特にありませんでした.

$ gotip doc testing.F

API 一覧が見られます.

今回 Go に入った fuzzing の機能は go test の一部として実装されていて,Test で始まる関数が単体テストBench で始まる関数がベンチマークであるのと同様に Fuzz で始まる *testing.F を引数に取る関数を書くと,それが fuzzing のターゲットとして定義されます.

上記のブログ記事に倣って fuzzing のためのファイル fuzz_test.goリポジトリ直下に置いて,

// +build gofuzzbeta

package yaml_test

import (
    "strings"
    "testing"

    "gopkg.in/yaml.v3"
)

func FuzzMarshalUnmarshalYAML(f *testing.F) {
    f.Add("{}")
    f.Add("v: hi")
    f.Add("v: true")
    f.Add("v: 10")
    f.Add("v: 0b10")
    f.Add("v: 0xA")
    f.Add("v: 4294967296")
    f.Add("v: 0.1")
    f.Add("v: .1")
    f.Add("v: .Inf")
    f.Add("v: -.Inf")
    f.Add("v: -10")
    f.Add("v: -.1")
    f.Add("123")
    f.Add("canonical: 6.8523e+5")
    f.Add("expo: 685.230_15e+03")
    f.Add("fixed: 685_230.15")
    f.Add("neginf: -.inf")
    f.Add("fixed: 685_230.15")
    f.Add("canonical: true")
    f.Add("canonical: false")
    f.Add("bool: True")
    f.Add("bool: False")
    f.Add("bool: TRUE")
    f.Add("bool: FALSE")
    f.Add("option: on")
    f.Add("option: y")
    f.Add("option: Off")
    f.Add("option: No")
    f.Add("option: other")
    f.Add("canonical: 685230")
    f.Add("decimal: +685_230")
    f.Add("octal: 02472256")
    f.Add("octal: -02472256")
    f.Add("octal: 0o2472256")
    f.Add("octal: -0o2472256")
    f.Add("hexa: 0x_0A_74_AE")
    f.Add("bin: 0b1010_0111_0100_1010_1110")
    f.Add("bin: -0b101010")
    f.Add("bin: -0b1000000000000000000000000000000000000000000000000000000000000000")
    f.Add("decimal: +685_230")
    f.Add("empty:")
    f.Add("canonical: ~")
    f.Add("english: null")
    f.Add("~: null key")
    f.Add("empty:")
    f.Add("seq: [A,B]")
    f.Add("seq: [A,B,C,]")
    f.Add("seq: [A,1,C]")
    f.Add("seq: [A,1,C]")
    f.Add("seq: [A,1,C]")
    f.Add("seq:\n - A\n - B")
    f.Add("seq:\n - A\n - B\n - C")
    f.Add("seq:\n - A\n - 1\n - C")
    f.Add("scalar: | # Comment\n\n literal\n\n \ttext\n\n")
    f.Add("scalar: > # Comment\n\n folded\n line\n \n next\n line\n  * one\n  * two\n\n last\n line\n\n")
    f.Add("a: {b: c}")
    f.Add("a: {b: c, 1: d}")
    f.Add("hello: world")
    f.Add("a: {b: c}")
    f.Add("a: {b: c}")
    f.Add("a: 'null'")
    f.Add("a: {b: c}")
    f.Add("a: {b: c}")
    f.Add("a:")
    f.Add("a: 1")
    f.Add("a: 1.0")
    f.Add("a: [1, 2]")
    f.Add("a: YES")
    f.Add("v: 42")
    f.Add("v: -42")
    f.Add("v: 4294967296")
    f.Add("v: -4294967296")
    f.Add("int_max: 2147483647")
    f.Add("int_min: -2147483648")
    f.Add("int_overflow: 9223372036854775808")
    f.Add("int64_max: 9223372036854775807")
    f.Add("int64_max_base2: 0b111111111111111111111111111111111111111111111111111111111111111")
    f.Add("int64_min: -9223372036854775808")
    f.Add("int64_neg_base2: -0b111111111111111111111111111111111111111111111111111111111111111")
    f.Add("int64_overflow: 9223372036854775808")
    f.Add("uint_min: 0")
    f.Add("uint_max: 4294967295")
    f.Add("uint_underflow: -1")
    f.Add("uint64_min: 0")
    f.Add("uint64_max: 18446744073709551615")
    f.Add("uint64_max_base2: 0b1111111111111111111111111111111111111111111111111111111111111111")
    f.Add("uint64_maxint64: 9223372036854775807")
    f.Add("uint64_underflow: -1")
    f.Add("float32_max: 3.40282346638528859811704183484516925440e+38")
    f.Add("float32_nonzero: 1.401298464324817070923729583289916131280e-45")
    f.Add("float32_maxuint64: 18446744073709551615")
    f.Add("float32_maxuint64+1: 18446744073709551616")
    f.Add("float64_max: 1.797693134862315708145274237317043567981e+308")
    f.Add("float64_nonzero: 4.940656458412465441765687928682213723651e-324")
    f.Add("float64_maxuint64: 18446744073709551615")
    f.Add("float64_maxuint64+1: 18446744073709551616")
    f.Add("v: 4294967297")
    f.Add("v: 128")
    f.Add("'1': '\"2\"'")
    f.Add("v:\n- A\n- 'B\n\n  C'\n")
    f.Add("v: !!float '1.1'")
    f.Add("v: !!float 0")
    f.Add("v: !!float -1")
    f.Add("v: !!null ''")
    f.Add("%TAG !y! tag:yaml.org,2002:\n---\nv: !y!int '1'")
    f.Add("v: ! test")
    f.Add("a: &x 1\nb: &y 2\nc: *x\nd: *y\n")
    f.Add("a: &a {c: 1}\nb: *a")
    f.Add("a: &a [1, 2]\nb: *a")
    f.Add("foo: ''")
    f.Add("foo: null")
    f.Add("foo: null")
    f.Add("foo: null")
    f.Add("foo: ~")
    f.Add("foo: ~")
    f.Add("foo: ~")
    f.Add("a: 1\nb: 2\n")
    f.Add("Line separator\u2028Paragraph separator\u2029")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: 1\n")
    f.Add("a: 1\nc: 3\nd: 4\n")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: -b_c")
    f.Add("a: +b_c")
    f.Add("a: 50cent_of_dollar")
    f.Add("a: {b: https://github.com/go-yaml/yaml}")
    f.Add("a: [https://github.com/go-yaml/yaml]")
    f.Add("a: 3s")
    f.Add("a: <foo>")
    f.Add("a: 1:1\n")
    f.Add("a: !!binary gIGC\n")
    f.Add("a: !!binary |\n  " + strings.Repeat("kJCQ", 17) + "kJ\n  CQ\n")
    f.Add("a: !!binary |\n  " + strings.Repeat("A", 70) + "\n  ==\n")
    f.Add("a:\n b:\n  c: d\n")
    f.Add("a: {b: c}")
    f.Add("a: 1.2.3.4\n")
    f.Add("a: 2015-02-24T18:19:39Z\n")
    f.Add("a: 2015-01-01\n")
    f.Add("a: 2015-02-24T18:19:39.12Z\n")
    f.Add("a: 2015-2-3T3:4:5Z")
    f.Add("a: 2015-02-24t18:19:39Z\n")
    f.Add("a: 2015-02-24 18:19:39\n")
    f.Add("a: !!str 2015-01-01")
    f.Add("a: !!timestamp \"2015-01-01\"")
    f.Add("a: !!timestamp 2015-01-01")
    f.Add("a: \"2015-01-01\"")
    f.Add("a: !!timestamp \"2015-01-01\"")
    f.Add("a: 2015-01-01")
    f.Add("a: []")
    f.Add("\xff\xfe\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00\n\x00")
    f.Add("\xff\xfe\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00 \x00=\xd8\xd4\xdf\n\x00")
    f.Add("\xfe\xff\x00\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00\n")
    f.Add("\xfe\xff\x00\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00 \xd8=\xdf\xd4\x00\n")
    f.Add("a: 123456e1\n")
    f.Add("a: 123456E1\n")
    f.Add("First occurrence: &anchor Foo\nSecond occurrence: *anchor\nOverride anchor: &anchor Bar\nReuse anchor: *anchor\n")
    f.Add("---\nhello\n...\n}not yaml")
    f.Add("hello")
    f.Add("true")
    f.Add("true")
    f.Add("a: b\r\nc:\r\n- d\r\n- e\r\n")
    f.Add("a: b")
    f.Add("---\na: b\n...\n")
    f.Add("---\n'hello'\n...\n---\ngoodbye\n...\n")
    f.Add("hello")
    f.Add("goodbye")
    f.Add("i: &i [*h,*h,*h,*h,*h,*h,*h,*h,*h]\n")
    f.Add("yaml: document contains excessive aliasing")
    f.Add("null")
    f.Add("s2: null\ns3: null")
    f.Add("s2: null\ns3: null")
    f.Add("\"\\0\\\r\n")
    f.Add("  0: [\n] 0")
    f.Add("? ? \"\n\" 0")
    f.Add("    - {\n000}0")
    f.Add("0:\n  0: [0\n] 0")
    f.Add("    - \"\n000\"0")
    f.Add("    - \"\n000\"\"")
    f.Add("0:\n    - {\n000}0")
    f.Add("0:\n    - \"\n000\"0")
    f.Add("0:\n    - \"\n000\"\"")
    f.Add(" \ufeff\n")
    f.Add("? \ufeff\n")
    f.Add("? \ufeff:\n")
    f.Add("0: \ufeff\n")
    f.Add("? \ufeff: \ufeff\n")

    f.Fuzz(func(t *testing.T, data string) {
        var n yaml.Node

        if err := yaml.Unmarshal([]byte(data), &n); err != nil {
            t.Skip() // Not a valid input
        }

        b, err := yaml.Marshal(&n)
        if err != nil {
            t.Fatalf("Marshal failed to encode valid YAML tree %#v: %v", &n, err)
        }
        if err := yaml.Unmarshal(b, &n); err != nil {
            t.Fatalf("Marshal failed to decode valid YAML bytes %#v: %v", b, err)
        }
    })
}

簡単に中身を解説すると,

// +build gofuzzbeta

今はこのビルドタグを付けておく必要があります.リリース済みのバージョンの Go との互換性のため?みたいなので,正式リリース時には不要になりそうです.

f.Add("{}")
// ...

f.Fuzz(func(t *testing.T, data string) {
    // ...
})

fuzzing では事前にデータセットコーパス)を与えることで効率的に入力を生成できます.多分無くても問題は無いですが,事前情報無しに入力を生成していくので効率は悪くなるはずです.Go では f.Add() で有効な入力を文字列で教えてやります.今回はお試しなので decode_test.go で使われているテストケースから適当に引っ張ってきました.

f.Fuzz() にコールバックを与えると,fuzzer が生成した入力に対してコールバックが呼ばれます.コールバックの第2引数は interface{} なので好きな引数型を指定して良さそうですが,[]byte にしてみたらランタイムエラーでダメだったので,上記ブログ記事に合わせて string にしてあります.今回は YAML パーサに対して試すので,入力はバイト列ならとりあえずなんでも良く,まあ string で OK です(Go の stringUTF-8 的に不正なシーケンスでも良いので).

var n yaml.Node

if err := yaml.Unmarshal([]byte(data), &n); err != nil {
    t.Skip() // Not a valid input
}

b, err := yaml.Marshal(&n)
if err != nil {
    t.Fatalf("Marshal failed to encode valid YAML tree %#v: %v", &n, err)
}
if err := yaml.Unmarshal(b, &n); err != nil {
    t.Fatalf("Marshal failed to decode valid YAML bytes %#v: %v", b, err)
}

f.Fuzz() のコールバックの中では fuzzer から与えられた入力を使って,普段の単体テストのようにテストを書きます.今回は YAML のパーサとジェネレータを fuzzing したいので,パーサに食わせてみて,YAML として正しくない入力だった場合(yaml.Unmarshalerror を返した場合)はそれ以降の実行を諦めて t.Skip() します. yaml.Unmarshal が成功し,YAML として正しい入力だと分かったら,パース結果を yaml.Marshal で再度文字列化してジェネレータがクラッシュしないかを見ます.さらにジェネレータが正しい出力を吐けたか見るために,再度 yaml.Unmarshal に食わせてみています.初回のパース結果と2回目は完全に一致することが期待されるので,go-cmp などを使ってチェックしても良いかもしれません.

問題を検知した場合には普段どおり t.Fatal を使えば良いみたいです.

実行してみる

$ gotip test -fuzz=FuzzMarshalUnmarshalYAML

-fuzz にターゲットを指定すると実行が始まります.コアをあるだけ使おうとするので,-parallel でコア数を制限したほうが良いかもしれません.あとは問題を検知するまで放置するだけです.

今回はこんな感じで割とすぐ panic を引くことができました.

OK: 45 passed
fuzzing, elapsed: 3.0s, execs: 504 (168/sec), workers: 20, interesting: 19
fuzzing, elapsed: 6.0s, execs: 975 (162/sec), workers: 20, interesting: 28
fuzzing, elapsed: 9.0s, execs: 1441 (160/sec), workers: 20, interesting: 41

snip...

fuzzing, elapsed: 126.0s, execs: 19330 (153/sec), workers: 20, interesting: 126
fuzzing, elapsed: 129.0s, execs: 19794 (153/sec), workers: 20, interesting: 126
fuzzing, elapsed: 132.0s, execs: 20256 (153/sec), workers: 20, interesting: 127
found a crash, minimizing...
fuzzing, elapsed: 134.3s, execs: 20482 (153/sec), workers: 20, interesting: 127
--- FAIL: FuzzMarshalUnmarshalYAML (134.26s)
        panic: runtime error: invalid memory address or nil pointer dereference
        goroutine 2190 [running]:
        runtime/debug.Stack()
                /Users/rhysd/sdk/gotip/src/runtime/debug/stack.go:24 +0x90
        testing.tRunner.func1.2({0x12ee440, 0x14eb340})
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1271 +0x267
        testing.tRunner.func1()
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1278 +0x218
        panic({0x12ee440, 0x14eb340})
                /Users/rhysd/sdk/gotip/src/runtime/panic.go:1038 +0x215

        snip...

        testing.(*F).Fuzz.func1.1(0x137d850)
                /Users/rhysd/sdk/gotip/src/testing/fuzz.go:347 +0x193
        testing.tRunner(0xc0005f5a00, 0xc0006188c0)
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1325 +0x102
        created by testing.(*F).Fuzz.func1
                /Users/rhysd/sdk/gotip/src/testing/fuzz.go:341 +0x545

        --- FAIL: FuzzMarshalUnmarshalYAML (0.00s)

    Crash written to testdata/corpus/FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa
    To re-run:
    go test gopkg.in/yaml.v3 -run=FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa
FAIL
exit status 1
FAIL    gopkg.in/yaml.v3        139.073s

問題を引いた入力は testdata/corpus/{ターゲット名} 以下に保存されます.保存されたファイルを見てみると,

go test fuzz v1
string("#\n - - QI\xd7")

となっていて,実際のクラッシュする入力は string 型で "#\n - - QI\xd7" という値になることが分かります.

go test gopkg.in/yaml.v3 -run=FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa

のように {ターゲット名}/{コーパス名} を指定してテスト実行すると,クラッシュを引いた入力を与えて再実行することができます.これでクラッシュに再現性があるかどうかを確認できます.

再現の仕方が分かれば,後はクラッシュを修正するなり報告するなりするだけです.

github.com

今回分からなかったこと

  • fuzzing は通常,ある fuzzing 実施で育てたコーパスを次の fuzzing 実行で使うみたいなことをすると思うのですが,上記の f.Add() で追加する以外でコーパスを追加する方法がわかりませんでした.libFuzzerコーパスディレクトリに吐いたりディレクトリから読み込むとかできるので,似た機能がありそうなもんですが…
  • f.Fuzz() のコールバックの第2引数に使える型が分からない.少なくとも string が使えますが,他に何が使えるのか

Rust で Profile-Guided Optimization やってみた

TLDR

Rust で実装した Wasm インタープリタで PGO 試したら 0〜10% ぐらい速くなった

Profile-Guided Optimization (PGO) とは

PGO はコンパイラの最適化の手法のうちの1つですが,プログラムを実行した後に行うという点で少し他と異なります.

  1. まずは普段どおりの最適化オプションでプログラムをビルドする
  2. プログラムを実環境で動かし,profile data を取る
  3. 再度プログラムをビルドしなおす.ただし,ここの最適化では 2. で収集した profile data に基づいてインライン化やレジスタ割り当てなどを行う
  4. より最適化されたプログラムが出来上がる

このように,実世界でどう実行されるかをフィードバックした最適化をかけて再ビルドすることで,プログラムのビルド時で完結していた従来の最適化よりも進んだ最適化をかけられるようにするというものです.

最近だと,FacebookBOLT という大規模アプリ向けの最適化フレームワークを研究開発していたり,Googlellvm-propeller というこれも大規模アプリ向けのフレームワークを研究開発していたりで,最適化の分野では熱いトピックだと思ってます.あと Android のネイティブコードでも PGO が使えるみたいです

この PGO の仕組みは LLVM に既に実装されており,Clang などで利用可能で,Clang のユーザマニュアルもあります.上記の 2. において profile data を収集するために Linux の perf などを使う方法も考えられますが,LLVM を使っていれば,より正確なデータを効率的に収集し,それを元にした最適化をかけるところまで全部やってくれます.Rust の PGO サポートは LLVM のこの仕組みに完全に乗っかる形になっています.

Rust で PGO する

最近 Rust で PGO が既にサポートされているのを rustc のガイドで見かけて,僕の観測範囲ではまだ誰も試してなさそうだったので試してみました. 基本的には下記の短いドキュメントに非常にミニマルな main.rs 単一ファイルでのやり方が書いてあります.

Profile Guided Optimization - The rustc book

ただ,小さすぎるプログラムだと効果が出なさそうなのと,自分の開発してるプログラムでどれぐらい効果があるものなのか興味があったので,今回は wain プロジェクトを使ってやることにしました.

github.com

wain は僕が趣味で開発している WebAssembly インタープリタで,no dependency, Safe Rust で約1.5万行ほどの実装規模です.小さいですが,小規模というほどでもない感じですね. 外部依存は無いですが,複数 crate に分割して workspace で管理しています.

準備

PGO は Stable Rust でサポートされているようですが,一応最新の LLVM でやりたかったので nightly を使っています. rustup を使って LLVM 関連のツールをインストールします.

rustup component add llvm-tools-preview

llvm-tools-preview コンポーネントをインストールしてもパスは通されないので,~/.rustup/toolchains/{toolchain}-{triple}/lib/rustlib/{triple}/bin にパスを自前で通しておきます.

# nightly なら
export PATH=$HOME/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/x86_64-apple-darwin/bin:$PATH

# stable なら
export PATH=$HOME/.rustup/toolchains/stable-x86_64-apple-darwin/lib/rustlib/x86_64-apple-darwin/bin:$PATH

まずは profile を有効にしてビルドする

profile data を収集するために,まずは profile data を自動生成してくれるオプションを有効にした実行ファイルをビルドします.

CARGO_BUILD_RUSTFLAGS="-Cprofile-generate=$(pwd)/pgo-data" cargo build --release

$CARGO_BUILD_RUSTFLAGS を使うことで,Cargo が rustc を使ってコンパイルする際に追加でコンパイルオプションを指定できます.

-Cprofile-generate=$(pwd)/pgo-data

というコンパイルオプションにより,カレントディレクトリの pgo-data というディレクトリに profile data が収集されていきます.

ここで注意なのですが,cargo rustc コマンドは使えません.今回は依存 crate を含むバイナリ全体を最適化したいので,依存 crate のコードでも profile data を収集する必要があります.そのため,依存 crate をビルドする際にも -Cprofile-generate オプションを指定するのですが,cargo rustc は依存 crate のビルド時には rustc に指定したオプションを渡しません.

上記 cargo build により,普段どおり ./target/release/ に最適化された実行ファイルが出来上がります(今回は ./target/release/wain

profile data を収集する

今回はお試しなので,単に examples ディレクトリにある Wasm ファイルを順番に実行することにします

./target/release/wain ./examples/brainfxxk.wasm
./target/release/wain ./examples/mandelbrot.wasm
./target/release/wain ./examples/mt19937.wasm
./target/release/wain ./examples/n_queens.wasm
./target/release/wain ./examples/pi.wasm
...

これによって,./pgo-data 内に .profraw という拡張子のバイナリファイルが生成されます..profraw ファイルは実行ファイルと動的リンクライブラリの分だけ生成されるので,例えば2つライブラリを動的リンクしている実行バイナリであれば,3つの .profraw ファイルが生成されます.

wain は動的リンクライブラリを使っていないので,1つだけ .profraw が生成されます.

> ls ./pgo-data
default_13294579539908499303_0.profraw

./target/release/wain に異なる引数を与えて新しい Wasm コードを実行するたびに,収集した profile data が自動でこのファイルに追加されていきます.各 Wasm ファイルを ./target/release/wain で実行しながら default_13294579539908499303_0.profraw を見ると,徐々にファイルサイズが大きくなっていくのが分かります.

profile data を1つのファイルにマージする

前節で説明したように,profile data を収集した .profraw ファイルは複数になることがあります.また,今回は手元の PC でしか profile data を収集していませんが,例えば複数の異なる本番環境で実行した profile data を1箇所に持ってきたりすると必然的に profile data は複数ファイルになります.

これらを llvm-profdata コマンドで1つのファイルにマージします.llvm-profdata コマンドは準備の節で説明した llvm-tools-preview コンポーネントに含まれています.

llvm-profdata merge -o merged.profdata ./pgo-data

このコマンドを走らせるだけで,マージした profile data ファイル merged.profdata を生成してくれます.

profile data を元にした最適化を有効にしてビルド

収集した merged.profdataコンパイラに食わせて,PGO を行います.

CARGO_BUILD_RUSTFLAGS="-Cprofile-use=$(pwd)/merged.profdata" cargo build --release

このように -Cprofile-use オプションで指定してやるだけです.後は rustc と LLVM がすべてやってくれます.-Cprofile-generate の場合と同様に,cargo rustc は使えないので注意してください.依存 crate を含むプログラム全体で PGO を有効にします.

これで ./target/release/wain に PGO を有効にしてビルドされた実行ファイルが生成されます.通常のリリースビルドでサイズが 716KB,PGO を有効にすると 783KB でわずかにサイズが増えていました.

どれぐらい速くなったのか測る

PGO を有効にした wain と通常のリリースモードでビルドした wain を用意します.

mv ./target/release/wain wain-pgo
cargo build --release
mv ./target/release/wain wain-orig

profile data の収集に使った examples ディレクトリにある Wasm ファイルhyperfine を使って比較します.hyperfine は比較したいコマンドを与えると良い感じに実行・計測して比較してくれるすごいやつです.

hyperfine './wain-pgo ./examples/brainfxxk.wasm' './wain-orig ./examples/brainfxxk.wasm'
hyperfine './wain-pgo ./examples/mandelbrot.wasm' './wain-orig ./examples/mandelbrot.wasm'
hyperfine './wain-pgo ./examples/mt19937.wasm' './wain-orig ./examples/mt19937.wasm'
hyperfine './wain-pgo ./examples/n_queens.wasm' './wain-orig ./examples/n_queens.wasm'
hyperfine './wain-pgo ./examples/pi.wasm' './wain-orig ./examples/pi.wasm'
...

計測結果

examples/brainfxxk.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/brainfxxk.wasm 25.0 ± 1.9 23.6 40.1 1.06 ± 0.10
./wain-pgo examples/brainfxxk.wasm 23.5 ± 1.2 22.0 28.3 1.00

examples/mandelbrot.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/mandelbrot.wasm 234.1 ± 5.5 227.3 248.3 1.09 ± 0.03
./wain-pgo examples/mandelbrot.wasm 214.6 ± 3.0 211.1 220.4 1.00

examples/mt19937.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/mt19937.wasm 74.4 ± 1.7 72.6 79.9 1.07 ± 0.03
./wain-pgo examples/mt19937.wasm 69.7 ± 1.6 67.8 75.2 1.00

examples/n_queens.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/n_queens.wasm 9.2 ± 0.6 8.5 12.9 1.06 ± 0.11
./wain-pgo examples/n_queens.wasm 8.7 ± 0.6 8.0 12.1 1.00

examples/nbodies.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/nbodies.wasm 131.1 ± 2.7 128.2 139.1 1.12 ± 0.03
./wain-pgo examples/nbodies.wasm 117.3 ± 2.3 114.9 125.0 1.00

examples/pi.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/pi.wasm 115.7 ± 2.8 113.2 124.6 1.04 ± 0.04
./wain-pgo examples/pi.wasm 111.6 ± 2.7 109.2 120.3 1.00

examples/primes.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/primes.wasm 2.6 ± 0.4 2.2 5.1 1.01 ± 0.21
./wain-pgo examples/primes.wasm 2.6 ± 0.4 2.3 6.0 1.00

examples/quicksort.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/quicksort.wasm 2.5 ± 0.4 2.0 5.4 1.00
./wain-pgo examples/quicksort.wasm 2.5 ± 0.5 2.0 6.3 1.02 ± 0.25

examples/sqrt.wasm

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/sqrt.wasm 2.6 ± 0.4 2.1 5.2 1.00 ± 0.20
./wain-pgo examples/sqrt.wasm 2.6 ± 0.4 2.1 5.2 1.00

examples/brainfxxk.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/brainfxxk.wat 25.3 ± 1.0 24.0 29.2 1.08 ± 0.07
./wain-pgo examples/brainfxxk.wat 23.4 ± 1.1 22.3 30.9 1.00

examples/mandelbrot.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/mandelbrot.wat 234.5 ± 5.0 229.0 244.1 1.08 ± 0.03
./wain-pgo examples/mandelbrot.wat 217.2 ± 3.5 212.6 223.2 1.00

examples/mt19937.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/mt19937.wat 75.2 ± 1.5 73.6 81.1 1.06 ± 0.04
./wain-pgo examples/mt19937.wat 70.6 ± 2.2 68.4 77.9 1.00

examples/n_queens.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/n_queens.wat 9.8 ± 0.7 9.0 12.3 1.05 ± 0.10
./wain-pgo examples/n_queens.wat 9.3 ± 0.6 8.6 11.9 1.00

examples/nbodies.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/nbodies.wat 132.2 ± 3.2 128.0 139.8 1.12 ± 0.03
./wain-pgo examples/nbodies.wat 117.9 ± 2.0 115.7 122.6 1.00

examples/pi.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/pi.wat 115.8 ± 2.8 112.6 122.0 1.04 ± 0.03
./wain-pgo examples/pi.wat 111.3 ± 2.3 109.2 118.4 1.00

examples/primes.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/primes.wat 2.9 ± 0.4 2.5 6.1 1.01 ± 0.22
./wain-pgo examples/primes.wat 2.9 ± 0.4 2.4 5.6 1.00

examples/quicksort.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/quicksort.wat 2.8 ± 0.4 2.4 6.2 1.00
./wain-pgo examples/quicksort.wat 2.8 ± 0.4 2.3 6.6 1.00 ± 0.19

examples/sqrt.wat

Command Mean [ms] Min [ms] Max [ms] Relative
./wain-orig examples/sqrt.wat 2.9 ± 0.4 2.4 5.3 1.01 ± 0.19
./wain-pgo examples/sqrt.wat 2.8 ± 0.4 2.4 5.3 1.00

ほぼ変わらないものもありますが,0〜10% ほど速くなっていることが分かります.実行対象がほぼ決まっているプログラムであれば,プログラムに直接手を入れること無く最大 10% の高速化が得られると考えるとかなりお得に見えます.

ただし,もちろん profile data 収集時に使わなかった入力では逆に遅くなる可能性もあるので,実運用時には profile data をどう上手く収集するかがカギの1つになりそうです.

ちなみに毎回手でコマンドを打つのが面倒だったので数十行のシェルスクリプトを書いてやってました.

https://gist.github.com/rhysd/1324f6726f8905f4e71c0f549cb35d97

実際に実行したコマンドを知りたい場合は参照してみてください

GitHub Action で Vim や Neovim を簡単にインストールできる action-setup-vim をつくった

今週ちまちまと git-messenger.vimclever-f.vim の CI を GitHub Actions に移行していました.毎回 Vim プラグインの CI のために Vim や Neovim のセットアップを書くのが面倒なのと,Windows 上で Vim や Neovim を入れるのが(Powershell に不慣れなこともあり)大変だったので,GitHub Action として切り出すことにしました.

github.com

1ステップで Vim や Neovim を簡単にインストールできます.

  • Vim と Neovim 両対応
  • Linux, macOS, Windows すべてで動作
  • 'stable' と 'nightly' の両方に対応
  • 追記: 特定バージョンにも対応(v1.1.0)

使い方

下記のようにステップを書けば Vim または Neovim をインストールしてくれます.

macOS または Linux で安定版 Vim をインストール:

- uses: rhysd/action-setup-vim@v1

Windows では github-token を input として与える必要があります.これは,vim-win32-installer から最新のリリースを持ってくる必要があり,そのために GitHub API を叩いているからです.

- uses: rhysd/action-setup-vim@v1
  with:
    github-token: ${{ secrets.GITHUB_TOKEN }}

最新の Vim をインストールするには version: nightly を input に指定します.

- uses: rhysd/action-setup-vim@v1
  with:
    version: nightly
    github-token: ${{ secrets.GITHUB_TOKEN }}

Neovim をインストールするには neovim: true を input に指定します.最新の stable の Neovim がすべての OS でインストールできます.Vim とは異なり,Windows 上でも github-token input は不要です.

- uses: rhysd/action-setup-vim@v1
  with:
    neovim: true

昨晩ビルドされたばかりの nightly の Neovim をインストールするには version: nightly を指定すれば OK です.

- uses: rhysd/action-setup-vim@v1
  with:
    neovim: true
    version: nightly

これらのステップを実行後,Vim をインストールした場合は vim コマンドが,Neovim をインストールした場合は nvim コマンドがそれぞれ利用可能になっているはずです.

また,action の executable output としてインストールした Vim または Neovim の実行ファイルへのフルパスをセットしていて,それを使うこともできます.

例えば checkout@v2themis.vim をインストールし,action-setup-vimVim をインストールして単体テストを走らせる例は

# テストしたいプラグインを checkout
- uses: actions/checkout@v2
# themis.vim を checkout
- uses: actions/checkout@v2
  with:
    repository: thinca/vim-themis
    path: vim-themis
# Vim をインストール
- uses: rhysd/action-setup-vim@v1
  id: vim
# プラグインの単体テストを themis.vim で実行
- name: Run unit tests with themis.vim
  env:
    THEMIS_VIM: ${{ steps.vim.outputs.executable }}
  run: |
    ./vim-themis/bin/themis ./test

実際に clever-f.vim のワークフロー で利用しています.

インストールされる Vim および Neovim の詳細

インストール元は OS と version input によって下記のようになっています.優先度は

  1. システムのパッケージマネージャ
  2. 公式リリース
  3. ソースからビルド

となっています.ユーザ数や実行の速さを考慮してこうなっています.

Vim

OS Version Installation
Linux stable gvim-gnome パッケージを apt でインストール
Linux nightly vim/vim リポジトリの HEAD をビルド
macOS stable brew install macvim で Homebrew からインストール
macOS nightly vim リポジトリの HEAD をビルド
Widnows stable Windows での公式安定版は無いので,Nightly と同じ
Windows nightly 公式インストーラ repository のリリースからインストール

Neovim

OS Version Installation
Linux stable Neovim 公式の stable release からインストール
Linux nightly Neovim 公式の nightly release からインストール
macOS stable Homebrew を使って brew install neovim でインストール
macOS nightly Neovim 公式の nightly release からインストール
Windows stable Neovim 公式の stable release からインストール
Windows nightly Neovim 公式の nightly release からインストール

制限

今のところ,特定のバージョンを指定してインストールはできません.技術的制約があるわけではないので,もし需要があればやるかもしれません. v1.1.0 で指定可能になりました.

# Vim v8.2.0126 を全ての OS でインストール.Windows でも github-token input は必要ありません
- uses: rhysd/action-setup-vim@v1
  with:
    version: v8.2.0126

# Neovim v0.4.3 を全ての OS でインストール
- uses: rhysd/action-setup-vim@v1
  with:
    neovim: true
    version: v0.4.3

また,GUI バージョンについては現状ではサポートしていませんが,リリース物に含まれる場合はインストールされます.具体的には下記の場合です:

まとめ

Vim または Neovim を簡単にインストールできる action action-setup-vim を作成しました. GitHub Action の Vim プラグイン CI への導入の敷居が個人的にぐっと下がったので,他のプラグインについても順次移行していきたいところ.