В продолжение темы хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019.
Условия возникновения задачи
В коде на С (не C++) требовалось разумными усилиями получить сортировку не хуже std::sort(), чтобы избавиться от накладных расходов использования библиотечной qsort(). В том числе, поэтому использовать макросы вместо шаблонов.
В свою очередь, если сортировать "мышей", а не "слонов", то затраты на qsort() достаточно велики: лишняя адресная арифметика и косвенный вызов функции-компаратора.
Результат
По имеющейся информации эта комбинация алгоритмов и особенностей реализации быстрее многих других вариантов в практическом смысле:
- по количеству сравнений и перемещений (измерено подстановкой класса
C++подсчитывающего сравнения и присваивания). - по объему машинного кода (занимает мало места в кэше).
- по объему исходного кода и его прозрачности.
- на длинных случайных последовательностях выигрыш стремится к 3-5%, в зависимости от SORT_THRESHOLD.
- до 1.5-2-3 раз быстрее при упорядоченных или преимущественно упорядоченных данных.
- небольшой проигрыш только на очень коротких последовательностях с обратным порядком.
Весьма вероятно, что этот вариант чуть быстрее и/или несущественно медленнее подавляющего большинства сортировок, но выяснить это — буквально титанический труд, который я не могу себе позволить.
Любопытно если кто-то сравнит этот вариант с текущими вариантами в Tarantool, PostgreSQL, SQLite и MySQL. Надеюсь kaamos не сможет пройти мимо со своим SysBench.
Как там Александреску?
В первом-же комментарии от RPG18 появилась ссылка на недавнее выступление Andrei Alexandrescu “Speed Is Found In The Minds of People", где он подводит к достаточно похожей идее, но ближе к финалу уходит в heap_sort.
Выступление мне показалось несколько затянутым (вот если-бы olegbunin хоть раз дал 90 минут...), а цифр недостаточно. В частности, хочется видеть поведение сортировки с ростом N, поскольку увеличение порога завершения QuickSort приводит к ускорению на больших размерах и замедлению на маленьких и т.п.
Тем не менее, судя по цифрам, которые приводит Александреску, описанный вариант внезапно даёт аналогичное ускорение. Однако, пока я не нашел показанного Александреску кода в готовом виде, чтобы "взять и сравнить", а кодировать по видео пока некогда (пишите если найдете или сделайте).
Идейная сторона
Теоретико-идейная сторона "алгоритма" достаточна проста:
- Для не-коротких последовательностей используем QuickSort со всеми приемлемыми оптимизациями:
- Не рекурсивно, используя внутренний стек позиций на указателях.
- В качестве опорного элемента используем медиану первого, среднего и последнего элементов.
- Не сортируем мелкие порции, оставляем это для ShellSort.
- После разбиения всегда помешаем в стек большую из частей, в результате стек не может быть глубже
Log2(N).
- До-сортировываем данные используя ShellSort:
- минимальное количество проходов.
- шаг на первом проходе соотносим с максимальным размером несортированного отрезка.
- итого всего два прохода с шагами 8 и (неизбежно) 1.
- Использование ShellSort позволяет относительно безболезненно увеличить порог выхода из QuckSort. В результате имеем комбинацию одного из лучших вариантов QuickSort с экономией за счет более раннего выхода и чуть более быструю до-сортировку.
Стоит отметить, что в зависимости от архитектуры процессора и условий применения можно увеличить выигрыш на длинных последовательностях до 10-15% выбрав SORT_THRESHOLD в пределах 128-256. Однако, при этом замедляется обработка последовательностей с обратным порядком и близким к нему.
Тем не менее, это хороший бонус если вы понимаете, что в ваших данных обратный порядок маловероятен, либо если вы можете дешево обнаруживать такие случаи и выполнять ветку с маленьким SORT_THRESHOLD.
P.S.
Описанный вариант сортировки был "допеределан" для моего проекта libmdbx (быстрая встраиваемая key-value БД с ACID), в котором на днях были актуализированы README и описание API (фактически написано заново). Поэтому буду благодарен как за исправление опечаток, так и за советы и предложения. Самому, как правило, не видна нехватка какой-то информации.
Автор: Леонид Юрьев
