为什么在 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

迭代器状态溢出。

\n

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

\n

#include <cstdint>\n\nstd::uint64_t sum1(std::uint64_t n) {  \n    std::uint64_t sum = 0;\n    for (std::uint64_t j = 0; j <= n; ++j) {\n        __asm__ ("");\n        sum += 1;\n    }\n    return sum;\n}\n\n#include <iostream>\n\nint main() {\n    std::cout << sum1(UINT64_C(0xffffffff\'ffffffff)) << std::endl;\n\n    return 0;\n}\n

\n

这是因为当循环计数器j最终达到时0xffffffff\'ffffffff，递增它会回到 0，这意味着循环不变j <= n始终满足并且循环永远不会退出。

\n

sum1严格来说，调用with的原始版本会触发0xffffffff\'ffffffff 未定义的行为，虽然不仅仅是因为溢出，而是因为没有外部可见副作用的无限循环是 UB ( [intro.progress]/1 )。这就是为什么在我的版本中，我__asm__向函数添加了一个空语句以充当虚拟 \xe2\x80\x98sideeffect\xe2\x80\x99 ，防止编译器采用 \xe2\x80\x98advantage\xe2\x80\x99优化过程中的情况。

\n

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

\n

use std::num::Wrapping;\n\nfn sum1(num: u64) -> u64 {\n    let mut sum = Wrapping(0);\n    for _ in 0..=num {\n        sum += Wrapping(1);\n    }\n    return sum.0;\n}\n\nfn main() {\n    println!("{}", sum1(0xffffffff_ffffffff));\n}\n

\n

上面的程序（稍微修改以避免陷入调试与发布模式的求和差异）将在 18\xc2\xa0446\xc2\xa0744\xc2\xa0073\xc2\xa0709\xc2\xa0551\xc2 后终止\xa0616 迭代并打印 0；Rust 版本仔细维护迭代器状态，以便迭代器中不会发生溢出。

\n

Answer 2

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

您的两个代码片段不具有相同的行为。for (uint64_t j = 0; j <= n; ++j)不处理n == uint64_t::MAX（使其无限循环）而for j in 0u64..=num执行（永远不会进入无限循环）。

Rust 等效代码可以是：

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 将其切换为闭合公式²。

循环分割优化适用于RangeInclusive大多数其他Chain迭代器，因为实际上 aRangeInclusive可以被认为是一次迭代器和半独占范围迭代器（以任一顺序）的链。它并不总是一个胜利：就像内联一样，它意味着重复循环体的代码，如果很大，可能会导致代码大小的显着开销。

不幸的是，LLVM 无法分割循环。我不确定是否是因为完全缺少优化，或者只是由于某种原因未能在此处应用它。我很期待后端rustc_codegen_gcc，因为 GCC 7 向 GCC 添加了循环拆分，它可能能够在那里生成更好的代码。

¹请参阅我留下的性能问题的评论RangeInclusive。2019 年，我花了很多时间思考这个问题，我非常希望RangeInclusive（以及所有范围）都不是Iterator；这是一个代价高昂的错误。

²一般来说，使用 链式迭代器的性能要好得多.for_each(...)，特别是因为循环是（手动）分割的。看到游乐场减少(0..=num).for_each(|_| sum += 1)到num + 1。