C 中的缓存性能（有关循环）

Question

我想知道，尽管逻辑上做同样的事情，为什么一组循环比另一组循环具有更好的缓存性能？

1. for (i = 0; i < n; i++) {
       for (j = 0; j < n; j++) {
           accum = 0.0;
           for (k = 0; k < n; k++) {
               accum += b[j][k] * a[k][i];
           }
           c[j][i] = accum;
       }
   }
   

2. for (j = 0; j < n; j++) {
       for (k = 0; k < n; k++) {
           val = b[j][k];
           for (i = 0; i < n; i++) {
               c[j][i] += val * a[k][i];
           }
       }
   }
   

我相信上面的第一个可以提供更好的缓存性能，但为什么呢？

另外，当我们增加块大小，但保持缓存大小和关联性不变时，它会影响未命中率吗？在某个点上，增加块大小会导致更高的丢失率，对吗？

Answer 1

一般来说，矩阵中最有效的循环将循环最后一个维度，而不是第一个维度（“最后一个”位于c中m[a][b][c]）。

例如，给定一个像图像这样的 2D 矩阵，其像素在内存中从左上角到右下角表示，顺序迭代它的最快方法将水平穿过每个扫描线，如下所示：

for (int y=0; y < h; ++y) {
    for (int x=0; x < w; ++x)
        // access pixel[y][x]
}

...不是这样的：

for (int x=0; x < w; ++x) {
    for (int y=0; y < h; ++y)
        // access pixel[y][x]
}

...由于空间局部性。这是因为计算机从层次结构中较慢、较大的区域获取内存，并将其移动到较大、对齐的块中的较快、较小的区域（例如：64 字节缓存行、4 KB 页面，以及较小的 64 位通用内存）目的寄存器，例如）。第一个示例在驱逐之前立即访问此类连续块中的所有数据。

harold在这个网站上，我对如何看待和解释这个主题有了一个很好的看法，建议不要过多关注缓存未命中，而是专注于在驱逐之前努力使用缓存中的所有数据。第二个示例无法对除最微不足道的小图像之外的所有图像执行此操作，方法是使用扫描线大小的大步幅垂直迭代图像，而不是使用像素大小的小步幅水平迭代图像。

另外，当我们增加块大小，但保持缓存大小和关联性不变时，它会影响未命中率吗？在某个点上，增加块大小会导致更高的丢失率，对吗？

这里的答案是“是”，因为块大小的增加自然会等同于更多的强制丢失（这将更简单地是“丢失”而不是“丢失率”），但也只是需要处理更多的数据，而这不会所有这些都必须适合最快的 L1 缓存。如果我们以大步幅访问大量数据，我们最终会得到更高的非强制未命中率，因为在我们使用它之前，更多的数据被从缓存中逐出，然后又将其冗余地加载回缓存中。更快的缓存。

还有一种情况，如果块大小足够小并且正确对齐，所有数据将只适合单个缓存行，并且我们如何顺序访问它并不重要。

矩阵乘法

现在，您的示例比上面这个简单的图像示例要复杂得多，但是相同的概念往往适用。

我们看第一个：

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        accum = 0.0;
        for (k = 0; k < n; k++)
            accum += b[j][k] * a[k][i];
        c[j][i] = accum;
    }
}

如果我们查看最内层的k循环，我们将访问b[j][k]. 这是一个相当最佳的访问模式：如果我们想象一个行顺序内存布局，则为“水平”。但是，我们也访问a[k][i]. 这并不是那么理想，特别是对于非常大的矩阵，因为它以大跨度的垂直模式访问内存，并且往往会遭受数据在使用之前从最快但最小形式的内存中逐出的情况，只是为了加载该数据数据块再次冗余。

如果我们看第二个j循环，那就是c[j][i]再次以垂直方式访问 ，这并不是那么理想。

现在让我们看一下第二个例子：

for (j = 0; j < n; j++) {
    for (k = 0; k < n; k++) {
        val = b[j][k];
        for (i = 0; i < n; i++)
            c[j][i] += val * a[k][i];
    }
}

如果我们查看k本例中的第二个循环，它会开始访问b[j][k]最佳（水平）。此外，它显式地记忆了值 to val，这可能会提高编译器将其移动到寄存器并在接下来的循环中将其保留在那里的可能性（但这与与别名相关的编译器概念有关，而不是 CPU 缓存）。

在最里面的i循环中，我们正在访问c[j][i]哪个也是最佳的（水平）以及a[k][i]哪个也是最佳的（水平）。

因此，第二个版本在实践中可能会更有效。请注意，我们不能绝对这么说，因为积极的优化编译器可以做各种神奇的事情，例如为您重新排列和展开循环。但除此之外，我们应该可以说第二种方法更有效率。

“什么是侧写器？”

我刚刚在评论中注意到这个问题。探查器是一种测量工具，可以为您提供代码中花费时间的精确细分，以及可能的进一步统计信息，例如缓存未命中和分支错误预测。

它不仅有利于优化现实世界的生产代码并帮助您更有效地将工作优先考虑到真正重要的地方，而且还可以加速学习过程，理解为什么在追逐一个又一个热点的过程中会出现效率低下的情况。

循环平铺/阻塞

值得一提的是一种对大型矩阵有用的高级优化技术——循环平铺/阻塞。这超出了本主题的范围，但人们会利用时间局部性。

深度 C 优化

希望以后你能够作为一个深度 C 探索者清楚地了解这些东西。虽然大多数优化最好保留在事后使用分析器进行分析，但当您越来越深入地探索 C 语言时，了解内存层次结构如何工作的基础知识是很有用的。