为什么在具有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());
}

当前回答

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

2019-08-13 14:26:57

其他回答

总结:在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，发出的程序集将有很大不同。在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发出的代码基本上首先只执行内部循环(计算总和)，然后通过将总和相加一堆次来模拟外部循环!

首先，我们看到与上面几乎相同的程序集(表示内部循环的程序集)。之后我们看到这个(我评论解释了组装;带有*的注释尤其重要):

        ; 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()是对数组中所有元素求和的更好方法。在第二个示例中改变这一点并不会导致发出的程序集有任何显著差异。您应该使用简短且惯用的版本，除非您认为这会影响性能。

2019-08-12 13:42:48

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

2019-08-13 14:26:57

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

推荐文章

最新文章

标签