«5 копеек» к разговору о Cортировках
В продолжение темы хочу поделиться своим кодом обгоняющим std::sort() из актуальных версий GNU C++ Library.
По имеющейся информации эта комбинация алгоритмов и особенностей реализации быстрее многих других вариантов в практическом смысле:
- по количеству сравнений и перемещений (измерено подстановкой класса C++ подсчитывающего сравнения и присваивания).
- по объему машинного кода (занимает мало места в кэше).
- по исходного объему код и его прозрачности.
- выигрыш до 3–5% (в зависимости от SORT_THRESHOLD) на длинных случайных последовательностях.
- на многих средних и/или частично упорядоченных случаях в полтора-два раза быстрее std: sort () из STL от GCC и clang версий 7, 8, 9.
- небольшой проигрыш только на очень коротких последовательностях с обратным порядком.
Весьма вероятно, что этот вариант чуть быстрее и/или несущественно медленнее подавляющего большинства сортировок, но выяснить это — буквально титанический труд, который я не могу себе позволить.
Любопытно если кто-то сравнит этот вариант с текущими вариантами в Tarantool, PostgreSQL, SQLite и MySQL. Надеюсь kaamos не сможет пройти мимо со своим SysBench.
Теоретико-идейная сторона «алгоритма» достаточна проста:
- Для не-коротких последовательностей используем 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 (фактически написано заново). Поэтому буду благодарен как за исправление опечаток, так и за советы и предложения. Самому, как правило, не видно отсутствие или нехватка какой-то информации.
