4

为了确定我是否可以/应该使用 Rust 而不是默认的 C/C++，我正在研究各种边缘情况，主要是考虑到这个问题：在 0.1% 确实重要的情况下，我总能得到编译器输出和 gcc 一样好（带有适当的优化标志）？答案很可能是否定的，但让我们看看...

在Reddit上有一个相当特殊的例子，它研究了无分支排序算法的子例程的编译器输出。

这是基准 C 代码：

#include <stdint.h>
#include <stdlib.h>
int32_t* foo(int32_t* elements, int32_t* buffer, int32_t pivot)
{
    size_t buffer_index = 0;

    for (size_t i = 0; i < 64; ++i) {
        buffer[buffer_index] = (int32_t)i;
        buffer_index += (size_t)(elements[i] < pivot);
    }
}

这是带有编译器输出的godbolt链接。

Rust 的第一次尝试如下所示：

pub fn foo0(elements: &Vec<i32>, mut buffer: [i32; 64], pivot: i32) -> () {
    let mut buffer_index: usize = 0;
    for i in 0..buffer.len() {
        buffer[buffer_index] = i as i32;
        buffer_index += (elements[i] < pivot) as usize; 
    }
}

有相当多的边界检查正在进行，请参阅Godbolt。

下一次尝试消除了第一次边界检查：

pub unsafe fn foo1(elements: &Vec<i32>, mut buffer: [i32; 64], pivot: i32) -> () {
    let mut buffer_index: usize = 0;
    for i in 0..buffer.len() {
        unsafe {
            buffer[buffer_index] = i as i32;
            buffer_index += (elements.get_unchecked(i) < &pivot) as usize; 
        }
    }
}

这稍微好一点（参见上面相同的godbolt链接）。

最后，让我们尝试完全删除边界检查：

use std::ptr;

pub unsafe fn foo2(elements: &Vec<i32>, mut buffer: [i32; 64], pivot: i32) -> () {
    let mut buffer_index: usize = 0;
    unsafe {
        for i in 0..buffer.len() {
            ptr::replace(&mut buffer[buffer_index], i as i32);
            buffer_index += (elements.get_unchecked(i) < &pivot) as usize; 
        }
    }
}

这会产生与 相同的输出foo1，因此ptr::replace仍会执行边界检查。unsafe在这些操作中，我当然超出了我的深度。这导致了我的两个问题：

  • 如何消除边界检查？
  • 像这样分析边缘情况是否有意义？或者，如果提供整个算法而不是其中的一小部分，Rust 编译器会看穿这一切。

关于最后一点，我很好奇，总的来说，Rust 是否可以被屠杀到“字面”的程度，即像 C 一样接近金属。经验丰富的 Rust 程序员可能会对这种调查感到畏缩，但它是……

4

2 回答 2

3
  • 如何消除边界检查？

数组，通过它们对切片的 deref-coercion，也有一种未经检查的可变获取形式。

pub unsafe fn foo(elements: &Vec<i32>, mut buffer: [i32; 64], pivot: i32) {
    let mut buffer_index: usize = 0;
    for i in 0..buffer.len() {
        unsafe {
            *buffer.get_unchecked_mut(buffer_index) = i as i32;
            buffer_index += (elements.get_unchecked(i) < &pivot) as usize; 
        }
    }
}

这可能导致与使用 Clang 编译等效 C 代码获得的机器代码相同。https://godbolt.org/z/ddxP1P

  • 像这样分析边缘情况是否有意义？或者，如果提供整个算法而不是其中的一小部分，Rust 编译器会看穿这一切。

与往常一样，即使您已在该部分代码中确定了瓶颈，也要对任何这些情况进行基准测试。否则，这是一种过早的优化，有一天可能会后悔。特别是在 Rust 中，编写代码的决定unsafe不应该掉以轻心。可以肯定地说，在许多情况下，仅消除边界检查的努力和风险就超过了预期的性能收益。

关于最后一点，我很好奇，总的来说，Rust 是否可以被屠杀到“字面”的程度，即像 C 一样接近金属。

不，您不希望这样做有两个主要原因：

  1. 尽管 Rust 具有抽象的力量，但不为不使用的东西付费的原则仍然非常贴切，类似于 C++。看看是什么让抽象成为零成本。在边界检查的情况下，这仅仅是语言设计决定在编译器无法确保此类访问是内存安全时始终执行空间检查的结果。
  2. 无论如何，C并不是那么低级。它可能看起来像字面意思并且接近金属，直到它真的不是。

也可以看看：

于 2020-12-09T13:35:23.040 回答
1

您可以使用老式指针算法来实现这一点。

const N: usize = 64;
pub fn foo2(elements: &Vec<i32>, mut buffer: [i32; N], pivot: i32) -> () {
    assert!(elements.len() >= N);
    let elements = &elements[..N];
    let mut buff_ptr = buffer.as_mut_ptr();
    for (i, &elem) in elements.iter().enumerate(){
        unsafe{
            // SAFETY: We increase ptr strictly less or N times
            *buff_ptr = i as i32;
            if elem < pivot{
                buff_ptr = buff_ptr.add(1);
            }
        }
    }
}

这个版本编译成：

example::foo2:
        push    rax
        cmp     qword ptr [rdi + 16], 64
        jb      .LBB7_4
        mov     r9, qword ptr [rdi]
        lea     r8, [r9 + 256]
        xor     edi, edi

        // Loop goes here
.LBB7_2:
        mov     ecx, dword ptr [r9 + 4*rdi]
        mov     dword ptr [rsi], edi
        lea     rax, [rsi + 4]
        cmp     ecx, edx
        cmovge  rax, rsi
        mov     ecx, dword ptr [r9 + 4*rdi + 4]
        lea     esi, [rdi + 1]
        mov     dword ptr [rax], esi
        lea     rsi, [rax + 4]
        cmp     ecx, edx
        cmovge  rsi, rax
        mov     eax, dword ptr [r9 + 4*rdi + 8]
        lea     ecx, [rdi + 2]
        mov     dword ptr [rsi], ecx
        lea     rcx, [rsi + 4]
        cmp     eax, edx
        cmovge  rcx, rsi
        mov     r10d, dword ptr [r9 + 4*rdi + 12]
        lea     esi, [rdi + 3]
        lea     rax, [r9 + 4*rdi + 16]
        add     rdi, 4
        mov     dword ptr [rcx], esi
        lea     rsi, [rcx + 4]
        cmp     r10d, edx
        cmovge  rsi, rcx
        // Conditional branch to the loop beginning
        cmp     rax, r8
        jne     .LBB7_2
        pop     rax
        ret
.LBB7_4:
        call    std::panicking::begin_panic
        ud2

如您所见，循环展开，单个分支是循环迭代跳转。

然而，令我惊讶的是，这个函数并没有被淘汰，因为它没有任何效果：它应该被编译成简单的 noop。可能在内联后会这样。

另外，我会说，将参数更改为 &mut 不会更改代码：

example::foo2:
        push    rax
        cmp     qword ptr [rdi + 16], 64
        jb      .LBB7_4
        mov     r9, qword ptr [rdi]
        lea     r8, [r9 + 256]
        xor     edi, edi
.LBB7_2:
        mov     ecx, dword ptr [r9 + 4*rdi]
        mov     dword ptr [rsi], edi
        lea     rax, [rsi + 4]
        cmp     ecx, edx
        cmovge  rax, rsi
        mov     ecx, dword ptr [r9 + 4*rdi + 4]
        lea     esi, [rdi + 1]
        mov     dword ptr [rax], esi
        lea     rsi, [rax + 4]
        cmp     ecx, edx
        cmovge  rsi, rax
        mov     eax, dword ptr [r9 + 4*rdi + 8]
        lea     ecx, [rdi + 2]
        mov     dword ptr [rsi], ecx
        lea     rcx, [rsi + 4]
        cmp     eax, edx
        cmovge  rcx, rsi
        mov     r10d, dword ptr [r9 + 4*rdi + 12]
        lea     esi, [rdi + 3]
        lea     rax, [r9 + 4*rdi + 16]
        add     rdi, 4
        mov     dword ptr [rcx], esi
        lea     rsi, [rcx + 4]
        cmp     r10d, edx
        cmovge  rsi, rcx
        cmp     rax, r8
        jne     .LBB7_2
        pop     rax
        ret
.LBB7_4:
        call    std::panicking::begin_panic
        ud2

因此，不幸的是，rustc 可能会发出该函数接受缓冲区参数作为 LLVM IR 中的指针。

于 2020-12-10T20:02:44.463 回答