Под капотом сортировок в STL

Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.

При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.

1. Однопоточные реализации

1.1. Готовые сортировки

• std::sort(). Еще в стандарте C++98/C++03 мы видим, что сложность алгоритма примерно n*log(n) сравнений. А также есть примечание, что если важна сложность в худшем случае, то следует использовать std::stable_sort() или std::partial_sort(). Похоже, что в качестве реализации std::sort() подразумевался quicksort (в худшем случае O(n²) сравнений). Однако, начиная с C++11 мы видим, что сложность std::sort() уже O(n*log(n)) сравнений безо всяких оговорок. GCC реализует предложенную в 1997 году introsort (O(n*log(n)) сравнений, как в среднем, так и в худшем случае). Introsort сначала сортирует как quicksort, но вскоре переключается на heapsort и в самом конце сортировки, когда остаются небольшие интервалы (в случае GCC менее 16 элементов), сортирует их при помощи insertion sort. А вот LLVM реализует весьма сложный алгоритм с множеством оптимизаций в зависимости от размеров сортируемых интервалов и того, являются ли сортируемые элементы тривиально копируемыми и тривиально конструируемыми.
• std::partial_sort(). Поиск некоторого числа элементов с минимальным значением из множества элементов и их сортировка. Во всех версиях стандарта сложность примерно n*log(m) сравнений, где n — количество элементов в контейнере, а m — количество минимальных элементов, которое нужно найти. Задача для heapsort. Сложность в точности совпадает с этим алгоритмом. Так и реализовано в LLVM и GCC.
• std::stable_sort(). Тут немного сложнее. Во-первых, в отличии от предыдущих сортировок в стандарте отмечено, что она стабильная. Т.е. не меняет местами эквивалентные элементы при сортировке. Во-вторых, сложность ее в худшем случае n*(log(n))² сравнений и n*log(n) сравнений, если есть достаточно памяти. Т.е. имеется ввиду 2 разных алгоритма стабильной сортировки. В варианте, когда памяти много подходит стандартный merge sort. Как раз ему требуется дополнительная память для работы. Сделать merge sort без дополнительной памяти за O(n*log(n)) сравнений так же возможно. Но это сложный алгоритм и не смотря на асимптотику n*log(n) сравнений константа у него велика, и в обычных условиях он будет работать не очень быстро. Поэтому обычно используется вариант merge sort без дополнительной памяти, который имеет асимптотику n*(log(n))² сравнений. И в GCC и в LLVM реализации в целом похожи. Реализованы оба алгоритма: один работает при наличии памяти, другой — когда памяти не хватает. Обе реализации, когда дело доходит до небольших интервалов, используют insertion sort. Она стабильная и не требует дополнительной памяти. Но ее сложность O (n²) сравнений, что не играет роли на маленьких интервалах.
• std::list::sort(), std::forward_list::sort(). Все перечисленные выше сортировки требуют итераторы произвольного доступа для задания сортируемого интервала. А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов? Например, std::list или std::forward_list. У этих контейнеров есть специальный метод sort(). Согласно стандарту, он должен обеспечить стабильную сортировку за примерно n*log(n) сравнений, где n число элементов контейнера. В целом вполне подходит merge sort. Ее и реализуют GCC и LLVM и для std::list::sort(), и для std::forward_list::sort(). Но зачем вообще потребовались частные реализации сортировки для списков? Почему бы для std::stable_sort() просто не ослабить итераторы до однонаправленных или хотя бы двунаправленных, чтоб этот алгоритм можно было применять и к спискам? Дело в том, что в std::stable_sort() используются оптимизации, которые требуют итераторы произвольного доступа. Например, как я писал выше, когда дело доходит до сортировки небольших интервалов в std::stable_sort() разумно переключиться на insertion sort, а эта сортировка требует итераторы произвольного доступа.
• std::make_heap(), std::sort_heap(). Алгоритмы по работе с кучей (max heap), включая сортировку. std::sort_heap() это единственный способ сортировки, алгоритм для которого указан явно. Сортировка должна быть реализована, как heapsort. Так и реализовано в LLVM и GCC.

Сводная таблица

Примечание. В качестве реализации в GCC и LLVM указан алгоритм, который используется для больших сортируемых интервалов. Для особых случаев (небольшие интервалы и т.п.) часто используются оптимизации.

1.2. Составляющие алгоритмов сортировки

• std::merge(). Слияние двух сортированных интервалов. Этот алгоритм не меняет местами эквивалентные элементы, т.е. он стабильный. Количество сравнений не более, чем сумма длин сливаемых интервалов минус 1. На базе данного алгоритма очень просто реализовать merge sort. Однако напрямую этот алгоритм не используется в std::stable_sort() ни LLVM, ни в GCC. Для шага слияния в std::stable_sort() написаны отдельные реализации.
• std::inplace_merge(). Этот алгоритм также реализует слияние двух сортированных интервалов и он также стабильный. У него есть интерфейсные отличия от std::merge(), но кроме них есть еще одно, очень важное. По сути std::inplace_merge() это два алгоритма. Один вызывается при наличии достаточного количества дополнительной памяти. Его сложность, как и в случае std::merge(), не более чем сумма длин объединяемых интервалов минус 1. А другой, если дополнительной памяти нет и нужно сделать слияние "in place". Сложность этого "in place" алгоритма n*log(n) сравнений, где n сумма элементов в сливаемых интервалах. Все это очень напоминает std::stable_sort(), и это неспроста. Как кажется, авторы стандарта предполагали использование std::inplace_merge() или подобных алгоритмов в std::stable_sort(). Эту идею отражают реализации. В LLVM для реализации std::stable_sort() используется std::inplace_merge(), в GCC для реализаций std::stable_sort() и std::inplace_merge() используются некоторые общие методы.
• std::partition()/std::stable_partition(). Данные алгоритмы также можно использовать для написания сортировок. Например, для quicksort или introsort. Но ни GCC ни LLVM не использует их напрямую для реализации сортировок. Используются аналогичные им, но оптимизированные, для случая конкретной сортировки, варианты реализации.

2. Многопоточные реализации

В C++17 для многих алгоритмов появилась возможность задавать политику исполнения (ExecutionPolicy). Она обычно указывается первым параметром алгоритма. Алгоритмы сортировок не стали исключением. Политику исполнения можно задать для большинства алгоритмов рассмотренных выше. В том числе и указать, что алгоритм может выполняться в несколько потоков (std::execution::par, std::execution::par_unseq). Это значит, что именно может, а не обязан. А будет вычисляться в несколько потоков или нет зависит от целевой платформы, реализации и варианта сборки компилятора. Асимптотическая сложность также остается неизменной, однако константа может оказаться меньше за счет использования многих потоков.

Тут ключевое слово «может». Дело в том, что однопоточные реализации, описанные выше, подходят для соответствующих алгоритмов, какая бы политика исполнения ни была задана. И однопоточные реализации часто используются на настоящий момент независимо от политики исполнения. Я рассмотрел следующие версии:

• LLVM/Clang (Apple clang version 11.0.3 (clang-1103.0.32.62)) и MacOS 10.15.4. В этом случае заголовочный файл execution не нашелся. Т.е. политику многопоточности задать не получится;
• LLVM/Clang 10.0.0 сборка из brew. Тот же результат, что и в случае Apple clang;
• GCC 10.1.0 — файл execution есть и политику задать можно. Но какая бы политика ни была задана, использоваться будет однопоточная версия. Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel. А для этого должна быть установлена библиотека Intel Threading Building Blocks (TBB) и пути поиска заголовочных файлов были прописаны. Установлен ли TBB проверяется при помощи специальной команды в gcc: __has_include(<tbb/tbb.h>) в файле c++config.h. И если данный файл виден, то используется многопоточная версия написанная на базе Threading Building Blocks, а если нет, то последовательная. Про TBB немного подробнее ниже. Дополнительную информацию о поддержке компилятором параллельных вычислений, как впрочем и другой функциональности, можно посмотреть на cppreference.com.

3. Intel Threading Building Blocks

Чтоб стало возможным использовать многопоточные версии разных алгоритмов, на сегодня нужно использовать дополнительные библиотеку Threading Building Blocks, разрабатываемую Intel. Это несложно:

• Клонируем репозиторий Threading Building Blocks с https://github.com/oneapi-src/oneTBB
• Из корня запускаем make и ждем несколько минут пока компилируется TBB или make all и ждем пару часов, чтоб прошли еще и тесты
• Далее при компиляции указываем пути к includes (-I oneTBB/include) и к динамической библиотеке (у меня был такой путь -L tbb/oneTBB/build/macos_intel64_clang_cc11.0.3_os10.15.4_release -ltbb, т.к. я собирал TBB при помощи Apple clang version 11.0.3 на MacOS)

4. Эпилог

Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации. Часто все развивается, как предполагалось. Иногда идет своим путем. Иногда не используется вовсе. Какие бы ни были реализации тех или иных алгоритмов или структур данных сегодня, завтра это может измениться. Измениться впрочем может и стандарт. Но меняясь, стандарт почти всегда обеспечивает совместимость с ранее написанным кодом. При выпуске новых версий компиляторов могут меняться и реализации. Но изменяясь они предполагают, что разработчики полагаются на стандарт. На мой взгляд, имеет смысл понимать, как обычно реализуются те или иные части стандартной библиотеки. Но полагаться при разработке нужно именно на ограничения, заданные стандартом.

Ссылки на упомянутые алгоритмы и библиотеку:

• Quicksort
• Introsort
• Insertion Sort
• Heapsort
• Merge Sort
• Threading Building Blocks

Благодарности

Большое спасибо Ольге Serine за замечание по статье и картинку.