«5 копеек» к разговору о Cортировках

В продолжение темы ^[1] хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library ^[2] и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019 ^[3].

Условия возникновения задачи

В коде на С (не C++) требовалось разумными усилиями получить сортировку не хуже std::sort(), чтобы избавиться от накладных расходов использования библиотечной qsort(). В том числе, поэтому использовать макросы вместо шаблонов.
В свою очередь, если сортировать "мышей", а не "слонов", то затраты на qsort() достаточно велики: лишняя адресная арифметика и косвенный вызов функции-компаратора.

Результат

По имеющейся информации эта комбинация ^[4] алгоритмов и особенностей реализации быстрее многих других вариантов в практическом смысле:

• по количеству сравнений и перемещений (измерено подстановкой класса C++ подсчитывающего сравнения и присваивания).
• по объему машинного кода (занимает мало места в кэше).
• по объему исходного кода и его прозрачности.
• на длинных случайных последовательностях выигрыш стремится к 3-5%, в зависимости от SORT_THRESHOLD ^[5].
• до 1.5-2-3 раз быстрее при упорядоченных или преимущественно упорядоченных данных.
• небольшой проигрыш только на очень коротких последовательностях с обратным порядком.

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

Любопытно если кто-то сравнит этот вариант с текущими вариантами в Tarantool, PostgreSQL, SQLite и MySQL. Надеюсь kaamos ^[6] не сможет пройти мимо со своим SysBench ^[7].

Как там Александреску?

В первом-же комментарии от RPG18 ^[8] появилась ссылка на недавнее выступление Andrei Alexandrescu “Speed Is Found In The Minds of People" ^[9], где он подводит к достаточно похожей идее, но ближе к финалу уходит в heap_sort.

Выступление мне показалось несколько затянутым (вот если-бы olegbunin ^[10] хоть раз дал 90 минут...), а цифр недостаточно. В частности, хочется видеть поведение сортировки с ростом N, поскольку увеличение порога завершения QuickSort приводит к ускорению на больших размерах и замедлению на маленьких и т.п.

Тем не менее, судя по цифрам, которые приводит Александреску, описанный вариант внезапно даёт аналогичное ускорение. Однако, пока я не нашел показанного Александреску кода в готовом виде, чтобы "взять и сравнить", а кодировать по видео пока некогда (пишите если найдете или сделайте).

Идейная сторона

Теоретико-идейная сторона "алгоритма" достаточна проста:

1. Для не-коротких последовательностей используем QuickSort со всеми приемлемыми оптимизациями:
   • Не рекурсивно, используя внутренний стек позиций на указателях.
   • В качестве опорного элемента используем медиану первого, среднего и последнего элементов.
   • Не сортируем мелкие порции, оставляем это для ShellSort.
   • После разбиения всегда помешаем в стек большую из частей, в результате стек не может быть глубже Log2(N).
2. До-сортировываем данные используя ShellSort:
   • минимальное количество проходов.
   • шаг на первом проходе соотносим с максимальным размером несортированного отрезка.
   • итого всего два прохода с шагами 8 и (неизбежно) 1.
3. Использование ShellSort позволяет относительно безболезненно увеличить порог выхода из QuckSort. В результате имеем комбинацию одного из лучших вариантов QuickSort с экономией за счет более раннего выхода и чуть более быструю до-сортировку.

Стоит отметить, что в зависимости от архитектуры процессора и условий применения можно увеличить выигрыш на длинных последовательностях до 10-15% выбрав SORT_THRESHOLD в пределах 128-256. Однако, при этом замедляется обработка последовательностей с обратным порядком и близким к нему.
Тем не менее, это хороший бонус если вы понимаете, что в ваших данных обратный порядок маловероятен, либо если вы можете дешево обнаруживать такие случаи и выполнять ветку с маленьким SORT_THRESHOLD.

P.S.
Описанный вариант сортировки был "допеределан" для моего проекта libmdbx ^[11] (быстрая встраиваемая key-value БД с ACID), в котором на днях были актуализированы README и описание API (фактически написано заново). Поэтому буду благодарен как за исправление опечаток, так и за советы и предложения. Самому, как правило, не видна нехватка какой-то информации.

Автор: Леонид Юрьев

Источник ^[12]