Почему мой код на C++ сильно замедляется при размере массива 8192?

Причина: конфликты ассоциативности кэша (Cache Associativity Conflicts)

Вы столкнулись с классическим эффектом, который известен как «проклятие степени двойки» (power-of-two stride problem). Проблема связана не с магией, а с устройством кэш-памяти процессора.

Кэш L1 данных (32KB в вашем процессоре) имеет ограниченную ассоциативность — обычно 8-канальную. Это означает, что каждый блок памяти может быть размещён только в одном из 8 «наборов» (sets) кэша. Адрес памяти разбивается на три части: тег, индекс набора и смещение внутри строки кэша (обычно 64 байта).

Когда вы работаете с матрицей int matrix[8192][8192]:

• Каждый int занимает 4 байта
• Строка матрицы состоит из 8192 × 4 = 32768 байт (ровно 32KB)
• Это в точности равно размеру кэша L1 (32KB)

При последовательном доступе к элементам одной строки (matrix[i][j] с j от 0 до 8191) каждая следующая строка матрицы будет отображаться на те же самые наборы кэша, что и предыдущая. Почему? Потому что шаг между строками (32768 байт) кратен размеру кэша. Когда процессор пытается загрузить строку i+1, все строки кэша из строки i вытесняются, так как они конкурируют за одни и те же 8 позиций в каждом наборе. Это называется thrashing (перемешивание) кэша.

При размере 8191 или 8193 шаг между строками не кратен 32KB, поэтому строки распределяются по разным наборам, и кэш работает эффективно.

Как это исправить?

Есть несколько решений:

1. Добавить отступ (padding) к строкам

const int SIZE = 8192;
const int PADDED_SIZE = SIZE + 64; // Добавляем отступ
std::vector<std::vector<int>> matrix(SIZE, std::vector<int>(PADDED_SIZE, 1));

// Доступ к данным: используем matrix[i][j], где j < SIZE
for (int i = 0; i < SIZE; ++i) {
    for (int j = 0; j < SIZE; ++j) {
        sum += matrix[i][j];
    }
}

Отступ в 64 байта (или любое значение, не кратное размеру строки кэша) нарушает периодичность индексов наборов.

2. Использовать одномерный массив с ручной индексацией

std::vector<int> flat(SIZE * SIZE);
// Доступ: flat[i * SIZE + j]

Здесь вы сами контролируете layout памяти. Можно даже сделать строки не кратными степени двойки.

3. Изменить порядок обхода (loop interchange)

// Обходим по столбцам, а не по строкам
for (int j = 0; j < SIZE; ++j) {
    for (int i = 0; i < SIZE; ++i) {
        sum += matrix[i][j];
    }
}

Это не решит проблему для данного размера, но в некоторых случаях помогает за счёт другого паттерна доступа. Однако при размере 8192 и обходе по столбцам вы получите ещё более сильное замедление.

4. Использовать выравнивание памяти

alignas(64) int matrix[8192][8192]; // Выравнивание по 64 байта

Иногда помогает, но не гарантирует решение, если размер строки остаётся степенью двойки.

Почему именно 8192?

8192 × 4 байта = 32768 байт = 32KB = размер кэша L1. Если размер кэша L1 был бы 64KB, проблема проявилась бы при размере 16384. Это фундаментальное свойство кэша с прямым отображением или наборно-ассоциативного кэша.

В вашем процессоре 8-канальный кэш L1. Каждый набор может хранить 8 строк кэша (8 × 64 = 512 байт на набор). Всего наборов: 32KB / 512 байт = 64 набора. При шаге 32KB все строки матрицы попадают в один и тот же набор, и 8-канальность не спасает — вы просто вытесняете одни строки другими.

#include <Eigen/Dense>
#include <iostream>

int main() {
    const int SIZE = 8192;
    Eigen::MatrixXi mat = Eigen::MatrixXi::Constant(SIZE, SIZE, 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    long long sum = mat.sum();
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "Время: " << elapsed.count() << " с, сумма: " << sum << std::endl;
    return 0;
}