АНАЛИЗ РАСХОЖДЕНИЯ МЕЖДУ ТЕОРЕТИЧЕСКОЙ СЛОЖНОСТЬЮ И ПРАКТИЧЕСКОЙ ПРОИЗВОДИТЕЛЬНОСТЬЮ АЛГОРИТМОВ СОРТИРОВКИ В ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

​ANALYSIS OF THE DISCREPANCY BETWEEN THEORETICAL COMPLEXITY AND PRACTICAL PERFORMANCE OF SORTING ALGORITHMS IN HIGH-PERFORMANCE COMPUTING SYSTEMS

Petrov Alexander Vladimirovich

Student, Department of Information Computer Systems, Institute of Mathematics and Computer Technologies, Far Eastern Federal University,

Russia, Vladivostok

Rebik Maria Mikhailovna

Student, Department of Information Computer Systems, Institute of Mathematics and Computer Technologies, Far Eastern Federal University,

Russia, Vladivostok

Semishova Violetta Grigorievna

Student, Department of Information Computer Systems, Institute of Mathematics and Computer Technologies, Far Eastern Federal University,

Russia, Vladivostok

Pashin Sergey Sergeevich

Scientific Supervisor, Associate Professor, Department of Information Computer Systems, Institute of Mathematics and Computer Technologies, Far Eastern Federal University,

Russia, Vladivostok

Elsukova Elena Anatolyevna

Scientific supervisor, Senior Lecturer, Department of Information Computer Systems, Institute of Mathematics and Computer Technologies, Far Eastern Federal University,

Russia, Vladivostok

АННОТАЦИЯ

В работе исследуется расхождение между асимптотической сложностью алгоритмов сортировки и их практической производительностью на современных CPU с учётом микроархитектурных факторов и применением воспроизводимых методик тестирования производительности.

ABSTRACT

This paper investigates the discrepancy between the asymptotic complexity of sorting algorithms and their practical performance on modern CPUs, taking into account microarchitectural factors and using reproducible performance benchmarking methodologies.

Ключевые слова: алгоритмы сортировки; асимптотическая сложность; производительность; микроархитектура процессора; кэш-память; предсказание ветвлений; иерархия памяти; cache misses; branch mispredictions; сравнительный анализ.

Keywords: sorting algorithms; asymptotic complexity; performance; processor microarchitecture; cache memory; branch prediction; memory hierarchy; cache misses; branch mispredictions; comparative analysis.

Введение

Алгоритмы сортировки являются фундаментальными компонентами современных программных систем и применяются в широком спектре приложений. Традиционно при изучении и выборе алгоритмов сортировки исследователи и разработчики руководствуются асимптотической сложностью как основной метрикой эффективности. Однако в условиях современной микроархитектуры процессоров теоретическая оценка сложности, базирующаяся на абстрактной RAM-модели, не учитывает ряд факторов, оказывающих существенное влияние на производительность.

Ключевыми особенностями современных вычислительных систем являются многоуровневая иерархия кэш-памяти, конвейеризация вычислений и механизмы предсказания ветвлений. Эти микроархитектурные механизмы повышают производительность, но одновременно создают нелинейные эффекты в процессе выполнения алгоритмов, которые не отражаются в классическом асимптотическом анализе. Как следствие, алгоритмы, обладающие лучшей теоретической сложностью, на практике могут демонстрировать худшую производительность по сравнению с алгоритмами, уступающими им, по асимптотической оценке, но более эффективно использующими аппаратные ресурсы.

Таблица 1.

Обзор алгоритмов сортировки

· Bubble Sort — последовательно проходит массив, меняя соседние элементы, если они в неправильном порядке. Простейший последовательный доступ. Предсказуемые ветвления. Многократные проходы по массиву усиливают пространственную локальность, но приводят к большому количеству повторных обращений к памяти.

· Insertion Sort — строит отсортированный массив, вставляя каждый следующий элемент в нужную позицию. Отличная временная локальность. Раннее завершение при вставке. Эффективен на почти отсортированных данных.

· Selection Sort — находит минимум в неотсортированной части и меняет с первым элементом. Последовательный доступ. Предсказуемые ветвления. Мало обменов (n-1 swap).

· Merge Sort — рекурсивно делит массив, сортирует половины и сливает с дополнительным буфером. Идеальная пространственная локальность при слиянии. Хорошая работа префетчера. Низкое число ветвлений.

· Quick Sort — выбирает pivot, разбивает массив на меньшие и большие элементы, рекурсивно сортирует части. Высокая чувствительность к предсказателю ветвлений. Непредсказуемый доступ при разбиении. Локальность внутри подмассивов.

· Heap Sort — строит кучу, затем извлекает максимум в конец массива, восстанавливая свойство кучи. Плохая пространственная локальность (прыжки по индексам 2i+1, 2i+2). Высокий уровень промахов кэша на больших данных. In-place.

· Radix Sort — сортирует числа по разрядам устойчивым подсчётом. Нет сравнений. Нет data-зависимых ветвлений. Линейные проходы по памяти. Memory-bandwidth bound.

В представленной реализации Radix Sort используется основание 10 для наглядности, однако в реальных задачах предпочтительнее основание 256. Это позволяет заменить дорогостоящие операции деления и взятия остатка на побитовые сдвиги и маски, что значительно ускоряет работу. Кроме того, основание 256 лучше согласовано с байтовой организацией памяти и уменьшает количество проходов по массиву.

Показательно сравнение Radix Sort и Heap Sort. Несмотря на то, что первый имеет линейную сложность O(n·k), а второй — O(n log n), их микроархитектурное поведение противоположно. Radix Sort минимизирует ветвления и обеспечивает линейный доступ к памяти, но расплачивается многократным копированием данных. Heap Sort, напротив, экономно использует память (in-place), однако страдает от непредсказуемых прыжков по индексам и сложных ветвлений в функции heapify. Этот контраст делает обе сортировки идеальными кандидатами для изучения компромиссов между теоретической сложностью и реальной производительностью.

Объекты тестирования

Примитивный тип (int32_t, 4 байта) — минимальный объём данных на элемент. Выбран в качестве базового сценария, минимизирующего влияние подсистемы памяти и позволяющего изолировать вычислительную составляющую алгоритмов.

Средние структуры (64 байта) — размер соответствует одной строке кэша (cache line) современных процессоров. Позволяет оценить эффективность использования пространственной локальности без дополнительных затрат на пересечение границ строк кэша.

Крупные структуры (128+ байт) — требуют загрузки двух и более строк кэша на элемент. Данный сценарий моделирует работу с составными типами данных в реальных приложениях и позволяет исследовать переход алгоритмов из compute-bound в memory-bound режим.

Размеры массивов

Тестирование проводилось на массивах размером 10 000, 50 000, 100 000, 250 000 и 500 000 элементов. Выбранный диапазон позволяет оценить масштабирование производительности алгоритмов при увеличении объёма входных данных.

Для целочисленного типа int32_t рабочий набор составляет от 40 КБ (при N = 10 000) до 2 МБ (при N = 500 000), что даёт возможность наблюдать поведение алгоритмов в пределах L1, L2 и на границе L3-кэша.

Для структурных типов MediumStruct (64 байта) и LargeStruct (128 байт) тестирование выполнено с использованием реализаций std::sort и std::stable_sort из стандартной библиотеки. Рабочий набор для 128-байтовых структур при N = 500 000 достигает 64 МБ, что превышает объём L3-кэша используемого процессора (25 МБ). Это позволяет оценить влияние выхода за пределы кэш-памяти на производительность.

Процедура измерений

Экспериментальное исследование проводилось по следующей методике:

1. Прогрев (warm-up). Перед каждым замером выполнялся дополнительный прогон алгоритма для стабилизации состояния кэша и предсказателя ветвлений.

2. Количество прогонов. Для каждого сочетания алгоритм–тип данных–размер массива выполнялось 30 измерений (предварительные тесты показали, что этого достаточно для стабильных результатов) с последующим усреднением и вычислением стандартного отклонения.

3. Контроль условий. Частота процессора фиксировалась (Turbo Boost отключён), использовалась привязка процесса к одному ядру (SetProcessAffinityMask) для минимизации внешних помех и исключения влияния планировщика ОС.

4. Инструментарий. Время выполнения измерялось с помощью std::chrono::high_resolution_clock. Сбор аппаратных счётчиков (cache-misses, branch-misses, IPC) и профилирование hotspots выполнялись в Intel VTune Profiler.

5. Верификация. Корректность сортировки подтверждалась вычислением checksum (суммы элементов) после каждого прогона. Корректность сортировки дополнительно проверялась с помощью функции std::is_sorted.

В рамках исследования использовались канонические реализации алгоритмов сортировки, соответствующие их классическому изложению в учебной литературе. Данный подход обеспечивает воспроизводимость и позволяет анализировать базовые алгоритмические свойства без влияния дополнительных оптимизаций.

Теоретические ожидания

Оценка количества операций

Для массива из  элементов теоретическое количество операций (сравнений и перемещений) составляет:

Таблица 2.

Теоретическая оценка трудоёмкости алгоритмов сортировки

Предсказание относительной производительности

Группа O():

· Bubble Sort должен быть самым медленным

· Selection Sort ожидается в ~2.0-2.5 раза быстрее Bubble (меньше обменов)

· Insertion Sort ожидается в ~1.5-2.0 раза быстрее Selection (в среднем меньше операций)

Группа O():

· Все алгоритмы данной группы имеют близкое количество операций (разброс не более 2-3 раз)

· По числу операций они должны превосходить квадратичные алгоритмы в 100-1000 раз

Radix Sort:

· При n=50 000, , k=10. По асимптотической оценке, Radix Sort имеет потенциальное преимущество перед O(n log n) алгоритмами

Ожидаемые соотношения времени

В абсолютных величинах (в условных единицах времени):

Таблица 3.

Теоретически ожидаемое относительное быстродействие алгоритмов сортировки

Ограничения теоретической модели

Данные предсказания основаны на RAM-модели и не учитывают:

· Иерархию кэш-памяти (эффекты локальности)

· Механизмы предсказания ветвлений

· Конвейеризацию инструкций

· Различия в стоимости операций (сравнение vs копирование)

· Влияние размера элемента (int vs struct)

В последующих разделах представлено сравнение теоретических ожиданий с реальными результатами, полученными на трёх различных процессорах.

Результаты эксперимента

Общая характеристика производительности (n = 50000)

Для анализа производительности алгоритмов сортировки были проведены эксперименты на трёх процессорах с различной архитектурой:

1. Intel i7-12700H (Alder Lake, гибридная архитектура: 6P+8E ядер, базовая частота 2.3 ГГц, L3-кэш 24 МБ)

2. AMD Ryzen 7 7700 (Zen 4, однородная архитектура: 8 ядер, базовая частота 3.8 ГГц, L3-кэш 32 МБ)

3. Intel i7-5930K (Haswell-E, однородная архитектура: 6 ядер, базовая частота 3.5 ГГц, L3-кэш 15 МБ)

Поскольку процессоры различаются по вычислительной мощности, анализ строится на относительных, а не абсолютных показателях.

В качестве базового сценария рассматривается сортировка массивов размером 50 000 элементов, при этом результаты агрегированы по трём типам данных: целочисленные значения (int32), структуры среднего размера (64 байта) и крупные структуры (128+ байт).

Таблица 4.

Экспериментальные результаты измерения времени выполнения алгоритмов сортировки на различных процессорах

Профилирование подтвердило ожидаемое доминирование квадратичных алгоритмов. На выполнение трёх квадратичных сортировок пришлось более 98% времени на каждом процессоре.

Ключевые наблюдения:

· radixSort — абсолютный лидер на всех процессорах

· Ryzen 7700 выигрывает на 8 из 9 алгоритмов (кроме selectionSort)

· i7-12700H показал аномально хороший результат на selectionSort

· i7-5930K ожидаемо медленнее современных процессоров (разница до 4 раз на bubbleSort)

Влияние подсистемы памяти (VTune)

Приведённые ниже данные получены в результате профилирования всех запусков программы (все типы данных, все размеры массивов, все 30 прогонов). Они отражают общую картину использования памяти и микроархитектурных ресурсов.

Ключевые данные из VTune для i7-12700H:

Таблица 5.

Микроархитектурные характеристики исследуемых алгоритмов сортировки по данным Intel VTune Profiler

Наиболее значимым результатом является стабильно высокая доля операций, связанных с доступом к памяти и перемещением данных. Согласно данным Intel VTune Profiler для процессора i7-12700H:

· std::vector<int>::operator[] — 138.85 с (26.5% процессорного времени), CPI 0.797, 41.1% потерь на спекулятивные вычисления

· std::swap — 78.54 с (15.0% процессорного времени), CPI 0.762, 38.4% потерь

Суммарно эти операции составили 217.4 секунд (41.5%) общего времени выполнения, что сопоставимо с долей самой медленной сортировки (bubbleSort, 43.1%).

Анализ микроархитектурных счетчиков показывает колоссальный разброс в эффективности использования процессора:

· selectionSort: CPI 0.147, 80.9% полезной работы (Retiring), всего 1.9% потерь на спекулятивные вычисления — идеальное микроархитектурное поведение

· insertionSort: CPI 0.152, 91.9% полезной работы, 3.6% потерь

· radixSort: 0% потерь на спекулятивные вычисления, CPI 0.421 — абсолютный лидер по времени благодаря отсутствию ветвлений

· bubbleSort: всего 14.2% полезной работы, 46.7% потерь на ошибки предсказания ветвлений

· heapify (ядро heapSort): 54.1% потерь — худший показатель

· partition (ядро quickSort): 49.5% потерь

Примечание:

1. CPI (Cycles Per Instruction) — количество тактов на инструкцию, чем ниже, тем лучше.

2. Retiring — доля полезной работы.

3. Bad Speculation — потери на ошибки предсказания ветвлений.

Ключевые выводы:

1. Даже простейшие операции доступа к памяти (operator[] и swap) вносят определяющий вклад в общее время выполнения — 41.5%

2. Разброс в эффективности использования процессора достигает катастрофических масштабов: от 80.9% полезной работы у selectionSort до 14.2% у bubbleSort

3. Основная причина низкой производительности — ошибки предсказания ветвлений (до 54.1% у heapify)

4. radixSort выигрывает благодаря полному отсутствию ветвлений, несмотря на не самый низкий CPI

Обсуждение результатов

Сравнение с теоретическими ожиданиями

Теоретическая модель (RAM-модель) предсказывала следующие соотношения:

· Selection Sort должен быть в ~2 раза быстрее Bubble Sort

· Insertion Sort — ещё в ~2 раза быстрее Selection

· O(n log n) алгоритмы — в ~1000 раз быстрее квадратичных

· Radix Sort — в ~3-4 раза быстрее O(n log n)

Реальные результаты на Intel i7-12700H показали иную картину:

Таблица 6.

Сравнение теоретически ожидаемого и экспериментально полученного соотношения производительности алгоритмов сортировки

Анализ расхождений:

1. Selection Sort vs Bubble Sort (расхождение в 4.5 раза)

Selection Sort имеет CPI 0.147 и 80.9% полезной работы против CPI 0.976 и 14.2% у Bubble Sort. Причина: Bubble Sort выполняет в 25000 раз больше обменов (1.25 млрд против 50000) и теряет 46.7% времени на ошибки предсказания ветвлений.

2. Quick Sort vs Insertion Sort (теория: 1000×, реальность: 15×)

Insertion Sort неожиданно эффективен (CPI 0.152, 91.9% полезной работы) благодаря временной локальности. Quick Sort теряет 49.5% времени на ошибки предсказания ветвлений в partition.

3. Radix Sort vs Quick Sort (теория: 3-4×, реальность: 6.4×)

Radix Sort имеет 0% потерь на спекулятивные вычисления — конвейер работает без простоев. Quick Sort теряет 49.5% времени на ошибки предсказания.

4. Insertion Sort vs Selection Sort (совпадает с теорией)

Оба алгоритма имеют близкие микроархитектурные показатели (Selection: CPI 0.147, Insertion: CPI 0.152), поэтому теоретическое соотношение выполняется.

Заключение

Проведённое исследование показало, что классическая RAM-модель недостаточна для предсказания реальной производительности алгоритмов сортировки на современных процессорах. Основные результаты:

1. Микроархитектурные факторы доминируют — до 41.5% общего времени выполнения приходится на простейшие операции доступа к памяти (operator[] и swap), а ошибки предсказания ветвлений могут достигать 54.1% (heapify).

2. Разброс внутри одного класса сложности достигает 4-5 раз — insertionSort в 2 раза быстрее selectionSort при одинаковой асимптотике O(n²), что объясняется различными паттернами доступа к памяти.

3. Архитектура процессора критически важна — Ryzen 7 7700 стабильно быстрее Intel на 8 из 9 алгоритмов, причём разница на RadixSort достигает 2.15 раза благодаря большему L3-кэшу и отсутствию гетерогенных ядер.

4. RadixSort — показал наилучшие результаты в рассматриваемом эксперименте благодаря полному отсутствию ветвлений (0% Bad Speculation), обгоняя QuickSort в 6.4 раза, что значительно превышает теоретическое ожидание (3-4 раза).

5. Bubble Sort — микроархитектурный анти-рекордсмен. На i7-12700H он показал катастрофически низкую эффективность: лишь 14.2% полезной работы (Retiring) при 46.7% потерь на ошибки предсказания ветвлений. Причина кроется в сочетании трёх факторов: непредсказуемые ветвления (на случайных данных условие обмена истинно в 50% случаев, что даёт 49.7% mispredictions), интенсивный доступ к памяти (1.25 млрд обменов порождают 5 млрд обращений) и глубокий конвейер Intel P-ядер, увеличивающий штраф за каждую ошибку до 15–20 тактов. В итоге на одинаковом с selectionSort классе сложности O(n²) bubbleSort оказался медленнее в 4.7 раза, а на Ryzen 7 7700 тот же алгоритм выполняется в 3.5 раза быстрее, что подтверждает критическую зависимость производительности от микроархитектуры.

При увеличении размера элемента данных происходит смена доминирующего фактора производительности: от количества операций (compute-bound) к стоимости перемещения данных (memory-bound), что делает классическую асимптотическую оценку недостаточной для практического анализа.

Практические рекомендации:

· Для массивов до 10⁴ элементов эффективен Insertion Sort благодаря временной локальности

· Для больших массивов целых чисел оптимален Radix Sort (отсутствие ветвлений)

· При работе со структурами предпочтителен std::sort как наиболее сбалансированный алгоритм

· На гетерогенных системах необходима привязка к производительным ядрам (SetProcessAffinityMask)

Таким образом, при выборе алгоритма сортировки необходимо учитывать не только асимптотическую сложность, но и микроархитектурные особенности целевой платформы, включая иерархию памяти, механизмы предсказания ветвлений и тип архитектуры процессора.

Список литературы:

1. Акиньшин, А. Профессиональный бенчмарк: искусство измерения производительности / А. Акиньшин. – СПб.: Питер, 2022. – 576 с.: ил. – (Серия «Библиотека программиста»). – ISBN 978-5-4461-1551-8.
2. Дреппер, У. Что каждый программист должен знать о памяти [Электронный ресурс] / У. Дреппер ; пер. с англ. С.В. Капустин, М. Ульянов, Н. Ромоданов. – 2007. – URL: https://rus-linux.net/lib.php?name=/MyLDP/hard/memory/memory.html (дата обращения: 07.03.2026).
3. Кнут, Д.Э. Искусство программирования. Том 3. Сортировка и поиск / Д.Э. Кнут. – 2-е изд. – М.: Вильямс, 2018. – 832 с.: ил. – ISBN 978-5-8459-0082-1.
4. Паттерсон, Д. Архитектура компьютера и проектирование компьютерных систем / Д. Паттерсон, Дж. Хеннесси. – 4-е изд. – М. ; СПб. : Питер, 2012. – 784 с. : ил. – ISBN 978-5-459-00233-8.