高效Rust代码技巧

How to write fast Rust code

翻译自:

How to write fast Rust code

之前该博主尝试将 Lisp 代码移植到 Rust ，结果发现执行效率实在不敢恭维，经过多次优化，性能得到了很大的提升。

让我们从原博主的错误出发，避坑，出发~

误用运算符

let mut n: BigUint = 1u8.into();
let ten: BigUint = 10u8.into();

// 这将分配一个新的 BigUint
n = n * &ten;

// 这不会分配新的实例
n = n * ten;

// 这也不会
n *= ten;

译注：其实就是需要注意使用借用则将重新分配。

Clone 不必要的数据

在 Rust 中每个数据都只有一个所有者，如果你正在使用一个临时数据结构，那么你应该使用数据的借用，而非拷贝数据

// String 数据的拥有者
let mut vec: Vec<String> = Vec::new();
vec.push("a".to_owned());
vec.push("b".to_owned());

{
    // 使用借用数据组成的数据结构
    let mut temp_vec: Vec<&str> = Vec::new();
    // 将原 String 借用为 &str
    temp_vec.push(&vec[0]);
}

{
    // 有所有权的数据结构
    let mut greedy_vec: Vec<String> = Vec::new();
    // 你需要 Clone 数据，否则将会报错
    greedy_vec.push(vec[1].to_owned());
}

需要注意的是使用包含引用的数据结构通常需要使用生命周期（lifetime），当可以避免克隆数据的成本（尽情的和生命周期 PvP 吧！编译器会慢慢把你“调教”成生命周期人形计算器的~）。

使用低效的的不可变数据结构

关于这一点可能存在一些争议，当使用不可变数据结构时可能会造成一些额外的 Clone，而不可变的数据本身更有效率。但不可否认的时：总是需要使用可变数据结构的。

特别是，当使用 Rust 的基本数据结构，比如 Vec ，任何操作都将克隆整个结构体，而不是像一些函数式语言那样使用 persistent data structures（持久数据结构）更有效率的运行。

因此需要如下优化：

/// before
for word in found_words {
    found_word = true;
    let mut partial_solution = words.clone();
    partial_solution.push(word);
    print_translations(num, digits, i + 1, partial_solution, dict)?;
}

/// after
for word in found_words {
    found_word = true;
    words.push(word);
    print_translations(num, digits, i + 1, words, dict)?;
    words.pop();
}

Naive! 打印输出

IO 操作是非常缓慢的，除了调试需要，请避免任何不必要的打印操作（这往往经常被大家忽略）

每一次打印都将获取 stdout 上的锁，然后调用 format! 宏解析格式，然后系统调用实际打印（听着就知道这很慢），同时这些所有的操作都是不带缓冲区的（即使有缓冲也于事无补）。

使用 Criterion.rs 评估性能

当我们需要分辨两种写法，谁会谁慢，你需要 Benchmark。Criterion.rs 是一个 Benchmark 微框架。（Rust 自带的 bench 还未 stable）

具体如何使用请查看官方文档吧。（Rust 的 Debug 与 release 性能差距巨大哦）

使用 SmallVec 避免堆分配

众所周知，Rust 的 Vec 是堆分配的，如果已经知道要使用一个非常小的 Vec 那么使用 SmallVec 就值得考虑了，它提供了和 Vec 类似的接口，同时却不是总是堆分配的，仅在需要“溢出”到堆上时，才是堆分配的。

原博主尝试使用它来代替 Vec 保存单词，但是使用 Criterion 进行 Benchmark 测试却并没取得预期的结果，实际性能都出现了不同程度的下降（最好的情况是时间上升了 15%），使用宏基准测试也证实了这一点，最好的情况下，也是二者没有区别

因此这一点需要进一步测试确定。

使用更快的 BigInt 实现

因为不是很常用，这一节我就省略了（懒），总而言之就是，有用，但是不大，我宁愿使用 Vec<u8>。

使用 bytes 迭代 str 而不是 chars

有人在 Reddit 上建议原博主使用 bytes 而不是 chars 迭代字符传，原本原博主对此表示不信，他认为 chars 应该是零成本的，但是他还是决定一试。

虽然在原博主的代码中，这样的改变仅仅提升了 3% 左右的性能，但是基准测试中，使用 bytes 迭代比使用 chars 迭代几乎快了整整一倍！

所以当你确定你输入的字符串仅包含 ASCII 时，使用 bytes 迭代它吧！

使用 `Vec<u8>` 代替 `BigUint`

这样做，在原博主的代码中带来了 7% 的提升，而另一位澳大利亚老哥在他的基础上移除了递归，这带来了 30% 的提升！

所以除非你确定你一定需要，不要使用 BigUint。

使用压缩字节实现更高效的存储

大多数情况下 Vec 都是极高性能的，但是它却是是堆分配的，相比于执行 CPU 指令的时间相比，还是显得比较昂贵的。

因此，我们需要一个更优化的数据结构来打包传递信息。

涉及原博主的具体算法我就不搬运了，感兴趣可以查看原帖。

使用更快的哈希函数

Rust 的标准库 Hash 使用 DoS-resistant 实现（安全性更好，但是性能并不是最优），当性能优先级很高的情况下，可以使用一些其他 hasher （比如 ahash ）作为替代。

原博主的算法在替换后，获得了 20% 到 40% 的性能提升。

Bloom Filter 等概率结构

暂时没看懂 T-T，也是优化数据结构啥的

Todo

5 October 2021

#Code
#Rust