Какой порядок вложенных циклов для итерации по двумерному массиву является более эффективным
Какой из следующих порядков вложенных циклов для итерации по двумерному массиву является более эффективным с точки зрения времени (производительность кэша)? Зачем?
int a[100][100];
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[i][j] = 10;
}
}
или же
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[j][i] = 10;
}
}
10 ответов
Первый способ немного лучше, так как ячейки, которые назначаются, лежат рядом друг с другом.
Первый метод:
[ ][ ][ ][ ][ ] ....
^1st assignment
^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment
Второй метод:
[ ][ ][ ][ ][ ] ....
^1st assignment
^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
Для массива [100][100] - они оба одинаковы, если кэш L1 больше, чем 100*100*sizeof(int) == 10000*sizeof(int) == [обычно] 40000. Примечание в Sandy Bridge - 100 * 100 целых чисел должно быть достаточным количеством элементов, чтобы увидеть разницу, поскольку кэш L1 составляет всего 32 КБ.
Компиляторы, вероятно, все равно оптимизируют этот код
При условии отсутствия оптимизации компилятора, и матрица не помещается в кэш L1 - первый код лучше из-за производительности кеша [обычно]. Каждый раз, когда элемент не обнаруживается в кеше - вы получаете ошибку в кеше - и вам нужно перейти в RAM или L2 кеш [что намного медленнее]. Перенос элементов из ОЗУ в кеш [заполнение кеша] выполняется в блоках [обычно 8/16 байт] - поэтому в первом коде вы получаете не более
1/4[предполагается, что блок кэша 16 байтов, 4 байта ints], тогда как во втором коде он неограничен и может быть даже 1. Во втором фрагменте кода - элементы, которые уже были в кэше [вставлены в заполнение кэша для смежных элементов] - были удалены, и вы получите лишний пропуск кеша.- Это тесно связано с принципом локальности, который является общим предположением, используемым при реализации системы кэширования. Первый код следует этому принципу, а второй - нет, поэтому производительность первого кэша будет лучше, чем второго.
Вывод: для всех реализаций кеша, о которых я знаю, первое будет не хуже второго. Они могут быть одинаковыми - если кеша вообще нет или весь массив полностью помещается в кеш - или из-за оптимизации компилятора.
Этот вид микрооптимизации зависит от платформы, поэтому вам нужно профилировать код, чтобы иметь возможность сделать разумный вывод.
В вашем втором фрагменте изменения в j в каждой итерации вырабатывается шаблон с низкой пространственной локальностью. Помните, что за кулисами ссылка на массив вычисляет:
( ((y) * (row->width)) + (x) )
Рассмотрим упрощенный кэш L1, в котором достаточно места только для 50 строк нашего массива. За первые 50 итераций вы заплатите неизбежную стоимость за 50 промахов кэша, но что тогда произойдет? Для каждой итерации от 50 до 99 вы все равно будете кэшировать промах и получать из L2 (и / или RAM и т. Д.). Затем, x меняется на 1 и y начинается заново, что приводит к еще одному отсутствию кэша, поскольку первая строка вашего массива была удалена из кэша и т. д.
Первый фрагмент не имеет этой проблемы. Он обращается к массиву в порядке следования строк, что обеспечивает лучшую локальность - вам нужно платить не более одного раза за кэш-ошибки (если строка вашего массива отсутствует в кэше во время запуска цикла) для каждой строки.
Тем не менее, это очень архитектурно-зависимый вопрос, поэтому вам необходимо принять во внимание особенности (размер кэша L1, размер строки кэша и т. Д.), Чтобы сделать вывод. Вы также должны измерить оба пути и отслеживать аппаратные события, чтобы получить конкретные данные, из которых можно сделать выводы.
Учитывая, что C++ является основным, я считаю, что первый метод будет немного быстрее. В памяти двумерный массив представлен в одномерном массиве, и производительность зависит от доступа к нему, используя основной ряд или основной столбец
Во втором методе кеш отсутствует, потому что в кеше хранятся недостоверные данные. следовательно, первый метод эффективнее второго.
Это классическая проблема о cache line bouncing
В большинстве случаев первый вариант лучше, но я думаю, что точный ответ таков: ЭТО ЗАВИСИТ, другая архитектура может привести к другому результату.
В вашем случае (заполните все значения массива 1) это будет быстрее:
for(j = 0; j < 100 * 100; j++){
a[j] = 10;
}
и ты все еще можешь лечить a как 2-х мерный массив.
РЕДАКТИРОВАТЬ: Как упоминал Биньямин Sharet, вы могли бы сделать это, если ваш a объявлен так:
int **a = new int*[100];
for(int i = 0; i < 100; i++){
a[i] = new int[100];
}
В целом, лучшая локальность (замеченная большинством респондентов) - это только первое преимущество для производительности цикла № 1.
Второе (но связанное) преимущество заключается в том, что для таких циклов, как #1, компилятор обычно способен автоматически векторизовать код с помощью шаблона доступа к памяти stride-1 (stride-1 означает, что существует непрерывный доступ к элементам массива один за другим в каждая следующая итерация). Напротив, для таких циклов, как #2, автоматическая векторизация обычно не будет работать нормально, потому что нет последовательного итеративного доступа шага-1 к смежным блокам в памяти.
Ну, мой ответ общий. Для очень простых циклов, таких как #1 или #2, могут быть использованы даже более простые агрессивные оптимизации компилятора (градуировка любых различий), а также компилятор обычно может автоматически векторизовать #2 с шагом-1 для внешнего цикла (особенно с # прагма симд или аналогичный).
Первый вариант лучше, так как мы можем хранить a[i] in a temp variable внутри первого цикла, а затем искать индекс J в этом. В этом смысле это можно сказать как кешированная переменная.