为什么我在使用行优先顺序时会看到性能下降？

Question

我有一段代码运行s 在一个大矩阵上并计算按列分箱的统计数据，其中分箱在向量 b 中给出。

代码是这样的：

for (item = 0; item < items; item++) {
    uint8 bin = binvec[item];
    for (col = 0; col < columns; col++) {
        int idx = item * items_stride + col * cols_stride;
        uint8 val = matrix[idx];
        float x = matrix2[idx];
        count[bin][val][col] += x;
    }
}

假设列数在编译时已知。 matrix 的值没有特定的结构/顺序 - 假定为纯随机值。数据量相当大：几百万个项目和数百列。

查看代码，我认为最佳性能将在以下情况下实现：

matrix 是行主要的，为了更好的缓存局部性。
count 将作为 count[bin][col][val] 访问，因此可以优化 count[bin][col] 地址的计算，从而更容易预取等

然而，当我创建 matrix 作为列主，并按照代码中出现的顺序访问 count 时，我获得了最佳性能。

尝试使用选项 (1) 或 (2) 会导致约 50% 运行的时间损失。这违背了我对缓存位置和编译器优化、矢量化等的直觉

知道为什么吗？这真的让我很困惑。

Answer 1

我有点困惑。在您的示例矩阵中，行主要。你能分享这两种实现而不考虑计数访问吗？

你的内部循环遍历列，所以确实行主要会更好，缓存行一次覆盖多个列。

至于计数，您的 val 取决于矩阵中存储的内容，而列是按顺序排列的，因此如果您以这种方式访问计数：

count[bin][val][col]

如果列中有多个连续的行具有相等的值，您将从缓存中获取数据。以这种方式访问它：

count[bin][col][val]

你从缓存中获取数据的机会基本上为零，因为你在递增 col 后跳得太远了。这是我在这部分的最佳选择。

你的矩阵（提供 val 的矩阵）是否像你想象的那样随机？

为什么我在使用行优先顺序时会看到性能下降？

Why do I see a performance drop when using row-major order?

c

optimization

caching

simd

nested-loops