请问这两段关于 vector 的代码为什么运行时间相差甚大

[RicardoY]

代码如下:

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace chrono;

const int maxn = int(5e7);

vector<int> G[maxn];
vector<int> a;

int main()
{

/*
    for(int i = 0; i < maxn; ++i)
        a.push_back(rand());
*/

    for(int i = 0; i < maxn; ++i)
        G[i].push_back(rand());
    return 0;
}

在 release 编译运行下前者需要 2.8s 后者则需要 7.8s

[shylockhg]

寻址缓存

[RicardoY]

@shylockhg 第二段代码也是在连续的访问数组 cache 命中率应该也不会太低吧

[hmzt]

@RicardoY 第二个数组不同当然不连续啊,不过竟然差别这么大

[shylockhg]

@RicardoY 数组连续,vector 不连续

[0x11901]

是不是因为第一个 vector 事先指定了大小。而另一个先随便蒙了个大小，发现空间不够了就把大小变成 1.5 倍。然后翻倍时发现内存连续空间不足以放下翻倍后的 vector 了之后，又到其他地方 alloc 一段空间，再把原来的数据复制过去，再释放原来位置的内存。反复多次就这样了。

[SAIKAII]

第二个每次 push_back()都分配新的内存吧，第一个是会分配大的内存，不够再重新分配。

[pwrliang]

第一个连续内存访问有加成吧…虽然要扩容

[GeruzoniAnsasu]

拿 clion 的 profiler 跑一下就能很直观地看到差异了

我这边的结果是，

第二种方式 97%的时间花在了一个叫__push_back_slow_path 的过程，这个过程包含了构造，这其中又有 79%的时间完全是在调用 operator new

与之相比，第一种方式仅有非常少量的__push_back_slow_path，推测是扩容时真正的 push_back，而其余所有的 push 都被优化成了 emplace new，只能看到 rand 函数的调用

[GeruzoniAnsasu]

补充一句 STL 的经验谈：

如果你发现某个 STL 容器效率很低，一定是频繁申请释放空间导致的，不要用 STL 的队列或者链表作为高速缓存，除非在使用 c++17 的 pmr allocator 并且你会写基于内存池的 allocator

[ipwx]

因为很多 vector 的实现是，如果 push_back 内存不够，那么就申请 2 倍与现在大小的内存，把现在的元素拷贝进去，然后释放原内存。此外，空的 vector 不申请内存，直到第一个元素放进去，才会申请一块有最小大小的内存。最小大小一般不会是 1。

你的第一种方式，在这个逻辑下，总共申请了 log2(maxn) 次内存。但是第二种方式申请了 maxn 次内存。

申请内存的时间开销不用我说吧？

[ipwx]

顺便地，我上面的分析和 @GeruzoniAnsasu 老哥的实验结果一致。不过话说，我认为这种问题不需要上 profiler，看过 STL 代码或者思考过如何自己实现 vector 的应该都清楚。。。

[kljsandjb]

直观感觉第二个空间局部性不友好吧…

[RicardoY]

@shylockhg 啊我大概明白了

[RicardoY]

@ipwx
@GeruzoniAnsasu
谢谢二位的指点 我想到 push_back 是均摊 O(1)的以后就没有继续思考具体申请内存的次数了...还是太缺乏经验了