是否每个元素都在std :: vector中访问缓存？

Question

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

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

如果我迭代std::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

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

你是对的,当你在a中查找一个元素时std::vector,有两个内存读取:首先,读取指向元素的指针的内存; 第二,读取元素本身的内存.但是,如果你std::vector对它进行多次顺序读取,那么你可能会在第一次读取时对元素进行缓存未命中,但所有连续读取都将在缓存中或不可避免.内存缓存针对引用的局部性进行了优化,因此每当将单个地址拉入缓存时,大量相邻的内存地址也会被拉入缓存.因此,如果迭代a的元素std::vector,大多数时候根本不会有任何缓存未命中.性能应该与常规数组非常相似.还值得记住的是,缓存存储了多个不同的内存位置,而不仅仅是一个,因此您正在读取堆栈中的内容(std::vector内部指针)和堆中的某些内容(元素)或两个不同的元素堆栈,不会立即导致缓存未命中.

要记住的是,与缓存命中相比,缓存未命中是非常昂贵的 - 通常慢10倍 - 因此,如果您确实在每个元素上看到缓存未命中,那么std::vector您将看不到性能差距仅为20%.你会看到更接近2倍或更大性能差距的东西.

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

然后就是这样的事实,你在这里写的代码是如此之小,以至于任何计时的尝试都会产生大量的噪音.要评估它的可靠速度是很困难的,因为与方法的"冷"运行相比,将它放入for循环这样简单的事情会使缓存行为陷入混乱.

总的来说,我不会将此归因于缓存未命中,因为我怀疑它们的数量明显不同.相反,我认为这是阵列上的编译器优化,其大小是静态已知的,而std::vectors的优化只能动态地知道.