Два варианта одного цикла: почему один втрое медленнее
Матрица double m[N][N] в статической памяти при N = 4096 суммируется двумя способами:
// вариант A
for (size_t i = 0; i < N; ++i)
for (size_t j = 0; j < N; ++j)
sum += m[i][j];
// вариант B
for (size_t j = 0; j < N; ++j)
for (size_t i = 0; i < N; ++i)
sum += m[i][j];
Оба варианта собраны одинаково и выполняют одинаковое число сложений. Вариант B работает примерно втрое медленнее, счётчики процессора показывают у него на порядок больше промахов кеша.
Чем объясняется разница?
- Вариант B выполняет больше арифметических операций: другой порядок индексов требует пересчитывать адрес на каждом шаге
- Вариант A нельзя векторизовать из-за зависимости по sum, поэтому B обязан быть быстрее — замер ошибочен
- В C двумерный массив хранится построчно: B идёт по памяти большим шагом и из каждой кеш-линии берёт один элемент
- Разница в том, что в B переменная внешнего цикла не помещается в регистр и постоянно читается из памяти