Почему branchless quicksort ускоряет сортировку

Помню, как в прошлом году оптимизировал сортировку в одном проекте. Стандартный std::sort работал неплохо, но бенчмарки показывали узкие места. Тогда я наткнулся на интересный подход — branchless quicksort. Недавно увидел библиотеку blqsort, которая использует этот подход и показывает впечатляющие результаты.

Суть простая: современные процессоры — машины предсказуемые. Когда код содержит много условных переходов (if/else), CPU пытается угадать, какая ветка выполнится. Если угадал — быстро. Если нет — приходится откатываться и пересчитывать. Это и есть branch misprediction, и стоит оно дорого.

Почему условные переходы замедляют сортировку

Классический quicksort постоянно принимает решения: этот элемент больше пивота или меньше? Идти влево или вправо? Каждый такой if — потенциальная ошибка предсказания.

Branchless-подход делает иначе. Вместо условного перехода результат сравнения превращается в число, которое влияет на индекс без прыжка по веткам. Процессор выполняет инструкции линейно, без попыток угадать.

Конечно, branchless-подход требует больше операций копирования — примерно вдвое больше, чем минимально необходимо. Но для данных, которые дёшево копировать, это выгоднее, чем платить за misprediction.

Как устроен blqsort

Автор библиотеки использует несколько техник одновременно:

• Branchless partitioning с вспомогательным буфером. Алгоритм выделяет стековый буфер на 1024 элемента. Сначала элементы копируются в буфер, освобождая место. Затем блоки попеременно копируются влево и вправо — без единого условного перехода.
• Median-of-medians для выбора пивота. Это помогает избежать худшего случая O(n²) и делает partition более сбалансированным.
• Heapsort как fallback. Если partition становится слишком неравномерным, алгоритм переключается на heapsort для проблемного участка.
• Сортировочные сети для маленьких массивов. Для 2-12 элементов используются оптимизированные схемы сравнений с branchless-примитивами.
• Explicit loop unrolling. Критические циклы вручную развёрнуты для лучшей работы с кэшем и меньшего числа прыжков.

BRANCHLESS PARTITION
────────────────────
Данные ──▶ [ buffer 1024 ] ──▶ Левая часть ──▶ Правая часть
           │                         │                │
           │   Branchless swap       │   Branchless   │
           │   (без if'ов)          │   (без if'ов)  │
           ▼                         ▼                ▼
        Копия                  < pivot?           >= pivot?

Сравнение производительности

Автор приводит бенчмарки на двух системах: Apple M1 и AMD Ryzen 3. Сортировались 50 миллионов double.

На M1 branchless-версия быстрее std::sort на 27%, на Ryzen — почти втрое. При этом на M1 многопоточная версия ещё в 3-4 раза быстрее однопоточной.

Интереснее случай с кастомными структурами. Если сортировать struct entry { int id; int value; }, то разница ещё заметнее:

Почти четырёхкратный выигрыш на M1. Объяснение простое: pdqsort оптимизирует количество swap-операций, но всё равно использует условные переходы для сравнений. blqsort убирает их на уровне partition, и для составных типов это окупается.

C API

Библиотека поставляется как single-header. Для C используется blqsort.h:

#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"

double data[SIZE];
blqsort(data, SIZE);

Макросы BLQS_CMP и BLQS_TYPE задают функцию сравнения и тип данных. Для многопоточности есть blqsort_thr.h, который использует POSIX threads.

C++ API

В C++ интерфейс выглядит привычно:

#include "blqs.h"

double data[SIZE];
blqs::sort(data, data + SIZE);

Интерфейс идентичен std::sort. Для многопоточности используется blqs_thr.h.

Для кастомных структур:

struct entry {
    int id;
    int value;
    bool operator<(const entry& other) const {
        return id < other.id;
    }
};

blqs::sort(data, data + SIZE);

Когда это работает, а когда нет

Branchless-подход не универсален. Для типов с дорогим копированием, например строк, используется вариант BlockQuicksort. Там branchless обрабатываются только индексы, а данные перемещаются оптимально.

На практике blqsort стоит попробовать, если:

• сортируете большие массивы примитивов или small structs
• профилирование показывает узкое место на сортировке
• работаете в high-frequency trading, игровом движке или базе данных

Можно оставить стандартный подход, если:

• сортируете строки или объекты с дорогим копированием
• массивы маленькие — десятки или сотни элементов
• код уже работает достаточно быстро

КОГДА ВЫБИРАТЬ BLQSORT
──────────────────────
Примитивы (double, int)      Small structs (< 16 байт)
     ✓                              ✓
Большие массивы (> 10K)       Многопоточная сортировка
     ✓                              ✓
Строки, complex objects      Edge cases (почти отсортировано)
     ✗                              ?

Выводы

Branchless quicksort — не магия, а аккуратная инженерия. Идея проста: убрать условные переходы там, где предсказатель CPU часто ошибается, и заплатить за это дополнительными копированиями.

Библиотека blqsort реализует этот подход чисто: single-header, C и C++ API, многопоточные версии. Бенчмарки особенно впечатляют на AMD Ryzen, где выигрыш достигает 2,7x против std::sort.

Мораль: прежде чем писать свою сортировку или тянуть тяжёлую библиотеку, проверьте, нельзя ли убрать лишние if из уже работающего кода.

Ссылки

• blqsort на GitHub — исходный код библиотеки
• pdqsort — реализация pattern-defeating quicksort
• BlockQuicksort (Edelkamp, Weiß) — исследование о branchless partition для сортировки