Row-major и column-major это две схемы линеаризации многомерного массива: способ уложить строки и столбцы в одну непрерывную последовательность адресов. Схема задаёт формулу вычисления адреса элемента, а значит и то, как быстро процессор достаёт соседние данные из кэша.
Короткий ответ на главный вопрос: обходить массив нужно в том порядке, в котором он лежит в памяти. Для row-major внешний цикл идёт по строкам, внутренний по столбцам; для column-major наоборот. Если порядок перепутать, каждый следующий элемент окажется в другой кэш-линии, и на больших матрицах время работы вырастает в несколько раз.
Ниже: точные определения, формулы адреса с числовыми примерами, разбор кэш-линии, таблица соответствия layout для C, Fortran, NumPy и BLAS, приёмы переписывания циклов и список ошибок, которые чаще всего портят производительность.
Что такое row-major и column-major: базовые определения
Линеаризация превращает многомерный индекс в одно число: смещение от начала массива. Обе схемы делают это одинаково просто, разница в том, какой индекс меняется быстрее всего при переходе к следующему адресу.
Построчное хранение (row-major)
В row-major подряд идут все элементы первой строки, затем второй и так далее. Быстрее всего меняется последний индекс. Матрица 2x3 укладывается в память так: A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2].
Схему называют C order, потому что именно так устроены массивы в C. Её используют C++, Java, Go, а также Python со списками списков. NumPy по умолчанию тоже создаёт массивы в этом порядке.
Постолбцовое хранение (column-major)
В column-major подряд лежат элементы первого столбца, затем второго. Быстрее всего меняется первый индекс. Та же матрица 2x3: A[0][0], A[1][0], A[0][1], A[1][1], A[0][2], A[1][2].
Схему называют Fortran order или F order. Она принята в Fortran, MATLAB, Julia, R, а также в классических библиотеках BLAS и LAPACK, которые выросли из Fortran-кода.
| Позиция в памяти | row-major, матрица 2x3 | column-major, матрица 2x3 |
|---|---|---|
| 1 | A[0][0] | A[0][0] |
| 2 | A[0][1] | A[1][0] |
| 3 | A[0][2] | A[0][1] |
| 4 | A[1][0] | A[1][1] |
| 5 | A[1][1] | A[0][2] |
| 6 | A[1][2] | A[1][2] |
Совпадают только первый и последний элементы. Всё, что между ними, лежит по-разному, и это определяет поведение циклов обработки.
Вычисление адреса элемента массива при разных layout
Формула адреса зависит от схемы и размеров массива. Ниже i это номер строки, j номер столбца, M число строк, N число столбцов, base адрес первого элемента, sizeof(T) размер одного элемента в байтах.
Формула для row-major
Для двумерного массива offset = i * N + j, адрес = base + (i * N + j) * sizeof(T). Для трёхмерного массива с размерами M x N x K: offset = i * N * K + j * K + k, где быстрее всего меняется k.
Числовой пример. Массив 3x4, нужен элемент [2][1]. Смещение равно 2 * 4 + 1 = 9. При base = 1000 и размере элемента 4 байта адрес = 1000 + 9 * 4 = 1036.
Формула для column-major
Для двумерного массива offset = j * M + i, адрес = base + (j * M + i) * sizeof(T). Для трёхмерного: offset = k * M * N + j * M + i, где быстрее всего меняется i.
Тот же элемент [2][1] в матрице 3x4, но в column-major: смещение равно 1 * 3 + 2 = 5. Адрес при тех же условиях: 1000 + 5 * 4 = 1020.
Логический элемент один и тот же, физические байты по этим адресам разные. Отсюда следствие: перепутанный layout даёт два эффекта сразу, медленный код и неверный числовой результат, если массив передают между библиотеками без преобразования.
Общее правило: offset равен сумме произведений каждого индекса на произведение длин всех более медленных измерений. В row-major более медленным считается первое измерение и все последующие за текущим, в column-major наоборот.
Когда массив живёт не в оперативной памяти, а в таблице базы данных, порядок укладки задают другие механизмы. Как выбирать между отдельной таблицей и массивом в колонке, разобрано в материале про нормализацию и денормализацию при хранении массивов, и там же есть чек-лист для выбора схемы на этапе проектирования.
Как порядок обхода влияет на кэш и производительность
Процессор не читает память по одному байту, обмен идёт кэш-линиями. Это главная связка между layout и реальной скоростью циклов. Все уровни кэша, от регистров и L1 до распределённых кешей приложений, описаны в полном руководстве по кешированию для DevOps и системных администраторов; здесь нас интересует ближайший к процессору уровень.
Кэш-линия и локальность
Кэш-линия это минимальный блок данных, который перемещается между оперативной памятью и кэшем. На большинстве современных x86- и ARM-процессоров её размер 64 байта. Одна линия вмещает 16 значений int32 или 8 значений double, поэтому последовательное чтение почти всегда использует загруженный блок целиком.
Когда код обращается к A[i][j], в кэш попадает вся линия, то есть соседние по адресу элементы. Если следующие итерации цикла берут именно их, промахов почти нет. Это пространственная локальность. Временная локальность означает повторное обращение к тем же данным: например, накопление суммы по столбцу в регистре, без повторного чтения памяти.
Пример: обход row-major массива по столбцам
Матрица объявлена как A[M][N] в C и лежит построчно. Цикл, где внешний счётчик идёт по столбцам, а внутренний по строкам, обращается к A[0][j], A[1][j], A[2][j] и далее. Каждый следующий элемент отстоит на N * sizeof(T) байт, то есть попадает в другую кэш-линию.
Для матрицы 10000x10000 типа double это около 800 МБ данных, длина строки 80 000 байт. Один блок кэша не переиспользуется между итерациями внутреннего цикла, и почти каждое обращение приводит к промаху: процессор ждёт память. При обходе по строкам те же данные читаются последовательно, и на 64-байтовую линию приходятся 8 полезных элементов.
Практический ориентир: на больших матрицах разница между двумя порядками обхода достигает 5-10 раз, на умножении матриц бывает больше. Точная цифра зависит от процессора, размера массива и от того, распознаёт ли аппаратный префекчер шаг по адресу.
Префекчер частично компенсирует и обратный порядок, но число отслеживаемых потоков доступа у него ограничено. Как только шагов или рабочих массивов становится больше, чем помещается в буфер предвыборки, подсказки перестают помогать и промахи возвращаются.
Соответствие layout в C, Fortran, NumPy и BLAS
Быстрый способ определить схему: посмотрите, какой индекс в объявлении меняется быстрее всего, и какой порядок циклов даёт последовательный доступ. Ниже сводка по четырём инструментам.
| Инструмент | Схема по умолчанию | Как изменить или проверить |
|---|---|---|
| C, C++ | row-major | не меняется, порядок задан объявлением |
| Fortran | column-major | не меняется, первый индекс быстрее всего |
| NumPy | row-major (C order) | order='F', np.asfortranarray, flags, strides |
| BLAS, LAPACK | column-major | CBLAS: CblasRowMajor, параметр LDA |
C и C++: row-major по умолчанию
Стандарт C задаёт многомерный массив как массив массивов. В объявлении int A[3][4] элементы идут строками: сначала A[0][0..3], затем A[1][0..3]. Выражение A[i] даёт указатель на начало строки, а A[i][j] разыменовывает смещение i * 4 + j.
При работе с указателями это нужно помнить. Если int *p = &A[0][0], элемент A[i][j] доступен как p[i * 4 + j]. Ошибка в множителе приводит к молчаливому чтению чужой памяти вместо ожидаемого значения.
Fortran: column-major по умолчанию
Fortran хранит массивы постолбцово и по умолчанию нумерует элементы с единицы. Объявление REAL A(3,4) означает, что A(1,1), A(2,1), A(3,1) лежат подряд, а быстрее всего меняется первый индекс. Внутренний цикл в Fortran пишут по первому индексу, иначе скорость падает так же, как в примере с матрицей выше.
При вызове Fortran-подпрограмм из C массив передают как указатель на первый элемент плюс размерности. Если C-код считает данные построчными, расчёт даст неверный ответ без единого сообщения об ошибке.
NumPy: row-major по умолчанию, но можно изменить
NumPy создаёт массивы в C order. Проверить это можно через атрибут flags: C_CONTIGUOUS говорит о row-major, F_CONTIGUOUS о column-major. Реальные шаги по осям лежат в strides, и именно они показывают порядок в памяти, а не логическую форму массива.
Создать массив в F order: np.zeros((3, 4), order='F') или np.asfortranarray(a). Преобразование копирует данные, для больших массивов это заметная по времени операция. Транспонирование через a.T данные не копирует, оно меняет strides, и массив может стать некотiguous по обеим осям, что замедляет последующие циклы. Вызов np.ascontiguousarray возвращает обычную построчную укладку.
BLAS и LAPACK: ожидание column-major
Классический интерфейс BLAS написан на Fortran и ожидает column-major. Отсюда параметр LDA, leading dimension: расстояние между соседними столбцами, выраженное в элементах, а не в байтах.
Сигнатура dgemm выглядит как C = alpha * op(A) * op(B) + beta * C, где op выбирается флагами TRANSA и TRANSB. Если передать row-major массив без преобразования, библиотека прочитает транспонированную матрицу. Варианты решения: транспонировать данные перед вызовом, использовать C-интерфейс CBLAS с флагом CblasRowMajor (его поддерживают OpenBLAS и Intel MKL) или взять обёртку, которая сама подставляет корректные параметры.
Смешение layout в BLAS даёт ошибку и по скорости, и по результату: неверные значения появляются молча, а отладка уходит в проверку формул вместо проверки раскладки данных.
Как переписать цикл под нужный layout: практические приёмы
Базовое правило одно: самый внутренний цикл должен идти по тому индексу, который меняется в памяти быстрее всего. Дальше речь о случаях, когда одной перестановки мало.
Перестановка циклов (loop interchange)
Для row-major матрицы схема с внешним циклом по i и внутренним по j даёт последовательный доступ к A[i][j]. Схема с внешним циклом по j идёт по памяти с шагом N. Перестановка циклов меняет шаблон доступа и не меняет результат, если тело цикла не зависит от порядка обхода.
Менять порядок можно не всегда: если в теле есть накопление с зависимостью по i или счётчик изменяется внутри, перестановка сломает логику. Компиляторы умеют делать это сами, GCC включает -floop-interchange при сборке с поддержкой Graphite, но анализ зависимостей не всесилен. Проверять результат после такой сборки всё равно нужно.
Блочная обработка (tiling/blocking)
Когда массив не помещается в кэш, помогает разбиение на блоки, которые в него влезают. Вместо обхода всей матрицы код идёт по блокам 64x64, обрабатывая каждый двумя вложенными циклами по строкам и столбцам.
Блок 64x64 типа double занимает 32 КБ. Это близко к типичному размеру L1 и уверенно помещается в L2, поэтому загруженный блок переиспользуется многократно, а число обращений к памяти падает. Умножение матриц получает от такой схемы больше всего. Размер блока подбирают под конкретный процессор: 32, 64 или 128 элементов, ориентируясь на замеры, а не на теорию.
Родственные приёмы: loop fusion объединяет два прохода по массиву в один, loop fission делит слишком большой цикл, чтобы промежуточные данные оставались в кэше. Техники уровня приложения, например многоуровневое кеширование и стратегии инвалидации, решают другую задачу, но опираются на тот же принцип локальности.
Измерения удобно проводить на отдельной машине, чтобы тестовый прогон не мешал рабочей нагрузке. Для этого подойдёт облачный сервер, например Timeweb Cloud, где ресурсы можно поднять под задачу и вернуть обратно после замеров.
Основной инструмент проверки: perf stat -e cache-misses,cache-references,LLC-load-misses ./program. Отношение промахов к обращениям показывает, насколько цикл дружелюбен к кэшу. Для NumPy хватает замера времени до и после перестановки осей, например через timeit на зафиксированной матрице.
Типичные ошибки и как их избежать
- Смешение layout между C и Fortran. Массив передают как есть, а индексацию читают в другом порядке. Проверка: сверить порядок объявления и параметр leading dimension, написать тест на матрице 2x3 с различимыми значениями элементов.
- Row-major данные, переданные в BLAS как column-major. Результат неверен, предупреждений нет. Транспонируйте матрицу или используйте CblasRowMajor.
- Обход row-major массива по столбцам. Скорость падает в разы, а код выглядит логично и проходит тесты на маленьких данных. Переставьте циклы.
- Игнорирование strides в NumPy. Срезы и транспонирование дают некотiguous массив, и цикл читает память большими шагами. Проверяйте flags и strides перед горячим участком.
- Правка кода без измерений. Кэш бывает не узким местом, если программа упирается в вычисления, в сеть или в дисковый ввод-вывод.
- Опора только на размер кэш-линии без учёта ассоциативности. Массивы с шагом, кратным размеру кэша, конфликтуют за одни и те же наборы, и обычное tiling в этом случае не спасает.
Отдельно проверяйте версии инструментов: набор флагов CBLAS и поведение NumPy по умолчанию могут отличаться между сборками, поэтому тест на корректность стоит держать рядом с тестом на скорость.
Заключение: как применять знания о layout на практике
Чек-лист для рабочего кода: определите layout по документации, по strides или по порядку объявления; проверьте порядок вложенных циклов, внутренний должен идти по быстрому индексу; снимите cache-misses до и после правки; транспонируйте или копируйте данные только при необходимости, помня о цене копии; для больших массивов добавьте блочную обработку.
Понимание порядка укладки даёт предсказуемость. Вы заранее знаете, где возникнут промахи кэша, меняете код осознанно и не перебираете варианты наугад.