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

Question

在Rust中对数组运行求和循环时，我注意到当capacity>=240时性能会有很大的下降。容量=239大约快80倍。

使用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字节，假设CPU为x86-64))。在这个基准中，一个特定的优化--仅对长度239执行--是造成巨大速度差异的原因。但让我们慢慢开始：

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/以及关于多个累加器来隐藏延迟（对于点积的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来说，它看起来很不一样！我们看到初始化循环和内部循环已经展开：到目前为止，与预期的一样。

重要的区别是对于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()是总结数组的所有元素的更好方法。并且在第二个示例中更改这一点不会导致发射组件的任何显著差异。您应该使用简短和惯用的版本，除非您测量到它会损害性能。