为什么在包含 240 个或更多元素的数组上循环时会对性能产生很大影响？

Question

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

Rust 是否对 "short" 数组进行了特殊的编译优化？

编译为 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 字节（你的数组是 usize 的数组，因此长度乘以 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，则发出的程序集会有很大不同。 See it on 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 多次粘贴循环体以避免执行所有那些"loop management instructions"，即递增循环变量，检查循环是否已经结束并跳转到循环的开始。

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

现代主流x86 CPUs（不是低功耗Atom）在命中L1d缓存时真的可以每时钟做2次矢量加载，paddq吞吐量也是每时钟至少2次，在大多数 CPU 上有 1 个周期的延迟。请参阅 https://agner.org/optimize/ and also 关于多个累加器以隐藏延迟（点积的 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
}

(On 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 Morgan 关于范围模式的建议。

这个optimized assembly还不错：

example::bar:
        movabs  rax, 14340000000
        ret

为什么在包含 240 个或更多元素的数组上循环时会对性能产生很大影响？

Why is there a large performance impact when looping over an array with 240 or more elements?

arrays

performance

rust

llvm-codegen