Какой порядок вложенных циклов для итерации по 2D-массиву является более эффективным

1. для массива [100] [100] - они оба одинаковы, если кэш L1 больше, то 100*100*sizeof(int) == 10000*sizeof(int) == [обычно] 40000. Примечание в Песчаный Мост - 100*100 целых чисел должно быть достаточно элементов, чтобы увидеть разницу, так как кэш L1 составляет всего 32k.

2. компиляторы, вероятно, оптимизируют этот код все равно

3. предполагая, что оптимизация компилятора отсутствует, а матрица не помещается в кэш L1 - the первый код лучше из-за производительности кэша [обычно]. Каждый раз, когда элемент не найден в кэш - вам cache miss - и нужно перейти в оперативную память или кэш L2 [которые намного медленнее]. Взятие элементов из ОЗУ в кэш [заполнение кэша] выполняется в блоках [обычно 8/16 байт] - так что в первом коде вы получаете максимум Мисс размере 1/4 [предполагая, что блок кэша 16 байт, 4 байта ints], а во втором коде он неограничен и может быть даже 1. Во втором коде snap-элементы, которые уже были в кэше [вставлены в заливку кэша для соседних элементов] - были удалены, и вы получаете избыточный промах кэша.

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

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

этот вид микро-оптимизации зависит от платформы, поэтому вам нужно будет профилировать код, чтобы иметь возможность сделать разумный вывод.

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

( ((y) * (row->width)) + (x) ) 

рассмотрим упрощенный кэш L1, который имеет достаточно места только для 50 строк нашего массива. За первые 50 итераций вы заплатите неизбежную цену за 50 промахов кэша, но что тогда произойдет? Для каждой итерации от 50 до 99 вы все равно будете пропускать кэш и должны извлекать из L2 (и / или Оперативной памяти и т. д.). Тогда,x изменения на 1 и y начинается снова, что приводит к другому пропуску кэша, потому что первая строка вашего массива была выселена из кэша, и так далее.

первый фрагмент не имеет этой проблемы. Он обращается к массиву в row-major order, что обеспечивает лучшую локальность - вам нужно только заплатить за промахи кэша не более одного раза (если строка вашего массива не присутствует в кэше в момент запуска цикла) за строку.

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

учитывая, что C++ является основным строком, я считаю, что первый метод будет немного быстрее. В памяти 2D массив представлен в одном размерном массиве, и производительность зависит от доступа к нему либо с помощью строки major, либо столбца major

Это классическая задача о cache line bouncing

в большинстве случаев первый лучше, но я думаю, что точно ответ:ЭТО ЗАВИСИТ, другая архитектура может быть другой результат.

во втором методе,промах кэша, потому что кэш хранит смежные данные. следовательно, первый метод эффективнее, чем второй.

в вашем случае (заполнить весь массив 1 значение), что будет быстрее:

   for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }

и вы все еще можете лечить a как 2 мерный массив.

EDIT: Как упоминал Биньямин Шарет, вы могли бы сделать это, если ваш a объявлена таким образом:

int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}

В общем, лучшая локальность (замеченная большинством респондентов) - это только первое преимущество для производительности loop #1.

второе (но связанное) преимущество, это то, что для циклы типа #1-компилятор обычно способен эффективно авто-векторизации код с шаблоном доступа к памяти stride-1 (stride-1 означает, что существует непрерывный доступ к элементам массива один за другим в каждой следующей итерации). Наоборот,для петель типа #2, авто-векторизация обычно не работает нормально, потому что нет последовательного итерационного доступа stride-1 к блокам contiguos в памяти.

Ну, мой ответ будет общим. Для очень простых циклов, таких как #1 или #2, могут использоваться еще более простые агрессивные оптимизации компилятора (оценивающие любую разницу) , а также компилятор обычно сможет автоматически векторизовать #2 С шагом-1 для внешний петли (особенно при использовании #Pragma Симд или аналогичные).

первый вариант лучше, так как мы можем хранить a[i] in a temp variable внутри первого цикла, а затем поиск индекса j в этом. В этом смысле его можно назвать кэшированной переменной.