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

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

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

如果我迭代std::vector事实证明，我总是首先访问向量本身的地址，然后访问下一个元素的地址。并且这些地址可能不在同一缓存行中。因此，每个元素访问都是缓存未命中。

但如果我迭代std::array地址位于同一高速缓存行中，因此应该更快。

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

我的假设正确吗？

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

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

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

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

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

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

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

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

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

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