[問題] 在特定條件下，deque與vector的效能比較

[Caesar08 (Caesar)]

我已經知道原因了，詳情我會發在另一篇

開發平台(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://www.ptt.cc/bbs/C_and_CPP/M.1456907774.A.C67.html
推 chchwy: 我的RAM沒那麼大 所以我用比較小的資料集(100萬筆)
→ chchwy: 測出來速度2>1>3 符合理論 但是1,2差距極小
感謝幫忙
能請教一下你的編譯器、編譯參數、環境嗎？ 謝謝

推 ZanFu5566: 23993 25924 22462 CentOs5 200gb mem gcc5.2.0
→ ZanFu5566: -O3
推 ZanFu5566: 會不會是你這範例程式記憶體需求太高了..?
恩...，我是想說測多一點比較準，所以才弄那麼高

推 chchwy: 我的參數 VS2013 release /Ox
推 AIGecko: 系統:Lubuntu15.04 編譯器:GCC 4.9.2 參數-std=c++14 -O3
→ AIGecko: 處理器: Pentium 4 631 3.0GHz 記憶體: DDR 4G
→ AIGecko: 1M次迭代:805/795/747 5M次迭代:4016/4208/3739
→ AIGecko: 最高6M次迭代(再上去就要吃分頁):4799/4837/4430
→ AIGecko: 若-O2則是 726/815/762 3954/4170/3759 4797/4936/4550
→ AIGecko: 無優化 1087/1297/1071 5503/7163/5294 6632/8261/6447
感謝各位提供數據

→ nowar100: 優化很多因素可能，如果真的有興趣，可以profiling，然
→ nowar100: 後找熱區，看組語差在哪，有時候因為剛好打到cache miss
→ nowar100: 或是什麼unroll開了反而會跟你想的不一樣  用猜的沒準
好，那我再研究看看deque內部好了

推 Clangpp: Exceptional C++ 這本跟 effective c++比起來如何??
effective c++我有整本讀完，exceptional c++我是跳著看的 XD
不過effective modern c++很讚，雖然大部分都已經懂了

推 Clangpp: 我目前也還在讀effective c++因為看到你再測試Gow的這本
→ Clangpp: 所以才會問你的
我之前很無聊的把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一定要看

推 Clangpp: 問一下 你vector 應該也可以用swap的技巧來回覆適當大小?
→ Clangpp: effective STL item 17
→ Clangpp: 這樣就不會有你說的缺點了?? 我請教一下
swap不會產生第三點問題，但仍然會有第二點問題
因為swap只是把內部的begin, end（記憶體最後一個）, last（現在的最後一個）交換，
因此若另一個vector有使用過多的記憶體，swap後，記憶體使用量仍然不變
※ 編輯: Caesar08 (223.136.12.0), 03/05/2016 11:27:37