这是一个创建于 2374 天前的主题，其中的信息可能已经有所发展或是发生改变。
代码如下:
#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