Почему существует значительная разница в этом времени выполнения цикла С++?

Ответ 1

Это проблема кэша памяти.

matrix[i][j] имеет лучшие кэш-запросы, чем matrix[j][i], так как matrix[i][j] имеет больше возможностей доступа к памяти.

Например, когда мы обращаемся к matrix[i][0], кеш может загружать непрерывный сегмент памяти, содержащий matrix[i][0], поэтому доступ к matrix[i][1], matrix[i][2],... будет полезен при скорости кеширования, поскольку matrix[i][1], matrix[i][2],... находятся рядом с matrix[i][0].

Однако, когда мы обращаемся к matrix[j][0], он далеко от matrix[j - 1][0] и может не кэшироваться и не может использовать скорость кеширования. В частности, матрица обычно хранится как непрерывный большой сегмент памяти, а cacher может предикатировать поведение доступа к памяти и всегда кэшировать память.

Вот почему matrix[i][j] работает быстрее. Это типично для оптимизации производительности на основе кеш-памяти.

Ответ 2

Разница в производительности обусловлена ​​стратегией кэширования компьютера.

2-мерный массив matrix[i][j] представлен как длинный список значений в памяти.

Например, массив A[3][4] выглядит следующим образом:

1 1 1 1   2 2 2 2   3 3 3 3

В этом примере каждая запись A [0] [x] установлена ​​в 1, каждая запись A [1] [x] установлена ​​в 2,...

Если ваш первый цикл применяется к этой матрице, порядок доступа таков:

1 2 3 4   5 6 7 8   9 10 11 12

Пока второй порядок доступа к петлям выглядит следующим образом:

1 4 7 10  2 5 8 11  3 6 9 12

Когда программа обращается к элементу массива, он также загружает последующие элементы.

например. если вы получаете доступ к A[0][1], A[0][2] и A[0][3] тоже загружены.

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

Ответ 3

Другие люди хорошо поработали, объясняя, почему одна из форм кода более эффективно использует кеш памяти, чем другой. Я хотел бы добавить некоторую справочную информацию, о которой вы, возможно, и не подозреваете: вы, вероятно, не понимаете, насколько дороги в настоящее время доступ к основной памяти.

Цифры, размещенные в этом вопросе, выглядят как подходящие для меня, и я буду воспроизводить их здесь, потому что они так важны:

Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns

Обратите внимание на изменение единиц для последних двух записей. В зависимости от того, какая у вас модель, этот процессор работает на частоте 2,9-3,2 ГГц; чтобы сделать математику проще, позвольте просто назвать ее 3 ГГц. Таким образом, один цикл составляет 0,333333 наносекунды. Таким образом, доступ DRAM также составляет 100-300 циклов.

Дело в том, что процессор мог выполнить сотни инструкций за время, затрачиваемое на чтение одной строки кэша из основной памяти. Это называется памятью. Из-за этого эффективное использование кеша памяти более важно, чем любой другой фактор общей производительности на современных процессорах.

Ответ 4

Ответ немного зависит от того, как определяется matrix. В полностью динамически распределенном массиве у вас будет:

T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
   t[i] = new T[m]; 
}

Итак, для каждого matrix[j] потребуется новый поиск в памяти для указателя. Если вы выполняете цикл j снаружи, внутренний цикл может повторно использовать указатель для matrix[j] для всего внутреннего цикла.

Если матрица является простым двумерным массивом:

T matrix[n][m];

тогда matrix[j] будет просто умножением на 1024 * sizeof(T) - это можно сделать, добавив 1024 * sizeof(T) индекс цикла в оптимизированный код, поэтому должен быть относительно быстрым в любом случае.

Кроме того, мы имеем коэффициенты локализации кэша. У кэшей есть "строки" данных, которые обычно составляют от 32 до 128 байт в строке. Поэтому, если ваш код читает адрес X, кеш загружается со значениями от 32 до 128 байтов вокруг X. Таким образом, если вам нужно только NEXT, это только sizeof(T) переместиться из текущего местоположения, он, скорее всего, уже находится в кеше [а современные процессоры также обнаруживают, что вы обходите в цикле, читающем каждую ячейку памяти, и предварительно загружаете данные ].

В случае внутреннего цикла j вы читаете новое местоположение расстояния sizeof(T)*1024 для каждого цикла [или, возможно, большее расстояние, если оно динамически распределено]. Это означает, что загружаемые данные не будут полезны для следующего цикла, потому что это не в следующих 32 - 128 байтах.

И, наконец, вполне возможно, что первый цикл более оптимизирован благодаря инструкциям SSE или аналогичным, которые позволяют выполнять расчет еще быстрее. Но это, вероятно, является маргинальным для такой большой матрицы, поскольку производительность сильно ограничена памятью при таком размере.

Ответ 5

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

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

Однако медленное упорядочение циклов использует только одну запись из каждой строки кэша, прежде чем двигаться дальше. Таким образом, каждая строка кэша должна загружаться несколько раз, один раз для каждой записи матрицы в строке. например если a double равно 8 байтам, а длина кеша - 64 байта, то каждый проход через внешний цикл должен читать каждую запись матрицы восемь раз, а не один раз.

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

(также хороший оптимизатор выполнил бы только один проход через самый внешний цикл, поскольку он распознает первые 999 раз, не имеет отношения к окончательному значению sum)

Ответ 6

Матрица хранится в памяти как вектор. Получив доступ к первому пути, он обращается к памяти последовательно. Для доступа к нему второй способ требует перехода по местам памяти. См. http://en.wikipedia.org/wiki/Row-major_order

Ответ 7

Если вы получаете доступ к j - i, размер j кэшируется, поэтому машинный код не должен менять его каждый раз, второе измерение не кэшируется, поэтому вы фактически удаляете кеш каждый раз, что вызывает разницу.

Ответ 8

Основываясь на концепции локальности ссылки, очень вероятно, что кусок кода будет иметь доступ к соседним ячейкам памяти. Таким образом, больше значений загружается в кеш, чем запрашивается. Это означает больше хитов кэша. Ваш первый пример удовлетворяет это хорошо, а во втором - код.