时间戳

首页 > 解决方案 > 为什么迭代 std::array 比迭代 std::vector 快得多？

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

问题描述

编者注：
启用优化的后续问题仅对循环进行计时：
为什么通过`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

标签： c++linuxperformancemicrobenchmark

解决方案

( ) 上的优化答案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迭代器没有被内联。因此，与数组访问相比，在调试中访问向量元素会产生额外的间接性。

推荐阅读