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;

其他一切都保持不变，为什么第一个算法比第二个算法快？

它与内存分配有关吗？

score 8 · Accepted Answer

第一个版本按顺序更改内存，因此最佳地使用了处理器缓存。第二个版本使用它加载的每个缓存行中的一个值，因此它对于缓存的使用非常不利。

要理解的一点是缓存被分成几行，每一行在整体结构中都会包含很多值。

编译器还可以优化第一个版本以使用更智能的指令（SIMD 指令），这将更快。

score 5 · Accepted Answer

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

score 2 · Accepted Answer

这是因为大型现代处理器架构（例如 PC 中的架构）经过大规模优化，可以在他们最近访问的“附近”（地址相关术语）内存的内存上工作。实际的物理内存访问比 CPU 理论上可以运行的速度要慢得多，因此帮助进程以最有效的方式进行访问的所有内容都有助于提高性能。

概括更多是几乎不可能的，但是“参考的局部性”是一件好事。

score 1 · Accepted Answer

由于内存的布局方式，第一个版本保持了数据局部性，因此减少了缓存未命中率。

score 1 · Accepted Answer

内存分配只发生一次，而且是在开始时，所以这不可能是原因。原因是运行时如何计算地址。在这两种情况下，内存地址都计算为

(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))

涉及两次乘法，越多需要更多时间。这就是原因

score 0 · Accepted Answer

是的，它与内存分配有关。第一个循环索引的内部维度img，每次恰好跨越 3 个字节。这很容易在一个内存页面内（我相信这里的常见大小是一页 4kB）。但是在您的第二个版本中，外部维度的索引变化很快。这将导致内存读取分布在更大范围的内存上——即sizeof (char[IMGX][3])字节，即 24kB。随着内部索引的每次变化，这些跳跃再次开始发生。这将影响不同的页面，并且可能会慢一些。我还听说 CPU 会提前读取内存。这将使第一个版本受益，因为在它读取时，该数据可能已经在缓存中。我可以想象第二个版本并没有从中受益，因为它会在内存中来回跳跃。

我怀疑差异并没有那么大，但如果算法运行多次，它最终会变得明显。您可能想阅读Row-major Order维基百科上的文章。这就是用于在 C 中存储多维数组的方案。

c - C中的算法比较，有什么区别？

6 回答 6

Related

Reference