为什么在包含范围内的迭代会在 Rust 中生成比在 C++ 中更长的程序集？

Question

这两个循环在 C++ 和 Rust 中应该是等价的：

#include <cstdint>

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;
}

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

神马：https://godbolt.org/z/xYW94qxjK

Rust 本质上试图阻止 C++ 无忧无虑的事情是什么？

Answer 1

迭代器状态溢出。

如果输入足够大，C++ 版本将永远循环：

#include <cstdint>

std::uint64_t sum1(std::uint64_t n) {  
    std::uint64_t sum = 0;
    for (std::uint64_t j = 0; j <= n; ++j) {
        __asm__ ("");
        sum += 1;
    }
    return sum;
}

#include <iostream>

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

    return 0;
}

这是因为当循环计数器

j

最终达到

0xffffffff'ffffffff

时，递增它环绕到 0，这意味着循环不变式

j <= n

总是满足并且循环永远不会退出。

严格来说，使用

sum1

infamously

调用 0xffffffff'ffffffff 的原始版本会触发未定义的行为，尽管不仅仅是因为溢出，而是因为没有外部可见副作用的无限循环是 UB（[intro.progress]/ 1).这就是为什么在我的版本中，我向函数添加了一个空的

__asm__

语句，作为一个虚拟的“副作用”，防止编译器在优化过程中利用它的“优势”。

另一方面，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));
}

上面的程序（稍作修改以避免陷入调试与发布模式在求和方面的差异）将在恰好 18 446 744 073 709 551 616 次迭代后终止并打印 0； Rust 版本仔细维护迭代器状态，以便迭代器中不会发生溢出。

Answer 2

这两个循环在 C++ 和 Rust 中是等价的

您的两个代码片段不具有相同的行为。

for (uint64_t j = 0; j <= n; ++j)

不处理

n == uint64_t::MAX

（使其无限循环）而

for j in 0u64..=num

做（永远不会进入无限循环）。

生锈等效代码可以是：

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 godbolt：

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

Answer 3

@user3840170 正确识别了差异：Rust 中的溢出检查，而不是 C++ 中的溢出检查。

仍然，问题仍然是为什么在 Rust 版本中每个循环有 2 次检查而不是 1 次，答案是 LLVM 不够智能和/或

RangeInclusive

设计没有很好地适应 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 将其切换为一个封闭的公式².

Loop Splitting 优化适用于

RangeInclusive

和大多数其他

Chain

迭代器，因为确实

RangeInclusive

可以被认为是一次迭代器和半独占范围迭代器（按任意顺序）的链。这 并不总是一个胜利：像内联一样，它意味着复制循环体的代码，如果它很大可能会导致代码大小的显着开销。

不幸的是，LLVM 无法拆分循环。我不确定这是因为优化完全缺失，还是由于某种原因未能在此处应用。我很期待

rustc_codegen_gcc

后端，因为 GCC 7 向 GCC 添加了循环拆分，它可能能够在那里生成更好的代码。

---

¹ 请参阅此评论 我遗留了

RangeInclusive

的性能问题。我在 2019 年花了很多时间思考这个问题，我非常希望

RangeInclusive

（以及所有范围）不是

Iterator

；这是一个代价高昂的错误。

² 链迭代器，一般来说，使用

.for_each(...)

的性能要好得多，特别是因为循环是（手动）拆分的。看到 游乐场

(0..=num).for_each(|_| sum += 1)

减少到

num + 1

.