Убрать проверку границ в цикле Rust в попытке достичь оптимального вывода компилятора

Question

Убрать проверку границ в цикле Rust в попытке достичь оптимального вывода компилятора

В попытке определить, могу ли я использовать 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);
    }
}

А вот ссылка goldbolt с выводом компилятора.

Первая попытка с 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, вероятно, будут съеживаться при таком расследовании, но вот оно...

10

loops rust bounds-check-elimination

Источник

user3929481 09 дек '20 в 12:53

2 ответа

Другие вопросы по тегам loops rust bounds-check-elimination

user1233251 09 дек '20 в 13:35 2020-12-09 13:35 · Answer 1 · 2020-12-09 13:35

Как можно исключить проверку границ?

Массивы, посредством их приведения к срезу, также имеют непроверенную форму изменяемого get .

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

В результате может получиться тот же машинный код, что и при компиляции эквивалентного кода C с помощью Clang. https://godbolt.org/z/ddxP1P

Имеет ли вообще смысл анализировать такие пограничные случаи? Или компилятор Rust все это увидит, если ему будет представлен весь алгоритм, а не только небольшая его часть.

Как всегда, сравните любую из этих ситуаций, даже если вы определили узкое место в этой части кода. В противном случае это преждевременная оптимизация, о которой однажды можно будет пожалеть. В частности, в Rust решение написать unsafeкод не следует воспринимать легкомысленно. Можно с уверенностью сказать, что во многих случаях усилия и риск, связанные с удалением проверки границ, перевешивают ожидаемые преимущества в производительности.

Что касается последнего пункта, мне любопытно, можно ли вообще разбить Rust до такой степени, что он станет таким же "буквальным", т.е. близким к металлу, как C.

Нет, и вы не хотели бы этого по двум основным причинам:

Несмотря на силу абстракций в Rust, принцип не платить за то, что вы не используете, по-прежнему актуален, как и в C++. Посмотрите , что делает абстракцию нулевой стоимостью . В случае проверки границ это просто следствие решения разработчиков языка всегда выполнять пространственные проверки, когда компилятор не может гарантировать, что такой доступ безопасен для памяти.
В любом случае C не такой уж низкоуровневый .Это может показаться буквальным и близким к металлу, пока на самом деле это не так.

Смотрите также:

user8195987 10 дек '20 в 20:02 2020-12-10 20:02 · Answer 2 · 2020-12-10 20:02

Вы можете добиться этого, используя арифметику указателей старой школы.

      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, к сожалению.