为什么在包含范围内的迭代会在Rust中生成更长的装配？

Question

这两个回路在C和Rust中等效：

#include <cstdint>
uint64_t sum1(uint64_t n) {  
    uint64_t sum = 0;
    for (uint64_t j = 0; j <= n; ++j) {
        sum += 1;
    }
    return sum;
}

pub fn sum1(num: u64) -> u64 {
    let mut sum: u64 = 0;
    for j in 0u64..=num {
        sum += 1;
    }
    return sum;
}

但是，C版本生成了一个非常简洁的程序集：

sum1(unsigned long):                               # @sum1(unsigned long)
        xor     eax, eax
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        add     rax, 1
        cmp     rax, rdi
        jbe     .LBB0_1
        ret

而Rust的版本很长，循环中有两个检查，而不是一个：

example::sum1:
        xor     eax, eax
        xor     ecx, ecx
.LBB0_1:
        mov     rdx, rcx
        cmp     rcx, rdi
        adc     rcx, 0
        add     rax, 1
        cmp     rdx, rdi
        jae     .LBB0_3
        cmp     rcx, rdi
        jbe     .LBB0_1
.LBB0_3:
        ret

C无忧无虑地想阻止什么？

锁销：https://godbolt.org/z/xYW94qxjK

Answer 1

@user3840170正确识别了差异：在Rust中进行溢出检查，而在C中没有。

然而，问题仍然是为什么在Rust版本中每个循环有2个检查而不是1个，答案是LLVM不够智能和/或Range包容性设计不适合LLVM¹.

短循环的最佳代码生成是分割循环，转换：

for j in 0u64..=num {
    sum += 1;
}

进入：

for j in 0u64..num { // equivalent to for (auto j = 0; j < num; ++j)
    sum += 1;
}

if 0 <= num {
    sum += 1;
}

这将导致主循环中只有一个分支，并允许LLVM将其切换到闭合公式²。

循环拆分优化适用于RangeInclusive和大多数其他Chain迭代器，因为实际上RangeInclusive可以被视为一次迭代器和半排他范围迭代器（按任意顺序）的链。这并不总是一个胜利：与内联一样，它意味着复制循环体的代码，如果较大，可能会导致代码大小的显著开销。

不幸的是，LLVM无法分割循环。我不确定这是因为优化完全缺失了，还是因为某种原因无法在这里应用它。我期待着rustc_codegen_gcc后端，因为gcc7向gcc添加了循环拆分，它可能能够在那里生成更好的代码。

¹查看我对RangeInclusive性能问题留下的评论。2019年，我花了大量时间研究这个问题，我非常希望RangeInclusive（以及所有范围）不是Iterator；这是一个代价高昂的错误。

²链迭代器通常使用执行得更好。对于每个（…） ，特别是因为存在（手动）拆分循环。有关（0..=num）的信息，请参见操场。对于每个（| | sum=1）减少到num 1。

Answer 2

这两个回路在C和Rust中是等效的

你的两个被剪断的代码不具有相同的行为<代码>用于（uint64_t j=0；j

防锈等效代码可以是：

pub fn sum1(num: u64) -> u64 {
    let mut sum: u64 = 0;
    let mut j = 0;
    while j <= num {
        sum = sum.wrapping_add(1);
        j = j.wrapping_add(1);
    }
    sum
}

目前生产以下asm锁紧螺栓：

example::sum1:
        xor     eax, eax
.LBB0_1:
        add     rax, 1
        cmp     rax, rdi
        jbe     .LBB0_1
        ret

Answer 3

迭代器状态下的溢出。

当给定足够大的输入时，C版本将永远循环：

#include <cstdint>

[[gnu::noinline]]
std::uint64_t sum1(std::uint64_t n) {  
    std::uint64_t sum = 0;
    for (std::uint64_t j = 0; j <= n; ++j) {
        sum += 1;
    }
    return sum;
}

#include <iostream>

int main() {
    std::cout << sum1(UINT64_C(0xffffffff'ffffffff)) << std::endl;

    return 0;
}

这是因为当循环计数器j最终达到0xffffffff'ffffffffff时，将其递增到0，这意味着循环不变量j

严格来说，使用0xffffffff'ffffffff调用sum1会引发未定义的行为，尽管这并不是因为溢出本身，而是因为没有外部可见副作用的无限循环是UB（[intro.progress]/1）。这就是为什么我将[[gnu::noinline]]属性应用到函数中，以防止编译器在优化过程中利用这一点。

另一方面，Rust版本不仅定义完美，而且迭代次数与范围的基数相同：

use std::num::Wrapping;

fn sum1(num: u64) -> u64 {
    let mut sum = Wrapping(0);
    for _ in 0..=num {
        sum += Wrapping(1);
    }
    return sum.0;
}

fn main() {
    println!("{}", sum1(0xffffffff_ffffffff));
}

上面的程序（稍微修改以避免陷入调试与发布模式的差异相对于求和）将在18446744073709551616迭代和打印0之后终止；Rust版本小心地维护迭代器状态，以便溢出不会发生在迭代器。