Краткий поэтапный план оптимизации «горячей» функции, работающей с большими массивами (C/C++) — профиль → анализ → оптимизации → проверка.
1) Подготовка и база
- Сделайте отдельный минимальный бенчмарк для функции с реалистичными входными данными; фиксируйте конфигурацию (частота CPU, привязка к ядрам). Привязка: `taskset` или `pthread_setaffinity_np`.
- Всегда сравнивайте с базовой версией и прогревайте кэши перед измерениями (несколько прогонов).
- Выключите непредсказуемые фоновые нагрузки и частотное турбо-ускорение при строгих измерениях.
2) Профилирование (внешнее → детальное)
- Слой 1 — где тратится время: `perf record`/`perf report`, `gprof` или `simple timing`.
- Слой 2 — CPU vs память: `perf stat` (события instructions, cycles, LLC-load-misses и т.д.) или `likwid-perfctr`.
- Слой 3 — детальное ветвление/векторизация: Intel VTune / Advisor (Hotspots, Memory Access, Vectorization reports).
- Слой 4 — симуляция кешей: `valgrind --tool=cachegrind` или `callgrind` (KCachegrind).
- Замеры памяти: загрузка памяти (bandwidth) с помощью `stream`-подобного бенча и инструмента (likwid, pcm).
3) Как интерпретировать результаты
- Определите, CPU-bound или memory-bound через operational intensity $I=\frac{\text{FLOP}}{\text{bytes transferred}}$ и сравнение с потолком памяти (roofline).
- Горячие точки: функции, где сосредоточено $>50\%$ времени, длинные периоды ожидания кэша (LLC misses) или частые ветвления с плохой предсказуемостью.
4) Алгоритмические улучшения (в первую очередь)
- Снизьте асимптотику (например, замена $O(n^2)$ на $O(n\log n)$ — FFT/сортировки/деревья).
- Устраните избыточные вычисления (кэшируйте повторно используемые результаты).
- Используйте более подходящие структуры данных для доступа по последовательным адресам.
5) Локальность данных и кэш-оптимизация
- Плотное хранение: массивы вместо массивов указателей; храните данные так, чтобы проход был последовательным.
- Выравнивание: выделение с выравниванием `posix_memalign(&p, $64$, size)` или `aligned_alloc($64$, size)`.
- Учитывайте размер кэш-линии (обычно \(\(64\)\) байт) — избегайте ложного шаринга и межячейкового наложения.
- Блокирование (tiling) для многомерных задач (матрицы): выбирайте блоки, умещающиеся в L1/L2 кеш. Пример подхода: разбить по блокам размера $B$ так, чтобы $B\times B\times$ элемент_size << размер кэша.
- Предвыборка (software prefetch) для предсказуемых последовательностей: `_mm_prefetch(addr, _MM_HINT_T0)`.
6) Векторизация
- Сначала попытайтесь автоваекторизацию: компиляция с `-O3 -march=native -ftree-vectorize` (gcc/clang). Просмотрите ассемблер/дисассемблер на наличие инструкций SIMD.
- Помогите компилятору: используйте `restrict` (C99) / `__restrict__`, объявляйте выравнивание, удаляйте алиасинг, располагайте циклы в удобной форме.
- Примеры средств: `#pragma omp simd` / `#pragma ivdep` / `__attribute__((always_inline))`.
- Если автоваекторизация не даёт результата — используйте SIMD-интринсики (AVX2/AVX-512) или ISPC.
- Ширины: AVX2 — \(\(256\)\)-bit (например, \(\(8\)\) float или \(\(4\)\) double), AVX-512 — \(\(512\)\)-bit (\(\(16\)\) float или \(\(8\)\) double).
- Остерегайтесь изменений в порядках операций и точности при применении векторизации/фаст-маф.
7) Параллелизация по потокам
- Разделяйте работу на крупные блоки, чтобы снизить накладные расходы и избежать ложного шаринга.
- Фиксируйте привязку потоков к ядрам, задавайте большие chunk'и для OpenMP (`schedule(static, chunk)`).
- Избегайте общих ресурсов и атомарных операций в «горячих» местах — используйте локальные буферы и затем редукцию.
- Следите за NUMA: выравнивайте и аллоцируйте память «ближе» к каждому сокету (numactl, libnuma).
8) Снижение затрат на память и пропускную способность
- Применяйте стриминговые (non-temporal) записи для больших последовательных выходов: `_mm_stream_si128`/`_mm256_stream_si256`.
- Минимизируйте объём передаваемых данных: сжимайте формат, используйте более узкие типы, если точность позволяет.
- Рефакторинг, чтобы уменьшить число проходов по данным (например, объединение циклов — loop fusion).
9) Низкоуровневые трюки (после алгоритмических и структурных изменений)
- Удаление ветвлений: замените условные ветки на маски/условные инструкции или предвычисления.
- Ручное развёртывание (unrolling) цикла там, где помогает избегать затрат на контрольный код.
- Избегайте дорогостоящих функций (деление, синус/косинус) в горячих петлях; используйте аппроксимации при приемлемой погрешности.
10) Проверка, регрессии и автоматизация
- После каждого улучшения — регресс-тесты (точность) и бенчмарк с реальными данными.
- Автоматизируйте профилирование и сбор метрик; используйте контрольные метрики: время, пропускная способность (GB/s), FLOPS.
- Для понимания потолков используйте roofline-модель: измерьте пиковую память и вычислительную производительность платформы и сравните с вашим кодом.
Короткий чек-лист (последовательность действий)
1. Снять baseline; обеспечить воспроизводимость.
2. Профайлить hotspots (perf/VTune/valgrind).
3. Определить: memory-bound или CPU-bound (операционная интенсивность $I$).
4. Улучшить алгоритм/структуры данных.
5. Оптимизировать локальность: выравнивание `posix_memalign(&p, $64$, size)`, блокирование.
6. Включить автоваекторизацию, помочь компилятору (`restrict`, `pragma omp simd`).
7. При необходимости — SIMD-интринсики / ISPC.
8. Параллелизация с учётом NUMA и избеганием ложного шаринга.
9. Микрооптимизации и проверка точности.
10. Снова профайлить и зафиксировать улучшения.
Если нужно, могу дать целевой чек-лист команд для профилирования на вашей машине или пример типичной рефакторинговой последовательности для конкретной функции (например, свёртка, умножение матриц, суммирование по массиву).