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

В продолжение темы хочу поделиться своим кодом обгоняющим std::sort() из актуальных версий GNU C++ Library.

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

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

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

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

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

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

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

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

FavoriteLoadingДобавить в избранное
Posted in Без рубрики

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *