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

    В продолжение темы хочу поделиться своим кодом, который обгоняет 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 приводит к ускорению на больших размерах и замедлению на маленьких и т.п.


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


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


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


    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 (фактически написано заново). Поэтому буду благодарен как за исправление опечаток, так и за советы и предложения. Самому, как правило, не видна нехватка какой-то информации.
    • +17
    • 4.6k
    • 6
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 6

        +1

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

          +1

          Есть нюансы. Например хочется что бы std::sort зная о том, что мы сортируем int, использовала бы radix sort и т.д.

            +1

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

        +1
        Что насчёт SIMD? (SSE, AVX, FMA, CVT, XOP, BMI, ...)
        Вроде как лучше использовать имеющиеся возможности параллельного исполнения. И, может быть, потребуется приспосабливать алгоритмы к имеющимся возможностям.
          +1

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




          Параллельно выполнение прикручивается к QuickSort достаточно просто, но требуется либо OpenMP, либо ручной возни с потоками. В моем случае это не приемлемо и не даёт эффекта из-за размера данных.


          SIMD может дать неплохое ускорение при сортировке элементов нативных типов как за счет более быстрого и/или удачного партиционирования в quick sort, так и за счет branch less перестановок не регистрах. Однако, если сортировать (например) структуры, то эффективность быстро идет к нулю и ниже. При этом SIMD-инструкции разные на разных платформах, т.е. требует диспетчеризации как при сборке, так и в runtime. Поэтому в моем случае это unreasonable.

        Only users with full accounts can post comments. Log in, please.