推 holymars:可是這是implementation-dependent11/30 00:15
通常 std 規定是 O(1) 的東西實作都不敢寫太差，不然會被 user 幹死。
其實我懷疑這篇會慢的原因慢在下面紅色的地方：
for( i = 0 ; i < gsObj.m_vbParam.size() ; i++ )
Exceptional C++ 的作者有說過 C++ compiler 很難最佳化這段，
我記得他是微軟的人所以應該 MSVC 也是他說的那樣吧。
推 holymars:剛剛在linux 2.6.31 amd64的機器上用g++ 4.3.4 -O2測11/30 02:10
C++ 程式建議用 -O3。
→ holymars:vector operator[]也是比native array和iterator來得慢11/30 02:10
→ holymars:測試方法是跑陣列的累加，固定跑十萬次 陣列大小random11/30 02:12
→ holymars:決定以避掉array size可能在compile time就被optimize掉11/30 02:12
→ holymars:的情況11/30 02:12
其實你擔心這個的話只要拆不同編譯單元再分別編譯，
讓 GCC 沒辦法同時看到兩邊就可以迴避被最佳化掉。
我也突然間認真了一下寫了測試 (純測 random access)：
main.cxx: http://nopaste.csie.org/66a3a
helper.cxx http://nopaste.csie.org/3e5b1
array size 我設一億，
迴圈我也設定一億次，
取 index 我用 (rand() % 一億) 決定，
陣列沒有初始化應該沒差不重要，
有值就好，
main() 的 return sum1 == sum2 就單純是要強迫 GCC 的 O3 一定要 call 進 foo()。
環境：
OS: Gentoo Linux (kernel: 2.6.30-gentoo-r4) x86_64
CPU: Xeon 5160 x 2 (3.00GHz)
Compiler: gcc version 4.4.2 (Gentoo 4.4.2 p1.0)
編譯：
g++ -std=gnu++0x -O3 -c main.cxx
g++ -std=gnu++0x -O3 -c helper.cxx
g++ -std=gnu++0x -O3 main.o helper.o -o main
-std=gnu++0x 只是我單純想用 <cstdint>，
你不想下的話可以用 <stdint.h>。
執行五次 (上面是傳統 array 下面是 vector)：
15656620 usecs
15083707 usecs
15568634 usecs
15183691 usecs
15544637 usecs
15078708 usecs
15562634 usecs
15151696 usecs
15550636 usecs
15171693 usecs
我看過 asm code 裡面都沒有其它雜質，
連 helper.cxx 的兩個 foo() 的差異也跟前篇講的一樣，
不過最好玩的地方還是...
如果我把 helper.cxx 裡的 sum += v[rand() % size] 改成循序存取，
也就是 sum += v[i]，
差異會更明顯：
513922 usecs
229965 usecs
510923 usecs
229965 usecs
509923 usecs
229965 usecs
506922 usecs
229965 usecs
501924 usecs
229965 usecs
515922 usecs
229965 usecs
我試過改用 clock() 去量時間，
也試過調換兩個 foo() 被 call 的順序，
甚至是程式完全拆開來編成兩個各自跑，
結果都是一樣，
而且時間測量點內的 asm code 兩邊都長差不多，
傳統 array 那邊的 asm code 也沒被塞入其它雜質，
我猜應該跟 Intel 的 CPU 特性有關吧，
沒時間拿 vTune 慢慢看。
雖然我很懷疑是不是我不會量時間或 code 寫錯，
可是目前我自己暫時還看不出來就是了，
找不到錯的話我就當 vector 贏了喔 XD
--
Ling-hua Tseng (uranus@tinlans.org)
Department of Computer Science, National Tsing-Hua University
Interesting: C++, Compiler, PL/PD, OS, VM, Large-scale software design
Researching: Software pipelining for VLIW architectures
Homepage: https://www.tinlans.org
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.111.116
※ 編輯: tinlans 來自: 118.160.111.116 (11/30 10:51)
推 littleshan:很有趣，我也測出一樣的結果 11/30 11:42
→ littleshan:另外我把 v2[0] 的位址直接餵給 array 版本的 foo 11/30 11:43
→ littleshan:跑出來的速度也比 v1 快 11/30 11:43
→ tinlans:我是在猜有沒有可能 vector 的初始化動作會把裡面的值 11/30 14:12
→ tinlans:load 到 cache 去。 11/30 14:12
→ tinlans:然後 random access 有賺到一點點，其它 miss，sequential 11/30 14:14
→ tinlans:因為 hit rate 比較大造成贏一倍。 11/30 14:14
→ tinlans:如果不是定義完馬上就用的話，或許就會輸一點了，畢竟多了 11/30 14:16
→ tinlans:一道 instruction 在 loop 裡。 11/30 14:16
推 littleshan:我看過用 gcc4.3 編出來的 assembly 11/30 14:20
→ littleshan:inline 過之後，vector 版本只多了一道 mov 指令 11/30 14:21
→ littleshan:而且是在迴圈「外」 11/30 14:21
→ littleshan:其它部份完全相同 11/30 14:21
→ tinlans:原來是我 label 看歪了，之前看還以為在裡面 XD 11/30 15:30
→ tinlans:有空我來測試一下再造一個 size 一億的 vector 在中間好了 11/30 15:31
→ tinlans:，看能不能洗掉 cache。 11/30 15:31
→ tinlans:測完了，數據還是不變，真神奇。 11/30 19:06
推 holymars:把foo(int64_t* v, size_t size)改成傳reference to ptr 12/01 04:56
→ holymars:的話，應該可以編出完全一樣的assembly 12/01 04:56
→ holymars:一模一樣的asm跑起來速度會差到兩倍也太神奇了@_@ 12/01 04:57
推 holymars:這等於說只因為記憶體起始位址不同，cache miss變兩倍XD 12/01 05:09
→ holymars:剛剛試了一下讓 v1 = &v2[0]; 去跑的話，就一樣快.. 12/01 05:10
推 holymars:看了一下ASM code，sequential的optimize居然動用到xmm0 12/01 05:38
→ holymars:一次讀兩個int64存進128 bit裡面一起加 等出了迴圈才把 12/01 05:39
→ holymars:xmm register的前64bit和後64bit加起來 囧... 12/01 05:39
推 holymars:我發現問題了..v1 new出來之後沒有initialize過... 12/01 06:08
→ holymars:你先把v1 memset一次再去跑 結果就會一樣快了 12/01 06:09
推 holymars:所以問題是在OS的memory model上.. 12/01 06:14
推 yoco315:大家都好認真 qq 12/01 20:30
→ tinlans:所以是跟內容值有關，影響加法的速度嗎？真有趣 XD 12/02 09:01
推 holymars:不是@@ 你initialize成5566也不會跑比較慢啊XD 12/02 10:38
推 holymars:應該是page在第一次access的時侯會有一些overhead 12/02 10:50