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

Summary:低于240，LLVM完全展开内部循环，这让它注意到它可以优化重复循环，打破你的基准.

You found a magic threshold above which LLVM stops performing certain optimizations.阈值是8字节*240=1920字节(您的数组是一个usize字节的数组，因此长度乘以8字节，假设x86-64 CPU).在这个基准测试中，一个特定的优化——仅针对长度239执行——导致了巨大的速度差.但让我们慢慢开始:

(All code in this answer is compiled with 100)

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

这段简单的代码将大致生成人们所期望的程序集:一个添加元素的循环.但是，如果将240更改为239，则emits 的部件会有很大的不同.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

这就是所谓的loop unrolling:LLVM将循环体粘贴一段时间，以避免执行所有那些"循环管理指令"，即递增循环变量，判断循环是否已结束以及跳转到循环的开始.

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

现代主流x86 CPU(不是低功耗的Atom)在L1d缓存中运行时，每个时钟可以执行2个向量加载，paddq吞吐量也至少是每个时钟2个，在大多数CPU上有1个周期的延迟.参见https://agner.org/optimize/和this Q&A关于多个累加器来隐藏延迟(对于点积，FP FMA的延迟)和吞吐量瓶颈.

LLVM在不是fully展开时，会展开some个小循环，并且仍然使用多个累加器.因此，通常情况下，前端带宽和后端延迟瓶颈对于LLVM生成的循环来说并不是什么大问题，即使没有完全展开.

至少不需要单独展开循环.让我们来看看实际的基准测试代码，它将一个循环放在另一个代码中:

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来说，它看起来非常不同！我们看到初始化循环和内部循环被展开:到目前为止，这是意料之中的.

The important difference is that for 239, LLVM was able to figure out that the result of the inner loop does not depend on the outer loop!因此，LLVM发出的代码基本上首先只执行内部循环(计算总和)，然后通过加上sum次模拟外部循环！

首先，我们看到与上面几乎相同的程序集(表示内部循环的程序集).后来我们看到了这一点(我对大会进行了解释；*的 comments 尤其重要):

        ; 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只能执行这种优化，因为它知道内部循环独立于外部循环.

This means the runtime changes from 100 to 101.这是造成巨大性能差异的原因.

另外一点:你能做些什么吗？不是真的.LLVM必须有这样神奇的阈值，如果没有它们，LLVM优化可能永远无法在某些代码上完成.但我们也可以同意，这个代码是高度人工的.在实践中，我怀疑会出现如此巨大的差异.在这些情况下，由于全循环展开而产生的差异通常不是系数2.所以不需要担心真实的用例.

注意:一个数组加上arr.iter().sum()个元素就更好了.在第二个例子中改变这一点并不会导致组件之间的任何显著差异.你应该使用简短且惯用的版本，除非你认为这会影响性能.