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

1sbrub3j  于 2023-03-02  发布在  其他
关注(0)|答案(3)|浏览(121)

这两个循环在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++无忧无虑的事情是什么?

wztqucjr

wztqucjr1#

迭代器状态下溢出。
当给定足够大的输入时,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'ffffffffx 1 e0f1x调用sum1的原始版本会触发未定义的行为,尽管不仅仅是因为溢出,但由于没有外部可见副作用的无限循环是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版本小心地维护迭代器状态,这样迭代器中就不会发生溢出。

rggaifut

rggaifut2#

@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。*

w1jd8yoj

w1jd8yoj3#

这两个循环在C++和Rust中是等效的
这两个代码片段的行为不同。for (uint64_t j = 0; j <= n; ++j)不处理n == uint64_t::MAX(使其无限循环),而for j in 0u64..=num处理(永远不会进入无限循环)。
rust eclipse 等效代码可以是:

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

相关问题