我猜 pointer 比較慢是因為其他的 container 在 initialize 時 container_t c(size, 0);
已經填了 size 個 0 了.

int* v = new int[size];
之後應該也要有對應的 fill(v, v+size, 0); 才公平.

Comment by kcwu — March 23, 2008 @ 13:54

@ kcwu,

不是這樣的.

不論 range (pointer, container, etc.) 的種類為何, 也不論 range 內的 integer 在 iterate 之前被填了什麼值. 在 iterate 時都會先被指派為 1, 然後再指派為 0. 而只有 iterate 的部份才有被計時.

小心起見, 我依然照著你說的用 GCC 試了. 結果並沒有差異.

你有用這樣的方法得到不一樣的結果嗎?

Comment by fr3@K — March 23, 2008 @ 17:08

我會這麼猜是因為若只 allocate, 但還未用過, OS 可能會把一些事留到第一次實際使用時才做.

至於我這邊的實驗結果, 無論是否先初始化過, pointer 跟 vector 的速度是差不多的(在測量誤差範圍內), deque 略慢, 但也只差 0.01~0.02 左右, 不像你的有明顯差異.

我的環境是 AMD Athlon XP 1.66G, FreeBSD 8.0-current, gcc 4.2.1

Comment by kcwu — March 28, 2008 @ 0:48

在另一台機器上, 用 VC++ 2005 Express, 編譯參數 cl /O2 /Ox, vector 跟 pointer 用 fill 產生的 asm code 是相同的, 但 pointer 約 0.5 秒, vector 約 0.43 秒. 若加上我說的初始化, 則 pointer 跟 vector 差不多也是 0.43 秒.
(vector loop 產生的 code 不一樣, 比較慢)

Comment by kcwu — March 28, 2008 @ 1:29

我會這麼猜是因為若只 allocate, 但還未用過, OS 可能會把一些事留到第一次實際使用時才做

關於這點, 我想不到有什麼是 OS 可能可以做的, 可否請你舉例?

曾有想過例如說 CPU cache 之類的影響. 但考慮到當迭代的是這麼大的 array (32×1024x1024 integers) , 即便是 vector 最前面的 element 出乎意料地被 cache 住了, 2 MB 的 cache 所能提供的 advantage 可說是非常有限.

用 VC++ 2005 Express, 編譯參數 cl /O2 /Ox, vector 跟 pointer 用 fill 產生的 asm code 是相同的

我能夠想到對 vector iterator 的最佳 performance 優化就是以 pointer 來實作它. 在這個情況下 vector 與 pointer 的 fill 會使用到同一個 fill 的 instance, 你注意到的現象應該就是這個情形.

若加上我說的初始化, 則 pointer 跟 vector 差不多也是 0.43 秒.

在寫完上一個 post 之後, 我手上已經沒有 windows 機器可供測試了. 沒辦法試先把 pointer fill 過的影響. 殘念…

你有在 windows 上試 list 的 debug build 測試嗎? 是否也得到跟我一樣不穩定的數字? (benchmark 3)

Comment by fr3@K — April 6, 2008 @ 7:53