Коротко о механике и последствиях
- Кэш — иерархия быстро‑медленно (L1, L2, L3) с блоками (cache lines) размером $L$ байт. Доступ к данным, лежащим в кэше, на порядок быстрее, чем к ОЗУ.
- Локальность данных:
- пространственная (spatial): если вы обращаетесь к адресу $A$, вероятно, будете обращаться и к соседним адресам в пределах той же строки $L$;
- временная (temporal): если вы используете данные сейчас, вы, вероятно, используете их снова в ближайшем будущем.
- Производительность определяется количеством кэш‑промахов. Если рабочее множество $W$ «влезает» в кэш (примерно $W\ll C$, где $C$ — размер уровня кэша), промахов мало, программа быстрая.
Практические оптимизации (код и структуры данных)
1. Контейнеры и макс. непрерывность
- Используйте массивы/векторы (contiguous memory) вместо связанных списков. Linked list — плохая пространственная локальность.
- Для C++: предпочитайте `std::vector` перед `std::list`, вызывайте `reserve` чтобы избежать фрагментации.
2. Выравнивание и упаковка
- Структуры упаковывайте так, чтобы нужные поля находились рядом; удаляйте лишние паддинги, либо наоборот — добавляйте паддинг для предотвращения false sharing в многопоточности.
- При многопоточности избегайте false sharing: не давать разным потокам писать в данные, расположенные в одной строке $L$ — добавьте padding до размера $L$.
3. Порядок обхода и шаг (stride)
- Итерируйте в порядке хранения (row‑major для C/C++): проход по строкам быстрее, чем по столбцам.
- Минимизируйте шаг доступа $s$. Если шаг $s\ge L$, каждое обращение, скорее всего, вызывает промах. Если $s<L$, много элементов попадает в одну строку и используют пространственную локальность.
4. Блочная обработка (tiling/blocking)
- Разбейте работу на блоки, чтобы рабочее множество каждой итерации помещалось в кэш. Пример для блочного умножения матриц: выбирайте размер блока $b$ так, чтобы три блока (A, B, C) поместились в кэше:
$$3b^2\cdot S\le C$$ где $S$ — размер элемента (например, $8$ для double), $C$ — доступный объём кэша.
- Блочная схема значительно уменьшает число промахов при матричных операциях и свёртках.
5. Форматы данных: Array of Structures (AoS) vs Structure of Arrays (SoA)
- Если обрабатываете один поле у многих объектов (например, координаты x всех частиц), SoA даёт лучшую локальность: храните отдельные массивы для x, y, z.
- AoS лучше, когда вы всегда используете все поля одного объекта одновременно.
6. Предвыборка (prefetch) и инструкции
- Компиляторы автоматически предвыбирают данные; для узких мест можно использовать явную предвыборку (например, __builtin_prefetch). Но неправильная предвыборка ухудшает производительность.
- Используйте restrict/`__restrict__` (C) или агрессивные атрибуты компилятора, чтобы помочь оптимизатору с алиасингом.
7. Уменьшение размера объектов и плотность
- Меньшие структуры → больше объектов в одной строке/кэше → меньше промахов.
- Сжатие/упаковка данных, использование целочисленных типов меньшего размера, если точность позволяет.
8. Алгоритмические и архитектурные приёмы
- Кэш‑обозначенные (cache‑oblivious) алгоритмы, которые автоматически хороши для иерархий кэша.
- Loop interchange (смена порядка вложенных циклов) для достижения последовательного доступа.
- Loop fusion (слияние циклов) для повторного использования данных в кэше; loop fission — если надо уменьшить working set.
9. Пул памяти и выделение объектов
- Используйте memory pools/arenas для связанных объектов, чтобы они располагались рядом в памяти.
- Избегайте частого мелкого распределения/free, это фрагментирует кэш‑локальность.
Как измерять и диагностировать
- Инструменты: perf, VTune, Linux perf_events, Valgrind Cachegrind. Смотрите показатели L1/L2/L3 misses, LLC misses, CPI.
- Микротесты: бенчмарки со встроёнными измерениями времени и counters, профилируйте именно узкие места.
Короткие правила‑эмпирика
- Доступы должны быть как можно более последовательными и локальными.
- Рабочее множество должно «умещаться» в ближайший кэш.
- Избегайте случайных указателей и частого перескакивания по памяти.
- Оптимизируйте данные перед алгоритмом: часто изменение структуры данных даёт больше выигрыша, чем изменение кода.
Если нужно — могу привести конкретные примеры (блочная матрица, преобразование AoS→SoA, пример предвыборки) для вашего кода.