为什么循环遍历一个有240个或更多元素的数组会对性能产生巨大影响？

Question

在 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());
}

- Guy Korland

---

https://github.com/gkorland/benchmark-rust - Guy Korland

也许使用240会导致CPU缓存行溢出？如果是这种情况，你的结果将非常依赖于CPU。 - rodrigo

在这里复制 链接。现在我猜它与循环展开有关。 - rodrigo

Answer 1

摘要: 当长度小于等于240时，LLVM完全展开内部循环，并且这使其注意到它可以优化掉重复循环，从而打破了您的基准测试。

---

你找到了一个神奇的阈值，超过该阈值LLVM会停止执行某些优化。该阈值为8个字节* 240 = 1920个字节（假设x86-64 CPU，您的数组是一个usize数组，因此长度乘以8个字节）。在这个基准测试中，仅针对长度为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()是求和数组所有元素的更好方式。在第二个示例中更改这一点不会导致汇编输出方面的显著差异。除非你已测量证明它会影响性能，否则应使用简短和惯用的版本。

- Lukas Kalbertodt

---

@lukas-kalbertodt 谢谢你的好答案！现在我也明白了为什么直接在非本地s上更新sum的原始代码运行得更慢。for i in 0..arr.len() { sum += arr[i]; } - Guy Korland

@LukasKalbertodt 在LLVM中发生了其他的事情，开启AVX2不应该有太大的影响。在Rust中也可以复现此问题。 - Mgetz

@Mgetz 有趣！但是对我来说，根据可用的SIMD指令来确定阈值并不太疯狂，因为这最终决定了完全展开循环中的指令数量。但不幸的是，我不能确定。如果能得到LLVM开发人员的回答，那就太好了。 - Lukas Kalbertodt

编译器或LLVM为什么没有意识到整个计算可以在编译时完成？我本来期望循环结果被硬编码。还是使用“Instant”阻止了这一点？ - Uncreative Name

我猜这是因为完全展开循环可以让后面的优化过程看到它。记住，优化编译器仍然关心快速编译和有效的汇编语言生成，因此它们必须限制它们所做任何分析的最坏情况复杂度，以避免用复杂的循环代码编译需要花费数小时/天的时间。但是，对于大小≥240，这显然是一次未能优化。我想知道不将内部循环优化掉是否有意为之，以避免破坏简单的基准测试？可能不是，但也许是。 - Peter Cordes

Answer 2

除了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

- mja

---

更好的做法是使用(0..CAPACITY).sum::<usize>() * IN_LOOPS，这将得到相同的结果。 - Chris Morgan

实际上，我需要解释一下的是，这个汇编并没有实际进行计算，LLVM 在这种情况下已经预先计算出了答案。 - Josep

我感到有些惊讶的是，rustc错失了进行这种强度缩减的机会。虽然在这个特定的上下文中，它似乎是一个定时循环，你有意让它不被优化掉。整个重点是从头开始重复计算那个数字并除以重复次数。在C语言中，这个（非正式）习惯用法是将循环计数器声明为volatile，例如Linux内核中的BogoMIPS计数器。在Rust中是否有实现这个的方法？可能有，但我不知道。调用外部的fn或许可以帮忙解决。 - Davislor

@Davislor：volatile 强制内存同步。将其应用于循环计数器只会强制实际重新加载/存储循环计数器的值。它不直接影响循环体。这就是为什么更好的方法通常是在循环之后（如果存在循环依赖）或每次迭代后将实际重要结果分配给 volatile int sink 或其他东西，以让编译器优化循环计数器，但强制将 您想要的结果 材料化到寄存器中，以便存储它。 - Peter Cordes

@Davislor：我认为Rust有类似GNU C的内联汇编语法。你可以使用内联汇编来强制编译器将一个值存储在寄存器中，而不强制它存储它。在每个循环迭代的结果上使用它可以防止优化消除。（但如果不小心的话也会阻止自动向量化）。例如，"Escape"和"Clobber"在MSVC中的等效解释了两个宏（同时询问如何将它们移植到实际上不可能的MSVC），并链接到Chandler Carruth的演讲，他展示了它们的用途。 - Peter Cordes