Rust性能分析之测试及火焰图，附(lru,lfu,arc)测试

性能测试，在编写代码后，单元测试及性能测试是重要的验收点，好的性能测试可以让我们提前发现程序中存在的问题。

测试用例

在Rust中，测试通常有两部分，一部分是文档测试，一部分是模块测试。
通常我们在函数定义的开始可以看到以///三斜杠开头的就是文档注释发布的时候会将自动生成到docs.rs中，其中以///包含的代码片断会就判断为文档测试，这样子就可以把功能与测试完美的结合在一起。
以下是Lru的例子：

/// LRU 全称是Least Recently Used，即最近最久未使用的意思
/// 一个 LRU 缓存普通级的实现, 接口参照Hashmap保持一致
/// 设置容量之后将最大保持该容量大小的数据
/// 后进的数据将会淘汰最久没有被访问的数据
///
/// # Examples
///
/// ```
/// use algorithm::LruCache;
/// fn main() {
///     let mut lru = LruCache::new(3);
///     lru.insert("now", "ok");
///     lru.insert("hello", "algorithm");
///     lru.insert("this", "lru");
///     lru.insert("auth", "tickbh");
///     assert!(lru.len() == 3);
///     assert_eq!(lru.get("hello"), Some(&"algorithm"));
///     assert_eq!(lru.get("this"), Some(&"lru"));
///     assert_eq!(lru.get("now"), None);
/// }
/// ```
pub struct LruCache<K, V, S> {
    /// 存储数据结构
    map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,
    /// 缓存的总容量
    cap: usize,
    /// 双向列表的头
    head: *mut LruEntry<K, V>,
    /// 双向列表的尾
    tail: *mut LruEntry<K, V>,
}

模块测试，在lru.rs文件底下会定义：#[cfg(test)] mod tests，这个将变成模块化测试

#[cfg(test)]
mod tests {
    use std::collections::hash_map::RandomState;

    use super::LruCache;

    #[test]
    fn test_insert() {
        let mut m = LruCache::new(2);
        assert_eq!(m.len(), 0);
        m.insert(1, 2);
        assert_eq!(m.len(), 1);
        m.insert(2, 4);
        assert_eq!(m.len(), 2);
        m.insert(3, 6);
        assert_eq!(m.len(), 2);
        assert_eq!(m.get(&1), None);
        assert_eq!(*m.get(&2).unwrap(), 4);
        assert_eq!(*m.get(&3).unwrap(), 6);
    }
}

我们将在执行cargo test的时候将会自动运行这些函数进行测试：可以显示如下内容：

   Compiling algorithm v0.1.5 (D:\my\algorithm)

    Finished test [unoptimized + debuginfo] target(s) in 1.95s
     Running unittests src\lib.rs (target\debug\deps\algorithm-3ecde5aa4c430e91.exe)

running 142 tests
test arr::circular_buffer::tests::test_iter ... ok
...

test result: ok. 142 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.16s    

   Doc-tests algorithm

running 147 tests

test src\cache\lruk.rs - cache::lruk::LruKCache (line 65) ... ok
...

test result: ok. 147 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 11.03s   

如果出错则会指出错误内容。

bench测试

在Rust中的bench可以测出每次迭代的耗时，但bench模块需要启用#![feature(test)]，即无法在stable版本的进行性能测试。
我们需要安装nightly版本，那么我们运行

rustup install nightly

如果需要在国内加速可以设置

$ENV:RUSTUP_DIST_SERVER='https://mirrors.ustc.edu.cn/rust-static' 
$ENV:RUSTUP_UPDATE_ROOT='https://mirrors.ustc.edu.cn/rust-static/rustup'

安装完之后我们可以用临时启用nightly版本进行运行，当前我们建立了benches/lru.rs文件
以下是bench的部分内容

#![feature(test)]

extern crate test;

use algorithm::{ArcCache, LfuCache, LruCache, LruKCache};
use test::Bencher;

static BENCH_SIZE: usize = 10000;

macro_rules! do_test_bench {
    ($cache: expr) => {
        for i in 0..BENCH_SIZE {
            $cache.insert(i, i);
            $cache.get(&i);
        }
    };
}

#[bench]
fn calc_lru(b: &mut Bencher) {
    b.iter(|| {
        let mut lru = LruCache::new(BENCH_SIZE / 2);
        do_test_bench!(lru);
    })
}

我们可以运行来进行bench测试

rustup run nightly cargo bench --bench lru

测试结果可以看出执行时间的变化

running 4 tests
test calc_arc  ... bench:   4,361,427.70 ns/iter (+/- 983,661.07)
test calc_lfu  ... bench:   3,170,039.17 ns/iter (+/- 571,925.64)
test calc_lru  ... bench:   1,306,854.55 ns/iter (+/- 198,070.97)
test calc_lruk ... bench:   1,282,446.16 ns/iter (+/- 226,388.14)

但是我们无法看出命中率这些参数，单纯时间的消耗并缓存结构并不公平。

测试命中率

我们将从速度和命中率两个维度来衡量，但是数据集目前不是很优，看不到Lfu及Arc的大优势。
完整代码放置在：https://github.com/tickbh/algorithm-rs/blob/master/examples/bench_lru.rs

顺序的数据集

插入数据的时候就快速获取该数据

前部分数据相对高频

插入数据的时候就获取之前插入的随机数据

相对来说，在非高频的场景中，Lfu需要维护频次的列表信息，耗时会Lru高很多，但是高频的访问场景中命中率的提高相对于cpu的消耗是可以接受的。

此处编写测试的时候不想大量的重复代码，且我们的实例并没有trait化，此处我们用的是运用宏处理来指的处理：

macro_rules! do_test_bench {
    ($name: expr, $cache: expr, $num: expr, $evict: expr, $data: expr) => {
        let mut cost = vec![];
        let now = Instant::now();
        let mut all = 0;
        let mut hit = 0;
        for v in $data {
            if v.1 == 0 {
                all += 1;
                if $cache.get(&v.0).is_some() {
                    hit += 1;
                }
            } else {
                $cache.insert(v.0, v.1);
            }
        }
        cost.push(now.elapsed().as_micros());
        println!("|{}|{}|{:.2}%|", $name, cost.iter().map(|v| v.to_string()).collect::<Vec<_>>().join("\t"), hit as f64 * 100.0 / all as f64);
    };
}

后续调用均可调用该宏进行处理：

fn do_bench(num: usize) {
    let evict = num * 2;
    let mut lru = LruCache::<usize, usize, RandomState>::new(num);
    let mut lruk = LruKCache::<usize, usize, RandomState>::new(num);
    let mut lfu = LfuCache::<usize, usize, RandomState>::new(num);
    let mut arc = ArcCache::<usize, usize, RandomState>::new(num / 2);
    println!("|名字|耗时|命中率|");
    println!("|---|---|---|");
    // let data = build_freq_data(evict);
    let data = build_high_freq_data(evict);
    // let data = build_order_data(evict);
    do_test_bench!("LruCache", lru, num, evict, &data);
    do_test_bench!("LruKCache", lruk, num, evict, &data);
    do_test_bench!("LfuCache", lfu, num, evict, &data);
    do_test_bench!("ArcCache", arc, num, evict, &data);
}

进行数据优化

编写代码尽量的不要过早优化，先实现完整功能，然后再根据火焰图耗时占比来进行热点函数优化。所以此时我们需要实现火焰图的显示：

安装火焰图https://github.com/flamegraph-rs/flamegraph

cargo install flamegraph 

在这里我使用的wsl启用的debian系统，安装perf

sudo apt install -y linux-perf

然后安装完之后就可以执行：

cargo flamegraph --example bench_lru

如果出现以下提前错误，则证明没有正确的连接perf版本，可以拷贝一个或者建一个软连接

/usr/bin/perf: line 13: exec: perf_5.15.133: not found
E: linux-perf-5.15.133 is not installed.

那么用如下的解决方案：

cp /usr/bin/perf_5.10 /usr/bin/perf_5.15.133

如果是macOs需要安装dtrace,如果未安装直接进行安装即可

brew install dtrace

此处需注意，macOs权限控制，需要用sudo权限。

然后运行完之后就可以得到一个flamegraph.svg的火焰图就可以查看耗时的程序了。

总结

好的测试用例及性能测试是对一个库的稳定及优秀的重要标准，尽量的覆盖全的单元测试，能及早的发现bug，使程序更稳定。