为什么迭代一个std::array比迭代一个std::vector快得多？

Question

编辑注：
启用优化后仅计时循环的后续问题：
为什么迭代 std::vector 比迭代 std::array 更快？
在这里，我们可以看到惰性分配页面错误对于读取未初始化 BSS 内存与动态分配的+写入内存的影响，它们在定时循环之外进行了初始化。

---

我尝试过对这段代码进行性能分析：

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

using namespace std;

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

int main()
{
    int res = 0;
    for(int x : v)
        res += x;
    printf("%d\n", res);
}

在我的电脑上，array 版本比 vector 快。

在这种情况下，内存分配是不相关的，因为它只发生一次。

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

real    0m0,445s
user    0m0,203s
sys 0m0,238s

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

real    0m0,749s
user    0m0,273s
sys 0m0,476s

我发现对于std::vector而言，反汇编要复杂得多：https://godbolt.org/z/111L5G

- tuket

---

你使用的是什么操作系统和编译器版本？“发布模式”是什么意思，使用了哪些编译标记？最重要的是，你是如何测量时间的？ - rustyx

你正在测量分配向量所需的时间，这是相当不可忽视的。分配std::array是免费的（需要零时间）。 - Galik

使用 g++ -O3 arrVsVec.cpp 进行编译。非优化的“基准测试”完全没有价值。 - M.M

你有没有读懂问题？我提到了内存分配是无关紧要的。这只发生一次。在这个例子中，reserve没有任何意义，因为我已经一次性分配了所有的内存。 - tuket

这是一个很好的基准测试（http://quick-bench.com/W3-XzeICyU7goJuUV2AD0NKwRNo）。 - BiagioF

Answer 1

优化(g++ -O2)的答案：

您没有使用最终结果，因此编译器可以自由地将整个循环进行优化。

这就是在array情况中发生的事情。

main:
        xor     eax, eax
        ret

但是向量会分配和释放堆内存，这会使优化变得复杂，并且编译器倾向于采取保守策略将其保留在原地:

main:
        xor     eax, eax
        ret
_GLOBAL__sub_I_v:
        sub     rsp, 8
        mov     edi, 400000000
        mov     QWORD PTR v[rip], 0
        mov     QWORD PTR v[rip+8], 0
        mov     QWORD PTR v[rip+16], 0
        call    operator new(unsigned long)
        lea     rdx, [rax+400000000]
        mov     QWORD PTR v[rip], rax
        mov     QWORD PTR v[rip+16], rdx
.L6:
        mov     DWORD PTR [rax], 0
        add     rax, 4
        cmp     rdx, rax
        jne     .L6
        mov     QWORD PTR v[rip+8], rdx
        mov     esi, OFFSET FLAT:v
        mov     edx, OFFSET FLAT:__dso_handle
        mov     edi, OFFSET FLAT:_ZNSt6vectorIiSaIiEED1Ev
        add     rsp, 8
        jmp     __cxa_atexit

因此，在这种情况下，array版本更快。在更实际的应用中，差别不会那么明显，主要取决于vector情况下堆分配/释放时间。

关闭优化（g ++）的答案：

不要对未经优化编译的内容进行基准测试。

差别可能是由于vector迭代器没有被内联造成的。所以在调试模式中访问向量元素会比数组访问多一个间接层。

- rustyx

---

重点是使用 std::array 版本实际上是一种未定义行为。您（即 OP）正在对一堆未初始化的值求和。结果，这个基准测试是完全无用的。 - BiagioF

@BiagioFesta 实际上不是这样的。它具有静态存储，因此被初始化为零。 - eerorika

你是对的，在反汇编中显示函数没有被内联。 - tuket

@tuket和rustyx：使用-stdlib=libc++而不是默认的libstdc++编译选项的clang++可以优化掉std::vector的new/delete或构造/析构。不确定是否适用于全局范围内的向量。这是一个棘手的优化，因为在ISO C++中，“new”是“可替换的”，所以除非标准中的语言消除了这种可能性，否则“new”可以被认为是可见的副作用。但是，+1不要对调试模式进行基准测试。C++标准库严重依赖于优化编译器的积极内联。 - Peter Cordes

Answer 2

How I compile:

g++ arrVsVec.cpp

Why is iterating an std::array much faster than iterating an std::vector?

因为您没有开启优化编译。此外，您没有使用迭代结果，整个计算中使用的都是编译时常量输入，所以即使您启用了优化，循环也可能被优化掉，然后你只能测量动态分配与不分配之间的差异。提示：执行动态分配比什么都不做要慢得多。因此，总结如下：

• 由于缺乏优化，未优化的二进制文件速度较慢；请测量优化后的二进制文件。
• 如果您想测量迭代速度，请仅测量迭代时间；不要测量内存分配。
• 尽量避免编译时常量输入。
• 使用测量代码的结果来防止其被优化删除。

- eerorika

Answer 3

你没有使用result，而是将向量初始化为零，并且你没有启用优化。一旦你这样做了：

int main()
{
    unsigned int res = 0;
    for(int &x : v)
        x = rand();

    for(int i = 0; i < 128; ++i) {
        for(int x : v)
            res += (unsigned int)x;
    }
    std::cout << res;
}

时钟是相同的：

Success #stdin #stdout 0.62s 54296KB
-2043861760
Success #stdin #stdout 0.62s 54296KB
-2043861760

编辑：将 res 类型更改为 unsigned int 以避免未定义的行为。

- Radosław Cybulski

---

算术溢出具有未定义的行为。这是您的随机值可能出现的情况。 - eerorika

你对未定义行为的看法是正确的，但是当改为“unsigned int”时，结果仍然保持不变。 - Radosław Cybulski