c - C语言中的缓存性能(关于循环)

Question

我在想，为什么一组循环允许比另一组循环更好的缓存性能，尽管逻辑上做了相同的事情？

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;
    }
}

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千字节的页面，并向下移动到少量的64位通用寄存器）。第一个示例在逐出之前立即从这样一个连续的块访问所有数据。
harold在这个网站上，我对如何看待和解释这个问题有了一个很好的看法，建议不要太关注缓存未命中，而应该在逐出之前努力使用缓存中的所有数据。第二个例子没有做到这一点，除了最琐碎的小图像，通过垂直迭代图像与一个大的，扫描线大小的步幅，而不是水平与一个小的，像素大小的步幅。
此外，当我们增加块大小，但保持缓存大小和关联性不变时，它是否会影响未命中率？在某一点上增加块大小会导致更高的未命中率，对吧？
这里的答案是“是”，因为块大小的增加自然会等同于更多的强制未命中（虽然更简单地说是“未命中”，而不是“未命中率”），但也只是需要处理更多的数据，这些数据不一定都适合最快的一级缓存。如果我们以一个很大的步幅访问大量数据，那么在使用缓存之前，会有更多的数据被逐出缓存，从而获得更高的非强制未命中率，结果却会冗余地将其重新加载到一个更快的缓存中。
还有一种情况是，如果块大小足够小并且正确对齐，那么所有数据将只适合于一个缓存线，而我们如何顺序地访问它就无关紧要了。
矩阵乘法
现在，您的示例比上面这个简单的图像示例要复杂得多，但是相同的概念往往也适用。
让我们看看第一个：

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]，同样是以一种垂直的方式，这不是最佳的。
现在让我们看一下第二个例子：

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];
    }
}

在这种情况下，如果我们看第二个 j循环，它开始访问 c[j][i]这是最佳的（水平的）。此外，它还显式地将值记为 k，这可能会提高编译器将该值移到寄存器并保留在该寄存器中以供后续循环使用的可能性（不过，这涉及与别名相关的编译器概念，而不是CPU缓存）。
在最里面的 b[j][k]循环中，我们访问的 val也是最优的（水平的），而 i也是最优的（水平的）。
所以第二个版本在实践中可能更有效。请注意，我们不能完全这么说，因为积极的优化编译器可以为您做各种神奇的事情，如重新排列和展开循环。然而，除此之外，我们应该可以说第二种方法更有效率。
“什么是轮廓仪？”
我刚在评论中注意到这个问题。profiler是一种度量工具，它可以为您提供代码中时间的精确分解，以及可能的进一步统计信息，如缓存未命中和分支预测失误。
它不仅有助于优化现实世界的生产代码，并帮助你更有效地将你的努力放在那些真正重要的地方，而且还可以加速学习过程，了解为什么一个接一个地追逐一个热点的过程中存在低效。
循环平铺/阻塞
值得一提的是一种先进的优化技术，它可以用于大型矩阵——循环平铺/阻塞。它超出了这个主题的范围，但它起到了时间局部性的作用。
深C优化
希望以后你能像一个深入的C探险家一样清楚地把这些东西C起来。虽然大多数优化最好是在事后用一个分析工具来保存，但是当您越来越深入地研究C时，了解内存层次结构的基本工作原理是很有用的。