Причина заблуждений: автор этого документа также является соавтором реализаций ipnsort и driftsort, используемых в стандартной библиотеке Rust.

Сценарий

Компоненту ПО передаются данные для сортировки. Известно, что значения могут иметь низкую кардинальность. Несмотря на тип u64, способный хранить 2⁶⁴ уникальных значений, в данных наблюдается всего четыре уникальных значения. Учитывая такие серьёзные ограничения, разработчик может разумно решить использовать специализированную реализацию сортировки, а не ту, которая есть в библиотеке, потому что он знает о данных больше, чем способна знать обобщённая реализация.

Структура бенчмарка

Бенчмарки выполняются на следующей машине с использованием набора бенчмарков sort-research-rs и паттерна random_d4.

Linux 6.16
rustc 1.91.0-nightly (6ba0ce409 2025-08-21)
AMD Ryzen 9 5900X 12-Core Processor (микроархитектура Zen 3)
CPU boost включен.

Алгоритмы, оптимизированные под специфику данных

BTree

fn bucket_sort(v: &mut [u64]) {
    let mut buckets = std::collections::BTreeMap::new();

    for elem in v.iter().copied() {
        *buckets.entry(elem).or_insert(0) += 1;
    }

    let mut offset = 0;
    for (elem, count) in buckets {
        v[offset..offset + count].fill(elem);
        offset += count;
    }
}

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

График производительности по оси Y получен из времени сортировки N значений, показанных на оси X с логарифмическим шагом. Значение примерно 145 миллионов элементов в секунду при длине входных данных 1_000 (10³ или 1e3) подразумевает, что медианное время сортировки 1_000 элементов примерно равно 6,9 мкс.

Это холодные, а не горячие бенчмарки: перед каждым измерением выполняется сброс L1i (но не L1d) и branch-target-buffer (BTB), а входные данные при каждой итерации генерируются случайным образом. При этом измеряются единичные вызовы сортировки, как часть большей программы, а не производительностью в классическом смысле, как это делают типичные горячие микробенчмарки. При длине входных данных больше 1e3 различия между горячими и холодными бенчмарками несущественны.

Изначально замеряемая производительность низка, потому что доминируют промахи кэша L1i, BTB и uop, а также затраты на распределение памяти. При больших размерах входных данных затраты амортизируются, а кэши становятся горячими, поэтому производительность растёт.

Из кэшей L1d (64 КБ), L2 (512 КБ) и L3 (32 МБ), доступ к которым выполняется в одном потоке при вычислениях бенчмарка, L3 остаётся самым большим и медленным, имея задержку около 47 тактов. Учитывая, что при производительности 150 миллионов элементов в секунду на элемент приходится около 32,7 тактов, CPU точно не может ждать вычисления каждого значения отдельно, чтобы потом получить следующее. В современных CPU существуют конвейеры, то есть они получают данные и команды ещё до того, как они потребуются, и стараются скрывать задержки тем, что обгоняют настолько, чтобы их не пришлось ждать. В идеале CPU нужно заранее знать, что он будет обрабатывать элемент XN, и заполнять это время ожидания XN обработкой элементов X0, X1, X2 ... XN-1.

Как минимум, функция сортировки должна будет один раз считать данные в v в регистры для их обработки, а затем записать их обратно. При однопоточном чтении L3 и скорости чтения около 122 ГБ/с мы получаем верхний предел производительности для входных данных размера L3 — 0,6 такта на элемент. Паттерн доступа к данным имеет вид for elem in v.iter() и v[offset..offset + count].fill(elem; это линейное сканирование, которое легко прогнозировать, легко выполнять её предварительную выборку, конвейерную и пакетную обработку.

Так как реализация тратит примерно на 32 такта больше, чем абсолютный минимум на элемент, она или ограничена compute, или выполняет другие операции доступа к памяти, которые сокрыты абстракцией.

Хэши

fn bucket_sort(v: &mut [u64]) {
    let mut buckets = fxhash::FxHashMap::default();

    for elem in v.iter().cloned() {
        *buckets.entry(elem).or_insert(0) += 1;
    }

    let mut buckets_sorted = buckets.into_iter().collect::<Vec<_>>();
    buckets_sorted.sort_unstable_by_key(|(val, _count)| *val);

    let mut offset = 0;
    for (elem, count) in buckets_sorted {
        v[offset..offset + count].fill(elem);
        offset += count;
    }
}

Хэш-таблицы имеют схожую с BTreeMap функциональность сопоставления ключей и значений, а быстрая хэш-функция может быть быстрее, чем B-деревья. Однако они не обеспечивают свойства отсортированности, поэтому требуется дополнительный этап сортировки. Этап сортировки занимает O(K * log(K)), где K — количество уникальных элементов v.

Решение с хэш-таблицей существенно быстрее B-дерева. Результаты варьируются в зависимости от реализаций хэш-функции и реализаций структуры данных.

Эффект был заметен и ранее, но здесь ещё более явно то, что при замеренных входных значениях больше 8 Б * 2e6 = 16 МБ производительность обоих решений снижается. Это говорит о простоях конвейера, вызванных высокими задержками, свойственными большой памяти вне чипа (DRAM). В частности, CPU не способен заполнить те ~400 тактов, которые ему приходится ждать DRAM с работой, и он тратит всё больше времени на ожидание, а не на обработку.

Match

// Это единственные четыре значения в данных, которые нужно сортировать.
macro_rules! bucket_value {
    // Статический поиск
    (0) => {
        4611686016279904256
    };
    (1) => {
        4611686018427387903
    };
    (2) => {
        4611686020574871550
    };
    (3) => {
        4611686022722355197
    };
    // Динамический поиск
    ($idx:expr) => {
        match $idx {
            0 => bucket_value!(0),
            1 => bucket_value!(1),
            2 => bucket_value!(2),
            3 => bucket_value!(3),
            _ => unreachable!(),
        }
    };
}

fn bucket_sort(v: &mut [u64]) {
    let mut counts = [0; 4];

    for val in v.iter() {
        match val {
            bucket_value!(0) => counts[0] += 1,
            bucket_value!(1) => counts[1] += 1,
            bucket_value!(2) => counts[2] += 1,
            bucket_value!(3) => counts[3] += 1,
            _ => unreachable!("Unexpected value: {val}"),
        }
    }

    let mut offset = 0;
    for (i, count) in counts.iter().enumerate() {
        v[offset..offset + count].fill(bucket_value!(i));
        offset += count;
    }
}

Возможных значений всего четыре, а значит, напрашивается решение с явной обработкой каждого из них по отдельному пути исполнения кода. Для этого нужно, чтобы значения кодировались в программе, что может привести к проблемам, если значения когда-нибудь поменяются.

В качестве чисел используются значения из паттерна u64-random_d4, они не выбирались специально для этого сравнения.

Благодаря тому, что нам не приходится распределять память, как в случае с BTreeMap и HashMap, мы получаем выигрыш при длине входных данных <= 100. При бóльшем количестве входных данных ошибки прогнозирования ветвления ограничивают производительность примерно 200 миллионами элементов в секунду, из чего можно сделать вывод, что CPU тратит около 24,5 тактов на элемент.

На практике протестированная версия rustc для нахождения соответствующей ветви match генерирует двоичный поиск.

Zen 3 содержит L1 BTB на 1024 элементов, позволяя без проблем уместить используемые в цикле 9 переходов. CPU знает, где в потоке команд находятся ветвления, но 3 из 9 переходов с равной вероятностью выполняются или не выполняются. Branch-target-buffer (BTB) обеспечивает почти идеальное прогнозирование, однако branch-history-buffer (BHB) обеспечивает для этих ветвлений неверные прогнозы в 50% случаев. В среднем это приводит к одному ошибочному прогнозированию ветвления на одну итерацию цикла. Если точнее, есть вероятность 25% отсутствия ошибочного прогноза, вероятность 50% одного ошибочного прогноза и вероятность 25% двух ошибочных прогнозов. Это, а также утеря конвейерной работы и задержки кэша объясняют низкую производительность.

Под спойлером приведён сгенерированный и аннотированный ассемблерный код цикла, а также более подробный анализ производительности.

        movabs  r11, 4611686020574871549 ; bucket_value!(2) - 1
        movabs  rbx, 4611686016279904256 ; bucket_value!(0)
        movabs  r14, 4611686018427387903 ; bucket_value!(1)
        movabs  r15, 4611686020574871550 ; bucket_value!(2)
        movabs  r12, 4611686022722355197 ; bucket_value!(3)
        xor     eax, eax ; counts[3] aliased to rax
        xor     ecx, ecx ; counts[2] aliased to rcx
        xor     r9d, r9d ; counts[1] aliased to r9
        xor     r8d, r8d ; counts[0] aliased to r8
.LBB1_3:
        mov     r13, qword ptr [rsi + r10] ; Загрузка значения
        cmp     r13, r11
        jg      .LBB1_7
        cmp     r13, rbx
        je      .LBB1_10
        cmp     r13, r14
        jne     .LBB1_9 ; Переход к панике
        inc     r9 ; counts[1] += 1
        jmp     .LBB1_13
.LBB1_7:
        cmp     r13, r15
        je      .LBB1_11
        cmp     r13, r12
        jne     .LBB1_9 ; Переход к панике
        inc     rax ; counts[3] += 1
        jmp     .LBB1_13
.LBB1_10:
        inc     r8 ; counts[0] += 1
        jmp     .LBB1_13
.LBB1_11:
        inc     rcx ; counts[2] += 1
.LBB1_13:
        add     r10, 8
        cmp     rdx, r10
        jne     .LBB1_3 ; Переход обратно к началу цикла

Снижение производительности при ошибочном прогнозировании для попаданий кэша uop равно для Zen3 15-16 тактов. Вычисляемая нагрузка mov r13, qword ptr [rsi + r10] занимает 5 тактов при передаче из L1 и 12 тактов при передаче из L2. Эта задержка может быть скрыта спекулятивным конвейерным исполнением, но только в случае точного на 100% прогнозирования. Предположение (ошибочное) о том, что конвейер заметит свою ошибку после завершения загрузки из L1 или L2 и что разделение между L1/L2 составляет 50/50, обеспечивает 15,5 + 8,5 = 24 тактов на элемент для цикла match. Из дополнительного тестирования можно сделать вывод, что заполнение значениями в конце занимает дополнительно примерно 0,6 такта на элемент. Это даёт нам вычисленные 24,6 такта на элемент, что очень близко к замеренным в реальности 24,5 такта на элемент. На практике аппроксимация игнорирует то, что значения, ожидающие L3, вызовут больший «пузырь», но это происходит реже, потому что «пузыри» могут дать предварительной выборке время для заполнения кэшей более низкого уровня. Она также игнорирует то, что случай двух ошибочных прогнозов в одной итерации цикла не должен будет ждать кэши во второй раз, он ждёт только перезапуск конвейера, вызванный первым ошибочным прогнозом.

Branchless

fn bucket_sort(v: &mut [u64]) {
    let mut counts = [0; 4];

    for val in v.iter() {
        counts[0] += (*val == bucket_value!(0)) as usize;
        counts[1] += (*val == bucket_value!(1)) as usize;
        counts[2] += (*val == bucket_value!(2)) as usize;
        counts[3] += (*val == bucket_value!(3)) as usize;
    }

    let mut offset = 0;
    for (i, count) in counts.iter().enumerate() {
        v[offset..offset + count].fill(bucket_value!(i));
        offset += count;
    }
}

Опасности конвейера CPU, вызванные ошибочным прогнозированием ветвлений, можно избежать благодаря безусловному вычислению каждой ветви и маскированию ненужного результата. Если ветвления для прогнозирования отсутствуют, CPU лишь время от време��и будет галлюцинировать ненужные, а затем неверно их прогнозировать.

Сочетание простых паттернов доступа к памяти и практически полное отсутствие ошибочных прогнозов ветвления приводит к существенному улучшению по сравнению с хэш-таблицей. Для входных данных размером до L3 производительность ограничена шириной декодирования и доступными ресурсами бэкенда. Суммарно получается около 20 команд на итерацию цикла. При том, что для заполнения в конце требуется около 0,6 тактов и около 4,5 тактов на элемент всего, получаем около 3,9 тактов на итерацию цикла или около 5,1 команды на такт (instruction-per-cycle, IPC). Значение IPC, равное примерно 5,1, близко к пиковой максимально возможной производительности (около 5,7), определяемой самым узким местом в конвейере Zen 3 — блоком переименования шириной 6. Все дополнительные возможности повышения производительности сортировки необходимо будет достигать снижением количества вычислений.

Perfect hash function (phf)

fn bucket_sort(v: &mut [u64]) {
    let mut counts = [0; 4];

    for val in v.iter() {
        let idx = 3 - ((val + 3) % 4);
        counts[idx as usize] += 1;
    }

    let mut offset = 0;
    for (i, count) in counts.iter().enumerate() {
        v[offset..offset + count].fill(bucket_value!(i));
        offset += count;
    }
}

Идеальная хэш-функция (perfect hash function) — это математический объект, позволяющий выполнять сопоставление из одного пространства ключей в другое пространство ключей без коллизий, но работающий только для заранее заданного множества ключей. Кроме того, 3 - ((val + 3) % 4) отображает значения в соответствующий индекс конечного вывода, по сути, сортируя их.

В случае входных данных размера L3 bucket_phf может обрабатывать около 1,7 миллиарда в секунду, то есть CPU тратит около 2,9 такта на элемент. На этом этапе, скорее всего, узким местом уже будет не сортировка, а все операции, выполняемые с данными.

Дальнейшее повышение производительности возможно благодаря автоматической или ручной векторизации.

Надёжность

Оптимизированные под специфику данных алгоритмы восприимчивы к изменениям в обрабатываемых ими данных. Например, могут измениться значения, или новый источник данных может добавить данные с другими характеристиками. Также возможно, что сделанные нами предположения не генерализируются до всех сценариев использования ПО.

В изменённом сценарии, где 5% данных полностью случайны, поведение меняется следующим образом:

Сравнение с обобщёнными алгоритмами

slice::sort_unstable

В этом сценарии стабильность сортировки не требуется, поэтому подходящей библиотечной функцией будет slice::sort_unstable.

В случае входных данных размера L3 rust_std_unstable способна обрабатывать около 660 миллионов элементов в секунду, то есть CPU тратит около 7,4 такта на элемент. Она достигает этого результата, ничего не зная о входных данных перед их обработкой и способна установить между двумя элементами только соотношение «меньше, чем».

Так как rust_std_unstable выполняет больше операций доступа к памяти, чем решение с хэш-функцией, на неё сильнее влияют повышенные задержки DRAM.

Различные обобщённые алгоритмы

Обобщённые реализации сортировки присутствуют в стандартных библиотеках большинства языков, часто имея стабильный вариант с распределением памяти и нестабильный вариант с сортировкой на месте. BlockQuicksort известна благодаря популяризации разбиения без ветвления. Основанная на BlockQuicksort pdqsort примечательна тем, что в ней изобретено устойчивое решение для отфильтровывания общих значений с ожидаемым временем сортировки N элементов с K уникальными элементами, равным O(N * log(K)).

Подробности о том, какие версии тестировались, можно найти здесь: https://github.com/Voultapher/sort-research-rs/blob/60e19e3d56912171b4356de77499f9d798f9f12a/Cargo.toml.

На этом графике не приведены результаты сортировки phf, branchless и match, чтобы не слишком его перегружать.

Примечательна любопытная форма результатов rust_std_stable. Дополнительное тестирование со стабильными quicksorts, fluxsort и glidesort показывает схожие результаты. Несмотря на то, что во всех трёх используются достаточно различающиеся способы разбиения, похоже, причина заключается в паттерне доступа к памяти в рамках стабильного разбиения и особенностях предварительной выборки Zen 3 и взаимодействия L2<->L3.

Все реализации сортировки с наилучшей производительностью позаимствовали обработку данных низкой кардинальности у pdqsort. Driftsort (rust_std_stable), ipnsort (rust_std_unstable) и crumsort.

Radsort — это радиксная сортировка, а потому она не может адаптироваться к паттернам в данных.

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

Выводы и мнение автора

Даже лучшие реализации сортировки абсолютно точно можно превзойти благодаря знанию специфики данных, аккуратному бенчмаркингу и пониманию микроархитектур CPU. В то же время, допущения становятся неверными, возможно возникновение ошибок, а хорошие реализации сортировки могут быть на удивление быстрыми даже без знания специфики данных. Если у вас есть доступ к высококачественной реализации сортировки, тщательно подумайте о её замене чем-то самописным.