c++ - 为什么迭代 `std::vector` 比迭代 `std::array` 更快？

Question

我最近问了这个问题: Why is iterating an std::array much faster than iterating an std::vector?

正如人们很快指出的那样，我的基准测试有很多缺陷。因此，当我试图修复我的基准时，我注意到 std::vector 并不比 std::array 慢，事实上，它恰恰相反.

#include <vector>
#include <array>
#include <stdio.h>
#include <chrono>

using namespace std;

constexpr int n = 100'000'000;
vector<int> v(n);
//array<int, n> v;

int main()
{
    int res = 0;
    auto start = chrono::steady_clock::now();
    for(int x : v)
        res += x;
    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    double elapsed =
        std::chrono::duration_cast<
            std::chrono::duration<double, std::milli>
        >(end - start).count();
    printf("result: %d\ntime: %f\n", res, elapsed);
}

我在之前的基准测试中尝试改进的地方:

• 确保我使用的是结果，所以整个循环没有被优化掉
• 使用 -O3 标志提高速度
• 使用std::chrono 代替time 命令。这样我们就可以隔离我们想要测量的部分(只是 for 循环)。变量的静态初始化和类似的东西不会被测量。

测量时间:

数组:

$ g++ arrVsVec.cpp -O3
$ ./a.out
result: 0
time: 99.554109

vector :

$ g++ arrVsVec.cpp -O3
$ ./a.out
result: 0
time: 30.734491

我只是想知道这次我做错了什么。

Watch the disassembly in godbolt

Answer 1

差异是由于 array 的内存页面不驻留在进程地址空间中(全局范围数组存储在尚未分页的可执行文件的 .bss 部分， it is zero-initialized )。而 vector 刚刚被分配和零填充，所以它的内存页面已经存在。

如果你添加

std::fill_n(v.data(), n, 1); // included in <algorithm>

作为 main 的第一行将页面引入(故障前)，这使得 array 的时间与 vector 的时间相同>.

---

在 Linux 上，您可以执行 mlock(v.data(), v.size() * sizeof(v[0])); 将页面放入地址空间。有关详细信息，请参阅 man mlock。