C++ выбирают ради скорости, поэтому на собесе ждут, что вы понимаете, откуда она берётся. Асимптотика важна, но на современном железе часто решает другое: как данные лежат в памяти.
Иерархия памяти
Порядки величин, которые стоит помнить (x86-64, порядок, а не точные цифры):
| Уровень | Задержка |
|---|---|
| Регистр | < 1 нс |
| L1-кеш (десятки КБ на ядро) | ~1 нс |
| L2 | ~3-5 нс |
| L3 (общий, мегабайты) | ~10-20 нс |
| Оперативная память | ~80-100 нс |
Процессор читает память не байтами, а кеш-линиями (64 байта на x86-64 и большинстве ARM). Если следующий нужный байт в той же линии, он уже в кеше. Аппаратный префетчер угадывает последовательный доступ и подгружает линии заранее.
Локальность данных
- Пространственная: обходите память подряд. Матрица в C++ хранится по строкам, поэтому цикл
for i { for j { a[i][j] } }в разы быстрее, чемfor j { for i { a[i][j] } }на больших матрицах. std::vectorнепрерывен и дружит с кешем.std::listиstd::mapразбросаны по куче: каждый переход по указателю потенциальный промах кеша. Поэтому поиск в отсортированном векторе часто быстрееstd::map, аvectorбыстрееlistдаже на вставках в середину небольших коллекций.vector<vector<T>>это множество отдельных аллокаций; плоскийvector<T>размераn · mс индексомi * m + jбыстрее.- AoS против SoA: массив структур удобен, но если горячий цикл читает одно поле из пяти, структура массивов (
vector<float> x, y, z) использует кеш полностью и лучше векторизуется.
False sharing
Два потока пишут в разные переменные, лежащие в одной кеш-линии. Протокол когерентности гоняет линию между ядрами, и «независимые» потоки тормозят друг друга. Лечится выравниванием и разнесением данных: alignas(64) или alignas(std::hardware_destructive_interference_size) (C++17, в GCC доступно с версии 12), а лучше локальными аккумуляторами с одной записью в конце.
Аллокации
Выделение памяти в куче стоит десятки и сотни наносекунд и плохо масштабируется по потокам. Приёмы:
reserveдля векторов и строк известного размера;- переиспользовать буферы между итерациями (
clear()не освобождает ёмкость); - короткие строки помещаются в
std::stringбез аллокации (SSO, в libstdc++ до 15 символов); - пулы, арены,
std::pmrдля множества мелких объектов.
Ветвления
Процессор предсказывает переходы. Непредсказуемое условие в горячем цикле стоит ~10-20 тактов на ошибку. Классика: цикл с if (x >= 128) по отсортированному массиву заметно быстрее, чем по случайному. Помогают безветвленные формы (std::min, умножение на bool), сортировка данных, атрибуты [[likely]] и [[unlikely]] (C++20) как подсказка.
Компилятор вам поможет
-O2или-O3,-march=native(если бинарник запускается на той же машине), LTO (-flto) для встраивания между единицами трансляции, PGO для оптимизации по профилю.- Встраивание (inlining) убирает цену вызова и открывает дальнейшие оптимизации. Шаблоны и лямбды встраиваются, виртуальные вызовы и
std::functionобычно нет. - Векторизация: простые циклы по непрерывным массивам без зависимостей превращаются в SIMD-инструкции.
Ввод-вывод
std::endl сбрасывает буфер, в цикле это тысячи системных вызовов: пишите '\n'. Для быстрого чтения std::ios::sync_with_stdio(false); std::cin.tie(nullptr);.
Сначала измерить
Оптимизация без измерения часто ускоряет не то. Порядок: воспроизводимый бенчмарк (Google Benchmark, hyperfine), профилировщик (perf, VTune, Instruments), гипотеза, изменение, повторное измерение. perf stat показывает промахи кеша и ошибки предсказания переходов.
Частые ошибки
- Обход матрицы по столбцам.
std::list«потому что вставки O(1)».- Аллокации в горячем цикле.
std::endlв цикле вывода.- Счётчики разных потоков в соседних полях структуры.
- Оптимизация без профиля.
Что спросят на собесе
- Что такое кеш-линия и как от неё зависит скорость обхода.
- Почему vector обычно быстрее list и map.
- Что такое false sharing и как его убрать.
- Как уменьшить число аллокаций.
- Как вы ищете узкое место.