248

When running a sum loop over an array in Rust, I noticed a huge performance drop when CAPACITY >= 240. CAPACITY = 239 is about 80 times faster.

Is there special compilation optimization Rust is doing for "short" arrays?

Compiled with 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());
}
4

2 回答 2

386

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



您发现了一个神奇的阈值,超过该阈值 LLVM 停止执行某些优化。阈值为 8 字节 * 240 = 1920 字节(您的数组是usizes 的数组,因此长度乘以 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
}

这个简单的代码将大致生成人们期望的程序集:一个循环添加元素。但是,如果您更改240239,则发出的程序集会有很大不同。在 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寄存器(xmm0xmm1)是并行使用的,这样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 编译器资源管理器上

for 的程序集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_LOOPSCAPACITY + IN_LOOPS。这是造成巨大性能差异的原因。


附加说明:你能对此做些什么吗?并不真地。LLVM 必须具有如此神奇的阈值,因为如果没有它们,LLVM 优化可能需要很长时间才能在某些代码上完成。但我们也可以同意这段代码是高度人为的。在实践中,我怀疑会发生如此巨大的差异。在这些情况下,由于完全循环展开导致的差异通常甚至不是因素 2。因此无需担心实际用例。

作为关于惯用 Rust 代码的最后一点:arr.iter().sum()是总结数组所有元素的更好方法。在第二个示例中更改这一点不会导致发出的程序集有任何显着差异。除非您测量到它会损害性能,否则您应该使用简短且惯用的版本。

于 2019-08-12T13:42:48.850 回答
31

除了 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-13T14:26:57.810 回答