алгоритм сравнения в C, в чем разница?

Question

#define IMGX 8192
#define IMGY 8192
int red_freq[256];
char img[IMGY][IMGX][3];

main(){ 

int i, j;
  long long total;
  long long redness;

  for (i = 0; i < 256; i++) 
    red_freq[i] = 0;

  for (i = 0; i < IMGY; i++) 
    for (j = 0; j < IMGX; j++) 
      red_freq[img[i][j][0]] += 1;

  total = 0;
  for (i = 0; i < 256; i++) 
    total += (long long)i * (long long)red_freq[i];

  redness = (total + (IMGX*IMGY/2))/(IMGX*IMGY); 

в чем разница, когда вы заменяете второй цикл for на

for (j = 0; j < IMGX; j++) 
    for (i = 0; i < IMGY; i++) 
      red_freq[img[i][j][0]] += 1;

все остальное остается прежним, и почему первый алгоритм работает быстрее, чем второй?

Это как-то связано с распределением памяти?

Answer 1

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

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

Первая версия также может быть оптимизирована компилятором, чтобы использовать более умные инструкции (инструкции SIMD), которые были бы еще быстрее.

Answer 2

Это связано с тем, что первая версия выполняет итерацию в памяти в том порядке, в котором она физически размещена, а вторая - в памяти, переходя от одного столбца в массиве к другому. Это приведет к перегрузке кеша и будет мешать оптимальной производительности ЦП, который затем должен будет тратить много времени на ожидание обновления кеша снова и снова.

Answer 3

Это связано с тем, что большие современные процессорные архитектуры (например, в ПК) в значительной степени оптимизированы для работы с памятью, которая является «близкой» (в терминах адреса) памяти, к которой они недавно обращались. Фактический доступ к физической памяти намного, намного медленнее, чем теоретически может выполнять процессор, поэтому все, что помогает процессу сделать его доступ наиболее эффективным способом, влияет на производительность.

Невозможно обобщить нечто большее, но «местность ссылок» - это хорошая цель, к которой нужно стремиться.

Answer 4

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

(i * (IMGY * IMGX)) + (j * IMGX) + 0

В первом алгоритме

(i * (IMGY * IMGX)) gets calculates 8192 times
(j * IMGX) gets calculated 8192 * 8192 times

Во втором алгоритме

(i * (IMGY * IMGX)) gets calculates 8192 * 8192 times
(j * IMGX) gets calculated 8192 times

С

(i * (IMGY * IMGX)) 

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

Answer 5

Из-за того, как память размещена, первая версия поддерживает локальность данных и, следовательно, вызывает меньше ошибок кэша.

Answer 6

Да, это как-то связано с распределением памяти. Первый цикл индексирует внутреннее измерение img, которое каждый раз занимает только 3 байта. Это легко в пределах одной страницы памяти (я думаю, что общий размер здесь составляет 4 КБ для одной страницы). Но с вашей второй версией индекс внешнего измерения быстро меняется. Это приведет к тому, что чтения памяти распространятся на гораздо больший диапазон памяти, а именно sizeof (char[IMGX][3]) байта, что составляет 24 КБ. И с каждым изменением внутреннего индекса эти скачки начинают происходить снова. Это будет попадать на разные страницы и, вероятно, будет немного медленнее. Также я слышал, что процессор читает впереди памяти. Это принесет пользу первой версии, потому что во время чтения эти данные, вероятно, уже находятся в кэше. Я могу представить себе, что вторая версия от этого не выигрывает, потому что она делает большие скачки по памяти взад-вперед.

Я подозреваю, что разница не так уж велика, но если алгоритм запускается много раз, он в конечном итоге становится заметным. Вы, вероятно, хотите прочитать статью Row-major Order в Википедии. Это схема, используемая для хранения многомерных массивов в C.