Почему порядок циклов влияет на производительность при итерации по двумерному массиву?

360

Ниже приведены две почти идентичные программы, за исключением того, что я переключил переменные iи j. Они оба бегут в разное количество времени. Может кто-нибудь объяснить, почему это происходит?

Версия 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Версия 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}
отметка
источник
26
en.wikipedia.org/wiki/…
Брендан Лонг,
7
Можете ли вы добавить результаты теста?
naught101
3
Связанный: stackoverflow.com/questions/9888154/…
Томас Падрон-Маккарти
14
@ naught101 Тесты покажут разницу в производительности от 3 до 10 раз. Это базовый C / C ++, я полностью озадачен тем, как это набрало столько голосов ...
TC1
12
@ TC1: я не думаю, что это так просто; возможно промежуточный. Но не должно быть сюрпризом, что «базовые» вещи, как правило, полезны для большего числа людей, отсюда и множество возражений. Более того, это вопрос, который трудно гуглить, даже если он «базовый».
LarsH

Ответы:

595

Как уже говорилось, проблема заключается в магазин в ячейку памяти в массиве: x[i][j]. Вот немного понимания почему:

У вас есть двумерный массив, но память в компьютере по своей сути является одномерной. Итак, пока вы представляете свой массив следующим образом:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Ваш компьютер хранит его в памяти в виде одной строки:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

Во втором примере вы получаете доступ к массиву, сначала перебирая 2-й номер, то есть:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Это означает, что вы бьете их по порядку. Теперь посмотрим на 1-ую версию. Ты делаешь:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Из-за способа, которым C разместил 2-й массив в памяти, вы просите его перепрыгнуть повсюду. Но теперь для кикера: почему это важно? Все обращения к памяти одинаковы, верно?

Нет: из-за кешей. Данные из вашей памяти передаются в ЦП небольшими порциями (называемыми «строками кэша»), обычно 64 байта. Если у вас есть 4-байтовые целые числа, это означает, что вы получаете 16 последовательных целых чисел в аккуратном небольшом пакете. На самом деле это довольно медленно, чтобы получить эти куски памяти; Ваш процессор может выполнять большую работу за время, необходимое для загрузки одной строки кэша.

Теперь вернемся к порядку доступа: второй пример: (1) захват фрагмента в 16 дюймов, (2) изменение всех из них, (3) повторение 4000 * 4000/16 раз. Это приятно и быстро, и процессору всегда есть над чем работать.

Первый пример: (1) получить фрагмент из 16 дюймов, (2) изменить только один из них, (3) повторить 4000 * 4000 раз. Для этого потребуется 16-кратное количество «выборок» из памяти. Ваш процессор на самом деле должен будет сидеть, дожидаясь появления этой памяти, а пока он сидит, вы теряете драгоценное время.

Важная заметка:

Теперь, когда у вас есть ответ, вот интересная заметка: нет никакой внутренней причины, по которой ваш второй пример должен быть быстрым. Например, в Фортране первый пример будет быстрым, а второй - медленным. Это потому, что вместо того, чтобы разложить вещи в концептуальные «строки», как это делает C, Fortran расширяется в «столбцы», то есть

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Раскладка C называется 'row-major', а Fortran называется 'column-major'. Как видите, очень важно знать, является ли ваш язык программирования основным или основным столбцом! Вот ссылка для получения дополнительной информации: http://en.wikipedia.org/wiki/Row-major_order

Роберт Мартин
источник
14
Это довольно тщательный ответ; это то, чему меня учили при работе с промахами кеша и управлением памятью.
Макото
7
У вас есть «первая» и «вторая» версии в неправильном направлении; первый пример изменяет первый индекс во внутреннем цикле и будет более медленным примером выполнения.
Кафе
Отличный ответ. Если Марк захочет узнать больше о таких мрачных вещах, я бы порекомендовал такую ​​книгу, как «Напиши великий код».
wkl
8
Бонусные баллы за указание на то, что С изменил порядок строк с Фортрана. Для научных вычислений размер кэша L2 - это все, потому что, если все ваши массивы помещаются в L2, тогда вычисления могут быть завершены без обращения к основной памяти.
Михаил Шопсин
4
@birryree: свободно доступное, что каждый программист должен знать о памяти , также является хорошим чтением.
Кафе
68

Ничего общего со сборкой. Это связано с отсутствием кэша .

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

Смотрите также: http://en.wikipedia.org/wiki/Loop_interchange .

Оливер Чарльзуорт
источник
23

Версия 2 будет работать намного быстрее, потому что она использует кэш вашего компьютера лучше, чем версия 1. Если подумать, массивы - это просто смежные области памяти. Когда вы запрашиваете элемент в массиве, ваша ОС, вероятно, внесет страницу памяти в кеш, содержащий этот элемент. Однако, поскольку следующие несколько элементов также находятся на этой странице (потому что они являются смежными), следующий доступ уже будет в кеше! Это то, что делает версия 2, чтобы ускорить процесс.

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

Oleksi
источник
При таких размерах массива, вероятно, за это отвечает менеджер кеша в ЦП, а не в ОС.
krlmlr
12

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

Кодер переменной длины
источник
11

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

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

Это менее вероятно для первого цикла, потому что он должен увеличивать указатель «p» каждый раз на 4000.

РЕДАКТИРОВАТЬ: p++ и даже *p++ = ..могут быть скомпилированы в одну инструкцию процессора в большинстве процессоров. *p = ..; p += 4000не может, поэтому есть меньше преимуществ в его оптимизации. Это также сложнее, потому что компилятор должен знать и использовать размер внутреннего массива. И это не происходит часто во внутреннем цикле в нормальном коде (это происходит только для многомерных массивов, где последний индекс остается постоянным в цикле, а второй - последний шаг), поэтому оптимизация является менее приоритетной ,

fishinear
источник
Я не понимаю, что «потому что нужно будет указывать« р »на 4000 каждый раз», значит.
Veedrac
@Veedrac Указатель должен быть увеличен на 4000 во внутреннем цикле: p += 4000isop++
fishinear
Зачем компилятору найти эту проблему? iуже увеличен на не-единичное значение, учитывая, что это приращение указателя.
Veedrac
Я добавил больше объяснений
fishinear
Попробуйте набрать int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; }в gcc.godbolt.org . Кажется, что два компилируются в основном одинаково.
Veedrac
7

Эта строка виновника:

x[j][i]=i+j;

Вторая версия использует непрерывную память, таким образом, будет существенно быстрее.

Я пробовал с

x[50000][50000];

и время выполнения составляет 13 с для версии 1 против 0,6 с для версии 2.

Николас Модржик
источник
4

Я пытаюсь дать общий ответ.

Потому i[y][x]что это сокращение от *(i + y*array_width + x)C (попробуйте классный int P[3]; 0[P] = 0xBEEF;).

Когда вы перебираете y, вы перебираете куски по размеру array_width * sizeof(array_element). Если у вас есть это во внутреннем цикле, то у вас будут array_width * array_heightитерации по этим частям.

Переключая порядок, вы будете иметь только array_heightчан-итерации, а между любыми чан-итерациями вы будете иметь array_widthтолько итерации sizeof(array_element).

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

Себастьян Мах
источник