c - 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 指令)，这会更快。