无分支 Rust 编程移除 if 让过滤器速度最高提升 4 倍支持乌克兰。捐赠作者Serhii Potapov博客关于项目标签这是一个关于软件开发的博客。在我的职业生涯中大部分时间我都在领域世界编程在这个领域正确性远比性能重要。使用 Rust 通常就能让程序足够快只要避免 “N 1 SQL 查询” 问题基本就没问题了。但最近我遇到了一个必须优化热点代码路径的情况。也正是在这个过程中我发现了无分支编程技术其效果让我大为惊叹。下面我将通过一个小例子和大家分享。问题描述为了简单起见我们要对一个数字切片进行过滤返回大于给定阈值的元素这是数据库引擎每天都会处理的典型问题。通常我会这样写代码pub fn filter_iter(input: [f64], threshold: f64) - Vecf64 { input.iter().copied().filter(|x| x threshold).collect() }这段代码易读、符合习惯且正确。通常我不会再去改动它。但如果这段代码恰好处于热点路径上呢让我们来对它进行基准测试输入是一百万个均匀分布在 0.0..100.0 范围内的随机 f64 值。我们会尝试几个不同的阈值使过滤器分别保留 1%、25%、50%、75% 或 99% 的元素。例如阈值 50.0 大约会保留一半的元素。基准测试使用 criterion 进行代码存放在 branchless-rust-benchmarks 仓库中你可以在自己的机器上复现这些测试。令人困惑的结果以下是在我的笔记本电脑Intel i7 - 10875H上criterion 报告的结果保留比例输出大小时间1%~10k0.59 ms25%~250k2.69 ms50%~500k3.94 ms75%~750k2.75 ms99%~990k1.49 ms看看 50% 这一行我们只复制了一半的元素但它却是所有情况中最慢的。保留 99% 的元素意味着复制的数据量几乎是 50% 时的两倍但速度却快了 2.6 倍。每一行的输入数据量是相同的输出数据量显然也无法解释这些时间差异。肯定有其他因素在起作用。初步猜测预分配内存我们先排除一个常见的因素。collect() 方法事先不知道输出的大小所以 Vec 会在过程中不断增长并重新分配内存。每个 Rust 开发者对此都有一个本能反应预分配内存pub fn filter_prealloc(input: [f64], threshold: f64) - Vecf64 { let mut out Vec::with_capacity(input.len()); for x in input { if x threshold { out.push(x); } } out }保留 50% 元素时的结果是3.87 ms只快了约 2%。内存重新分配确实存在但它并非瓶颈所在。那么真正的瓶颈是什么呢CPU 的幕后工作原理让我们暂停一下回顾一下 CPU 的实际工作方式。现代 CPU 并非一次只执行一条指令而是采用深度 流水线 技术当一条指令正在执行时后续的指令已经在被提取和解码了。这种方式非常高效直到指令流遇到分支if x threshold { /* 保留 */ } else { /* 跳过 */ }CPU 不知道该走哪条路直到比较操作实际完成。但它不会干等着而是会进行猜测负责猜测的硬件被称为 分支预测器并沿着猜测的路径提前执行。分支预测器就像一位咖啡师你一进门他就开始为你制作平时常点的咖啡。如果你是常客这很棒你走到柜台时咖啡就已经准备好了但如果你每天都点不同的咖啡咖啡师就只能把做好的咖啡倒掉。错误的预测代价很高。CPU 必须丢弃所有提前执行的内容清空流水线然后从分支点重新开始。在典型的现代 x86 核心上这大约需要 15 - 20 个时钟周期而比较操作本身只需要大约 1 个时钟周期。现在我们的表格 就说得通了保留 1%答案几乎总是 “跳过”。预测器猜测 “跳过”并且 99% 的情况下都是正确的几乎没有代价。保留 99%情况相反原理相同。保留 50% 的随机数据没有规律可循。预测器就像抛硬币一样每处理两个元素就会猜错一次。这意味着大约有五十万次流水线清空操作。在 4 GHz 的核心上每次 15 - 20 个时钟周期总共大约会增加 2 ms 的纯开销这几乎就是 50% 和 99% 这两行之间的时间差距。需要注意的是问题不在于分支本身而在于依赖于不可预测数据的分支。这启发我们做一个有趣的实验。关键线索如果分支预测错误是问题所在我们应该可以保持相同的数据、相同的阈值和相同的代码只改变元素的顺序。让我们对输入数据进行排序当然排序操作不在测量范围内然后重新运行保留 50% 元素的测试输入数据保留 50%时间打乱顺序4.15 ms排序后0.93 ms同样是一百万个浮点数同样的阈值同样的函数速度却快了 4.5 倍。对于排序后的数据分支在前半部分一直说 “跳过”在后半部分一直说 “保留”。即使是最简单的预测器在一次错误预测后也能学会这种模式。Stack Overflow 上有一个获得 27K 点赞的问题正是关于这个现象“为什么处理排序后的数组比处理未排序的数组更快”当然对输入数据进行排序并不是一个可行的解决方案排序的开销远大于过滤本身而且我们通常需要保留原始数据的顺序。但现在我们知道了具体要解决的问题。我们能否在不排序数据的情况下避免这种类似抛硬币的预测呢欢迎来到无分支编程无分支编程的理念是完全移除不可预测的分支这样就没有需要猜测的内容了。我们不再决定是否写入某个元素而是始终写入然后通过比较结果来决定下一个元素的写入位置pub fn filter_branchless(input: [f64], threshold: f64) - Vecf64 { let mut out vec![0.0; input.len()]; let mut n 0; for x in input { out[n] x; n (x threshold) as usize; } out.truncate(n); out }花点时间来理解这个技巧每个元素都会无条件地写入 out[n]。(x threshold) as usize 在保留元素时为 1否则为 0。如果保留该元素游标 n 会向前移动如果不保留下一次迭代会直接覆盖掉被拒绝的值。最后n 保存了保留元素的数量truncate(n) 会截断多余的部分。比较操作仍然存在但它的结果现在被用作一个数字而不是决定程序下一步走向的决策。从编译器的角度来看我们将控制依赖转化为了数据依赖。实际上在生成的汇编代码中比较操作变成了一个 seta 指令只会产生 0 或 1。不再有分支也就不会有预测错误。细心的读者可能会指出out[n] x 会进行边界检查循环条件也是一个分支。确实如此但这些分支会连续执行一百万次相同的操作所以预测器可以轻松处理。只有不可预测的分支才是问题所在。以下是测试结果保留比例迭代方式无分支方式1%0.59 ms1.09 ms25%2.69 ms1.05 ms50%3.94 ms1.03 ms75%2.75 ms1.02 ms99%1.49 ms1.11 ms最坏情况下的速度几乎提高了 4 倍。看看无分支方式这一列运行时间不再依赖于数据这正是我们想要的结果。不过我们也付出了代价。在保留 1% 元素的情况下符合习惯的版本更快因为几乎总是能正确预测的分支几乎没有开销而无分支版本总是要进行一百万次写入操作。一般来说无分支代码并不一定更快它是用最佳情况换取了最坏情况的性能提升。是否应该采用无分支编程大多数情况下不建议采用。无分支代码更难阅读也更容易出错。此外编译器本身就掌握了很多优化技巧已经为我们做了很多类似的工作。只有当性能分析工具指出某个热点循环存在问题并且该循环中包含依赖于不可预测数据的分支时这种技术才可能带来显著的性能提升。总结分支本身开销不大但预测错误的分支代价很高。这就是为什么在处理打乱顺序的数据时相同的过滤器在保留 50% 元素时最慢分支预测器只能像抛硬币一样进行猜测。无分支编程用简单的算术运算取代了不可预测的分支始终写入有条件地前进。最坏情况下的速度几乎提高了 4 倍并且不再依赖于数据。这是一种权衡并非魔法最佳情况的性能会变差代码可读性也会降低。建议仅在经过性能测量的热点路径上使用。相关链接branchless-rust-benchmarks - 本文中的代码和基准测试为什么处理排序后的数组比处理未排序的数组更快 - Stack Overflow分支预测器 - Wikipedia错误预测的分支会成倍增加运行时间 - Daniel LemireC 中的无分支编程 - Fedor Pikus, CppCon 2021返回顶部索引问题描述令人困惑的结果初步猜测预分配内存CPU 的幕后工作原理关键线索欢迎来到无分支编程是否应该采用无分支编程总结相关链接关于 网站地图