本ブログではRustでのベンチマークテストを2通りで実装例と合わせて説明します．

Motivation

プログラミングの問題を解いていたときに，自分より速く動きそうだなと思う解答を見つけたので，パフォーマンスを測定してみようと思いました．問題と答案は参考として最後に記載しています．

Rustでのベンチマーク測定

調べてみると大きく2つの方法があるとわかったのでそれぞれ試します．

test crateのベンチマークテスト
criterion crateのベンチマークテスト

実装に移る前にいくつか前提事項を記載しておきます．

使ったライブラリのバージョン
rustc: 1.53.0
cargo: 1.53.0
criterion: 0.3.4

プロジェクト配下のディレクトリ構造

.
├── Cargo.lock
├── Cargo.toml
├── Dockerfile
├── src
│   ├── comp_answer.rs
│   ├── main.rs
│   └── my_answer.rs
└── target

src/my_answer.rs: 私の答案
src/comp_answer.rs: 比較対象の答案

（この2つの解答のパフォーマンスを比較します）

Dockerfile

FROM rust:latest

WORKDIR /usr/src/benchmark
COPY . /usr/src/benchmark

RUN apt-get update && apt-get install -y gnuplot
RUN rustup install nightly 
RUN cargo install --path .

必要最小限のイメージビルド
もちろんローカルで開発しても大丈夫
- その場合gnuplot（後述）というライブラリをローカルにインストールする必要がある
- Dockerで動かしたのはそれを避けたかったというだけです

それでは以降で2つのベンチマークテストの方法を説明します．

方法1）test crateを使う

Rustにはtestというcrateがあり，ベンチマークテストが可能です（Docs）．ただしまだunstableなので，nightlyバージョン^[1]でしか利用できないという特徴があります．

以下手順です．

1. nightlyバージョンをインストール

$ rustup install nightly
# (Dockerfileでイメージビルド時に実行)

2. テスト項目として `#[bench]` を追加

通常のテストとある程度同じような見た目の書き方になりますが，以下のように記述します．

/src/main.rs

#![feature(test)]
extern crate test;

mod my_answer;
mod comp_answer;

fn main() {
    // 省略
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_pascals_triangle_10(b: &mut Bencher) {
        b.iter(|| my_answer::pascals_triangle(10));
    }
    
    // ...
}

ファイル先頭の#![feature(test)]によってコンパイル時にcrate全体でunstableな"test"機能が利用可能になります（詳説は脚注参照^[2]^[3]）

extern crate testでこのファイルをtest crateが読み込めるようにします（externについては脚注参照^[4]）

#[bench]テストはBencherだけを引数に取り，iter()メソッドのクロージャの中に記載された処理を計測します
- したがって共通処理など測定対象から外したいものはiter()外に記述しておきましょう

3. ベンチマークテスト

# Dockerで実行する場合
$ docker run <IMAGE_TAG_NAME> cargo +nightly bench

# ローカルで実行する場合
$ cargo +nightly bench

結果は以下のようなフォーマットで出力されます．

running 1 tests
test tests::bench_pascals_triangle_10       ... bench:       3,306 ns/iter (+/- 256)

数字の意味ですが，ドキュメントに明記はないもののソースコードを見る限り「実行時間の中央値が3,306ns，標準偏差が256ns」ということのようです^[5]．

参考）test::benchソースコード

    write!(
        output,
        "{:>11} ns/iter (+/- {})",
        fmt_thousands_sep(median, ','),
        fmt_thousands_sep(deviation, ',')
    )

方法2）criterionを使ったベンチマーク測定

criterionは元々Haskell製のmicrobenchmarkツールですがRustでも利用できるようになっています．出力がHTMLで出来上がることもひとつの特徴です（CSVやJSONでの出力も可能です）．そしてstableでも利用できます．

以下手順です．

1. gnuplotをインストール

gnuplotとはC言語で書かれたGUI上に2次元・3次元図形を描画するツールで，その期限は1986年にも遡るようです．

# Linuxの場合（今回はDockerfileに記載してビルド時に実行）
$ apt-get update && apt-get install -y gnuplot

# Mac OSローカルに落とす場合
$ brew install gnuplot

2. テストディレクトリの作成

はじめにCargo.tomlに以下を追加します．

[dev-dependencies]
criterion = "0.3"

[[bench]]
name = "benchmark"
harness = false

次にbenches ディレクトリを作り，配下にbenchmark.rs (ファイル名はtomlと整合していれば自由）を作成します．このファイルにテストを記述することになります．

もちろん，測定したい関数をbenchmark.rsに再度直書きしても問題はないのですが，DRYに書くためにsrc配下に作成したファイルをモジュール的に読み込んで使うようにします．

このために一手間加える必要があります．というのも，benchesディレクトリは独立したcrateとしてコンパイルされるため，srcディレクトリを読み込むことができないためです．

benchmarks in the benchmarks directory are compiled as though they were a separate crate, so all the usual limitations that implies are in force. The benchmarks can only call functions that are publically visible outside of the crate (so pub(crate) won't work), and you will have to import things as use my_crate:my_module::my_function;

出所）https://github.com/bheisler/criterion.rs/issues/301

その解決策として，測定したい関数をコンパイル時にバイナリだけではなくライブラリとして出力する方法がプラクティスとして好まれるようです^[6]．

3. ライブラリとして利用できるようにする

src配下で作った関数を再利用可能なライブラリとして出力するように設定を変更していきます．

まず，src/lib.rsを作成し，Cargo.tomlファイルでライブラリ出力の設定を以下のように追加します．

[lib]
name = "mylib"
path = "src/lib.rs"

ベンチマークテストで利用するsrc/my_answer.rsとsrc/comp_answer.rsをlib.rsで読み込んでおきます．

src/lib.rs

pub mod my_answer;
pub mod comp_answer;

これで，ライブラリとして2つのファイルの関数が利用できるようになります．
最終的にディレクトリは以下のような構成になっています．

.
├── Cargo.lock
├── Cargo.toml
├── Dockerfile
├── benches（追加）
│   └── benchmark.rs（追加）
├── src
│   ├── comp_answer.rs
│   ├── lib.rs（追加）
│   ├── main.rs
│   └── my_answer.rs
└── target

4. ベンチマークテスト記述

いよいよテストを書いていきます．benchmark.rsファイルは次のように記述します．

benchmark.rs

use criterion::{criterion_group, criterion_main, Criterion};

use mylib::my_answer;
use mylib::comp_answer;

fn bm1(c: &mut Criterion) {
    c.bench_function("My Answer", |b| b.iter(|| my_answer::pascals_triangle(10)));
}

fn bm2(c: &mut Criterion) {
    c.bench_function("Comp Answer", |b| b.iter(|| comp_answer::pascals_triangle(10)));
}

criterion_group!(benches, bm1, bm2);
criterion_main!(benches);

use mylib:: がライブラリの読み込みをしているところ
criterion_group!マクロの2つ目以降の引数に計測する関数を渡す

5．ベンチマークテスト

cargo bench でcriterionによるベンチマークテストが実行されます

# Dockerで実行する場合
$ docker run <IMAGE_TAG_NAME> cargo bench

# ローカルで実行する場合
$ cargo bench

実行すると，target/criterion/report/ にindex.htmlが作成されます．これを開くと次のような画面でこれまでベンチマークテストを実行した処理が見れます．

（fib20というのはtutorial実行時の残骸）

個別のページを開くとわりと詳細なレポーティングチャートやテーブルが確認できます．

ページの説明
左上グラフ
KDE（Kernel Density Estimation）と呼ばれるもので，ヒストグラムを”なめらかにしたもの”と考えると良いかもしれません．横軸の値（処理時間）に対してそうなる確率（正確には確率密度）を示しています．criterionはヒストグラムを採用しなかった理由について，bins（何階層に分けるか）を決める必要がないためと説明しています^[7]．

右上グラフ
左上のKDEを算出するにあたって利用した元データのプロット．横軸がイテレーション回数，縦軸が実際の測定時間．引かれている直線は線形回帰（Linear Regression）直線．直線の傾きはslopeと呼ばれます．

左下表
各種統計量．Lower bound/Upper boundはそれぞれ95％区間の下限と上限．つまり95％の確率でこの範囲内になると推定することができます．なおslopeとmeanの値が微妙に異なりますがslopeのほうが最小二乗法による誤差最小となる値なのでより正確と言われています．

slope: 右上グラフの傾き：つまり処理を1回増やすと何秒増加するか
mean: 処理時間の平均値

↓グラフをクリックすると詳細も見れる

使ってみた感想

test crate

実装が簡単，実装時に調べることも少ない
実行が早すぎる時はイテレーション回して平均出してくれるのでありがたい
出力結果があるいみシンプルでわかりやすい（medianだけ！）
やはりstableで使えないのが気になる

criterion crate

アウトプットのクオリティが高い
設定しなくてもイテレーションを相当数回して回帰線を引いてくれる
stableで利用できる
わざわざlib.rsに必要な処理を書き出す手間がある
出力される数字が多いので「結局何を見る？」という迷いが生じそう

つまらない結論かもしれませんが，一長一短といったところでしょうか．

参考）実際パフォーマンスどうだったのか

解いていた問題

パスカルの三角形と呼ばれる数字を上から順に並べて配列で返す，という問題です．

解答

私の書いた答え

vector of vectorsを用意し， $i$ 番目要素にパスカルの三角形 $i+1$ 段の数字の配列を格納．最後にフラットなvectorにする
1つ下の段を作る際，足し算の元になる上段の数字を2つ複製し，片方をスライドしてから"縦方向に"足す
一時的にしか使わない配列をイテレーションごとに3つも作成するのでコストが高い

src/my_answer.rs

pub fn pascals_triangle(n: usize) -> Vec<usize> {
    // vector of vectors
    let mut rows = Vec::new();

    rows.push(vec![1]);

    for i in 0..n-1 {
        // create i+1 row from i th row
        // ex) generate 6th row of Pascal's Triangle
        //     5th row: [1, 4, 6, 4, 1]
        //     
        //     tmp left : [0, 1, 4, 6, 4, 1]  <-- shift to right and pad 0
        //     tmp right: [1, 4, 6, 4, 1, 0]  <-- push 0
        //             +) ------------------
        //     6th row  : [1, 5,10,10, 5, 1]  <-- column-wise addition
        let mut left = vec![0];
        let mut right = rows[i].clone();
        left.extend(rows[i].clone());
        right.push(0);
        let row = (0..i+2).map(|j| left[j] + right[j]).collect::<Vec<usize>>();
        // push i th row to vector
        rows.push(row);
        // loop above procedure
    }
    // flatten 
    rows.into_iter().flatten().collect::<Vec<usize>>()
}

比較対象とした解答

常に1次元ベクトルへのpushのみ
余計なベクトルを作成せず参照アドレスの計算を適切に行うことで次の値を計算

src/comp_answer.rs

fn pascals_triangle(n: usize) -> Vec<usize> {
    let mut res = vec![1];
    for i in 1..n {
        let r = res.len() - i;
        res.push(1);
        for j in 1..i {
            res.push(res[r + j - 1] + res[r + j]);
        }
        res.push(1)
    }
    res
}

ベンチマークテスト結果

test::benchでのbenchmarkテスト

上から順に

私の解答（n=10）
私の解答（n=100）
比較対象の解答（n=10）
比較対象の解答（n=100）

$ docker run rust-criterion cargo +nightly bench
   Compiling pascal_triangle v0.1.0 (.../pascal_triangle)
    Finished bench [optimized] target(s) in 1.15s
     Running unittests (.../pascal_triangle/target/release/deps/pascal_triangle-166431c5239c5f43)

running 4 tests
test tests::bench_pascals_triangle_10       ... bench:       3,306 ns/iter (+/- 256)
test tests::bench_pascals_triangle_100      ... bench:      94,793 ns/iter (+/- 6,237)
test tests::comp_bench_pascals_triangle_10  ... bench:         461 ns/iter (+/- 62)
test tests::comp_bench_pascals_triangle_100 ... bench:      12,661 ns/iter (+/- 5,342)

Criterionでのbenchmarkテスト

私の解答（n=10）：

比較対象とした解答（n=10）：

結論

10倍遅いコード書いてすみませんでした

反省

コードの読みやすさ（何をしてるかわかりやすいか）を意識するより，ぱっと見なんでそれで答えが出るのかわからなくても速いことを意識すべきだった
.clone()書いた時点で負けた．というか配列作りすぎ

ちなみに戻り値の配列の要素数は $(n^2+n)/2$ なので，ループ回数もほぼ同様であり，計算時間は $O(n^2)$ かなと思われました． $n$ を大きくして結果をプロットし，2次関数近似曲線を当ててみましたがよくフィットしていそうです．

参考文献

test crate
criterion｜Haskell
criterion｜Rust GitHub
Add example of calling source code from src/｜GitHub Issue
Rust: How to run benchmark tests｜Youtube
解いていた問題｜Pascal's Triangle

脚注

RustはChoo Choo Train方式のリリース管理をしており，nightly -> beta -> stableの順で状態が移行し，6週おきにstableが更新される． ↩︎
#[]はattributeと呼ばれるcrateやmoduleのメタデータ．!がつくとcrate全体に適用されます．ここでは"feature"属性に値"test"をセットしていますが，feature属性はビルトイン属性の一つで，unstableだったりexperimentalなコンパイラの機能を利用できるようにするものです． ↩︎
実際にtest crateのソースコードをみると，執筆時点では冒頭に#![unstable(feature = "test", issue = "50297")]と宣言されているのがわかります．unstable属性についてはRust developer guideを参照してください． ↩︎
externキーワードは2つの場面で利用されるもので，その一つが依存関係解決を目的とするものでした．ただし2018年版から基本的にextern crate xxxという構文は書く必要がなくなりました（Cargo.tomlに記載すればOK）．例外がsysrootのcrateで，今回のtest crateはその数少ないケースです． ↩︎
なお平均値ではなく中央値を用いた理由の一つは外れ値（偶然極端に遅かったケース）の影響を避けることができるからだと思われます．また，標準偏差について，真の値が平均値（≒中央値）の±標準偏差x2の範囲にある確率が95%という議論は測定値が正規分布に従うことが前提となるため，必ずしも適用できるわけではありません． ↩︎
https://github.com/bheisler/criterion.rs/issues/301 での議論及びそこで参照されるStackoverflow等を参照．一応読み込みファイルのパスをいじることで解決する方法もあるようですが推奨されていません． ↩︎
引用元．これは実際にその通りで，ヒストグラムはbinsの設定次第で形の見た目が全然違ってきますが，いくつにするかは自分たちで決める必要があります．一応「良いbinsの決め方」としtてSturge’s Ruleなどがあります． ↩︎

Discussion