c - 高速缓存如何工作？

Question

今天在上计算机组织课的时候，老师讲了一件我很感兴趣的事情。当谈到为什么缓存内存起作用时，他说：

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

用第二行改变第一行是不好的。您对此有何看法？为什么会这样？

Answer 1

Red Hat 的 Ulrich Drepper 和 glibc 的名气有一篇非常好的论文，What Every Programmer Should Know About Memory。一节非常详细地讨论了缓存。例如，在 SMP 系统中存在缓存效应，其中 CPU 最终可能会来回颠倒修改过的缓存行的所有权，从而极大地损害性能。

Answer 2

参考地点。因为数据是按行存储的，所以对于每一行，j 列都在相邻的内存地址中。操作系统通常会将整个页面从内存加载到缓存中，并且相邻的地址引用可能会引用同一页面。如果您在内部循环中增加行索引，则这些行可能位于不同的页面上（因为它们被 j 分开）并且缓存可能必须不断地引入和丢弃内存页面，因为它引用数据。这称为抖动，对性能不利。

在实践中，对于更大的现代缓存，行/列的大小需要相当大才能发挥作用，但这仍然是一种很好的做法。

[编辑] 上面的答案是特定于 C 的，可能因其他语言而异。我知道唯一不同的是 FORTRAN。FORTRAN 以列主要顺序存储事物（上面是行主要），在 FORTRAN 中更改语句的顺序是正确的。如果您想要/需要效率，了解您的语言如何实现数据存储非常重要。

Answer 3

之所以如此，是因为缓存就像局部性一样。访问的相同数量的内存，但间隔更远，将命中不同的缓存“行”，甚至可能完全错过缓存。因此，只要您有选择，最好组织数据，以便可能在时间上彼此接近的访问也在空间中进行。这增加了缓存命中的机会，并为您提供了更高的性能。

当然，有很多关于这个主题的信息可用，例如参见这个关于参考位置的维基百科条目。或者，我猜，你自己的课程教科书。:)

Answer 4

在 C 中，n 维矩阵是行主要的，这意味着矩阵的最后一个索引代表内存中的相邻空间。这与其他一些语言不同，例如 FORTRAN，它们是列专业的。在 FORTRAN 中，像这样遍历 2D 矩阵更有效：

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

高速缓存是非常快且非常昂贵的内存，靠近 CPU。CPU 不是每次从 RAM 中获取一小块数据，而是获取一大块数据并将其存储在缓存中。赌注是，如果您只读取一个字节，那么您读取的下一个字节很可能就在它之后。如果是这种情况，那么它可以来自缓存。

通过按原样布置循环，您可以按照它们存储在内存中的顺序读取字节。这意味着它们在缓存中，并且可以被 CPU 快速读取。如果您在第 1 行和第 2 行进行交换，那么您每次在循环中都会读取每“N”个字节。您正在读取的字节在内存中不再连续，因此它们可能不在缓存中。CPU 必须从（较慢的）RAM 中获取它们，因此您的性能会降低。