Алгоритмы сортировки всегда были и остаются фундаментальной темой в информатике и программировании. Одним из наиболее популярных и часто используемых является быстрая сортировка (quicksort), которая благодаря своей эффективности и простоте реализации занимает важное место в стандартных библиотеках языков программирования. Ключевым элементом быстрой сортировки является операция разбиения (partition), от правильного выбора и реализации которой во многом зависит производительность всего алгоритма. В последние годы наблюдается интересное возвращение к классической схеме Ломуто, которая долгое время была в тени схемы Хоара, традиционно считающейся более эффективной. Почему же стратегия, казалось бы, менее оптимальная, всё чаще используется и даже превосходит альтернативы на современных платформах? Ответ кроется в деталях работы современных процессоров и особенностях механизма предсказания ветвлений (branch prediction).
Схема разбиения Ломуто была определена значительно позже, чем более известная схема Хоара, и описывает простой метод обхода массива с одной стороны, поддерживая две позиции: позицию чтения и позицию записи. При проходе по массиву каждый элемент сравнивается с опорным значением (pivot). Если элемент меньше или равен опорному, он меняется местами с элементом на позиции записи, а индекс записи продвигается вперёд. Итогом становится разделение массива на две части: меньшие и большие опорного значения. Несмотря на очевидность и простоту, этот метод долгое время критиковали за избыточные операции обмена.
В худших сценариях схема Ломуто может существенно уступать схеме Хоара по количеству обменов, особенно на упорядоченных данных, что негативно отражается на времени выполнения. В отличие от неё, схема Хоара использует два указателя, двигающихся навстречу друг другу с обеих сторон массива. Они пропускают элементы, уже корректно расположенные относительно опорного значения, и обменивают лишь необходимые элементы, что снижает количество обменов и сравнений. Загружая меньше лишней работы, схема Хоара заслужила репутацию более производительной и надёжной. Однако с развитием архитектур современных процессоров стало ясно, что классический подход к оценке алгоритмов, основанный лишь на подсчёте сравнений и обменов, уже недостаточен.
Современные CPU содержат сложные механизмы предсказания ветвлений, позволяющие ускорять выполнение, пока условные переходы работают эффективно. Ошибки предсказания ветвления приводят к серьёзным задержкам и снижению производительности. Важным моментом является то, что ветвления внутри главного цикла разбиения, например условие сравнения элемента с опорным значением, с равной вероятностью бывают истинными или ложными, что затрудняет предсказание и создаёт "непрогнозируемые" ветвления. Схема Ломуто, реализованная традиционно, базируется на таких условных переходах, что приводит к значительным потерям из-за неэффективного предсказания ветвлений. Исследования последних лет показали, что применяя так называемый "безветвевой" (branch-free) подход к реализации схемы Ломуто, можно значительно повысить её эффективность.
Идея сводится к исключению условных операторов, управляющих потоком выполнения, и замене их на арифметические операции и вычисления с помощью масок. Вместо того чтобы выборочно выполнять обмены, алгоритм всегда выполняет одинаковое число операций обмена в каждой итерации, используя арифметические приёмы для "наложения" изменений только там, где необходимо. Это означает, что процессор не сталкивается с неопределённостью в предсказании ветвлений и не теряет циклы на их обработку. Хотя такой подход может приводить к увеличению фактического количества операций обмена - так называемых перезаписей элементов с самим собой - снижение стоимости неправильных предсказаний ветвлений вместе с высокой параллелизацией современных CPU и эффективным использованием кэш-памяти приводит к общему выигрышу производительности. Разработчики экспериментировали с разными способами реализации минимизируя условные переходы и добиваясь увеличения скорости за счёт улучшения предсказуемости потока данных.
В частности, оригинальный цикл обхода массива был переписан так, что для каждого элемента в любой итерации выполняется фиксированное число операций записи с индексами, вычисленными через побитовые маски, а показатель необходимости обмена преобразуется в маску для выбора действий. В результате получается код, который выглядит нестандартно и на первый взгляд неинтуитивно, однако при компиляции с современными оптимизациями он приводит к гораздо более эффективному машинному коду. Эта техника особенно хорошо работает на архитектурах Intel и совместимых с ними процессорах, где эффективное предсказание ветвлений является определяющим фактором скорости исполнения цикла. Помимо архитектурных особенностей важной деталью является выбор опорного элемента. В классических реализациях часто используется первый, последний, или медиана из трёх элементов.
Для общей оценки производительности тестировали схему Ломуто с опорным элементом, выбранным как минимум из крайних элементов, что и сравнивалось с аналогичной схемой Хоара. В чисто теоретическом плане схема Хоара сохраняет преимущество по количеству обменов, при этом оба метода имеют одинаковое (по порядку) число сравнений. Тем не менее, на практике, используя безветвевую реализацию схемы Ломуто, время выполнения сортировки на массиве со случайными данными значительно снижается, что подтверждено в многочисленных экспериментах в языках программирования C++ и D. Измерения с помощью специализированных профилировщиков Intel VTune указывают на то, что традиционная реализация схем Хоара и Ломуто теряет примерно тридцать процентов потенциала из-за ошибок предсказания ветвлений, в то время как безветвевой вариант схемы Ломуто этих потерь практически не имеет. Уровень использования ресурсов процессора, измеренный на так называемой "микропайп-линии", оказывается заметно выше для безветвевой реализации.
Эти результаты открывают дверь для пересмотра традиционных предпочтений в выборе схемы разбиения для быстрой сортировки, особенно при работе с большими объёмами данных на современных архитектурах. Однако стоит отметить, что такая безветвеевая реализация требует некоторого усложнения исходного кода, а также понимания особенностей машинной архитектуры и работы компилятора. Всё это делает её менее очевидной для непосредственного использования без должной подготовки и тестирования. Некоторые эксперты обращают внимание, что схема Ломуто используется и из-за своей простоты и возможностей для обобщения на структуры данных с ограниченными возможностями обхода, например, на однонаправленных списках, где схема Хоара неприменима из-за необходимости двунаправленного итератора. Но основным драйвером её возрождения именно сейчас является указанный эффект от уменьшения количества пропущенных прогнозов ветвлений и связанных с ними задержек.
Помимо повышения производительности, безветвевой метод открывает новые горизонты для оптимизаций, используя преимущественно универсальные арифметические и логические операции, что может быть особенно полезно для компиляторов и платформ с ограниченной поддержкой ветвления. Это наглядно демонстрирует, насколько классические алгоритмы даже спустя десятилетия могут претерпевать изменения и улучшения с учётом изменений аппаратной базы. Возвращение схемы Ломуто иллюстрирует, что устоявшиеся взгляды на предпочтительность алгоритмов всегда следует рассматривать с позиций современных реалий вычислений. В мире, где скорость не определяется только количеством операций, а зависит от распараллеливания, кеширования и предсказуемости, эффективное кодирование становится комплексной задачей, требующей учета всех аспектов. Подводя итог, возрождение интереса к схеме Ломуто связано не только с её исторической простотой, но, главное, с грамотной реализацией, учитывающей особенности современной аппаратной архитектуры.
Безветвевой вариант с минимизацией непредсказуемых переходов превосходит классические схемы и возвращает долгое время забытый метод в разряд востребованных и практически применимых. Это обстоятельство может привести к пересмотру подходов к реализации быстрой сортировки в стандартных библиотеках и промышленных решениях, а также стимулировать дальнейшие исследования в области оптимизированных алгоритмов для современных вычислительных платформ. .
