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

这是因为第一个版本按照物理布局的顺序迭代内存,而第二个版本在内存中从数组中的一列跳到下一列.这将导致缓存抖动并干扰CPU的最佳性能,然后CPU必须花费大量时间等待缓存一次又一次地刷新.