c++ - std::vector 中的每个元素访问都是缓存未命中吗？

Question

众所周知，std::vector 将其数据保存在堆上，因此 vector 本身的实例和第一个元素具有不同的地址。另一方面，std::array 是原始数组的轻量级包装器，其地址等于第一个元素的地址。

让我们假设集合的大小足以容纳 int32 的一个缓存行。在我有 384kB L1 缓存的机器上它是 98304 个数字。

如果我迭代 std::vector，我总是首先访问 vector 本身的地址，然后访问下一个元素的地址。并且可能这个地址不在同一个缓存行中。所以每次元素访问都是缓存未命中。

但如果我迭代 std::array 地址在同一个缓存行中，那么它应该更快。

我用 VS2013 进行了全面优化测试，std::array 快了大约 20%。

我的假设是否正确？

更新:为了不创建第二个类似的主题。在这段代码中，我有一个数组和一些局部变量:

void test(array<int, 10>& arr)
{
    int m{ 42 };

    for (int i{ 0 }; i < arr.size(); ++i)
    {
        arr[i] = i * m;
    }
}

在循环中，我正在访问一个数组和一个堆栈变量，它们在内存中彼此相距很远。这是否意味着每次迭代我都会访问不同的内存并错过缓存？

Answer 1

您所说的许多事情都是正确的，但我不相信您看到缓存未命中的速度与您认为的一样。相反，我认为您看到了编译器优化的其他效果。

你是对的，当你在 std::vector 中查找一个元素时，有两个内存读取:首先，内存读取指向元素的指针；其次，读取元素本身的内存。但是，如果您对 std::vector 进行多次顺序读取，那么您执行的第一次读取很可能会在元素上发生缓存未命中，但所有后续读取都将在缓存中或不可避免。内存缓存针对引用位置进行了优化，因此每当将单个地址拉入缓存时，大量相邻的内存地址也会拉入缓存。因此，如果您遍历 std::vector 的元素，大多数时候你根本不会有任何缓存未命中。性能看起来应该与常规阵列的性能非常相似。还值得记住的是，缓存存储多个不同的内存位置，而不仅仅是一个，因此您正在读取堆栈中的内容(std::vector 内部指针)和堆中的内容(元素)，或两个堆栈上的不同元素不会立即导致缓存未命中。

要记住的是，与缓存命中相比，缓存未命中极其代价高昂——通常慢 10 倍——所以如果你确实在 std::vector 的每个元素上看到缓存未命中您不会看到只有 20% 的性能差距。您会看到更接近 2 倍或更大的性能差距。

那么，为什么您会看到性能差异？您尚未考虑的一个重要因素是，如果您使用 std::array<int, 10> ，然后编译器可以在编译时告诉数组中恰好有十个元素，并且可以展开或以其他方式优化您必须消除不必要检查的循环。事实上，编译器原则上可以用 10 个连续的代码块替换循环，这些代码块都写入一个特定的数组元素，这可能比在循环中重复向后分支要快得多。另一方面，等效代码使用 std::vector ，编译器无法总是提前知道循环将运行多少次，因此它很可能无法生成与它为数组生成的代码一样好的代码。

事实上，您在此处编写的代码非常小，任何对其计时的尝试都会产生大量噪音。很难评估这有多快可靠，因为与方法的“冷”运行相比，将它放入 for 循环这样简单的事情会搞乱缓存行为。

总的来说，我不会将此归因于缓存未命中，因为我怀疑缓存未命中的数量是否存在明显差异。相反，我认为这是对数组的编译器优化，与对 std::vector 的优化相比，其大小是静态已知的。 s 的大小只能动态知道。