Как биты находят свой ритм в Rust? Разбираемся со сдвигами, ротациями и тонкими нюансами оптимизации кода.

Недавно мне понадобились манипуляции с битами, и мне было любопытно реализовать циклический сдвиг влево в Rust. Эта операция сдвигает биты влево, а биты, переходящие в левый конец, повторно вводятся с правой стороны. С другой стороны, обычная операция сдвига влево вводит нули справа. Процессоры часто имеют операцию сборки, называемую ROL, для эффективного выполнения этой операции.

Вот простая функция Rust, которую я написал:

fn rol_u8(value: u8, shift: u8) -> u8 {
    (value << shift) | (value >> (8 - shift))
}

Эта функция сдвигает биты влево на позиции «x», вставляя нули справа. Затем он сдвигает те же биты вправо, но на этот раз вставляет нули слева. Наконец, результаты обоих сдвигов объединяются с помощью операции ИЛИ. Этот многошаговый процесс имитирует циклический сдвиг влево.

Мне не терпелось увидеть, как Rust и LLVM будут компилировать этот код. Онлайн Compiler Explorer предоставил мне ассемблерное представление функции. При отсутствии каких-либо флагов оптимизации сгенерированный код выглядит следующим образом:

example::rol_u8:
        push    rax
        mov     al, sil
        mov     byte ptr [rsp + 6], al
        mov     cl, dil
        mov     byte ptr [rsp + 7], cl
        cmp     al, 8
        setb    al
        test    al, 1
        jne     .LBB0_1
        jmp     .LBB0_2
.LBB0_1:
        mov     cl, byte ptr [rsp + 6]
        mov     al, byte ptr [rsp + 7]
        and     cl, 7
        shl     al, cl
        mov     cl, byte ptr [rsp + 6]
        mov     byte ptr [rsp + 4], al
        mov     al, 8
        sub     al, cl
        mov     byte ptr [rsp + 5], al
        mov     al, 8
        cmp     al, cl
        setb    al
        test    al, 1
        jne     .LBB0_4
        jmp     .LBB0_3
.LBB0_2:
        lea     rdi, [rip + str.0]
        lea     rdx, [rip + .L__unnamed_1]
        mov     rax, qword ptr [rip + core::panicking::panic@GOTPCREL]
        mov     esi, 35
        call    rax
        ud2
.LBB0_3:
        mov     al, byte ptr [rsp + 5]
        cmp     al, 8
        setb    al
        test    al, 1
        jne     .LBB0_5
        jmp     .LBB0_6
.LBB0_4:
        lea     rdi, [rip + str.1]
        lea     rdx, [rip + .L__unnamed_2]
        mov     rax, qword ptr [rip + core::panicking::panic@GOTPCREL]
        mov     esi, 33
        call    rax
        ud2
.LBB0_5:
        mov     al, byte ptr [rsp + 4]
        mov     dl, byte ptr [rsp + 7]
        mov     cl, byte ptr [rsp + 5]
        and     cl, 7
        shr     dl, cl
        mov     cl, dl
        or      al, cl
        pop     rcx
        ret
.LBB0_6:
        lea     rdi, [rip + str.2]
        lea     rdx, [rip + .L__unnamed_3]
        mov     rax, qword ptr [rip + core::panicking::panic@GOTPCREL]
        mov     esi, 36
        call    rax
        ud2

.L__unnamed_4:
        .ascii  "/app/example.rs"

.L__unnamed_1:
        .quad   .L__unnamed_4
        .asciz  "\017\000\000\000\000\000\000\000\002\000\000\000\005\000\000"

str.0:
        .ascii  "attempt to shift left with overflow"

.L__unnamed_2:
        .quad   .L__unnamed_4
        .asciz  "\017\000\000\000\000\000\000\000\002\000\000\000\"\000\000"

str.1:
        .ascii  "attempt to subtract with overflow"

.L__unnamed_3:
        .quad   .L__unnamed_4
        .asciz  "\017\000\000\000\000\000\000\000\002\000\000\000\030\000\000"

str.2:
        .ascii  "attempt to shift right with overflow"

При осмотре сборка относительно длинная и прямо отражает мою логику Rust: один сдвиг влево (SHL), один сдвиг вправо (SHR) и одна операция логического ИЛИ. Это кажется неэффективным, учитывая, что ЦП может достичь этого за одну операцию ROL. Но что произойдет, если мы включим оптимизацию -C opt-level=3?

example::rol_u8:
        mov     ecx, esi
        mov     eax, edi
        rol     al, cl
        ret

Это значительное улучшение! Вся операция сводится к одной инструкции по сборке ROL. Слава LLVM!

Подожди минутку! Я заметил что-то странное в начальном выводе сборки: он содержит три пути паники. Эти пути предполагают, что Rust выполняет проверки, которые могут привести к панике:

  • попытка сдвинуться влево с переполнением
  • попытка вычитания с переполнением
  • попытка сдвинуться вправо с переполнением

Я считаю, что каждый из них может быть запущен, но давайте сосредоточимся только на одном сценарии: rol_u8(2, 9). Это вызывает панику с сообщением:

rol_u8(2, 9)

thread 'main' panicked at 'attempt to shift left with overflow', src/main.rs:379:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Это тревожно! Тем более, что выполнение этого в режиме выпуска не вызывает паники. Функция сборки ROL может управлять 9 левыми валками, что эквивалентно одному круговому смещению влево.

Два основных вывода из этого опыта:

  1. LLVM впечатляет тем, что умело выводит намерения из сложных реализаций.
  2. Режимы отладки и выпуска в Rust могут различаться не только по производительности, но и по фактическому поведению.

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу