作者Caesar08 (Caesar)
看板C_and_CPP
标题[问题] 在特定条件下，deque与vector的效能比较
时间Wed Mar 2 16:36:11 2016
我已经知道原因了，详情我会发在另一篇
开发平台(Platform): (Ex: VC++, GCC, Linux, ...)
vc++ 14.0
问题(Question)：
原本我都是信奉，如果只是要存放资料，则使用
vector
如果有需要放在头，则使用
deque
如果有需要在中间插入，则使用
forward_list
不过读了GotW #54之後，改变了我一些想法
这边先讲一下我对
vector与
deque的了解
vector的实作，就是一块
连续的记忆体空间
当空间不够时，会跟记忆体要求一个更大的空间，并且
copy or move原本的资料
优点：
1. 记忆体空间是
连续的，可以很快traverse所有资料
2. 如果已经知道需要多少数量，可以使用
reserve，这样不需要再跟记忆体要求空间
3. 承上，不需要
copy or move原本的资料
缺点：
1. 记忆体的使用比较严苛，因为需要是
连续的
2. 如果不知道到时候会需要多少数量，则
resize时容易造成记忆体空间的浪费（当然，
可?
3. 承上，需要
copy or move原本的资料
deque的实作，应该如同这张图一样
http://i.stack.imgur.com/dbPA6.jpg
因此，deque在增大的时候，会跟记忆体要求一个固定size的memory
优点：
1. 记忆体的使用比较不严苛，能更有效利用零碎的空间
2. 在增大的时候，不需要
copy or move原本的资料
缺点：
2. traverse比vector慢
3.
operator[]比vector慢一点点（这影响应该不大）
接下来就是要探讨的问题
1. 假设只需要
存放资料，且
不知道会放几笔资料，那应该是
deque比
vector快（
deque不
需?
2. 假设只需要
存放资料，且
知道会放几笔资料，那应该是
deque比
vector慢（
vector不需
要
但理论只是理论，实际上还是要跑程式才知道，因此我在这边放上我的code
http://ideone.com/LqQbqW
环境：
CPU: intel i7 4930k
OS: windows 7 enterprise sp1, 64 bit
Memory： 64G
Compiler: visual c++ 2015 （vc++ 14.0）
Compiler Option: release, x64, full optimization （/Ox）
输出：
165497（
deque）
331978（
vector没有
reserve）
271584（
vector有
reserve）
回到问题1，
deque的确比
vector快（165497<331978），实验数据符合预期结果
回到问题2，？？？
不对阿，我的test_vector2里面有做
reserve，test_vector2比test_vector快，这很正常
但是test_vector2不可能比test_deque
慢才对啊
如果根据理论分析，
vector只要使用
reserve，他就不可能输给
deque才对
如果问题2的推论是正确的，那为什麽实验数据不符合预期结果呢？
补一台
环境：
CPU: intel i7 4700HQ
OS: windows 10 1511, 64 bit
Memory： 4G
Compiler: gcc 5.2.0
Compiler Option: -std=c++14 -O3
输出：
iteration为5000000（原本的1/20），执行5次取平均
1706
1275
1170
（不符合预期结果）
再补一台：
环境：
同上，除了
Compiler: visual c++ 2015 （vc++ 14.0）
Compiler Option: release, x64, full optimization （/Ox）
输出：
iteration为5000000（原本的1/20），执行5次取平均
2814
2664
2420
（不符合预期结果）
难道在资料没有很多的情况下，
vector比
deque快？
（可是这样很怪，那什麽原因会造成资料很多的情况下，
vector比
deque慢？）
原本是觉得可能跟实作有关，可是最後那两台的数据，都是1>2>3，真是怪了（不过VC的O
x?
code分析：vector的emplace_back（与push_back）的增大
VC++ 14.0：
max(capacity()*1.5,capacity()+1)
gcc 5.2.0：
capacity()+max(capacity(),1)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.161.61.190
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1456907774.A.C67.html
1F：推 chchwy: 我的RAM没那麽大 所以我用比较小的资料集(100万笔)03/02 17:20
2F：→ chchwy: 测出来速度2>1>3 符合理论 但是1,2差距极小03/02 17:20
感谢帮忙
能请教一下你的编译器、编译参数、环境吗？ 谢谢
3F：推 ZanFu5566: 23993 25924 22462 CentOs5 200gb mem gcc5.2.003/02 21:15
4F：→ ZanFu5566: -O303/02 21:15
5F：推 ZanFu5566: 会不会是你这范例程式记忆体需求太高了..?03/02 21:20
恩...，我是想说测多一点比较准，所以才弄那麽高
6F：推 chchwy: 我的参数 VS2013 release /Ox03/02 23:03
7F：推 AIGecko: 系统:Lubuntu15.04 编译器:GCC 4.9.2 参数-std=c++14 -O303/02 23:57
8F：→ AIGecko: 处理器: Pentium 4 631 3.0GHz 记忆体: DDR 4G03/02 23:58
9F：→ AIGecko: 1M次迭代:805/795/747 5M次迭代:4016/4208/373903/03 00:00
10F：→ AIGecko: 最高6M次迭代(再上去就要吃分页):4799/4837/443003/03 00:01
11F：→ AIGecko: 若-O2则是 726/815/762 3954/4170/3759 4797/4936/455003/03 00:06
12F：→ AIGecko: 无优化 1087/1297/1071 5503/7163/5294 6632/8261/644703/03 00:12
感谢各位提供数据
13F：→ nowar100: 优化很多因素可能，如果真的有兴趣，可以profiling，然03/03 09:21
14F：→ nowar100: 後找热区，看组语差在哪，有时候因为刚好打到cache miss03/03 09:21
15F：→ nowar100: 或是什麽unroll开了反而会跟你想的不一样 用猜的没准03/03 09:22
好，那我再研究看看deque内部好了
16F：推 Clangpp: Exceptional C++ 这本跟 effective c++比起来如何??03/03 13:56
effective c++我有整本读完，exceptional c++我是跳着看的 XD
不过effective modern c++很赞，虽然大部分都已经懂了
17F：推 Clangpp: 我目前也还在读effective c++因为看到你再测试Gow的这本03/03 14:41
18F：→ Clangpp: 所以才会问你的03/03 14:42
我之前很无聊的把GotW全部看一遍，首先是放在这网站的
http://herbsutter.com/gotw/
这是新的，建议都看
如果是旧的，建议只看
GotW #54: Using Vector and Deque
GotW #56: Exception-Safe Function Calls
还有这篇文章
http://www.gotw.ca/publications/mill18.htm
其他的GotW，我觉得比较没那麽重要
exceptional c++不太合我口味，但pimpl一定要看
19F：推 Clangpp: 问一下 你vector 应该也可以用swap的技巧来回覆适当大小?03/03 16:29
20F：→ Clangpp: effective STL item 1703/03 16:30
21F：→ Clangpp: 这样就不会有你说的缺点了?? 我请教一下03/03 16:31
swap不会产生第三点问题，但仍然会有第二点问题
因为swap只是把内部的begin, end（记忆体最後一个）, last（现在的最後一个）交换，
因此若另一个vector有使用过多的记忆体，swap後，记忆体使用量仍然不变
※ 编辑: Caesar08 (223.136.12.0), 03/05/2016 11:27:37