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

Question

Ниже приведены две почти идентичные программы, за исключением того, что я переключил переменные 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; }
   }
}

Answer 1

Как уже говорили другие, проблема заключается в сохранении в ячейке памяти в массиве: 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-м примере вы получаете доступ к массиву, сначала циклически перебирая 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 выложил в память двумерный массив, вы просите его перепрыгнуть повсюду. Но теперь для кикера: почему это важно? Все обращения к памяти одинаковы, верно?

Нет: из-за кешей. Данные из вашей памяти передаются в ЦП небольшими порциями (называемыми «строками кэша»), обычно размером 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 называется «мажор строк», а фортран - «мажор столбцов». Как видите, очень важно знать, является ли ваш язык программирования основным или основным столбцом! Вот ссылка для получения дополнительной информации: http://en.wikipedia.org/wiki/Row-major_order

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Я пробовал с

x[50000][50000];

и времядля версии 1 - 13 с против 0 для версии 2.

Answer 7

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

Поскольку 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 выполняет много предварительной выборки и кэширования данных.Вы, вероятно, создаете много ошибок кэша в своем более медленном порядке итерации.