为什么迭代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

Answer 1

（g++ -O2）的优化答案：

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

在这种array情况下会发生什么。

main:
        xor     eax, eax
        ret

但是vector分配和释放堆内存使优化变得复杂，并且编译器倾向于安全地将其保留并保留在原处：

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迭代器未内联。因此，与数组访问相比，在调试中访问向量元素会导致额外的间接访问。

Answer 2

我如何编译：

g++ arrVsVec.cpp

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

因为您未在启用优化的情况下进行编译。

此外，您不会将迭代结果用于任何事情，并且整个计算都使用编译时常数输入，因此，即使您确实启用了优化功能，也可能会优化掉循环，然后只能测量动态分配与非动态分配。提示：执行动态分配比执行任何操作都要慢得多。

因此，得出以下结论：

• 由于缺乏优化，未优化的二进制文件速度很慢。测量优化的二进制文件
• 如果打算测量迭代速度，则仅测量迭代；不要衡量内存分配。
• 最好避免编译时间常数输入。
• 使用测量代码的结果，以便无法对其进行优化。

Answer 3

您没有使用结果，而是将向量初始化为零，并且没有启用优化。完成后：

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以避免未定义的行为。