为什么迭代 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("%dn", 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类型更改为无符号int以避免未定义的行为。