Производительность

Row-major vs column-major: порядок доступа и разрыв в 9x

Суть Смена порядка двух циклов на одной матрице даёт разницу в 9x по wall-clock — потому что шаг от строки к столбцу превращает каждый доступ из cache hit в cache miss.

Высота — путь к senior

НольJuniorMiddleSenior

Ты на junior-высоте — поверхность

◷ 12 min

Два цикла matrix-multiply. Тот же алгоритм. Та же матрица 10 000 × 10 000. Одинаковое число сложений и умножений. Один заканчивается за 300 мс. Другой — за 2 800 мс. Единственная разница: порядок двух for-циклов.

Как 2D-массивы лежат в памяти

В C, Java, Rust, Python (NumPy default) и большинстве других языков 2D-массив arr[rows][cols] хранится в row-major порядке: все элементы строки 0 — contiguous, потом вся строка 1, и т.д.

Для матрицы 10 000 × 10 000 из 8-байтных doubles:

arr[0][0], arr[0][1], ..., arr[0][9999],   ← строка 0: байты 0–79999
arr[1][0], arr[1][1], ..., arr[1][9999],   ← строка 1: байты 80000–159999
...

Что происходит внутри каждого порядка цикла

Row-major итерация (for i: for j: arr[i][j]):

Обращается к arr[i][0], arr[i][1], arr[i][2], …
Каждый шаг — 8 байт вперёд в памяти.
Cache line 64 байта (8 doubles). Первый read грузит 8 элементов сразу; следующие 7 — бесплатные L1-хиты.
Prefetcher детектирует sequential pattern и pre-грузит следующую line вперёд.
Стоимость per element: ~1 нс.

Column-major итерация (for j: for i: arr[i][j]):

Обращается к arr[0][j], arr[1][j], arr[2][j], …
Каждый шаг — 10 000 × 8 = 80 000 байт вперёд — далеко за пределы любой загруженной cache line.
Каждый доступ — свежая cache line, не prefetch-нутая.
Стоимость per element: ~70–100 нс (full RAM latency).

Порядок цикла	Шаг в памяти	Поведение cache	Время (10k×10k doubles)
`for i: for j: arr[i][j]`	8 байт (sequential)	7 из 8 accesses — L1 hit	~300 мс
`for j: for i: arr[i][j]`	80 000 байт (random)	Почти каждый доступ — miss	~2 800 мс

Instruction count идентичен. Арифметика идентична. Разница в 9x — полностью из-за cache-miss latency.

Исключение Fortran и языковые конвенции

Fortran хранит массивы в column-major порядке — все элементы столбца 0 сначала, потом столбец 1. NumPy имеет Fortran-order опцию (order='F'). Если твой код или библиотека использует Fortran layout, «очевидно правильный» цикл в C — worst case в Fortran. Всегда проверяй memory layout языка перед оптимизацией inner loops.

Cache-oblivious blocking

Иногда оба порядка необходимы — например, в matrix transposition или некоторых linear algebra routines. Фикс — cache-oblivious blocking (тайлинг): делай матрицу маленькими тайлами (~64 строки × 64 столбца, чтобы каждый тайл влезал в L2), обрабатывай каждый тайл перед переходом к следующему. Внутри тайла доступы по порядку; весь тайл влезает в cache при обработке, и row, и column dimensions видят mostly cache hits.

Почему это работает

Пример 9x использует матрицу 10 000 × 10 000, потому что это гарантирует, что working set намного превышает L3 cache. На маленьких матрицах (100 × 100) вся матрица влезает в L1, и оба порядка быстры. Performance cliff появляется только когда матрица вырастает за cache — это типичный production сценарий для реальных data processing workloads.

Викторина

Матрица 10 000 × 10 000 doubles хранится row-major. Inner loop итерирует по столбцам (arr[i][j], j от 0 до N). Почему это быстро?

Викторина

Команда переключила matrix multiply с row-major на column-major порядок цикла и наблюдает замедление 9x без изменения алгоритма. Корневая причина:

Расставь шаги по порядку

Проследи, что происходит, когда row-major код обращается к arr[i][0] через arr[i][7] (8 consecutive doubles, 64 байта total):

1 CPU запрашивает arr[i][0] (address X)
2 Cache miss: загружает 64-байтную line в X в L1 (стоит ~100 нс один раз)
3 arr[i][0] через arr[i][7] — все в загруженной line
4 Доступы к arr[i][1] через arr[i][7] каждый hit L1 (~1 цикл каждый)
5 Prefetcher срабатывает и грузит следующую 64-байтную line до того, как она нужна
6 arr[i][8] через arr[i][15] приходят с нулевым ожиданием

Вспомните перед уходом

01
Почему row-major matrix iteration в 9 раз быстрее column-major на матрице 10 000×10 000, когда обе выполняют то же число element accesses?
02
Что такое cache-oblivious blocking и когда его использовать?

Итог

В row-major языке (C, Java, Rust, Python/NumPy) элементы одной строки занимают consecutive addresses. 64-байтная cache line держит 8 doubles; sequential (row-major) итерация читает 8 элементов per cache miss. Column-major итерация на том же массиве шагает на 80 000 байт per element на 10 000-column матрице, попадая в свежую cache line каждый раз и платя full RAM latency на каждой load. Результат — разница 9x по wall-clock без изменения алгоритма. Всегда знай memory layout языка и выравнивай порядок циклов под него; используй cache-oblivious blocking, когда оба направления доступа неизбежны.

Связанные уроки

опирается на

Иерархия памяти: почему расстояние важнее числа операцийjunior

углубляется в

встречается в159

Продолжить восхождение ↑Cache lines и false sharing: когда параллелизм замедляет код