Rustでn!の再帰(if)、再帰(match)、反復をcriterionで性能比較した

## 概要
criterion の使用感を共有する記事です。
Rust の `test::bench` は手軽で便利なのですが stable で使えないので、criterion の使い方を試して見ることにした。

手元に次の階乗の実装があったので、比較してみた。

* 再帰で実装(条件分岐は if を使用)
* 再帰で実装(条件分岐は match を使用)
* 反復処理で実装

結果だけ言うと、反復処理で実装した非再帰版が半分の時間で終わりました。

### 環境

* WSL (Ubuntu 18.04)
   * rustc 1.57.0
   * criterion v0.3.5
   * cargo-criterion v1.1.0

## 結果

## 実行結果1 (計測誤りあり)

* 再帰で実装(条件分岐は if を使用) ※ u32
* 再帰で実装(条件分岐は match を使用) ※ u64
* 反復処理で実装 ※ u64

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/326797/199e1d48-0f29-54ab-2d95-02cb3d071228.png)

```console
$ cargo install cargo-criterion
...
factorial_recursive_if_else(20)
                        time:   [22.941 ns 23.075 ns 23.265 ns]

factorial_recursive_use_match(20)
                        time:   [41.701 ns 42.030 ns 42.381 ns]

factorial_iterative(20) time:   [21.983 ns 22.092 ns 22.231 ns]
```

## 実行結果2 (計測誤りを修正)
何気に前回実行した結果を覚えていて、劣化あるいは改善したことを伝えてくれている。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/326797/ca1618e4-207c-8c45-d49e-d0ef2bdee7fb.png)

```
$ cargo criterion
...
factorial_recursive_if_else(20)
                        time:   [42.656 ns 44.186 ns 46.075 ns]
                        change: [+83.448% +87.044% +91.432%] (p = 0.00 < 0.05)
                        Performance has regressed.

factorial_recursive_use_match(20)
                        time:   [40.481 ns 40.636 ns 40.818 ns]
                        change: [-4.1826% -3.2633% -2.3409%] (p = 0.00 < 0.05)
                        Performance has improved.

factorial_iterative(20) time:   [21.847 ns 21.980 ns 22.160 ns]
                        change: [-1.3603% -0.0827% +1.0785%] (p = 0.90 > 0.05)
                        No change in performance detected.
```

## 検証に使ったコード

factorial/src/lib.rs に測定対象のコードを入れている。

### 測定コード1: 再帰で実装(条件分岐は if を使用)

間違って u32 で実装していたもので比較していて、性能が良くでていてしまった。

```rust
pub fn factorial_recursive_if_else(n: u32) -> u32 {
    if n < 2 {
        1
    } else {
        n * factorial_recursive_if_else(n - 1)
    }
}
```

間違って u64 に修正したコード。

```rust
pub fn factorial_recursive_if_else(n: u64) -> u64 {
    if n < 2 {
        1
    } else {
        n * factorial_recursive_if_else(n - 1)
    }
}
```

### 測定コード2: 再帰で実装(条件分岐は match を使用)

```rust
pub fn factorial_recursive_use_match(num: u64) -> u64 {
    match num {
        0 | 1 => 1,
        _ => factorial_recursive_use_match(num - 1) * num,
    }
}
```

### 測定コード3: 反復処理で実装(u64)

```rust
pub fn factorial_iterative(num: u64) -> u64 {
    // (1..=num).product()
    (1..=num).fold(1, |acc, v| acc * v)
}
```

### Cargo.toml

`[dev-dependencies]` 以降が追加した行。

```toml
[package]
name = "factorial"
version = "0.1.0"
authors = ["..."]
edition = "2018"

[dependencies]

[dev-dependencies]
criterion = "0.3"

[[bench]]
name = "factorial_benchmark"
harness = false
```

### ベンチマーク用のコード

`black_box()` はコンパイラの最適化を妨げるために用意された補助関数です。

**factorial/benches/factorial_benchmark.rs**

```rust
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use factorial::factorial_recursive_if_else;
use factorial::factorial_recursive_use_match;
use factorial::factorial_iterative;

pub fn bm_factorial(c: &mut Criterion) {
    c.bench_function("factorial_recursive_if_else(20)", |b| b.iter(
        || factorial_recursive_if_else(black_box(20)))
    );

    c.bench_function("factorial_recursive_use_match(20)", |b| b.iter(
        || factorial_recursive_use_match(black_box(20)))
    );

    c.bench_function("factorial_iterative(20)", |b| b.iter(
        || factorial_iterative(black_box(20)))
    );
}

criterion_group!(benches, bm_factorial);
criterion_main!(benches);
```

## 参考: criterionで生成された各関数のレポート (2回目)

一応、補足すると n! 自体は $O(n \log(n))$ の計算量なのですが、`factorial_benchmark.rs` にあるとおり、 n は定数ですので、反復によって処理時間の変動はない想定です。今回は各実装の比較なので n が定数のほうが都合がよかったのですが、nを変えた比較が有効なこともあると思います。

* 右下のグラフ  
  横軸が反復回数(Iterations)、縦軸がトータルの処理時間(Total sample time)です。
  線形に増えているのであれば問題ないでしょう。別の言い方をすれば、メモリリークやらフラグメントやらを引き起こすコードが含まれているなら、徐々に劣化することもあるでしょう。また、キャッシュを生かすアプリの場合は高速化することもあると思います。
* 左下のグラフ  
  分布が分かるみたいですね。今回は単純なコードなので正規分布に従っているんだな…ぐらいの結果です。
  * 平均や中央値だけでOK!とは言えないことがある  
    バラつきが少ない場合は平均や中央値がおおよその傾向を表すことになるでしょうが、バラつきが大きい場合はそうとも言い切れず、オンラインアプリケーションなどでは問題となることもあります。
  * 複雑なアプリケーションの場合は複数の山の重ね合わせだったりすることもありますが、その場合は平均値の付近に多くのサンプルが集中していないこともあります
* Violin Plot
  * 分布の傾向が見やすいですね

### 測定コード1: 再帰で実装(条件分岐は if を使用; u64)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/326797/f26928fe-b52c-9033-525e-1517f25ffc0c.png)

### 測定コード2: 再帰で実装(条件分岐は match を使用; u64)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/326797/896daed8-b6b4-c56e-69fa-8e4233bd2835.png)

### 測定コード3: 反復処理で実装(u64)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/326797/831c6554-3ed6-372f-017c-7a74c196b52c.png)

## 参考

* [Criterion.rs Documentation](https://bheisler.github.io/criterion.rs/book/criterion_rs.html)
* [criterion.rs/faq.md at master · bheisler/criterion.rs](https://github.com/bheisler/criterion.rs/blob/master/book/src/faq.md)  
  `block_box` について言及がある