这是一个创建于 2040 天前的主题，其中的信息可能已经有所发展或是发生改变。
代码如下:
#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
 |
1
shylockhg 2019-04-22 10:27:48 +08:00
寻址缓存
|
 |
5
0x11901 2019-04-22 11:48:17 +08:00
是不是因为第一个 vector 事先指定了大小。而另一个先随便蒙了个大小，发现空间不够了就把大小变成 1.5 倍。然后翻倍时发现内存连续空间不足以放下翻倍后的 vector 了之后，又到其他地方 alloc 一段空间，再把原来的数据复制过去，再释放原来位置的内存。反复多次就这样了。
|
 |
6
SAIKAII 2019-04-22 12:01:58 +08:00 via Android
第二个每次 push_back()都分配新的内存吧，第一个是会分配大的内存，不够再重新分配。
|
 |
7
pwrliang 2019-04-22 13:48:10 +08:00 via Android
第一个连续内存访问有加成吧…虽然要扩容
|
 |
8
GeruzoniAnsasu 2019-04-22 14:08:30 +08:00
拿 clion 的 profiler 跑一下就能很直观地看到差异了
我这边的结果是， 第二种方式 97%的时间花在了一个叫__push_back_slow_path 的过程，这个过程包含了构造，这其中又有 79%的时间完全是在调用 operator new 与之相比，第一种方式仅有非常少量的__push_back_slow_path，推测是扩容时真正的 push_back，而其余所有的 push 都被优化成了 emplace new，只能看到 rand 函数的调用 |
|
9
GeruzoniAnsasu 2019-04-22 14:15:14 +08:00
补充一句 STL 的经验谈：
如果你发现某个 STL 容器效率很低，一定是频繁申请释放空间导致的，不要用 STL 的队列或者链表作为高速缓存，除非在使用 c++17 的 pmr allocator 并且你会写基于内存池的 allocator |
 |
10
ipwx 2019-04-22 14:51:26 +08:00
因为很多 vector 的实现是，如果 push_back 内存不够，那么就申请 2 倍与现在大小的内存，把现在的元素拷贝进去，然后释放原内存。此外，空的 vector 不申请内存，直到第一个元素放进去，才会申请一块有最小大小的内存。最小大小一般不会是 1。
你的第一种方式，在这个逻辑下，总共申请了 log2(maxn) 次内存。但是第二种方式申请了 maxn 次内存。 申请内存的时间开销不用我说吧？ |
|
11
ipwx 2019-04-22 14:56:47 +08:00
顺便地，我上面的分析和 @GeruzoniAnsasu 老哥的实验结果一致。不过话说，我认为这种问题不需要上 profiler，看过 STL 代码或者思考过如何自己实现 vector 的应该都清楚。。。
|
 |
12
kljsandjb 2019-04-22 14:58:15 +08:00 via iPhone
直观感觉第二个空间局部性不友好吧…
|
 |
14
RicardoY OP |
Select Language