Практическая оптимизация: кэш, ветвления, профилирование, SIMD

Весь трек мы считали операции. Мы говорили «этот алгоритм O(n log n), а тот O(n²)» и делали вывод, кто победит. Это правда — но правда про поведение на бесконечности. На конкретной машине с конкретными данными разница между двумя реализациями одного и того же O(n) алгоритма легко достигает 10–50×. Ни одна из них не «лучше по асимптотике». Просто одна разговаривает с железом на его языке, а вторая — нет.

Эта статья про константу под знаком O. Про то, почему обход матрицы по строкам в 5 раз быстрее обхода по столбцам при абсолютно одинаковом числе операций. Почему сортировка массива перед циклом, который его фильтрует, ускоряет цикл втрое. Почему std::map проигрывает std::vector с линейным поиском на тысяче элементов. И главное — как вообще понять, что чинить, вместо того чтобы угадывать.

Ключевая мысль, которую стоит забрать даже если вы бросите чтение на середине: оптимизация без измерения — это не оптимизация, а суеверие. Современный процессор слишком сложен, чтобы предсказывать его поведение головой. Даже опытные инженеры угадывают узкое место примерно в половине случаев.

Модель машины, которой у нас не было

Всё, что мы делали раньше, опиралось на RAM-модель: любая ячейка памяти доступна за одну единицу времени, каждая операция стоит одинаково. Эта модель была честной примерно до середины 1990-х. Дальше скорость процессоров росла на ~50% в год, а латентность DRAM — на ~7%. Разрыв, известный как memory wall, к сегодняшнему дню составляет два порядка.

Реальная машина отличается от RAM-модели по четырём осям:

1. Память иерархична. Между регистрами и DRAM — три уровня кэша. Промах в L1 стоит ~14 тактов, промах в L3 — ~250. Данные переносятся не байтами, а строками кэша по 64 байта (на некоторых ARM — 128).
2. Процессор суперскалярный и внеочередной. Он выполняет 4–6 инструкций за такт, в произвольном порядке, спекулятивно, поддерживая сотни инструкций «в полёте». Считать инструкции бессмысленно — важна длина критической цепочки зависимостей и загрузка портов исполнения.
3. Ветвления предсказываются. Условный переход не стоит ничего, если предсказатель угадал, и 15–20 тактов, если ошибся (весь конвейер сбрасывается).
4. Инструкции векторные. Одна операция AVX-512 складывает 16 чисел float. Скалярный код использует 1/16 арифметической мощности ядра.

Хорошая обзорная модель для этого — roofline (Williams, Waterman, Patterson, CACM 2009, DOI). Она вводит арифметическую интенсивность AI = FLOP / байт трафика с памятью и говорит: достижимая производительность равна min(пиковый FLOPS, AI × пиковая пропускная способность памяти). Если ваш код имеет AI < 1 (а это почти любой обход графа, любая база данных, любой JSON-парсер), вы упираетесь в память, и оптимизировать арифметику бессмысленно. Если AI > 10 (плотная линейная алгебра, свёртки), вы упираетесь в вычисления, и надо думать про SIMD и FMA. Первый вопрос при оптимизации всегда: я memory-bound или compute-bound?

Эта карта — практический чек-лист. Обходите её сверху вниз: сначала алгоритм, потом память, потом микроархитектура. Обратный порядок — самая распространённая ошибка начинающего оптимизатора.

Дисциплина: цикл оптимизации

Кнут в 1974 году написал фразу, которую с тех пор цитируют неправильно («Structured Programming with go to Statements», ACM Computing Surveys, DOI):

Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация — корень всех зол. Но мы не должны упускать наши возможности в этих критических 3%.

Вторая половина цитаты важнее первой. Тезис не «не оптимизируйте», а «найдите те 3%». Поиск — это процесс, и он выглядит так:

Два узла здесь неочевидны и оба критичны.

«Откатить». Оптимизация, не давшая измеримого выигрыша, — это чистый долг: код стал сложнее, а быстрее не стал. Её надо удалять без сожалений, даже если она «должна была» помочь.

«Записать почему так». Через полгода никто не вспомнит, почему здесь ручной цикл вместо std::transform, и «упростит» его обратно. Комментарий с числами (было 340 нс, стало 95 нс, замер X) — обязательная часть оптимизации.

Как правильно мерить

Микробенчмарки лгут чаще, чем говорят правду. Основные способы обмануть себя:

• Компилятор выкинул код. Результат не используется — цикла нет. Лечится «стоком»: benchmark::DoNotOptimize, std::hint::black_box в Rust, запись в глобальную переменную в Go.
• Нет прогрева. Первый прогон греет кэш, страничные таблицы, JIT. В JVM/PyPy/V8 без прогрева вы измеряете интерпретатор, а не скомпилированный код.
• Нереалистичные данные. Отсортированный массив, всегда попадающий кэш рабочий набор на 1 КБ, ключи без коллизий. В проде размеры и распределения другие — и вывод переворачивается.
• Шум машины. Turbo Boost, троттлинг, соседи по хосту, ASLR, выравнивание кода. Разброс 20% между запусками — норма для ноутбука. Меряйте медиану многих прогонов и сравнивайте распределения, а не единичные числа.
• Измерение не того. Wall-clock включает ожидание I/O и планировщика; CPU-time — нет. При отладке блокировок нужен именно off-CPU-анализ.

# Стабильный запуск на Linux: изоляция ядра, фиксированная частота, отключённый THP-дефраг
sudo cpupower frequency-set -g performance
taskset -c 3 chrt -f 99 ./bench          # закрепить ядро и приоритет

# Сравнение двух бинарников со статистикой, а не «на глазок»
hyperfine --warmup 5 --runs 50 './old' './new'

# Счётчики микроархитектуры: это первое, что стоит смотреть
perf stat -e cycles,instructions,branches,branch-misses,\
cache-references,cache-misses,L1-dcache-load-misses,dTLB-load-misses ./bench

# Где именно горячо
perf record -F 999 -g ./bench && perf report --stdio
# Флеймграф
perf script | stackcollapse-perf.pl | flamegraph.pl > cpu.svg

Из вывода perf stat сразу читаются две цифры:

• IPC (instructions / cycles). Меньше 1.0 — процессор стоит: промахи кэша, ошибки предсказания, длинные зависимости. Больше 3.0 — вы близки к пределу фронтенда, дальше только уменьшать число инструкций (SIMD).
• branch-miss rate. Больше 2–5% — есть смысл смотреть на branchless.

Более систематичный способ — Top-down Microarchitecture Analysis (TMA, Ahmad Yasin, ISPASS 2014). Он раскладывает каждый слот конвейера на четыре корзины: Retiring (полезная работа), Bad Speculation (ошибки предсказания), Frontend Bound (не успели подать инструкции), Backend Bound (память или порты исполнения). В Linux это perf stat --topdown или toplev из pmu-tools. Корзина с наибольшей долей и говорит, какую главу этой статьи читать.

Инструменты по экосистемам: perf и eBPF для нативного кода и всей системы, async-profiler для JVM, pprof для Go, py-spy и cProfile для Python, Instruments/dtrace для macOS, Intel VTune для глубокого микроархитектурного анализа, valgrind --tool=cachegrind для точного моделирования кэша (медленно, но детерминированно — удобно в CI). Про флеймграфы — канонический материал Брендана Грегга: brendangregg.com/flamegraphs.html.

Кэш: главный источник ускорений

Если оптимизация даёт больше 2×, почти всегда дело в памяти. Разберём приёмы по возрастанию сложности.

Локальность: пространственная и временная

Пространственная: обращённые рядом адреса приезжают одной строкой. Временная: недавно использованные данные ещё в кэше. Классическая демонстрация — обход двумерного массива в двух порядках.

import numpy as np, time

n = 4096
a = np.zeros((n, n), dtype=np.float32)

def by_rows(a):          # порядок обхода совпадает с раскладкой (C-order, row-major)
    s = 0.0
    for i in range(a.shape[0]):
        s += a[i].sum()  # непрерывный блок 16 КБ — идеально для префетчера
    return s

def by_cols(a):          # каждый шаг — новая строка кэша, шаг 16 КБ
    s = 0.0
    for j in range(a.shape[1]):
        s += a[:, j].sum()
    return s

Число арифметических операций идентично: n² сложений. Время отличается в 3–8 раз (на матрицах больше L2 — сильнее). Причина: при обходе по столбцам каждый элемент тянет свою строку кэша, из которой используется 4 байта из 64, а при шаге 16 КБ ещё и выбрасывает запись TLB.

Отсюда правило: порядок циклов должен совпадать с раскладкой памяти. В C, C++, Python/NumPy по умолчанию — row-major; в Fortran, MATLAB, Julia — column-major. Перестановка двух вложенных циклов местами (loop interchange) — самая дешёвая оптимизация в мире.

AoS против SoA

Вторая по частоте победа — изменение раскладки структур.

// AoS: удобно писать, плохо для массовых операций над одним полем
typedef struct { float x, y, z, vx, vy, vz; int id; unsigned flags; } Particle;
Particle ps[N];
for (int i = 0; i < N; i++) sum += ps[i].x;   // 12.5% полезного трафика, gather для SIMD

// SoA: неудобнее писать, но линейный доступ и автовекторизация
typedef struct { float *x, *y, *z, *vx, *vy, *vz; int *id; unsigned *flags; } Particles;
for (int i = 0; i < N; i++) sum += p.x[i];    // 100% полезного трафика, 16 float за инструкцию

Это ядро data-oriented design — подхода, который в геймдеве продвигал Майк Актон (CppCon 2014) и который лежит в основе ECS-архитектур (Unity DOTS, Bevy) и колоночных БД (ClickHouse, DuckDB, Parquet). Колоночное хранение — это ровно SoA, поднятое на уровень системы хранения: запрос SELECT sum(price) читает один столбец вместо всех строк целиком.

Обратная сторона: если типичный доступ — «взять один объект и прочитать все его поля», AoS выигрывает (одна строка вместо восьми). Компромисс — AoSoA: массив блоков по 8–16 объектов, внутри блока SoA. Так устроены современные физдвижки и ядра inference.

Родственный приём — сжатие структур. Убрать padding (-Wpadded покажет дыры), заменить int64 на int32 там, где хватает, вынести редко используемые поля в отдельный «холодный» массив (hot/cold splitting). Уменьшение структуры с 72 до 32 байт удваивает число объектов в строке кэша и часто даёт больше, чем любые микротрюки.

Указательная погоня и структуры данных

std::list, std::map, HashMap с цепочками, дерево из объектов на куче — все они делают pointer chasing: следующий адрес известен только после того, как загружен текущий. Внеочередное исполнение бессильно, префетчер не угадывает, каждый шаг — полная латентность промаха. Именно поэтому:

• Двоичный поиск по отсортированному vector бьёт std::map до сотен тысяч элементов.
• Хеш-таблицы с открытой адресацией (Abseil Swiss tables, flat_hash_map, Rust HashMap на hashbrown) бьют цепочки: абсl.io — там же трюк, где SSE2-инструкция проверяет 16 контрольных байтов за раз.
• В памяти выигрывают B-деревья, а не бинарные: узел на 16–64 ключа — это 1–4 строки кэша, высота дерева падает в 5 раз. Это же соображение стоит за Eytzinger-раскладкой для поиска.
• Граф в формате CSR (два плоских массива) обходится в разы быстрее списка списков — см. https://courses.digitable.life/post/algorithms/08-graph-traversal/.

Общее правило: плоские массивы вместо графа объектов; индексы вместо указателей (uint32 индекс вдвое меньше указателя и переживает realloc).

Блокировка (tiling) и I/O-сложность

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

// Наивно: B обходится по столбцам, на каждом элементе C — n промахов
for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++) {
    float s = 0;
    for (int k = 0; k < n; k++) s += A[i*n+k] * B[k*n+j];
    C[i*n+j] = s;
  }

// Блочно: работаем с подматрицами T×T, которые целиком лежат в L1/L2
for (int ii = 0; ii < n; ii += T)
  for (int jj = 0; jj < n; jj += T)
    for (int kk = 0; kk < n; kk += T)
      for (int i = ii; i < ii+T; i++)
        for (int k = kk; k < kk+T; k++) {        // k во внешнем — B[k] читается линейно
          float aik = A[i*n+k];
          for (int j = jj; j < jj+T; j++)
            C[i*n+j] += aik * B[k*n+j];
        }

Строгий анализ даёт внешняя память (модель Aggarwal–Vitter, M — размер кэша, B — строка). Наивный алгоритм переносит Θ(n³) строк, блочный — Θ(n³ / (B·√M)). Нижняя граница Хонга–Кунга (red-blue pebble game, STOC 1981, DOI) говорит, что лучше нельзя: Ω(n³/√M) обращений к памяти. То есть блокировка не эвристика, а асимптотически оптимальный ответ. Число арифметических операций при этом не меняется — меняется только трафик, и именно он был узким местом. Подробнее про эту модель и cache-oblivious алгоритмы — https://courses.digitable.life/post/algorithms/17-streaming-and-external-memory/.

Тот же приём в других обличьях: свёртки в CNN считаются по тайлам, GROUP BY в СУБД — хеш-партиционированием под размер L3, DP по подотрезкам — блочно (https://courses.digitable.life/post/algorithms/07-dynamic-programming/).

TLB и большие страницы

Виртуальные адреса транслируются через TLB — кэш таблицы страниц на ~1500–3000 записей. При странице 4 КБ это покрывает 6–12 МБ. Рабочий набор в 10 ГБ со случайным доступом даёт промах TLB почти на каждом обращении, а промах TLB — это дополнительный проход по таблице страниц (до 4 обращений в память). Лечение — huge pages (2 МБ вместо 4 КБ): madvise(MADV_HUGEPAGE), -XX:+UseLargePages в JVM, THP в ядре. На больших хеш-таблицах и базах это стабильные 10–30%.

False sharing

Многопоточный код умеет деградировать до однопоточного, не имея ни одного мьютекса.

Логически потоки независимы, физически — дерутся за одну строку. Диагностика: perf c2c record/report. Лечение — выравнивание и padding:

#include <stdalign.h>
typedef struct { alignas(64) _Atomic long value; } PaddedCounter;  // каждый счётчик — своя строка
PaddedCounter counters[NTHREADS];

В C++17 для этого есть std::hardware_destructive_interference_size, в Go — вручную _ [64]byte в структуре, в Java — @Contended (с -XX:-RestrictContended). Общий принцип: изменяемые данные разных потоков не должны делить строку кэша; и обратно — данные, читаемые вместе, желательно держать в одной (true sharing, hardware_constructive).

Ветвления и спекуляция

Конвейер современного x86 — 15–20 стадий. Чтобы он не простаивал, процессор угадывает исход условного перехода и начинает выполнять код за ним спекулятивно. Ошибка стоит полного сброса конвейера: 15–20 тактов впустую.

Простейший (исторический) предсказатель — двухбитный счётчик насыщения на каждый переход:

Реальные предсказатели (TAGE и его варианты) используют историю сотен предыдущих переходов и хеши путей исполнения, распознавая довольно сложные периодические паттерны. Но случайность они не предскажут принципиально: на if (data[i] > 128) при равномерно случайных данных точность падает до 50%, и это худший возможный случай.

Отсюда знаменитый эффект «отсортированный массив обрабатывается быстрее» (разбор на Stack Overflow): после сортировки условие сначала всегда ложно, потом всегда истинно — предсказатель почти не ошибается, и цикл ускоряется в 3–6 раз при том же числе операций.

Branchless-приёмы

Если ветвление непредсказуемо и находится в горячем цикле, его можно убрать, заменив поток управления на поток данных:

// Ветвление: непредсказуемо при случайных данных
if (x > threshold) sum += x;

// Без ветвления: маска. Компилятор выдаст cmov или арифметику без переходов
sum += x * (x > threshold);

// Классика: min/max без переходов
int min_ = b + ((a - b) & ((a - b) >> 31));   // работает для int32 без переполнения

// Branchless-разбиение (используется в быстрых сортировках и фильтрах)
out[k] = x;              // пишем всегда
k += (x > threshold);    // но продвигаем указатель только при выполнении условия

Сюда же — branchless binary search, где вместо if используется условное присваивание и предвыборка обеих ветвей (https://courses.digitable.life/post/algorithms/03-searching-and-binary-search/), таблицы переходов вместо цепочек if/else, и арифметика вместо % (Lemire’s fastmod: (uint64)(x * M >> 64) вместо деления, лемма и код).

Когда branchless вредит. Он выполняет обе ветви. Если условие предсказуемо на 95% или одна ветвь дорогая, ветвление дешевле: предсказатель работает бесплатно, а branchless платит всегда. Правило: branchless — только там, где perf stat показал высокий branch-misses и профиль указал на этот цикл. Никогда — «на всякий случай».

Ещё один способ убрать промахи предсказателя — убрать сам вопрос: разделить данные по условию заранее (партиционирование), развернуть цикл, вынести проверку из внутреннего цикла наружу (loop unswitching).

Дорогие операции

Таблица не про «избегайте всего» — про порядок величин, чтобы прикидывать бюджет. Если цикл делает 10⁸ итераций с делением, вы уже потратили секунду только на деление.

SIMD: одна инструкция — много данных

Векторные регистры — самый большой неиспользованный ресурс в типичном коде. SSE — 128 бит (4 float), AVX2 — 256 (8 float), AVX-512 — 512 (16 float), ARM NEON — 128, ARM SVE — переменная ширина. Идеальное ускорение равно ширине регистра; реальное — 2–8×, потому что упираешься в память.

Три уровня доступа, от простого к сложному.

1. Автовекторизация. Компилятор сам превращает цикл в векторный, если может доказать безопасность. Условия: простой цикл for с известным числом итераций, без зависимостей между итерациями, без указателей, которые могут пересекаться (aliasing), без вызовов и сложных ветвлений.

// Векторизуется: restrict обещает, что массивы не пересекаются
void axpy(float * restrict y, const float * restrict x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];   // станет vfmadd + AVX
}

gcc -O3 -march=native -ffast-math -fopt-info-vec-missed axpy.c   # что НЕ векторизовалось и почему
clang -O3 -march=native -Rpass-analysis=loop-vectorize axpy.c

Диагностический флаг -fopt-info-vec-missed — главный инструмент здесь: компилятор прямо пишет, что ему помешало («possible alias», «control flow in loop», «not enough data-refs»). Часто достаточно добавить restrict, убрать if из тела или заменить int64 индексы на int32. Важно: -ffast-math разрешает переассоциацию суммы (иначе редукция по float невекторизуема из-за неассоциативности), но меняет результаты — для финансов и численно неустойчивых алгоритмов он опасен.

2. Портируемые абстракции. std::experimental::simd в C++, Vector API в Java (JEP 338+), std::simd в Rust nightly, xsimd/Highway (google/highway) как библиотеки. Пишете один раз — компилируется под SSE/AVX/NEON.

3. Интринсики. Максимальный контроль, нулевая портируемость.

#include <immintrin.h>
// Сумма массива float с четырьмя независимыми аккумуляторами:
// одна цепочка сложений упёрлась бы в латентность FADD (~4 такта), четыре — в пропускную способность
float sum_avx2(const float *a, int n) {
    __m256 s0 = _mm256_setzero_ps(), s1 = s0, s2 = s0, s3 = s0;
    int i = 0;
    for (; i + 32 <= n; i += 32) {
        s0 = _mm256_add_ps(s0, _mm256_loadu_ps(a + i));
        s1 = _mm256_add_ps(s1, _mm256_loadu_ps(a + i + 8));
        s2 = _mm256_add_ps(s2, _mm256_loadu_ps(a + i + 16));
        s3 = _mm256_add_ps(s3, _mm256_loadu_ps(a + i + 24));
    }
    __m256 s = _mm256_add_ps(_mm256_add_ps(s0, s1), _mm256_add_ps(s2, s3));
    float buf[8]; _mm256_storeu_ps(buf, s);
    float tail = buf[0]+buf[1]+buf[2]+buf[3]+buf[4]+buf[5]+buf[6]+buf[7];
    for (; i < n; i++) tail += a[i];       // «хвост» обрабатывается скалярно
    return tail;
}

Здесь видны два обязательных элемента любого SIMD-кода: несколько аккумуляторов (чтобы скрыть латентность зависимой цепочки) и скалярный хвост для остатка длины.

Ключевой момент: SIMD любит SoA и ненавидит ветвления и косвенность. Векторизуется плоский массив с шагом 1. Если нужна условная логика — используйте маски (_mm256_blendv_ps, маски AVX-512), а не переходы. Если нужны данные по индексам — gather работает, но заметно медленнее линейной загрузки.

SIMD применяют далеко не только к числам: simdjson парсит JSON на гигабайтах в секунду, используя векторные инструкции для классификации байтов (Langdale & Lemire, arXiv:1902.08318); memchr, UTF-8 валидация, base64, Swiss tables, поиск подстроки, пересечение отсортированных списков в поисковых движках — всё это векторное.

В управляемых языках интринсиков обычно нет, и правильный ход — не бороться, а делегировать: в Python это NumPy/Numba/Cython (векторизованная операция уходит в скомпилированное ядро на BLAS), в Go — math/bits и ассемблерные вставки в стандартной библиотеке, в Java — Vector API, в C#/.NET — System.Numerics.Vector и System.Runtime.Intrinsics. Переписывание цикла на NumPy — это в 90% случаев и есть «SIMD для Python»:

# Плохо: интерпретируемый цикл, ~100 нс на элемент
total = 0.0
for i in range(len(xs)):
    if xs[i] > threshold:
        total += xs[i] * w[i]

# Хорошо: одна векторная операция, ~0.5 нс на элемент — три порядка на ровном месте
mask = xs > threshold
total = float(np.dot(xs[mask], w[mask]))

Компилятор — тоже инструмент оптимизации

Прежде чем переписывать код, стоит выжать из сборки:

• -O2 против -O3. -O3 агрессивнее разворачивает и векторизует, но раздувает код и иногда вредит (промахи i-cache). Меряйте оба.
• LTO (-flto): межмодульный инлайнинг. Часто 3–10% бесплатно.
• PGO (profile-guided optimization): собираете с -fprofile-generate, гоняете реалистичную нагрузку, пересобираете с -fprofile-use. Компилятор узнаёт, какие ветви горячие, и раскладывает код так, чтобы горячий путь был линейным. Типично 5–20% — это одна из самых выгодных оптимизаций «без изменения кода». В Go это PGO с профилем pprof, в JVM — AutoFDO.
• BOLT (facebookincubator/BOLT): переупорядочивание уже слинкованного бинарника по профилю. Ещё 5–15% на больших сервисах за счёт i-cache и iTLB.
• -march=native / -mtune: разрешить AVX2/AVX-512. Осторожно в контейнерах — бинарник может не запуститься на другом парке машин. Решение — runtime dispatch (__builtin_cpu_supports, ifunc, Highway).

Полезно уметь читать вывод: godbolt.org для ассемблера, llvm-mca и uiCA для оценки пропускной способности цикла по портам, uops.info и таблицы инструкций Агнера Фога для латентностей.

Приоритизация: что делать раньше

Не все оптимизации равны по соотношению «выигрыш / внесённая сложность».

Верхний левый угол — то, что делается почти всегда и почти бесплатно. Правый верхний — делается только тогда, когда профиль однозначно указал на этот цикл и есть бенчмарк в CI. Нижний правый — почти всегда преждевременно.

И не забывайте про закон Амдала: если оптимизируемая часть занимает долю p времени, а ускоряется в s раз, общее ускорение равно 1 / ((1-p) + p/s). Ускорив вдесятеро функцию, занимающую 20% времени, вы получите 1/(0.8+0.02) = 1.22× — 22%, а не 10×. Поэтому профиль первичен: работать надо над тем, что занимает бо́льшую долю, а не над тем, что интереснее оптимизировать.

Типичные ошибки

1. Оптимизация без профиля. Самая частая. Интуиция про современный CPU у людей плохая; узкое место обычно не там, где красиво.
2. Оптимизация не того слоя. Векторизовали цикл, который занимает 3% времени, пока рядом лежит O(n²) там, где нужен хеш, или синхронный запрос в базу в цикле (N+1).
3. Бенчмарк на нереалистичных данных. Всё влезает в L2, все ключи уникальны, все ветви предсказуемы — и вывод разворачивается на проде на 180°.
4. Замер шума. Разница 4% на трёх прогонах — это не разница. Нужны распределения и достаточное число повторов.
5. Микрооптимизация вместо удаления работы. Самый быстрый код — тот, который не выполняется: кэширование, ленивость, ранний выход, отсечение по границам.
6. -ffast-math в численном коде без анализа. Меняет семантику; в накопительных суммах и итерационных методах может изменить результат ощутимо.
7. Игнорирование «сначала правильно, потом быстро». Оптимизированный код должен быть покрыт тестами до оптимизации — иначе вы не узнаете, что сломали.
8. Забыть про параллелизм и I/O. Однопоточная микрооптимизация на 20% против распараллеливания на 8 ядер — несопоставимые масштабы. Но и тут: сначала сделайте однопоточную версию эффективной, иначе распараллелите неэффективность (https://courses.digitable.life/post/algorithms/16-parallel-and-distributed/).
9. Отсутствие защиты от регрессий. Без бенчмарка в CI ускорение исчезнет через три спринта, и никто не заметит.
10. Оптимизация p50 вместо p99. Пользователь чувствует хвост распределения. Часто хвост определяют GC-паузы, промахи кэша на холодных данных и блокировки — а не средняя стоимость операции.

Как это выглядит в проде

• ClickHouse — векторизованный движок выполнения: обрабатывает данные блоками по 65 536 значений колоночного формата, что даёт и локальность, и автовекторизацию, и амортизацию накладных расходов интерпретатора выражений.
• simdjson / rapidjson — парсинг на скорости, ограниченной пропускной способностью памяти, за счёт SIMD-классификации байтов и branchless-переходов.
• Abseil Swiss tables / hashbrown — открытая адресация плюс SIMD-проверка 16 слотов за инструкцию; заменили unordered_map в Google и HashMap в Rust.
• Facebook BOLT и Google AutoFDO — оптимизация layout кода по профилю с продакшена; на масштабе парка машин единицы процентов CPU — это миллионы долларов.
• NumPy / BLAS (OpenBLAS, MKL) — блокировка по кэшу и ассемблерные микроядра под конкретную микроархитектуру; ровно то, что мы разбирали в разделе про tiling.
• Ядро Linux: likely()/unlikely(), выравнивание горячих структур по строкам кэша, per-CPU переменные вместо общих счётчиков (борьба с false sharing) — те же приёмы на уровне ОС.
• JVM-сервисы: escape analysis, off-heap буферы, @Contended, снижение аллокаций ради укорочения GC-пауз — оптимизация памяти как способ починить p99.

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

Мини-итог

• Асимптотика решает, кто победит на больших n; константа решает, кто победит сегодня. Обе нужны — см. https://courses.digitable.life/post/algorithms/01-analysis-and-proofs/.
• Реальная машина — иерархия памяти плюс конвейер. Промах в DRAM ~250 тактов, ошибка предсказания ~15–20, векторный регистр — до 16 значений за инструкцию.
• Сначала выясните, memory-bound вы или compute-bound (roofline, perf stat, TMA). Ответ определяет весь дальнейший план.
• Память: локальность, SoA, компактные структуры, плоские массивы вместо указателей, блокировка, huge pages, отсутствие false sharing.
• Ветвления: предсказуемые бесплатны, случайные дороги. Branchless — по показаниям профиля, не «на всякий случай».
• SIMD: сначала помогите автовекторизации (restrict, простые циклы, SoA), потом портируемые абстракции, интринсики — в последнюю очередь.
• Компилятор: LTO, PGO, BOLT дают проценты без изменения кода — начните с них.
• Всё измеряйте, всё откатывайте, если не помогло, и закрепляйте результат бенчмарком в CI.

Источники

• U. Drepper. What Every Programmer Should Know About Memory, 2007 — PDF. Всё ещё лучший единый текст про кэши.
• S. Slotin. Algorithms for Modern Hardware — en.algorithmica.org/hpc. Современный, практичный, с бенчмарками.
• A. Fog. Optimization manuals and instruction tables — agner.org/optimize.
• Intel. 64 and IA-32 Architectures Optimization Reference Manual — intel.com.
• S. Williams, A. Waterman, D. Patterson. Roofline: An Insightful Visual Performance Model, CACM 2009 — DOI.
• J.-W. Hong, H. T. Kung. I/O Complexity: The Red-Blue Pebble Game, STOC 1981 — DOI.
• A. Aggarwal, J. S. Vitter. The Input/Output Complexity of Sorting and Related Problems, CACM 1988 — DOI.
• D. Knuth. Structured Programming with go to Statements, 1974 — DOI (та самая цитата, в контексте).
• G. Langdale, D. Lemire. Parsing Gigabytes of JSON per Second, 2019 — arXiv:1902.08318.
• A. Yasin. A Top-Down Method for Performance Analysis and Counters Architecture, ISPASS 2014 — DOI.
• B. Gregg. Systems Performance, 2nd ed. и flame graphs.
• C. Carruth. Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!, CppCon 2015 — видео.
• M. Acton. Data-Oriented Design and C++, CppCon 2014 — видео.
• Блог Д. Лемира — lemire.me/blog; Abseil — Swiss tables design notes.
• Инструменты: perf, hyperfine, Google Benchmark, Compiler Explorer, uops.info.

Смежные статьи трека: константы и асимптотика — https://courses.digitable.life/post/algorithms/01-analysis-and-proofs/; почему Timsort и radix быстрее «теоретически равных» — https://courses.digitable.life/post/algorithms/02-sorting/; Eytzinger и branchless-поиск — https://courses.digitable.life/post/algorithms/03-searching-and-binary-search/; скользящее окно как способ убрать лишнюю работу — https://courses.digitable.life/post/algorithms/04-two-pointers-sliding-window/; свёртка DP по слоям и локальность — https://courses.digitable.life/post/algorithms/07-dynamic-programming/; CSR и обходы графов — https://courses.digitable.life/post/algorithms/08-graph-traversal/; геометрические ядра и предикаты — https://courses.digitable.life/post/algorithms/12-computational-geometry/; параллелизм и его пределы — https://courses.digitable.life/post/algorithms/16-parallel-and-distributed/; модель внешней памяти и cache-oblivious — https://courses.digitable.life/post/algorithms/17-streaming-and-external-memory/.

Что дальше

Это последняя статья трека «Алгоритмы». Мы прошли путь от доказательства корректности и асимптотики до тактов конкретного процессора — и замкнули круг: анализ говорит, какой алгоритм выбрать, а практическая оптимизация — как заставить выбранный алгоритм работать на реальном железе. Хорошая точка, чтобы перечитать карту трека уже другими глазами: многое, что при первом чтении выглядело абстракцией, теперь имеет цену в наносекундах.

Куда идти дальше, зависит от того, что вы хотите строить:

• Фундамент под алгоритмами. Структуры данных — их реализации, инварианты и амортизация — трек Структуры данных.
• Языки и рантаймы. Многое из этой статьи проявляется по-разному в зависимости от среды исполнения: Go с его планировщиком и GC, TypeScript и JIT-компиляция в V8, C# со Span<T> и структурами без аллокаций, Elixir с моделью акторов и BEAM.
• Проектирование систем. Как алгоритмические решения превращаются в архитектуру: Принципы, Паттерны проектирования, Архитектурные паттерны.
• Данные и модели. Там оптимизация из этой статьи становится ежедневной работой: Инженерия данных, Машинное обучение, Нейронные сети.

Общая карта всех треков портала и рекомендованные маршруты обучения — Роадмап.