为什么在循环访问具有 240 个或更多元素的数组时会对性能产生很大影响

Question

在 Rust 中的数组上运行 sum 循环时，我注意到当CAPACITY>= 240 时性能大幅下降。CAPACITY= 239 大约快 80 倍。

Rust 是否正在为"短"数组进行特殊的编译优化？

用rustc -C opt-level=3编译。

use std::time::Instant;
const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;
fn main() {
let mut arr = [0; CAPACITY];
for i in 0..CAPACITY {
arr[i] = i;
}
let mut sum = 0;
let now = Instant::now();
for _ in 0..IN_LOOPS {
let mut s = 0;
for i in 0..arr.len() {
s += arr[i];
}
sum += s;
}
println!("sum:{} time:{:?}", sum, now.elapsed());
}

Answer 1

总结：低于 240，LLVM 完全展开内部循环，这让它注意到它可以优化重复循环，打破您的基准。

---

您发现了一个神奇的阈值，超过该阈值，LLVM 将停止执行某些优化。阈值为 8 字节 * 240 = 1920 字节(您的数组是usizes 的数组，因此长度乘以 8 字节，假设 x86-64 CPU)。在此基准测试中，一个特定的优化(仅针对长度 239 执行)是造成巨大速度差异的原因。但让我们慢慢开始：

(本答案中的所有代码均使用-C opt-level=3编译)

pub fn foo() -> usize {
let arr = [0; 240];
let mut s = 0;
for i in 0..arr.len() {
s += arr[i];
}
s
}

这个简单的代码将产生人们期望的大致程序集：一个添加元素的循环。但是，如果将240更改为239，则发出的程序集会有很大不同。在 Godbolt Compiler Explorer 上看到它。下面是程序集的一小部分：

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

这就是所谓的循环展开：LLVM粘贴循环体大量时间以避免执行所有这些"循环管理指令"，即递增循环变量，检查循环是否已结束并跳转到循环的开始。

如果您想知道：paddq和类似的指令是 SIMD 指令，允许并行汇总多个值。此外，两个16字节SIMD寄存器(xmm0和xmm1)并行使用，因此CPU的指令级并行性基本上可以同时执行其中两条指令。毕竟，它们是相互独立的。最后，将两个寄存器相加，然后水平相加得到标量结果。

现代主流的 x86 CPU(不是低功耗 Atom)在 L1d 缓存中命中时，每个时钟确实可以做 2 次矢量加载，paddq吞吐量也至少为每个时钟 2 个，大多数 CPU 都有 1 个周期的延迟。 请参阅 https://agner.org/optimize/以及有关多个累加器的问答，以隐藏延迟(点积的FP FMA)和吞吐量瓶颈。

LLVM 在未完全展开时会展开一些小循环，并且仍然使用多个累加器。因此，通常，即使没有完全展开，前端带宽和后端延迟瓶颈对于LLVM生成的环路来说也不是一个大问题。

---

但是循环展开并不会导致 80 倍的性能差异！至少不是单独循环展开。让我们看一下实际的基准测试代码，它将一个循环放入另一个循环中：

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;
pub fn foo() -> usize {
let mut arr = [0; CAPACITY];
for i in 0..CAPACITY {
arr[i] = i;
}
let mut sum = 0;
for _ in 0..IN_LOOPS {
let mut s = 0;
for i in 0..arr.len() {
s += arr[i];
}
sum += s;
}
sum
}

(在 Godbolt Compiler Explorer 上)

CAPACITY = 240的程序集看起来很正常：两个嵌套循环。(在函数的开头，有相当多的代码仅用于初始化，我们将忽略这些代码。然而，对于 239，它看起来非常不同！我们看到初始化循环和内部循环被展开：到目前为止是预期的。

重要的区别在于，对于 239，LLVM 能够弄清楚内循环的结果不依赖于外循环！因此，LLVM 发出的代码基本上首先只执行内部循环(计算总和)，然后通过多次加sum来模拟外部循环！

首先，我们看到与上面几乎相同的程序集(表示内部循环的程序集)。之后我们看到这个(我评论是为了解释大会;带有*的评论尤其重要)：

; at the start of the function, `rbx` was set to 0
movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
add     rax, 711      ; add up missing terms from loop unrolling
mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
add     rbx, rax      ; * rbx += rax
add     rcx, -1       ; * decrement loop variable
jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
mov     rax, rbx      ; move rbx (the sum) back to rax
; two unimportant instructions omitted
ret                   ; the return value is stored in `rax`

正如你在这里看到的，内部循环的结果被采用，加起来的频率与外部循环运行然后返回的频率一样多。LLVM 只能执行此优化，因为它知道内部循环独立于外部循环。

这意味着运行时从CAPACITY * IN_LOOPS更改为CAPACITY + IN_LOOPS。这是造成巨大性能差异的原因。

---

另外要注意的是：您能对此做些什么吗？没有。LLVM必须有这样的神奇阈值，如果没有它们，LLVM优化可能需要很长时间才能完成某些代码。但我们也可以同意，这段代码是高度人为的。在实践中，我怀疑会发生如此巨大的差异。在这些情况下，由于全循环展开而产生的差异通常甚至不是因素 2。因此，无需担心实际用例。

作为关于惯用 Rust 代码的最后一点说明：arr.iter().sum()是总结数组所有元素的更好方法。在第二个示例中更改此设置不会导致发出的程序集出现任何显着差异。您应该使用简短和惯用的版本，除非您认为这会损害性能。

Answer 2

除了 Lukas 的回答，如果你想使用迭代器，试试这个：

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;
pub fn bar() -> usize {
(0..CAPACITY).sum::<usize>() * IN_LOOPS
}

感谢@Chris摩根关于范围模式的建议。

优化后的组装相当不错：

example::bar:
movabs  rax, 14340000000
ret