为什么在包含范围内的迭代在Rust中生成的汇编比在C++中生成的汇编更长?

kgqe7b3p  于 2023-04-30  发布在  其他
关注(0)|答案(3)|浏览(141)

这两个循环在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

Godbolt:https://godbolt.org/z/xYW94qxjK
Rust本质上试图阻止C++无忧无虑的是什么?

vc9ivgsu

vc9ivgsu1#

迭代器状态中溢出。
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总是满足,并且循环永远不会退出。
严格地说,用0xffffffff'ffffffffinfamously调用sum1的原始版本会触发未定义的行为,虽然不是因为溢出,而是因为没有外部可见副作用的无限循环是UB([intro.进度]/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版本小心地维护迭代器状态,以便在迭代器中不会发生溢出。

rxztt3cl

rxztt3cl2#

这两个循环在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
goqiplq2

goqiplq23#

@user3840170正确识别了差异:Rust中的溢出检查,而不是C++。
尽管如此,问题仍然是为什么Rust版本中每个循环有2次检查而不是1次,答案是LLVM不够智能和/或RangeInclusive设计不适合LLVM 1。

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将其切换到闭合公式2。
循环拆分优化适用于RangeInclusive和大多数其他Chain迭代器,因为RangeInclusive实际上可以被认为是一次迭代器和半排异范围迭代器的链(以任何顺序)。这并不总是一场胜利:像内联一样,它意味着重复循环体的代码,如果很大,则可能导致代码大小的显著开销。
不幸的是,LLVM无法拆分循环。我不确定这是因为优化完全缺失,还是因为某些原因无法在这里应用它。我很期待rustc_codegen_gcc后端,因为GCC 7为GCC添加了循环分割,它可能能够在那里生成更好的代码。
1请参阅我留下的关于RangeInclusive性能问题的评论。我在2019年花了大量时间研究这个问题,我非常希望RangeInclusive(和所有范围)不是Iterator;这是个代价高昂的错误
2一般来说,链式迭代器使用.for_each(...)的性能会更好,特别是因为循环是手动拆分的。参见the playground,将(0..=num).for_each(|_| sum += 1)缩减为num + 1

相关问题