Что значит "cache-friendly" код и как писать эффективные программы на C++?

Почему обход по строкам быстрее: анатомия кеша процессора

Разница в скорости, которую вы наблюдаете, — классический пример того, как локальность данных влияет на производительность. Чтобы понять это, нужно разобраться, как работает кеш процессора.

Как устроен кеш

Современные процессоры имеют несколько уровней кеша (L1, L2, L3). Кеш — это маленькая, но очень быстрая память, расположенная прямо на кристалле процессора. Когда программа запрашивает данные из оперативной памяти (RAM), процессор:

• Сначала проверяет кеш L1 (самый быстрый, ~1 нс)
• Если данных нет — проверяет L2 (~5 нс)
• Затем L3 (~15 нс)
• И только потом идёт в RAM (~100 нс)

Разница между L1 и RAM — в 100 раз! Поэтому попадание в кеш (cache hit) критически важно.

Кеш-линии: почему процессор загружает данные блоками

Процессор никогда не читает один байт из памяти. Он читает кеш-линии — блоки по 64 байта (типичный размер). Если вы обращаетесь к arr[0][0], процессор загружает в кеш 64 байта, начиная с этого адреса. В случае int (4 байта) это 16 элементов подряд.

Разбор вашего примера

Двумерный массив int arr[N][N] хранится в памяти по строкам (row-major order). То есть сначала идут все элементы первой строки, затем второй и т.д.:

arr[0][0], arr[0][1], ..., arr[0][9999],
arr[1][0], arr[1][1], ..., arr[1][9999],
...

Обход по строкам (быстрый):

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        arr[i][j] = i * j;
    }
}

Здесь мы обращаемся к элементам последовательно: arr[0][0], arr[0][1], arr[0][2]... Когда мы читаем arr[0][0], процессор загружает кеш-линию с элементами 0–15. Следующие 15 обращений будут попадать в кеш (cache hit). Это пространственная локальность — обращение к данным, расположенным рядом в памяти.

Обход по столбцам (медленный):

for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        arr[i][j] = i * j;
    }
}

Здесь мы обращаемся к arr[0][0], затем arr[1][0], arr[2][0]... Каждый раз мы прыгаем на 10000 * 4 = 40000 байт вперёд. Кеш-линия, загруженная для arr[0][0], содержит элементы 0–15 первой строки. Но следующий запрос — arr[1][0] — находится в другой строке, то есть в другой кеш-линии. Процессор вынужден снова идти в RAM. Это вызывает промах кеша (cache miss) на каждой итерации внутреннего цикла.

Результат: 10000 × 10000 = 100 миллионов промахов кеша, каждый из которых в 100 раз медленнее попадания. Отсюда и 8-кратная разница.

Основные принципы cache-friendly кода

• Пространственная локальность: обращайтесь к данным в порядке их хранения в памяти. Для массивов — по строкам.
• Временная локальность: используйте одни и те же данные многократно, пока они в кеше. Например, если вы обрабатываете элемент несколько раз, делайте это сразу, а не через 1000 итераций.
• Структуры данных с учётом кеша: вместо массива указателей на объекты (разбросанных по памяти) используйте std::vector или std::array — они хранят данные последовательно.
• Размер рабочих наборов: старайтесь, чтобы данные, к которым вы часто обращаетесь, помещались в кеш L1 (32 КБ) или L2 (256 КБ).
• Избегайте случайного доступа: хеш-таблицы и связные списки (std::list) часто приводят к промахам кеша.

Как проверить эффективность использования кеша

Используйте профайлеры:

• Valgrind с Cachegrind: valgrind --tool=cachegrind ./program — покажет количество промахов L1, L2, L3.
• perf (Linux): perf stat -e cache-misses,cache-references ./program
• Visual Studio Profiler (Windows): встроенные инструменты с метриками кеша.

Пример вывода perf для вашего медленного варианта:

Performance counter stats for './slow':
    1,234,567,890      cache-references
    987,654,321        cache-misses      # 80% промахов!

Для быстрого варианта промахов будет менее 1%.

Практический совет

Если вам нужно транспонировать матрицу или обрабатывать её по столбцам, измените структуру данных: храните массив как std::vector<std::vector<int>> по столбцам или используйте библиотеки вроде Eigen, которые автоматически оптимизируют доступ.

Запомните: кеш — это не абстракция, а физическая реальность. Игнорирование его принципов может сделать вашу программу в 10–100 раз медленнее, даже если алгоритмическая сложность одинакова.

const int BLOCK = 64; // размер блока, помещается в кеш
for (int i = 0; i < N; i += BLOCK) {
    for (int j = 0; j < N; j += BLOCK) {
        for (int k = 0; k < N; k += BLOCK) {
            // Обработка блока [i:i+BLOCK][j:j+BLOCK]
            for (int ii = i; ii < i + BL