为什么在具有240个或更多元素的数组上循环时会有很大的性能影响?

当在Rust中对数组运行求和循环时，我注意到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());
}
22160 次浏览
小开
最佳答案

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

< br >

您发现了一个神奇的阈值，超过该阈值LLVM将停止执行某些优化。阈值是8字节* 240 = 1920字节(您的数组是__abc0数组，因此长度乘以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编译器资源管理器上看到它。下面是这个程序的一小部分:

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/和这Q&关于多个累加器来隐藏延迟(对于点积的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编译器资源管理器)

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

因此，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只能执行这种优化，因为它知道内部循环与外部循环是独立的。

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

另外一个提示:对此你能做些什么吗?不是真的。LLVM必须有这样的神奇阈值，因为如果没有它们，LLVM优化可能需要很长时间才能在某些代码上完成。但我们也可以同意，这种代码是高度人为的。在实践中，我怀疑是否会出现如此巨大的差异。在这些情况下，由于全循环展开而产生的差异通常连因子2都不到。所以不需要担心真实的用例。

关于惯用Rust代码的最后一点说明:arr.iter().sum()是对数组中所有元素求和的更好方式。在第二个示例中改变这一点并不会导致发出的程序集有任何显著差异。您应该使用简短且惯用的版本，除非您认为这会影响性能。

小开

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

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;


pub fn bar() -> usize {
(0..CAPACITY).sum::<usize>() * IN_LOOPS
}

感谢chris Morgan关于范围模式的建议。

优化组装非常好:

example::bar:
movabs  rax, 14340000000
ret

提交答案