Везение с кодогенерацией компилятора - косметическая правка ускорила код в 6 раз

Кристоф Казер (Christof Kaser) оптимизировал branchless-версию quicksort на C и наткнулся на случай, когда два логически идентичных варианта одного и того же горячего цикла по скорости различались больше чем в шесть раз. Сортировка 50 миллионов чисел типа double на M1 компилятором Clang с флагом -O3 в одном случае заняла 4.39 секунды, а в другом - 0.70 секунды. Быстрая версия к тому же почти вдвое обогнала std::sort (1.33 с). Алгоритм, данные и флаги компилятора были одинаковыми. Изменилась лишь запись цикла разбиения (partition).

Изменение

Шаг разбиения проходит по массиву и отправляет каждый элемент в один из двух указателей записи в зависимости от сравнения с опорным элементом (pivot). В явном виде сдвиг указателя вынесен в отдельную инструкцию:

if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr--; }

Идиоматичная форма объединяет сохранение и инкремент:

if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr-- = x;

Эффект тот же, семантика та же. Но Clang компилирует их по-разному. Компактная форма превращается в цикл без ветвлений на базе csel на AArch64 (cmov на x86): результат сравнения передаётся в условный выбор (conditional select), который определяет целевой указатель и инкремент, а затем выполняется одно безусловное сохранение в память. Явная же форма сохраняет настоящее условное ветвление вокруг записи. GCC игнорирует разницу и в обоих случаях генерирует более медленный вариант с ветвлением.

Почему формулировка важна для компилятора

Механизм разобрали в треде на HN. В варианте с одной инструкцией последней операцией в каждой ветке LLVM IR оказывается сохранение в память. Проход SimplifyCFG в LLVM ищет инструкции сохранения, идентичные за исключением одного операнда, выносит их в общий последующий блок и заменяет выбор на инструкцию select, которая позже транслируется в условное перемещение (conditional move). В варианте с двумя инструкциями последней операцией в каждой ветке становится арифметика указателей, а не сохранение. Сами указатели различаются двумя операндами (разные базовые адреса: один инкрементируется, другой декрементируется), поэтому SimplifyCFG сразу сдаётся и до инструкций сохранения даже не доходит. Анализ пайплайна в Compiler Explorer показывает ту же картину: после преобразования в SSA быстрая версия вычисляет сдвиг указателя до сохранения, медленная - после, и этого порядка достаточно, чтобы сопоставление с шаблоном сломалось. Исходный код никак не подсказывает, по какую сторону этой границы вы окажетесь.

Почему именно здесь выигрывает branchless

Условное перемещение не быстрее ветвления автоматически. Оно быстрее, только если ветвление трудно предсказать. Разбиение в quicksort на случайных данных - почти худший сценарий для предсказателя переходов: примерно половина элементов распределяется в каждую сторону без какой-либо закономерности, предсказатель ошибается примерно в половине случаев, и каждый промах сбрасывает конвейер. У csel/cmov нет ветвления, на котором можно ошибиться: инструкция всегда выполняет один и тот же объём работы. Поэтому она выигрывает на непредсказуемых данных и проигрывает там, где ветвление легко предсказывалось бы. Во время компиляции компилятор не знает распределение данных и строит догадки. На этой нагрузке догадка в пользу branchless случайно оказалась верной - отсюда и слово "везение": быстрый путь возник лишь потому, что косметическая правка подтолкнула компилятор к шаблону, подошедшему данным во время выполнения. Общий баланс компромиссов описан в conditional-move. В Clang есть __builtin_unpredictable(), позволяющий подсказать, что вероятность ветвления 50/50, но это полезно, только если вы заранее знаете, что его нужно применить.

Более широкий вывод

Самое полезное - выводы, которые участники обсуждения сделали в треде. Оптимизаторы компилятора распознают конкретные формы IR, поэтому идиоматичный код повышает шансы на срабатывание прохода, но такое сопоставление хрупко, не документировано, и семантически одинаковый код может повести себя как угодно. Для производительного кода локальность по памяти, векторизация и поведение ветвлений обычно важнее алгоритмической сложности, причём ничего из этого по исходному коду не видно. Постоянный совет: измеряйте, читайте сгенерированный ассемблер (Compiler Explorer, perf) и не верьте предрассудкам о том, что "должно" быть быстрым.

Обратный пример - wasmi-2-interpreter-engineering: в Rust 1.92 проход по MIR объединил две точки диспетчеризации ветвлений в интерпретаторе в csel и одну ветку, а откат этого изменения дал прирост ~50% в CoreMark.

Этот пример стоит в одном ряду с другими случаями в этом vault'е, когда две сборки одного и того же кода расходятся по причинам, которых в исходниках не видно: linux-7-postgres-regression, где отказ от одного из режимов вытеснения в ядре привёл к тому, что держатель spinlock'а в PostgreSQL вытеснялся посреди page fault, уполовинив пропускную способность, и huge-pages, где один лишь размер страницы на порядки меняет количество page fault'ов и нагрузку на TLB. В каждом из них производительность определяется слоями ниже написанного вами кода.

В этот же список входят ещё два примера, оба про работу компилятора с доступом к памяти, а не с выбором инструкций. В false-sharing-alignment-128 показано, что padding, необходимый для предотвращения разделения кэш-линии двумя атомиками на x64, составляет 128 байт, а не 64, как можно было бы ожидать исходя из размера кэш-линии. go-bounds-checks-unsafe заходит с другой стороны, убирая проверки границ, которые компилятор Golang не смог счесть избыточными, и показывает, насколько узкими становятся предположения о платформе, если пойти на этот шаг.

Митчелл Хашимото (Mitchell Hashimoto) приходит к тому же выводу относительно автовекторизации в everyone-should-know-simd: компилятор может иногда векторизовать скалярный цикл, но когда цикл достаточно важен, чтобы требовать пятикратного ускорения, он предпочитает явно прописывать векторизацию, а не полагаться на догадки компилятора, чтобы случайная правка или обновление компилятора не превратили его обратно в скалярный.

Фронтенд во всём этом остаётся пробелом: каждая страница здесь начинается уже после парсинга. intro-compilers-language-design - учебник, закрывающий ту часть, которой больше нет нигде в vault'е.