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

Возможные Дубликаты:
какой из этих двух циклов for является более эффективным с точки зрения времени и производительности кэша

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

7 ответов:

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

у вас есть 2-мерный массив, но память в компьютере, по своей сути является 1-мерным. Поэтому, пока вы представляете себе свой массив следующим образом:

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

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

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

в первый пример (1) захватите кусок 16 дюймов, (2) Измените только один из них, (3) повторите 4000*4000 раз. Это потребует в 16 раз больше "выборки" из памяти. Ваш процессор на самом деле придется тратить время, сидя вокруг, ожидая, что память появится, и пока она сидит вокруг вы тратите драгоценное время.

Важное Замечание:

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

536

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

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

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

62

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

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

22

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

12

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

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

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

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

10

эта строка виновного :

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

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

Я пробовал с 

x[50000][50000];

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

8

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

, потому что 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 chunk-итерации, и между любой chunk-итерации, вы будете иметь array_width итераций только sizeof(array_element).

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

3