作者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/m.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