Почему код на C++ для проверки гипотезы Коллатца работает быстрее, чем написанный вручную ассемблер?

Почему C++ быстрее ручного ассемблера: магия оптимизатора

Ваша ситуация — классический пример того, как современные компиляторы C++ превосходят ручной ассемблер. Дело не в том, что ассемблер плох, а в том, что компилятор применяет множество оптимизаций, которые вы упустили.

Основные причины

• Векторизация (SIMD): Компилятор может обрабатывать несколько чисел одновременно с помощью SSE/AVX инструкций. Ваш ассемблер работает с одним числом за раз.
• Разворачивание циклов: C++ код может быть развёрнут так, что несколько итераций выполняются без проверки условия.
• Условные переходы и спекулятивное выполнение: Компилятор может переписать ветвления так, чтобы минимизировать непредсказуемые переходы (branch mispredictions).
• Использование битовых трюков: Например, проверка чётности через n & 1 вместо n % 2.
• Инлайнинг и оптимизация вызовов: Компилятор может встроить функцию и убрать накладные расходы на вызов.

Что делает компилятор с вашим C++ кодом?

Посмотрим на то, что может сгенерировать компилятор с флагом -O3:

collatz(int):
    xor eax, eax          ; steps = 0
    cmp edi, 1
    je .done
    ; Компилятор может переписать так:
.loop:
    mov ecx, edi
    shr ecx, 1            ; n >> 1
    and edi, 1            ; n & 1 (проверка чётности)
    lea edx, [edi*2+edi+1] ; 3*n+1 (но только если нечётное)
    ; Здесь компилятор может использовать CMOV (conditional move)
    test edi, edi
    cmovne edi, edx       ; если нечётное, то n = 3*n+1
    cmove edi, ecx        ; если чётное, то n = n/2
    inc eax
    cmp edi, 1
    jne .loop
.done:
    ret

Обратите внимание на CMOV — это инструкция условного перемещения, которая не создаёт ветвления. Процессор не гадает, какая ветка выполнится, а просто вычисляет оба варианта и выбирает нужный. Это резко снижает штраф за непредсказуемые переходы.

Как улучшить ваш ассемблер?

Вот оптимизированная версия, приближенная к тому, что делает компилятор:

collatz_opt:
    xor eax, eax
    cmp edi, 1
    je .done
.loop:
    mov ecx, edi
    shr ecx, 1          ; чётный вариант: n/2
    lea edx, [edi*2+edi+1] ; нечётный вариант: 3n+1
    test edi, 1
    cmovnz edi, edx     ; если нечётное, берём 3n+1
    cmovz edi, ecx      ; если чётное, берём n/2
    inc eax
    cmp edi, 1
    jne .loop
.done:
    ret

Эта версия уже будет сопоставима по скорости с C++ кодом. Но компилятор может пойти дальше:

• Векторизация: Он может обрабатывать 4 или 8 чисел одновременно, используя AVX2 инструкции.
• Предварительные вычисления: Иногда компилятор замечает паттерны и предвычисляет последовательности.
• Агрессивное разворачивание: Цикл может быть развёрнут в 4, 8 или 16 раз, уменьшая накладные расходы на проверку условия.

Вывод

Современные компиляторы C++ (GCC, Clang, MSVC) — это результат десятилетий оптимизаций для конкретных архитектур. Они знают о процессоре больше, чем 99% разработчиков. Ручной ассемблер оправдан только в узких случаях:

• Когда нужно использовать специфические инструкции (например, AES-NI, SHA).
• Когда компилятор не справляется с определённым паттерном.
• Для низкоуровневой отладки или написания драйверов.

В остальных случаях доверьтесь компилятору — он напишет ассемблер лучше вас.