Ниже — сжатая, но содержательная сводка приёмов оптимизации на двух уровнях и критериев выбора.
Алгоритмический уровень
- Выбор асимптотики: заменить алгоритм $O(n^2)$ на $O(n\log n)$ (сортировка, хеширование, деревья, графовые алгоритмы). Асимптотика важнее констант при больших данных.
- Правильные структуры данных: хеш-таблицы vs деревья, куча, очередь, битовые наборы, sparse-структуры — уменьшение времени/памяти за счёт подходящей структуры.
- Избегать лишней работы: мемоизация, динамическое программирование, отсечение ветвей (branch-and-bound), ленивые вычисления.
- Разбиение задач: декомпозиция, divide-and-conquer, алгоритмы "разделяй и властвуй" для кэш-локальности.
- Параллелизм на уровне алгоритма: распараллеливание независимых задач, использование map-reduce; учитывать Amdahl: скорость $S=\frac{1}{(1-P)+P/N}$, где $P$ — доля параллельной работы, $N$ — число потоков/ядер.
- Работа с потоками данных: потоковые/онлайн-алгоритмы для больших объёмов, стриминг, алгоритмы с ограниченной памятью.
- Снижение сложности по памяти: сжатие, sparse-форматы, in-place-алгоритмы.
Уровень языка/компиляции/реализации
- Компиляция и флаги: использовать оптимизации компилятора ($-O2/-O3$, профильно-ориентированная PGO), LTO (link-time optimization).
- Инлайнинг: уменьшает накладные вызовы функций; применять для маленьких часто вызываемых функций, учитывать рост размера кода и влияние на I-cache.
- Автовекторизация / SIMD: использовать компиляторные автогенерации или ручные SIMD-интринсики (SSE/AVX/NEON). Требует выровненных данных и подходящего доступа (последовательные массивы). Преимущественно для операций над массивами/векторами.
- Параллельные примитивы и библиотеки: OpenMP, TBB, pthreads, GPU/CUDA для данных с высокой параллельностью.
- Локальность данных и кеширование: упорядочивание доступов (row-major vs column-major), blocking/tiling (напр., для матричных операций), уменьшение страничных промахов, использование локальных буферов.
- Предвыборка (prefetch), уменьшение ветвлений, упрощение предсказуемости ветвей.
- Уменьшение аллокаций: пул объектов, arena-аллокаторы, избегать частых malloc/free; использовать move/rueсемантику в C++.
- Жизненный цикл объектов: escape analysis (в JVM/Go) для уменьшения сборок мусора; уменьшение удерживаемых ссылок.
- Профилирование-ориентированная оптимизация: PGO и встраивание горячих путей, оптимизация горячего кода.
- Специализация и генерация кода: шаблоны/генераторы для конкретных типов/параметров (динамическая компиляция, JIT).
- Использование проверенных библиотек: BLAS, FFTW, std::algorithms — часто оптимизированы под платформа.
Конкретные техники и трюки
- Loop unrolling (ручное/компиляторное) для уменьшения накладных проверок цикла.
- Blocking/tiling для матриц: уменьшает количество промахов в кеше.
- Data layout: AoS (array of structs) vs SoA (struct of arrays) для лучшей векторизации.
- Сведение ветвлений к арифметическим операциям (branchless code) там, где выгодно.
- Использование готовых примитивов (memcpy, memset), которые оптимизированы под платформа.
Критерии выбора оптимизаций
- Профилирование и измерение: сначала найти узкие места (горячие функции/строки) с помощью профайлеров и счётчиков производительности.
- Влияние на асимптотику vs константные факторы: при больших N важна сложность; при малых — часто важны константы и накладные расходы.
- Стоимость реализации и поддерживаемость: сложные оптимизации (ручной SIMD, нестандартные структуры) оправданы только при значительном выигрыше.
- Портируемость и переносимость: аппаратно-зависимые оптимизации (AVX, CUDA) ограничивают платформы.
- Корректность и численная устойчивость: векторизация/перестановки операций могут менять округления.
- Память vs CPU: определить, является ли код compute-bound или memory-bound (профи-утилиты, roofline-модель).
- Масштабируемость: как оптимизация ведёт себя при росте данных/ядер.
- Затраты на тестирование и отладку: более хитрые оптимизации требуют больше QA.
- Возврат инвестиций: скорость разработки vs выигрыш в производительности.
- Энергопотребление/латентность: для встроенных систем важна энергия и задержки, не только throughput.
Практическая последовательность действий
1. Измерить (профайлинг, счетчики).
2. Определить тип узкого места: CPU/memory/IO/латентность.
3. Применять сначала алгоритмические улучшения, затем простые компиляторные флаги и настроить кеш/локальность.
4. Если нужно — PGO, LTO, векторизация, параллелизация, затем более низкоуровневые ручные оптимизации.
5. Каждый шаг измерять и регрессии тестировать.
Краткое напоминание о компромиссах: оптимизация — баланс скорости, памяти, читабельности и портируемости; базируйтесь на измерениях, а не на догадках.