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

Почему компилятор C++ побеждает ручной ассемблер

Ваш эксперимент — классический пример того, что современные компиляторы (GCC, Clang, MSVC) генерируют код, который часто превосходит наивный ручной ассемблер. Вот основные причины:

1. Компилятор применяет продвинутые оптимизации

С флагом -O2 (или -O3) GCC делает следующее:

• Раскрутка циклов (loop unrolling) — уменьшает количество проверок и переходов.
• Векторизация — использует SSE/AVX инструкции для обработки нескольких чисел одновременно.
• Удаление мёртвого кода — если результат не используется, компилятор может полностью убрать вычисления.
• Инлайнинг — встраивает функцию collatz_steps прямо в цикл main, устраняя накладные расходы на вызов.

2. Проблемы вашего ассемблерного кода

Ваша ручная вставка содержит несколько узких мест:

• Неправильное использование mul rbx — инструкция MUL умножает rax на rbx и сохраняет 128-битный результат в rdx:rax. После умножения rdx может быть не равен нулю, что ломает последующие операции. Нужно использовать imul rax, rax, 3 или обнулять rdx перед div/mul.
• Избыточные переходы — jmp loop_start после каждой ветки создаёт дополнительные циклы процессора. Компилятор перестраивает код так, чтобы уменьшить количество безусловных переходов.
• Отсутствие предсказания ветвлений — ваш код не оптимизирован для branch predictor. Компилятор использует CMOV (conditional move) или другие трюки, чтобы избежать дорогих промахов предсказания.

3. Улучшенная версия ассемблера (сравнимая с C++)

Вот исправленный вариант, который использует imul и CMOV:

int collatz_asm_fast(uint64_t n) {
    int steps = 0;
    __asm {
        mov rax, n
        xor ecx, ecx
    loop_start:
        cmp rax, 1
        je done
        ; проверка чётности
        mov rdx, rax
        and edx, 1          ; младший бит
        ; если чётное: n/2, иначе: 3n+1
        mov rbx, rax
        shr rbx, 1          ; n/2 (чётный случай)
        imul rax, rax, 3
        inc rax             ; 3n+1 (нечётный случай)
        ; выбираем правильный результат
        test edx, edx
        cmovz rax, rbx      ; если чётное (ZF=1), берём n/2
        inc ecx
        jmp loop_start
    done:
        mov steps, ecx
    }
    return steps;
}

Но даже этот код может быть медленнее, чем версия компилятора, потому что GCC дополнительно:

• Использует битовые трюки — например, заменяет n % 2 на n & 1.
• Применяет конвейеризацию и выполнение вне порядка.
• Генерирует код с учётом микроархитектуры конкретного процессора (например, для Skylake или Zen).

4. Вывод

Писать ассемблер вручную имеет смысл только в трёх случаях:

• Вы используете специфические инструкции, которые компилятор не генерирует (например, POPCNT, SHA).
• Вы работаете на экзотическом железе без компилятора.
• Вы профилировали код и точно знаете, что компилятор сделал плохо — но это редкость.

В вашем случае доверьтесь компилятору: он знает о процессоре больше, чем среднестатистический программист. Для гипотезы Коллатца можно ещё ускорить C++ код, используя таблицы предвычислений или SIMD, но это уже другая история.

int collatz_fast(uint64_t n) {
    int steps = 0;
    while (n != 1) {
        if (n & 1) {          // нечётное
            n = (n * 3 + 1) >> 1; // сразу делим на 2
            steps += 2;
        } else {
            n >>= 1;
            steps++;
        }
    }
    return steps;
}

if (__builtin_expect(n & 1, 0)) { // редко
    n = 3 * n + 1;
} else {
    n /= 2;
}