Два цикла с одинаковым числом итераций и одинаковой сложностью дают разную скорость, потому что процессор тратит время не на вычисления, а на ожидание данных из памяти. Когда вы обходите массив подряд, каждая загруженная кэш-линия используется целиком: одно обращение к DRAM отдаёт данные для 16 последовательных элементов int. Когда вы прыгаете по массиву, та же линия отдаёт один нужный элемент, а остальные байты уходят впустую.
Задержки доступа к памяти растут с каждым уровнем иерархии: попадание в L1 измеряется единицами тактов, промах до DRAM — сотнями. Точные значения зависят от конкретного ядра, его частоты и настроек, поэтому универсальных чисел в наносекундах приводить не стоит: корректнее измерять задержки на целевой платформе. Промах по всем уровням означает простой конвейера на сотни тактов, и этот простой нельзя скрыть инструкциями. Отсюда правило: сначала смотрим, сколько раз процессор ждёт память, и только потом трогаем арифметику.
Единица обмена между памятью и кэшем - кэш-линия, на x86_64 это 64 байта. Кэш процессора работает с линиями памяти, а кэш приложения хранит готовые результаты: это разные механизмы с разными метриками. Про уровни выше по стеку читайте в материале про паттерны кэширования в коде приложения. Дальше речь только о процессорных кэшах и о том, как переписать цикл под них.
Почему порядок обхода массива решает больше, чем алгоритм
Что такое кэш-линия и почему она важнее отдельного байта
Кэш-линия это минимальный блок, которым обмениваются процессор и оперативная память. Для x86-64 размер кэш-линии составляет 64 байта, для A64 ARM — 128 байт. Проверить значение на конкретной машине можно программно: команда getconf LEVEL1_DCACHE_LINESIZE на x86 возвращает 64. В sysfs то же значение лежит в файле /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size. В том же каталоге находятся размер и тип каждого уровня: index0 - L1 данных, index1 - L1 инструкций, index2 - L2, index3 - L3.
Практический вывод из размера линии простой. Массив из 16 значений int (по 4 байта) занимает ровно 64 байта, то есть одну кэш-линию. Обращение к arr[0] приведёт к загрузке всех 16 элементов, и если следующая итерация читает arr[1], данные уже готовы в L1. На этом строится весь выигрыш последовательного обхода: память масштабируется по линиям, а не по отдельным байтам.
Железо добавляет к этому предсказатель доступа. Аппаратный префетчер распознаёт монотонный шаг (stride) и подтягивает следующие линии заранее, пока ядро занято вычислениями. При ровном шаге вперёд префетчер работает почти бесплатно, при больших шагах, движении назад или обходе по столбцам матрицы он либо отключается, либо приносит линии, которые не пригодятся.
Второй эффект - TLB, кэш трансляций виртуальных адресов в физические. Размер страницы обычно 4 КБ, поэтому при обходе с шагом в 4 КБ (а именно такой шаг даёт столбец int-матрицы) каждый следующий элемент попадает на новую страницу. Кэш трансляций переполняется, и к промахам по данным добавляются промахи по таблицам страниц.
Уровни кэша L1/L2/L3 и их роль в производительности
Иерархия кэшей различается объёмом и задержкой. Типичные объёмы для серверных и десктопных ядер: L1 данных 32-64 КБ, L2 256 КБ - 1 МБ, L3 8-32 МБ. L1 и L2 привязаны к ядру, L3 делится между ядрами, поэтому соседние процессы и потоки конкурируют за него. На многосокетных серверах L3 разбит на домены, и обращение к чужому домену идёт заметно медленнее. Конкретные задержки каждого уровня зависят от модели процессора и частоты, поэтому их стоит измерять на целевой платформе, а не переносить из общих таблиц.
Разница проявляется на данных, которые не помещаются в L2. Возьмём матрицу 1024×1024 из int: это 4 МБ, объём укладывается в L3, но не в L2. При обходе по строкам элементы идут по памяти подряд, и доля промахов остаётся низкой. При обходе по столбцам шаг равен 4 КБ, поэтому линия отдаёт 4 полезных байта из 64. Полезная утилизация линии падает примерно в 16 раз, во столько же растёт трафик из DRAM, и время выполнения растёт соответственно. Измерения на матрице 10000×10000 показывают, что построчный обход примерно в 6,9 раза быстрее обхода по столбцам при том же алгоритме и тех же оптимизациях компилятора: последовательный проход эффективно заполняет кэш-линии, а обход по столбцам постоянно выбивает кэш и заставляет снова обращаться к основной памяти. По доле промахов разрыв ещё нагляднее: для построчного обхода это единицы процентов, для обхода по столбцам — десятки процентов. Как индекс превращается в адрес при разных схемах линеаризации, разобрано в статье про row-major и column-major.
Вывод для горячего цикла: важнее не количество операций, а то, сколько разных кэш-линий цикл трогает на каждой итерации. Последовательный обход трогает одну линию на 16 итераций, обход по столбцам - одну линию на каждую итерацию.
Как измерить эффект кэш-локальности: инструменты и метрики
Сравнение вариантов обхода строится на счётчиках производительности процессора (PMU). Порядок действий: собрать программу с -O2, прогнать оба варианта через perf stat, сравнить долю промахов, при необходимости разобрать конкретные строки кода через cachegrind.
Снятие метрик через perf stat
Базовый набор событий: cache-references и cache-misses дают общее отношение промахов, LLC-loads и LLC-load-misses показывают попадания в последний уровень кэша, L1-dcache-load-misses указывает на промахи в L1 данных.
perf stat -e cache-references,cache-misses,LLC-loads,LLC-load-misses,L1-dcache-load-misses ./program
Вывод по двум вариантам обхода одной матрицы (числа иллюстративные, важна разница между вариантами):
последовательный обход: cache-references 2 097 152, cache-misses 65 536 (3,1%), LLC-load-misses 32 768
обход по столбцам: cache-references 2 097 152, cache-misses 1 048 576 (50,0%), LLC-load-misses 1 015 808
Ключевой показатель не абсолютное число промахов, а их доля и связь с объёмом полезной работы. Если доля cache-misses на потоковом цикле выше 10%, шаблон доступа почти наверняка стоит проверить. Есть два ограничения. Ядро Linux отдаёт доступ к PMU только при значении /proc/sys/kernel/perf_event_paranoid не выше 2. В контейнерах и виртуальных машинах счётчики кэша часто не проброшены: проверяется командой perf stat -e cache-misses true, и при отсутствии поддержки perf сообщит об этом сразу.
Для воспроизводимости замеров нужны три вещи: фиксированная частота (cpupower frequency-set -g performance), отключённый турбо-буст и привязка к ядру через taskset -c 2 ./program. Прогонов делайте не меньше пяти, берите медиану, а первые итерации отбрасывайте как прогрев: первые прогоны подтягивают страницы и код в кэш.
Анализ через cachegrind
Команда valgrind --tool=cachegrind ./program даёт модель кэшей с разбивкой промахов по строкам исходника. Отчёт читается через cg_annotate cachegrind.out.12345, где 12345 это PID процесса. События в отчёте: Ir (исполненные инструкции), D1mr (промахи чтения в L1 данных), D1mw (промахи записи в L1), DLmr и DLmw (промахи последнего уровня), а также итоговые D1 miss rate и LL miss rate.
cachegrind считает по симуляции, а не по аппаратным счётчикам, поэтому работает в контейнере, без root и без доступа к PMU. Плата - замедление в десятки раз и приблизительность модели: по умолчанию берётся конкретная конфигурация кэшей, которую можно задать флагами --I1, --D1 и --LL. Для поиска виновника среди сотен строк это самый быстрый путь: в отчёте сразу видно, какая строка даёт основную массу D1mr.
Блочный (tiled) обход: как переписать цикл под кэш
Идея tiling проста: вместо обхода всей матрицы за один проход цикл разбивается на блоки такого размера, чтобы рабочий набор блока помещался в L1 или L2 и оставался там до конца обработки. Тогда данные из DRAM читаются один раз, а повторные обращения обслуживает кэш.
Классический пример - умножение матриц. Наивный тройной цикл по i, j, k читает строку A и столбец B, причём столбец B идёт с шагом в целую строку, что даёт почти полный промах по L1 на каждом обращении. Блочный вариант разбивает индексы на диапазоны размером B и прогоняет внутренние циклы внутри блока, поэтому и A, и B, и аккумулятор C остаются в кэше.
Выбор размера блока под конкретный кэш
Размеры кэшей смотрятся через lscpu или напрямую: /sys/devices/system/cpu/cpu0/cache/index2/size для L2 и index0 для L1 данных. Дальше оценка: чтобы три блока по B×B элементов жили в кэше, нужно 3 × B² × размер_элемента ≤ объём кэша. Отсюда B ≈ sqrt(объём_кэша / 3 / размер_элемента).
Пример для L1 32 КБ и double (8 байт): B ≈ sqrt(32768 / 3 / 8) ≈ 36, на практике берут 32 или 64. Для L2 1 МБ и тех же double получится B ≈ sqrt(1048576 / 3 / 8) ≈ 209, то есть блок 128 или 256. Блокировка применима на каждом уровне иерархии со своим размером блока: например, B=8 для L1 и B=80 для L2. Округление до степени двойки удобно, но иногда даёт конфликтные промахи: строки матрицы ложатся в один и тот же набор кэша и вытесняют друг друга. Если результат нестабилен, попробуйте размер с нечётным множителем: 48, 96, 192.
Проверка одна: прогнать бенчмарк с B равным 16, 32, 48, 64, 128 и 256 и сравнить время. Оптимум обычно шире, чем ожидается, а резкий провал появляется там, где рабочий набор блока перестаёт влезать в целевой уровень кэша. Слишком маленький блок тоже плох: растёт доля накладных расходов на переиндексацию и хуже работает векторизация.
Транспонирование как альтернатива tiling
Если матрица нужна только для чтения по столбцам, её можно транспонировать один раз и дальше обходить по строкам. Тогда основной цикл получает последовательный доступ без блокировки. Цена: дополнительная память O(n²) и один проход копирования. Само транспонирование тоже требует блочного подхода, потому что наивный обмен элементов (i, j) и (j, i) читает или пишет с шагом в строку и упирается в те же промахи. Квадраты 16×16 или 32×32 убирают проблему.
Сравнение по применению. Tiling не требует лишней памяти и работает на месте, но усложняет индексацию и иногда мешает компилятору векторизовать вложенные циклы. Транспонирование оставляет основной цикл линейным и легко векторизуемым, зато требует памяти и лишнего прохода. Для матриц, которые читаются многократно, выгоднее транспонирование, для однократной обработки - блоки.
Практический сценарий: оптимизация горячего цикла в реальном сервисе
Типовой случай: бэкенд на C++ обрабатывает большой массив записей в памяти, профилировщик показывает, что 70% времени уходит на один цикл агрегации. Дальше шаги повторяются почти всегда.
- Найти горячий цикл: perf record -g ./service, затем perf report. Убедиться, что он упирается именно в память: высокая доля cache-misses и низкий IPC.
- Снять perf stat по событиям кэша до правок и сохранить цифры.
- Определить шаблон доступа: последовательный, с постоянным шагом или случайный.
- Переписать структуру данных или порядок обхода.
- Повторить замер и сравнить с исходным.
В таком примере переход с обхода структур на поля в отдельных массивах и разбиение цикла на блоки заметно сокращает время на том же наборе данных. Конкретные цифры зависят от размера данных, структуры записи и платформы, поэтому их нужно получать замером на своём коде, а не переносить из чужого бенчмарка. Принцип один: каждое изменение подтверждается замером до и после. Тот же порядок работ применим к ускорению сервисов без замены железа, подробнее в руководстве как повысить производительность автоматизированных систем без замены оборудования.
AoS vs SoA: как структура данных влияет на кэш
Пусть записи лежат как массив структур вида struct {int x; int y; int z;}. Размер такой структуры 12 байт, в одну 64-байтовую линию помещается пять полных записей. Если цикл суммирует только поле x, полезными оказываются 20 байт из 64, то есть меньше трети линии. Остальной трафик уходит впустую.
Схема SoA разносит поля по отдельным массивам: xs, ys, zs. Цикл по xs идёт сплошным потоком, и каждая линия отдаёт 16 полезных значений int. Эффект измерим: на бенчмарке с 10 миллионами частиц (около 610 МБ данных) переход от AoS к SoA сократил медианное время выполнения с 28,45 мс до 6,92 мс, то есть дал ускорение примерно в 4,11 раза. Причина видна из арифметики: в AoS на 24 байта полезных данных приходится 64 байта загруженной линии, то есть только 37,5% пропускной способности DRAM и кэша тратится на нужные поля. Схема AoS остаётся удобнее, когда код читает все поля записи одновременно: тогда линия используется целиком, и разницы почти нет.
У SoA есть цена. Код становится многословнее, появляется больше индексов и отдельных структур, а случайная вставка одной записи требует записи в несколько массивов. Для горячих циклов чтения это обычно оправдано, для структур с частой модификацией - не всегда.
Использование prefetch для скрытия задержек
Когда шаблон доступа известен заранее, но не линеен (например, обход разреженной структуры по списку индексов), помогает программная предвыборка: __builtin_prefetch(ptr, 0, 3) в GCC и Clang. Второй аргумент 0 означает чтение, 1 - запись, третий задаёт уровень локальности в значениях 0, 1, 2 или 3.
Механика такая: адрес следующего нужного элемента вычисляется за несколько итераций вперёд и подтягивается в кэш, пока ядро занято текущими данными. Дистанцию подбирают экспериментально, обычно это 4-16 итераций, то есть одна-две кэш-линии вперёд. Слишком близкий prefetch не успевает отработать, слишком далёкий вытесняет нужные данные.
Польза есть не всегда. Аппаратный префетчер сам справляется с линейными и шаговыми обходами, и ручная предвыборка там только добавляет инструкции. Вред возможен, если линия загружается впустую или вытесняет данные, которые ещё нужны. Эффект проверяется тем же perf stat: полезный prefetch снижает LLC-load-misses, бесполезный не меняет ничего или ухудшает.
Типичные ошибки и ограничения при оптимизации кэш-локальности
Основные грабли: правки без профилирования, ложное разделение в многопоточном коде, слишком большой блок, вытесняющий данные, и некорректный бенчмарк без прогрева и с включённым турбо-бустом. Ниже два самых частых случая и границы, за которыми приёмы не работают.
Ложное разделение (false sharing) в многопоточном коде
Два потока пишут каждый в свой счётчик, но переменные лежат в одной 64-байтовой линии. Протокол когерентности кэшей переводит линию в состояние единоличного владения у одного ядра, и второму потоку приходится забирать её себе. Линия начинает курсировать между ядрами, а каждый такой обмен стоит десятки и сотни наносекунд. Симптом узнаётся сразу: добавление потоков не ускоряет код, а замедляет его.
Лечится разнесением переменных по разным линиям: alignas(64) в C++, padded-структуры, константа std::hardware_destructive_interference_size из C++17 для переносимого размера. Значение этой константы зависит от платформы, поэтому в кросс-платформенном коде её проверяют на целевой архитектуре. Как компилятор расставляет padding и как выравнивание по границе кэш-линии убирает ложное разделение, разобрано в статье про выравнивание данных и padding в массивах.
Когда оптимизация кэш-локальности не поможет
Есть границы, за которыми переписывание циклов не даёт ничего.
- Данные уже в кэше. Массив на несколько десятков килобайт целиком живёт в L1 и L2, промахов почти нет, и менять порядок обхода бессмысленно.
- Цикл упирается в вычисления. Если в теле деление, квадратный корень или вызовы libm, время уходит в арифметику. Признак: высокий IPC и низкая доля cache-misses.
- Доступ непредсказуем. Обход хеш-таблицы, дерева или связного списка зависит от данных, и tiling тут не применим. Помогают другие приёмы: открытая адресация вместо цепочек, размещение узлов в общем пуле рядом друг с другом, сортировка ключей перед обходом.
- Упор в пропускную способность памяти. Если поток данных уже насыщает канал DRAM, локальность не добавит скорости. Тогда смотрят в сторону streaming stores и non-temporal подсказок кэшу.
Архитектура тоже важна: размер линии и уровней кэша отличается между x86_64 и ARM, между серверными и мобильными ядрами. Код с блоком 64 на одной машине даст выигрыш, на другой не даст ничего. Проверяйте на целевой платформе, а не на рабочем ноутбуке.
Отдельная ловушка - компилятор. На -O2 и -O3 GCC и Clang умеют сами переставлять циклы и применять блочную обработку, поэтому часть ручных правок может не дать эффекта. Если результат непонятен, посмотрите ассемблер: gcc -O2 -S -o - program.c. Преждевременная оптимизация без профиля остаётся самой дорогой ошибкой: время уходит на усложнение кода, а узкое место лежит в другом месте.
Чек-лист: как переписать цикл под кэш
- Профилировать и найти горячий цикл: perf record -g, затем perf report.
- Снять метрики кэша до правок: perf stat -e cache-references,cache-misses,LLC-loads,LLC-load-misses.
- Определить шаблон доступа и рабочий набор: помещается ли он в L1, L2 или L3.
- Для матриц и вложенных циклов применить tiling, размер блока посчитать по формуле и уточнить бенчмарком.
- Для массивов структур проверить, не выгоднее ли SoA, и не мешает ли padding.
- Добавить prefetch только там, где аппаратный префетчер не справляется, и подтвердить эффект метрикой.
- Зафиксировать частоту, отключить турбо-буст, замерить медиану из 5-10 прогонов до и после.
- Проверить результат на целевой платформе и под рабочей нагрузкой, а не только на синтетике.
Возьмите один самый горячий цикл в своём сервисе, снимите perf stat по событиям кэша и запишите числа. Если доля cache-misses высокая, начните с порядка обхода и структуры данных, а не с блочности: часто последовательный проход по SoA даёт больше, чем аккуратный tiling поверх неудачной раскладки памяти.
Источники
- cache-bench: hands-on lesson in CPU cache behavior — сравнение построчного и постолбцового обхода матрицы 10000×10000, доли промахов кэша.
- cache-bench (nemeth06) — поведение LLC при обходе матрицы 2048×2048 по столбцам.
- aos-vs-soa-benchmark — бенчмарк AoS против SoA на 10 миллионах частиц.
- Matrix multiplication and blocking — ограничение размера блока объёмом кэша и многоуровневая блокировка.
- Aligning to cache line and knowing the cache line size — определение размера кэш-линии через getconf.
- Smarter CPU testing: memory and cache — размеры кэш-линий для x86-64 и A64 ARM.