Какой из следующих порядков вложенных циклов для итерации по двумерному массиву более эффективен с точки зрения времени (производительности кэша)? Почему?
int a[100][100];
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[i][j] = 10;
}
}
or
for(i=0; i<100; i++)
{
for(j=0; j<100; j++)
{
a[j][i] = 10;
}
}
Первый способ немного лучше, так как присваиваемые ячейки располагаются рядом друг с другом.
Первый метод:
[ ][ ][ ][ ][ ] ....
^1st assignment
^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment
Второй метод:
[ ][ ][ ][ ][ ] ....
^1st assignment
^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
Для array[100][100] - они оба одинаковы, если кэш L1 больше, чем 100*100*sizeof(int) == 10000*sizeof(int) == [обычно] 40000. Примечание в Sandy Bridge — 100*100 целых чисел должно быть достаточно, чтобы увидеть разницу, поскольку кэш L1 составляет всего 32 КБ.
Компиляторы, вероятно, все равно оптимизируют этот код.
Предполагая, что компилятор не оптимизировал и матрица не помещается в кеш L1 - первый код лучше из-за производительности кеша [обычно]. Каждый раз, когда элемент не найден в кеше — вы получаете промах кеша — и вам нужно перейти в оперативную память или Кэш L2 [который намного медленнее]. Перемещение элементов из ОЗУ в кеш [заполнение кеша] выполняется блоками [обычно 8/16 байтов] — так что в первом коде вы получаете максимум процент промахов 1/4 [при условии 16-байтового блока кеша, 4 байта ints], а во втором коде она неограничена, и может быть даже 1. Во втором снапе кода — элементы, которые уже были в кеше [вставлены в кеш заливки для соседних элементов] — вынимаются, и получается избыточный кеш-промах.
Вывод: Для всех известных мне реализаций кеша - первая будет не хуже второй. Они могут быть одинаковыми - если кеша нет вообще или весь массив полностью помещается в кеш - или из-за оптимизации компилятора.
1/4 и 1?
- person sgnsajgon; 17.01.2017
Такого рода микрооптимизация зависит от платформы, поэтому вам потребуется профилировать код, чтобы сделать разумный вывод.
Во втором фрагменте изменение j на каждой итерации создает шаблон с низкой пространственной локальностью. Помните, что за кулисами ссылка на массив вычисляется:
( ((y) * (row->width)) + (x) )
Рассмотрим упрощенный кэш L1, в котором достаточно места только для 50 строк нашего массива. За первые 50 итераций вы неизбежно заплатите за 50 промахов кэша, но что потом? Для каждой итерации с 50 по 99 вы все равно будете промахиваться в кэше и должны получать из L2 (и/или ОЗУ и т. д.). Затем x изменяется на 1, а y начинается заново, что приводит к еще одному промаху кеша, потому что первая строка вашего массива была вытеснена из кеша, и так далее.
В первом фрагменте такой проблемы нет. Он обращается к массиву в порядке строк, что обеспечивает лучшую локальность — вам нужно платить только за промахи в кэше не более одного раза (если строка вашего массива отсутствует в кэше в момент цикл начинается) за строку.
При этом этот вопрос очень зависит от архитектуры, поэтому вам нужно будет принять во внимание особенности (размер кэша L1, размер строки кэша и т. д.), чтобы сделать вывод. Вы также должны измерять оба способа и отслеживать аппаратные события, чтобы иметь конкретные данные, на основе которых можно делать выводы.
Учитывая, что C++ является основным, я считаю, что первый метод будет немного быстрее. В памяти 2D-массив представлен в одномерном массиве, и производительность зависит от доступа к нему либо с использованием основных строк, либо основных столбцов.
Это классическая задача о cache line bouncing
В большинстве случаев первый лучше, но я думаю, что точный ответ: ЭТО ЗАВИСИТ, другая архитектура может привести к другому результату.
Во втором методе кэш отсутствует, поскольку в кеше хранятся непрерывные данные, следовательно, первый метод эффективнее второго.
В вашем случае (заполните все значения массива 1) это будет быстрее:
for(j = 0; j < 100 * 100; j++){
a[j] = 10;
}
и вы все еще можете рассматривать a как двумерный массив.
EDIT: как упомянул Биньямин Шарет, вы можете сделать это, если ваш 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 для внешнего цикла (особенно с #pragma simd или подобным).
Первый вариант лучше, так как мы можем сохранить a[i] in a temp variable внутри первого цикла, а затем искать в нем индекс j. В этом смысле можно сказать, что это кэшированная переменная.
