Кэши и локальность: почему одинаковый по сложности код работает в 10 раз медленнее

Асимптотическая сложность — прекрасный инструмент с одним катастрофическим допущением: модель RAM считает, что любое обращение к памяти стоит одинаково. На реальном железе это неправда уже лет тридцать. Обращение в L1 стоит около 1 наносекунды, обращение в DRAM — около 80. Это разрыв в восемьдесят раз внутри операции, которую вы в анализе сложности посчитали за единицу.

Отсюда наблюдение, ради которого написана статья: два цикла, оба Θ(n), оба без единой лишней инструкции, могут отличаться по времени в 10, 50 и 100 раз. Разница не в том, сколько работы делает код, а в том, в каком порядке он трогает адреса. Асимптотика этот порядок не видит вообще.

Мы уже умеем измерять (https://courses.digitable.life/post/performance/01-measuring/), честно бенчмаркать (https://courses.digitable.life/post/performance/02-benchmarking/) и находить горячий код (https://courses.digitable.life/post/performance/03-cpu-profiling/). Профиль часто заканчивается фразой «86% времени в этой функции, а в ней ничего нет — просто цикл». Вот с этого места и начинается разговор про кэши. И в духе всего трека: сначала измерь. Локальность — область, где интуиция ошибается особенно уверенно, потому что «плохой» код выглядит абсолютно нормально.

1. Стена памяти: почему кэш вообще существует

С середины 1980-х производительность ядра росла примерно на 50% в год, а латентность DRAM улучшалась на 5–7%. Пропускная способность памяти догоняла, латентность — практически нет: случайный доступ к DRAM в 1995 году занимал около 100 нс, сегодня — около 70–90. Расходящийся разрыв Уилф и Маккей в 1994 году назвали memory wall.

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

Оговорка про числа. Все таблицы «latency numbers every programmer should know» восходят к списку Джеффа Дина примерно 2010 года. Как карта порядков величин он жив, но конкретные значения устарели неравномерно: L1 почти не изменилась, DRAM подешевела мало, а SSD, сеть и сжатие ускорились в разы. Есть интерактивная версия Колина Скотта с ползунком по годам — она полезна именно тем, что показывает, какие строки стареют быстро. Правильное использование любой такой таблицы: понять, что дороже чего и во сколько раз, а потом измерить своё железо.

lscpu -C                                                        # уровни, размеры, ассоциативность
getconf -a | grep -i cache                                      # LEVEL1_DCACHE_LINESIZE и друзья
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size

NAME ONE-SIZE ALL-SIZE WAYS TYPE        LEVEL SETS PHY-LINE COHERENCY-SIZE
L1d       32K     384K    8 Data            1   64        1             64
L1i       32K     384K    8 Instruction     1   64        1             64
L2       512K       6M    8 Unified         2 1024        1             64
L3        16M      32M   16 Unified         3 16384       1             64

Не выучивайте эти числа — узнайте их для машины, где реально работает ваш код. У прод-сервера, ноутбука и CI-раннера L3 различается в разы, и рабочий набор, который на ноутбуке помещается, в проде — нет.

2. Кэш-линия: минимальная единица обмена

Процессор никогда не читает один байт. Он читает кэш-линию — 64 байта на x86-64 и большинстве ARMv8 (у Apple Silicon 128, у IBM z — 256). Это ключ ко всему остальному: прочитали один int32 — заплатили за 64 байта трафика, и если остальные 60 не понадобятся, 94% работы шины впустую. Прочитали 16 подряд идущих int32 — заплатили за те же 64 байта, стоимость на элемент упала в 16 раз. Записали один байт — линия целиком сменила состояние, и все ядра, у которых была её копия, свою потеряли.

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

3. Куда именно ложится линия: наборы, пути, конфликты

Искать линию по всему массиву дорого, поэтому адрес жёстко задаёт набор (set), а внутри набора линия может занять любой из N путей (way). Это и есть N-way ассоциативность.

Для L1d 32 KiB, 8 путей, линия 64 B: 512 линий, 64 набора, биты 0–5 — смещение, биты 6–11 — номер набора, остальное — тег. И здесь прячется самая коварная ошибка производительности: адреса, различающиеся на кратное 4096, всегда попадают в один набор. Значит, при шаге по памяти, кратном 4 KiB, вы используете не 32 KiB кэша, а 8 линий = 512 байт. Классика — обход столбца матрицы 4096×4096 из float: шаг равен 16 384 байтам, все 4096 элементов столбца метят в один набор, из восьми путей выживают последние восемь.

Лечится унизительно просто — паддингом строки:

float a[4096][4096];                 // БЫЛО: шаг между элементами столбца ровно 16 KiB

#define STRIDE 4112                  // СТАЛО: 4096 + 16 элементов = +64 байта,
static float a[4096 * STRIDE];       // номер набора «гуляет» при переходе к следующей строке
#define A(i, j) a[(i) * STRIDE + (j)]

Поэтому библиотеки линейной алгебры почти никогда не хранят матрицу с шагом, равным степени двойки: у BLAS есть отдельное понятие leading dimension (lda), которое сознательно делают не равным числу столбцов. Если видели в чужом коде «странное» ld = n + 8 — теперь знаете зачем.

Классификация «3C» введена Марком Хиллом в 1987 году, четвёртую категорию добавили с приходом многоядерности. Она полезна не как теория, а как диагностическое дерево: у каждого типа промаха своё лекарство, и лечить не тот тип — потерянная неделя.

4. Прежде чем чинить — измерить

perf stat -e cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses,dTLB-loads,dTLB-load-misses ./traverse column

    12 415 208 331      cycles                    #    3,987 GHz
     6 730 118 442      instructions              #    0,54  insn per cycle
     2 214 003 190      L1-dcache-loads
     1 892 447 011      L1-dcache-load-misses     #   85,48% of all L1-dcache accesses
     1 810 336 774      LLC-loads
     1 764 998 302      LLC-load-misses           #   97,50% of all LL-cache accesses
     2 213 900 442      dTLB-loads
       268 774 119      dTLB-load-misses          #   12,14% of all dTLB cache accesses

       3,114 682 011 seconds time elapsed

IPC 0,54 — красный флаг: современное ядро способно на 3–4 инструкции за такт, ниже единицы означает, что оно стоит и ждёт, и ждёт почти всегда память. 85% промахов L1 при последовательной работе невозможны, значит, доступ не последовательный. 97,5% промахов LLC — данные не помещаются никуда, каждый доступ идёт в DRAM. 12% промахов dTLB — отдельный диагноз, про него раздел 8.

# Где именно в коде промахи: сэмплирование с адресом источника (Intel PEBS / AMD IBS)
perf mem record -- ./traverse column && perf mem report --sort=mem,symbol

# Разложение простоя по причинам: Frontend / Backend / Memory Bound
perf stat --topdown -a -- ./app          # или мощнее: toplev.py -l3 --no-desc ./app

# Симуляция кэша: в 20–100 раз медленнее, зато детерминированно и без шума — годится для CI
valgrind --tool=cachegrind --cache-sim=yes ./traverse column && cg_annotate cachegrind.out.*

# Разделяемые между ядрами линии (false sharing)
perf c2c record -- ./app && perf c2c report --stdio

Методика Top-down Ахмада Ясина (описание Intel) разбивает каждый слот выдачи микроопераций на четыре корзины и позволяет отличить «упёрлись в память» от «упёрлись в неверно предсказанные ветвления». Без неё вы перебираете полдюжины гипотез наугад. В управляемых рантаймах счётчики железа доступны хуже, но perf stat на весь процесс работает всегда — он не знает про рантайм и считает честно; сверху добавляются JOL для раскладки объектов в JVM, dotnet-counters в .NET и профиль аллокаций Go (https://courses.digitable.life/post/performance/04-memory/).

Не делайте целью метрику «cache miss rate». Она обманчива: 5% промахов на зависимой цепочке загрузок хуже, чем 40% промахов в потоке, который процессор успевает предвыбирать. Порядок такой: сначала время, потом IPC, потом причина простоя, и только потом абсолютное число промахов.

5. Эксперимент первый: два одинаковых по сложности цикла

Оба цикла обходят 16,7 млн элементов, оба Θ(n²), оба делают одинаковое число сложений.

#define N 4096
static float *a;                       // N*N float32 = 64 МиБ, заведомо больше любого L3

double sum_rows(void) {                // соседние итерации трогают соседние адреса
    double s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s += a[(size_t)i * N + j];         // шаг 4 байта
    return s;
}

double sum_cols(void) {                // соседние итерации трогают адреса через 16 КиБ
    double s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            s += a[(size_t)i * N + j];         // шаг 16384 байта
    return s;
}

Разница — порядок двух строк; компилятор выполнит ровно столько же сложений и загрузок. Замер с gcc -O2 (без -O3, чтобы компилятор не переставил циклы сам):

12,9 раза на одинаковой асимптотике, и время раскладывается по четырём причинам:

1. Каждая итерация sum_cols требует новую линию → 16,7 млн × 64 байта = 1,07 ГБ трафика вместо 64 МБ: шина отдала в 16 раз больше байт, пригодилась 1/16.
2. Шаг 16 КиБ кратен 4096 → весь столбец бьётся в один набор → вытесняются даже те линии, что дожили бы до следующего столбца.
3. Шаг больше страницы в 4 КиБ → каждое обращение к новой странице → dTLB thrashing.
4. Адрес предсказуем, но у аппаратной предвыборки лимит на число потоков и она обычно не пересекает границу страницы — на 16 КиБ она пасует.

Проверяйте эти гипотезы измерением, а не верой: включите huge pages (раздел 8) — время sum_cols упадёт процентов на двадцать, это вклад пункта 3; добавьте паддинг строки — упадёт ещё, это пункт 2. Так и выглядит отладка производительности: гипотеза → изменение → замер → вычитание.

В Python эффект тот же, хотя маскируется рантаймом:

import numpy as np
a = np.ones((4096, 4096), dtype=np.float32)   # C-порядок: строки лежат подряд

a.sum(axis=1)      # обход подряд
a.sum(axis=0)      # обход с шагом 16 КиБ — те же элементы, кратно дольше

print(a.flags['C_CONTIGUOUS'], a.T.flags['C_CONTIGUOUS'])   # True False

Транспонирование в numpy бесплатно: оно меняет только strides, не двигая байты. Поэтому a.T выглядит обычным массивом, но обходится с плохой локальностью, и следующая операция внезапно медленнее в разы. Если транспонированный массив читается многократно, np.ascontiguousarray(a.T) один раз заплатит за копирование и вернёт это с процентами.

6. Эксперимент второй: массив против связного списка

Задача: просуммировать 10 млн 64-битных чисел. Три структуры, все обходятся за Θ(n).

86 раз между первой и третьей строкой. Причина не в «указатели медленные», а в зависимости по данным: чтобы узнать адрес следующего узла, надо дождаться загрузки текущего. Это pointer chasing, и он уничтожает главное оружие внеочередного ядра — параллелизм по памяти. Ядро умеет держать 10–16 промахов в полёте одновременно, и при обходе массива так и делает, пряча латентность. При обходе перемешанного списка в полёте всегда ровно один промах, и каждые 78 нс складываются последовательно.

Практические выводы заметно расходятся с учебником по структурам данных (https://courses.digitable.life/post/data-structures/03-linked-lists/ даёт классическую картину, здесь — поправка на железо):

• «Вставка в список за O(1)» верна, но дойти до места вставки — самая дорогая операция из существующих. std::vector со сдвигом обгоняет std::list вплоть до десятков тысяч элементов, потому что memmove идёт на полной скорости шины.
• Дерево с указателями на маленькие узлы почти всегда проигрывает B-дереву с узлами в 1–4 кэш-линии, даже при большей высоте. Поэтому индексы в СУБД — B-деревья, а не красно-чёрные (https://courses.digitable.life/post/performance/08-database-performance/).
• Хеш-таблица с открытой адресацией быстрее таблицы с цепочками не из-за меньшего числа операций, а потому что коллизии разрешаются внутри той же линии.
• list из объектов int в Python — массив указателей на разбросанные по куче объекты, то есть pointer chasing по построению. Разрыв с numpy — не только «интерпретатор медленный».

7. Предвыборка: единственный бесплатный обед

Аппаратный префетчер следит за потоком адресов и подтягивает линии заранее. Он умеет последовательный поток вперёд и назад, постоянный шаг (a[i], a[i+8], a[i+16]), держит 8–32 таких потока одновременно и обычно не пересекает границу страницы, потому что не знает физического адреса следующей. Он не умеет угадывать указатели, следовать по индексам b[a[i]] и работать с шагом больше страницы. Это исчерпывающе объясняет обе таблицы выше.

// Программная предвыборка помогает ровно там, где аппаратная слепа — при обходе по индексам.
for (size_t i = 0; i < n; i++) {
    __builtin_prefetch(&values[index[i + 16]], 0, 0);   // 0 = чтение, 0 = нет временной локальности
    sum += values[index[i]];
}

Это инструмент последней очереди: расстояние подсказки подбирается экспериментально (близко — не успело, далеко — вытеснили до использования), инструкция занимает слот выдачи, а на другом процессоре оптимум другой. Сначала измените раскладку, чтобы префетчер заработал сам, и только если это невозможно — подсказывайте руками. В правильно уложенных данных выигрыш от __builtin_prefetch обычно нулевой или отрицательный.

Отдельный приём — запись мимо кэша (non-temporal stores, _mm256_stream_si256) для данных, которые вы пишете и больше не читаете: она избавляет от RFO-чтения линии перед записью и не вымывает кэш. Нужна в копировании больших буферов и кодеках, в прикладном коде почти никогда.

8. Локальность по страницам: TLB, huge pages, NUMA

Кэш линий — не единственный кэш на пути. Виртуальный адрес надо перевести в физический, а таблица страниц живёт в памяти; перевод ускоряет TLB — кэш трансляций на несколько сотен–тысяч записей. При странице 4 КиБ типичный dTLB (64 записи L1 + 1536–3072 L2) покрывает 6–12 МиБ. Рабочий набор в 4 ГБ он покрыть не может в принципе: каждый «далёкий» доступ добавляет обход таблиц на 4 уровня, то есть до четырёх дополнительных обращений к памяти. Лечение — huge pages: одна запись TLB покрывает 2 МиБ вместо 4 КиБ, охват растёт в 512 раз.

cat /sys/kernel/mm/transparent_hugepage/enabled     # [always] madvise never; madvise — разумный дефолт
grep -i AnonHugePages /proc/self/smaps_rollup       # сколько реально получили
# из кода: madvise(ptr, len, MADV_HUGEPAGE); статически: vm.nr_hugepages + mmap(MAP_HUGETLB)

perf stat -e dTLB-load-misses,cycles ./app          # эффект проверяется счётчиком, а не ощущением

Оговорки, которые обычно узнают дорогой ценой: режим always даёт задержки от дефрагментации (khugepaged) и раздувание RSS, поэтому Redis, MongoDB и многие JVM-нагрузки официально советуют его выключать; выигрыш заметен на больших разбросанных наборах (БД, аналитика, графы) и почти незаметен на потоковой обработке. Механику страниц целиком разбирает https://courses.digitable.life/post/operating-systems/04-memory-management/.

К той же семье относится NUMA-локальность: на двухсокетном сервере доступ к памяти чужого узла дороже в полтора-два раза. Смотрится через numactl --hardware и numastat -p PID, лечится привязкой (numactl --cpunodebind=0 --membind=0) и правилом first-touch: страница физически размещается на узле того потока, который первым в неё записал, — значит, инициализировать массив должен тот же поток, который потом будет с ним работать.

9. Раскладка данных: где выигрыш обычно самый большой

Рычаг 1: порядок полей. Компилятор обязан выравнивать поля, а переставлять их (C, C++, Go, Rust с repr(C)) не имеет права. Дырки выравнивания — чистый убыток.

// 24 байта: bool(1) + дырка(7) + float64(8) + int32(4) + хвостовая дырка(4)
type BadPoint struct {
    Alive  bool
    Weight float64
    ID     int32
}

// 16 байт: та же семантика, поля упорядочены от больших к меньшим
type GoodPoint struct {
    Weight float64
    ID     int32
    Alive  bool
}
// Проверять инструментом, а не глазами: go vet -vettool=$(which fieldalignment) ./...

На 10 млн элементов это 80 МБ разницы в трафике при полном обходе. Аналоги проверок: fieldalignment в Go, -Wpadded в clang, JOL в Java, Marshal.SizeOf в .NET (где CLR по умолчанию переставляет поля сама — одна из редких сред, в которых рантайм умнее вас).

Рычаг 2: hot/cold splitting. Если горячий цикл читает два поля из двадцати, вынесите остальные восемнадцать в отдельный объект по указателю.

// Было: 128 байт на запись, из которых цикл поиска трогает 8
struct Order { uint64_t id; double price; char customer[64]; char notes[48]; };

// Стало: горячая часть 16 байт — 4 записи в линию вместо половины записи
struct OrderHot  { uint64_t id; double price; struct OrderCold *cold; };
struct OrderCold { char customer[64]; char notes[48]; };

Рычаг 3: AoS → SoA. Массив структур заменяется структурой массивов. Самое дорогое изменение (ломает API, ухудшает читаемость) и самое результативное для аналитики и симуляций. На нём стоят колоночные СУБД (ClickHouse, DuckDB, Parquet), векторные движки и Apache Arrow: если запрос читает две колонки из ста, колоночное хранение читает 2% данных, а строчное — все 100%.

// AoS: 32 байта на частицу, цикл по X использует 12,5% принесённого
struct Particle { public float X, Y, Z, VX, VY, VZ; public uint Id, Flags; }

// SoA: каждое поле — свой непрерывный массив, и JIT векторизует проход через SIMD
sealed class ParticleSoA {
    public float[] X = [], VX = [];
    public void Advance(float dt) {
        var x = X.AsSpan(); var vx = VX.AsSpan();
        for (int i = 0; i < x.Length; i++) x[i] += vx[i] * dt;
    }
}

Первоисточники: доклад Майка Актона «Data-Oriented Design and C++» (CppCon 2014), книга Ричарда Фабиана «Data-Oriented Design» и доклад Чандлера Каррута «Efficiency with Algorithms, Performance with Data Structures» о том, почему алгоритм даёт эффективность, а структура данных — производительность.

10. Тайлинг: когда лечится алгоритмом, а не раскладкой

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

BLOCKED-MATMUL(A, B, C, n, T):
    для ii от 0 до n шагом T:
        для kk от 0 до n шагом T:
            для jj от 0 до n шагом T:          # три подматрицы T×T должны влезать в L1/L2
                для i от ii до min(ii+T, n):
                    для k от kk до min(kk+T, n):
                        r = A[i][k]            # инвариант внутреннего цикла
                        для j от jj до min(jj+T, n):
                            C[i][j] = C[i][j] + r * B[k][j]

// Порядок ikj + блокирование. T подбирается замером; стартовая оценка —
// 3*T*T*sizeof(elem) не больше размера L1d или L2.
void matmul_tiled(const double *A, const double *B, double *C, int n, int T) {
  for (int ii = 0; ii < n; ii += T)
    for (int kk = 0; kk < n; kk += T)
      for (int jj = 0; jj < n; jj += T) {
        int iM = ii + T < n ? ii + T : n, kM = kk + T < n ? kk + T : n, jM = jj + T < n ? jj + T : n;
        for (int i = ii; i < iM; i++)
          for (int k = kk; k < kM; k++) {
            double r = A[(size_t)i * n + k];              // читается раз на строку блока
            for (int j = jj; j < jM; j++)                 // подряд и по B, и по C → векторизуется
              C[(size_t)i * n + j] += r * B[(size_t)k * n + j];
          }
      }
}

Сложность. По времени все варианты Θ(n³), по памяти Θ(n²) — тайлинг не меняет ни того, ни другого. Меняется число промахов (модель внешней памяти: B — элементов в линии, M — ёмкость кэша):

Нижняя граница Θ(n³/(B·√M)) доказана Хонгом и Кунгом в 1981 году: блочное умножение асимптотически оптимально по обмену с памятью. Для n = 1024 и double это выражается в наивный ijk ~1,2 с, ikj ~0,34 с, блочный с T = 64 ~0,22 с — и всё ещё в 5–10 раз медленнее OpenBLAS, который поверх тайлинга делает упаковку панелей, микроядра на AVX-512 и явную предвыборку. Числа иллюстрируют форму эффекта; ваши будут другими.

Есть вариант без подбора T — cache-oblivious алгоритмы (Фриго, Лейзерсон, Прокоп, Рамачандран, FOCS 1999): рекурсивно делить задачу пополам, пока подзадача не станет меньше любого кэша. Оптимально сразу для всех уровней иерархии и без единой константы про железо. Модель внешней памяти подробно разобрана в https://courses.digitable.life/post/algorithms/17-streaming-and-external-memory/.

11. Соседние эффекты, которые выглядят как «кэш»

Кэш инструкций. L1i так же конечен (обычно 32 КиБ). Раздутый горячий путь, агрессивный инлайнинг, мегаморфные вызовы, интерпретаторы с гигантским switch дают промахи по инструкциям, которые в профиле выглядят как «время размазано ровным слоем». Диагностика — perf stat -e L1-icache-load-misses,iTLB-load-misses; лечение — PGO и посткомпоновочная переупаковка кода: BOLT даёт на серверных бинарях 5–15% только тем, что кладёт горячие базовые блоки рядом.

Предсказание ветвлений. Знаменитый вопрос «Why is processing a sorted array faster than processing an unsorted array?» — ускорение примерно в 6 раз без единого изменения в коде, только от порядка данных. Штраф за неверное предсказание — 15–20 тактов на сброс конвейера; лечится сортировкой данных и превращением ветки в арифметику без ветвлений.

Когерентность. Линия существует в нескольких кэшах одновременно, состояние поддерживает протокол MESI (и варианты MOESI, MESIF):

Отсюда false sharing: два потока пишут в разные переменные, случайно попавшие в одну 64-байтную линию. Логически конфликта нет, физически линия мечется между ядрами, и каждая запись стоит 40–100 тактов вместо одного. Диагностируется perf c2c, лечится выравниванием (alignas(64) в C++, поле-заполнитель [64]byte в Go, PaddedReference в .NET). Подробный разбор — в https://courses.digitable.life/post/performance/07-concurrency-performance/.

12. Как бенчмарки локальности врут

Здесь микробенчмарк ошибается не на проценты, а в противоположную сторону.

• Рабочий набор помещается в L1/L2. Прогнали цикл по массиву из 1000 элементов и не увидели разницы между AoS и SoA — конечно, 32 КБ целиком лежат в L1. В проде тот же код ходит по 4 ГБ, и разница оказывается пятикратной. Всегда варьируйте размер входа по логарифмической шкале и стройте график «время на элемент от размера рабочего набора»: ступеньки на нём — это и есть границы ваших L1, L2, L3 (метод из «Gallery of Processor Cache Effects»).
• Слишком тёплый кэш. Бенчмарк зовёт вашу функцию в цикле, её данные всегда в L1. В проде между двумя вызовами работает вся остальная программа и вымывает кэш начисто. Приём: между итерациями прогонять «загрязнитель» — проход по буферу размером с L3.
• Слишком холодный кэш. Обратная ошибка: первая итерация тянет данные с диска через page cache, и вы измерили ввод-вывод вместо вычислений. Разогрев обязателен и должен быть явным (https://courses.digitable.life/post/performance/02-benchmarking/).
• Выравнивание и ASLR. Mytkowicz и соавторы «Producing Wrong Data Without Doing Anything Obviously Wrong!» (ASPLOS 2009) показали: смена размера переменной окружения или порядка линковки меняет производительность на проценты и легко перебивает эффект «оптимизации» — ровно потому, что сдвиг адресов меняет попадания в наборы. Отсюда setarch -R на стенде и требование нескольких независимых процессов.
• Соседи по LLC. L3 общий на сокет. Ваш бенчмарк на пустой машине показал одно, в проде рядом живут ещё пять контейнеров, вымывающих общий кэш. Это не шум, а систематическое смещение; на серверах с Intel RDT его можно измерить и даже ограничить.
• Ошибка выжившего. Промахи кэша не имеют собственного кадра стека: время утекает в обычные загрузки внутри обычных функций и размазывается по всему профилю. Поэтому «плоский профиль без явного горячего места плюс низкий IPC» — это диагноз «memory bound», а не «оптимизировать нечего».
• Симуляция вместо железа. cachegrind даёт стабильные цифры, но моделирует упрощённый кэш без предвыборки и внеочередного исполнения: отлично ловит регрессии, но абсолютным числам верить нельзя.

13. Рабочий процесс: от симптома к исправлению

1. Убедиться, что вы memory bound. IPC ниже 1,0 при высоком проценте промахов LLC, либо Top-down показывает Backend Bound → Memory Bound. Без этого шага всё остальное — гадание.
2. Найти виноватые данные. perf mem report или cachegrind с cg_annotate дают привязку к строке исходника и структуре, а не только к функции.
3. Классифицировать промах. Набор больше кэша → тайлинг, сжатие, hot/cold. Шаг — степень двойки → паддинг. Много ядер пишут рядом → выравнивание. Первое касание → укрупнение и предвыборка.
4. Сделать ровно одно изменение и перемерить. Не два: эффекты локальности нелинейны и охотно компенсируют друг друга, скрывая, что именно сработало.
5. Проверить на прод-размере данных. Изменение, дающее +30% на 1 ГБ, может давать 0% на 10 МБ и −5% на 100 ГБ.
6. Зафиксировать регрессионный тест. Время слишком шумное для CI; счётчик промахов или инструкций стабильнее (https://courses.digitable.life/post/performance/12-optimization-workflow/).

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

• Оптимизировать локальность до профилирования. Если 80% времени уходит в JSON-парсер или ожидание сети, идеальная раскладка структур не изменит ничего.
• Считать промахи целью. Ноль промахов у программы, делающей вдвое больше работы, — проигрыш. Метрика служит времени, а не наоборот.
• Переносить чужие константы. «Линия 64 байта» неверно на Apple Silicon, «L3 32 МБ» неверно на вашем ноутбуке, «huge pages всегда помогают» неверно для Redis.
• Заменять всё на SoA. SoA проигрывает, когда цикл читает большинство полей записи: вместо одной линии вы тянете восемь. AoS против SoA — вопрос профиля доступа, а не моды.
• Забывать про запись. Запись в невладеемую линию вызывает RFO — чтение линии перед изменением. Цикл, который только пишет большой массив, генерирует вдвое больше трафика, чем кажется.
• Микрооптимизировать там, где решает алгоритм. Хеш-таблица вместо линейного поиска даст 1000 раз, а лучшая раскладка линейного поиска — 3 раза. Локальность — множитель к правильному алгоритму, а не замена ему (https://courses.digitable.life/post/algorithms/18-practical-optimization/).

Мини-итог

• Асимптотика считает обращения к памяти одинаковыми, железо — различающимися в 80 раз. Отсюда весь разрыв между «одинаковой сложностью» и десятикратной разницей во времени.
• Единица обмена — кэш-линия в 64 байта. Всё, что вы можете сделать, сводится к вопросу: сколько байт из принесённых 64 реально пригодилось.
• Адрес жёстко задаёт набор. Шаг, кратный 4096, превращает 32 KiB кэша в 512 байт — самая частая «необъяснимая» просадка на матрицах и буферах со степенью двойки.
• Pointer chasing хуже большого рабочего набора: он убивает параллелизм по памяти, и латентности складываются вместо того, чтобы перекрываться.
• Диагностика — не догадка: IPC ниже единицы, доля промахов LLC, perf mem, perf c2c, Top-down, cachegrind. У каждого типа промаха своё лекарство.
• Микробенчмарк локальности врёт систематически, потому что его рабочий набор помещается в кэш. Стройте кривую по размеру входа, а не одну точку.
• Числа из любых таблиц задержек — карта порядков, а не константы. Проверяйте своё железо, свои данные, свой рабочий набор.

Источники

• Ulrich Drepper. What Every Programmer Should Know About Memory (2007) — до сих пор лучший подробный текст по теме; числа устарели, механика нет. Исходная серия на LWN.
• John Hennessy, David Patterson. Computer Architecture: A Quantitative Approach, 6th ed. — глава 2 и приложение B про иерархию памяти и классификацию промахов; Wulf, McKee. Hitting the Memory Wall, 1994.
• Denis Bakhvalov. Performance Analysis and Tuning on Modern CPUs — свободная книга, разделы про Memory Bound и Top-down.
• Agner Fog. Optimization manuals и Intel 64 and IA-32 Optimization Reference Manual — латентности и правила предвыборки от первоисточника.
• Brendan Gregg. Systems Performance, 2nd ed.; Igor Ostrovsky. Gallery of Processor Cache Effects — семь коротких экспериментов, каждый стоит прогнать самому.
• Scott Meyers. CPU Caches and Why You Care; Mike Acton. Data-Oriented Design and C++; Richard Fabian. Data-Oriented Design.
• Frigo, Leiserson, Prokop, Ramachandran. Cache-Oblivious Algorithms, FOCS 1999.
• Инструменты: perf-c2c(1), perf-mem(1), Cachegrind, pmu-tools / toplev, Intel MLC, BOLT.
• Смежное на портале: https://courses.digitable.life/post/computer-science/06-memory-hierarchy/ — иерархия памяти с нуля; https://courses.digitable.life/post/operating-systems/04-memory-management/ — страницы, TLB, page fault; https://courses.digitable.life/post/data-structures/01-complexity-and-memory/ — стоимость структур с учётом памяти.

Что дальше

Мы разобрали, что происходит, когда данные уже в оперативной памяти, и почему цена доступа к ним меняется на два порядка в зависимости от порядка обхода. Но самая дорогая строка в таблице задержек — не DRAM, а диск и сеть, где счёт идёт на микросекунды и миллисекунды. Причём главный расход обычно не в самом устройстве, а в том, как программа с ним разговаривает: по одному байту через системный вызов или крупными буферами, блокируя поток или отдавая его планировщику. Следующая статья — про это.

Ввод-вывод: блокирующий и асинхронный, syscalls, буферизация