benchmark_tests.md

# 基准测试

基准测试通常是在开发的最后阶段进行的(虽然也有例外)，用途是知道代码运行所花的时间，或提供代码中存在的性能缺陷的测试信息。

对所开发的程序执行基准测试有多种方法。

第一种简单的方法是使用 std::time::Instant 来测量程序的执行时间，虽然这并不能提供精确和完善的数据。

```rust
fn main() {
    use std::time::Instant;
    let now = Instant::now();

    // Code block to measure.
    {
        println!("test");
    }

    let elapsed = now.elapsed();
    println!("Elapsed: {:.2?}", elapsed);
}
```

第二种是使用 Rust 库，比较常见的库有 criterion 和 flamegraph


要做好一个基准测试及代码优化并不容易，需要考虑的因素很多：
- 不要过早的对代码进行优化和测试
- 在代码优化和安全性之间要平衡取舍
- 如果需要，对编译速度和编译文件大小之间要平衡取舍
- 使用优化编译命令对代码做基准测试，即编译的时候使用 rustc -O3 选项或 cargo build --release. 在使用 cargo bench 命令时它会自动打开优化
- 多次测试并进行统计。单次测试往往不够准确，测试用机的负载(操作系统，CPU，硬盘，缓存等)不同测试结果都会不同。
- 确保你的测试代码不会被后端优化掉，如 LLVM 会在后端进行各种级别的各种优化，或按照测试框架的库的说明来操作。
- 更多其他注意事项



对于 Fibonacci 序列算法，在以下的 Benchmark 中调用了四种算法

```rust

use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
use rust_fibonacci::*;
use std::collections::HashMap;

fn bench_fibs(c: &mut Criterion) {
    let mut group = c.benchmark_group("Fibonacci");

    for i in [20, 21].iter() {
        group.bench_with_input(BenchmarkId::new("Standard", i), i, |b, i| {
            b.iter(|| fib_standard(*i))
        });

        group.bench_with_input(BenchmarkId::new("Recursion", i), i, |b, i| {
            b.iter(|| fib_recursive(*i))
        });

        group.bench_with_input(BenchmarkId::new("Memoization", i), i, |b, i| {
            b.iter(|| {
                let mut memo = HashMap::new();
                fib_memoization(*i, &mut memo);
            })
        });

        group.bench_with_input(BenchmarkId::new("Iterator", i), i, |b, i| {
            b.iter(|| {
                FibIterator::default().nth(*i).unwrap();
            })
        });
    }
    group.finish();
}

criterion_group!(benches, bench_fibs);
criterion_main!(benches);

```



问答：
    在如下的四种算法代码中，预期最慢的是：


## 答案

A

```rust

pub fn fib_recursive(n: usize) -> usize {
    match n {
        0 | 1 => 1,
        _ => fib_recursive(n-2) + fib_recursive(n-1),
    }
}

```


## 选项

### 

B


```rust

pub fn fib_standard(n: usize) -> usize {
    let mut a = 1;
    let mut b = 1;

    for _ in 1..n {
        let old = a;
        a = b;
        b += old;
    }

    b
}

```

###

C

```rust

use std::collections::HashMap;

pub fn fib_memoization(n: usize, memo: &mut HashMap<usize, usize>) -> usize {
    if let Some(v) = memo.get(&n) {
        return *v;
    }

    let v = match n {
        0 | 1 => 1,
        _ => fib_memoization(n-2, memo) + fib_memoization(n-1, memo),
    };

    memo.insert(n, v);
    v
}

```

###

D

```rust

pub struct FibIterator {
    a: usize,
    b: usize
}

impl Default for FibIterator {
    fn default() -> Self {
        FibIterator { a: 1, b: 1 }
    }
}

impl Iterator for FibIterator {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.a;
        self.a = self.b;
        self.b = curr + self.a;

        Some(curr)
    }
}

```


<!--
ref:
    https://www.umcconnell.net/posts/2021-03-13-fibonacci-rust/
    https://stackoverflow.com/questions/13322479/benchmarking-programs-in-rust
    https://zhuanlan.zhihu.com/p/451184900
-->