Условное перемещение (cmov / csel)

Условное перемещение записывает в приёмник одно из двух исходных значений в зависимости от флага условия, без ветвления. В x86 оно называется cmov, в AArch64 - csel (conditional select). Вместо того чтобы перепрыгивать через запись, процессор вычисляет оба входных значения-кандидата, а затем инструкция фиксирует то, которое выбрано флагом. Поток управления остаётся линейным - через цикл проходит ровно один путь.

Компромисс

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

Поэтому всё решает предсказуемость:

• Если переход легко предсказать (он почти всегда выполняется или почти всегда нет), ветвление быстрее: предсказатель угадывает почти всегда, и переход практически бесплатен.
• Если переход непредсказуем, как бросок монеты, условное перемещение быстрее: реальное ветвление ошибалось бы примерно в половине случаев, а каждый промах сбрасывает конвейер и заново запрашивает инструкции.

Разбиение в быстрой сортировке на случайных данных близко к худшему сценарию для предсказателя переходов: около половины элементов оказывается по обе стороны от опорного элемента без какой-либо закономерности. Именно здесь беспереходный вариант себя оправдывает. См. compiler-codegen-luck - пример, где один и тот же цикл разбиения работал в 6 раз быстрее, как только Clang сгенерировал csel вместо ветвления.

Кто принимает решение

Компилятор выбирает между ветвлением и условным перемещением на этапе компиляции, когда распределение данных ещё неизвестно, поэтому он действует наугад. Этот выбор к тому же хрупок: в LLVM он зависит от прохода SimplifyCFG, сопоставляющего определённую форму IR, и мелкие, семантически несущественные различия в исходном коде могут изменить решение на противоположное. GCC и Clang на одном и том же коде часто принимают разные решения.

Если заранее известно, что переход действительно непредсказуем, компилятор можно подтолкнуть. В Clang есть __builtin_unpredictable(), чтобы пометить условие как случайное. Тернарный оператор (p = cond ? a : b) часто транслируется в условное перемещение, но гарантии нет. Когда это важно, надёжный способ проверки - смотреть в сгенерированный ассемблер, а не полагаться на структуру исходного кода. Более глубокая причина сложности: польза от условного перемещения зависит от данных во время выполнения, которые исходный код выразить не может, так что никакие ухищрения на уровне исходников не решают вопрос окончательно.

Условный выбор - лишь один пункт в гораздо более обширном каталоге беспереходных целочисленных трюков: арифметика с насыщением, извлечение знака, min/max без сравнения и перехода, деление на константу. Все они собраны в книге Уоррена hackers-delight, и её чтение - самый быстрый способ распознавать конструкции, к которым компилятор прибегает, когда выдаёт неожиданный код.