作者NDark (溺於黑暗)
看板C_and_CPP
標題[問題] vector與array效能問題
時間Mon Nov 16 14:54:56 2009
已獲得解答,外加一些測試結果比較請看最後面
原問題:
開發平台 VC++ ( 專案為clr專案,但此部分為un-managed )
不好意思我想詢問一個std::vector與c array效能問題.
我在google上查過這個問題,一般看到的說法都是表示兩者之間效能是一樣好的.
(不管陣列長度會變化這件事情)
但是在我自己的一個專案中測試卻發現c array的花費時間較短.不知道問題是出在哪裡?
說明如下:
1.
我宣告一個class,內含一個std::vector,如下-
class Class
{
public : std::vector< bool > m_vbParam ;
} ;
2.
我宣告一個上述類別的全域變數物件
Class gsObj ;
3.
[此物件已經resize完成,大小大約是10萬左右.(因此是一個10萬長度的bool vector)]
在一個全域函式中透過迴圈access此全域變數的vector,迴圈的index都沒有超過長度
void Func1( void )
{
for( i = 0 ... )
{
gsObj.m_vbParam[ i ] ; // (操作取值及存值)
}
}
計算開始及結束的時間
4.
在另一個全域函式中傳入一個C Array,然後作相同的事情
void Func2( bool *_cArray )
{
for( i = 0 ... )
{
_cArray[ i ] ; // (操作取值及存值)
}
}
計算開始及結束的時間
5.
將bool vector的內容複製給一個c array,並呼叫Func2()
bool *cArray = NULL ;
cArray = new bool[ gsObj.m_vbParam.size() ] ;
for( i = 0 ; i < gsObj.m_vbParam.size() ; i++ )
cArray[ i ] = gsObj.m_vbParam[ i ] ;
// 這邊我本來想用memcpy,可是執行的時候會出錯,煩請指點
void Func2( cArray ) ;
delete [] cArray ;
6.比較Fun1. Fun2.的花費時間(不考慮取得記憶體,複製的時間)
c array的時間 比 std vector快7倍左右.
可能的原因有
A global vs. local : Func1是去使用global變數,Func2是使用傳入的array ptr.
B vector in class : Func1的global物件內部的vector,較array來的麻煩.
C vector vs. array : 長度很長的index下,效能真的有差別.
D 其他.
雖然我覺得是不應該是這些原因,但結果確實如此.不知問題比較可能出在哪裡?
感謝holymars說明,我改用unsigned char vector,就有提升效能了.我分別用
幾種不同的函式參數,測試結果如下:
A.使用std::vector<bool>(原來的舊方法)
B.函式中使用全域物件內的std::vector< unsigned char >成員
FuncB(){ gsObj.m_vParam[ ... ] ... }
C.函式呼叫時傳入std::vector的reference
FuncC( std::vector< unsigned char >& _param ){ _param[ ... ] ... }
D.函式呼叫時傳入由std::vector轉型的unsigned char*
FuncD( unsigned char* _param ){ _param[ ... ] ... }
E.先將std::vector用memcpy複製為unsigned char array.然後傳入
FuncE( unsigned char* _param ){ _param[ ... ] ... }
陣列長度大約在十萬左右,迴圈兩層(遊走總數不超過陣列長度),
迴圈內共有三次取值,三次判斷,一次assign.
花費時間 參考比例
A. 14.93 ms 7.35
B. 3.98 ms 1.96
C. 4.31 ms 2.12
D. 2.03 ms 1
E. 2.26 ms* 1.11
*E方法的時間包含記憶體宣告,複製過去,複製回來,記憶體釋放
--
"May the Balance be with U"(願平衡與你同在)
視窗介面遊戲設計教學(
http://0rz.tw/V28It )，討論，分享。歡迎來信。
視窗程式設計（Windows CLR Form）遊戲架構設計（Game Application Framework）
遊戲工具設計（Game App. Tool Design ）
電腦圖學架構及研究（Computer Graphics）論文代讀(含投影片製作)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.96.77.176
1F：推 holymars:答案是vector<bool>不是一般的std::vector，是特化過的 11/16 15:09
2F：→ holymars:為了節省空間，犧牲了效率 11/16 15:09
3F：→ holymars:vector<bool>是用一個bit一個bit去存bool的 11/16 15:10
4F：→ holymars:喔對了 Effective C++裡面有告訴你不要用vector<bool> 11/16 15:11
5F：→ holymars:因為它其實不符合作為一個STL容器的定義 11/16 15:12
6F：→ NDark:這樣的話.我應該改用其他類別vector來達到我目的? 11/16 15:15
7F：推 holymars:對 你換成vector<int>和int[]再試一次吧 11/16 15:21
8F：→ holymars:vector<bool>是個美麗的錯誤，就和Valarray一樣 11/16 15:22
9F：→ NDark:了解了....我會試看看的, 3q 11/16 15:30
10F：→ NDark:我加一些測試結果...請勿推文 11/16 16:08
11F：→ NDark:完畢.謝謝 11/16 16:29
※ 編輯: NDark 來自: 140.96.77.176 (11/16 16:30)
12F：推 holymars:測試程式是debug build還是release build? optimization 11/16 18:44
13F：→ holymars:的設定參數分別是？ 11/16 18:44
14F：→ NDark:通通都是release,沒有另外設定參數 11/16 19:05
15F：推 yoco315:然後如果你真的很堅持要 bool 的話請用 deque<bool> 11/16 21:16
16F：推 softwind:"std::vector轉型的unsigned char*"? howto? 11/17 00:04
17F：→ NDark:(unsigned char*) &(*ucharvector.begin()) 11/17 09:24