這陣子 trace 一些老專案,發現一些效能上的議題,記性不好,僅做筆記。然後老專案是用 vc6 開發的,裡面一些常用的東西拉出來實測後真的是讓人暈倒。

有些議題可能必須開文慢慢紀錄,但實在沒太多時間撰 blog, 只好先把想法記錄下來。

 

1. C++ STL vs MFC ATL 

(1) CArray<int, int> 速度比 vector<int> 還慢 ,而且慢不少。

(2) STL 裡面有提供 <algorithm> , 但 MFC 裡之 ATL container 真的單純只是資料結構而已,其他要做排序、搜尋、有的沒的就.. 嗯。

(3) ATL 裡面只有 CMap , 但沒有 CMultiMap (明明 multimap 是常用的 container ,真想不透為什麼 MFC 沒做)。

 

2. 效率部份

(1) qsort  : C library qsort 函式我在 vc6 / vc2010 上測過,這支函式效能很差,自己重刻隨便寫一支 qsort 都比較快,細節原因我沒追下去,但猜可能我沒用 function pointer 做 compare 關係。

(2) recursive opt : 這點必須稱讚了。測了 binary search 遞回版 / binary search 非遞回版;自己寫的 qsort 一般版 / qsort M3 法則版 / qsort M3 法則 + 去一層遞迴版,有沒有 recursive 效能其實都差不多 ( 沒再細分析,估可能被編譯器去遞迴優化掉了 )。

(3) sort : c++ 裡,在 <algorithm> 裡之 sort 大多為人所稱讚,所以早期我也常用這東西做排序 (畢竟手邊資料很少要求一定要 stable)。尷尬的事情是,vc6 的 std::sort 速度慢到爆,好一點的排序法都可以打掉它,換到 2010 再測過之後就真的是神快了。

 

3. 非關語言 / 其他部份

 

目前還有摸索較有效率的 link-list 實做方式, 及 bucket 之資料結構, re-search 並沒找到合適的文章閱讀。

 

(1) vs2010 編出來的 dll 特大

同一份 dll 用 release 編譯,vc6.0 編出來只有數十到數百 KB;換 vs2010 編完後變數十 MB。目前找過網路的一些 solution   無有效方案解決。

 

(2) bucket 資料結構

目前我是用 vector< list<Type> > 方式去做,不過後來想想用 vector< vector<Type> > 好像也還不錯,差異在 vector<> 沒辦法做 pop_front,所以要循序取出的時候,只好再多一個 vector<size_t> vbeg 去記錄每個 bucket 目前取到了哪些元素做取代。

 

* (3) 有效率的 link-list 

這點我覺得自己有點掉到邏輯缺陷裡,或者說我已不知道我的想法到底算不算是 "有效率" 的做法。

以 single link 而言,一般教科書上(其實 SGI 使用的策略也差不多) 寫的 link-list 是每次要新增一個 node 時才做 allocate 動作 (所以可能間接付出物件之 ctor 成本);要刪除時是直接一個一個 node 做 release 。

換個角度想,如果一次就先 allocate 10 個 node , 全都串接起來的話,不就省了很多 allocate 動作 ?如果 node 超過 10 個的話就再多 allocate 新的 10 個 node 就好了,效率應該會較好?奇怪,上述整個 allocate 的動作不就整個和 vector 很像? 大概長這樣 (去 template)

 

struct node {
    int data;
    node *nxt;
};

class slist {
private:
    node *m_phead;  // linklist 開頭
    vector<node*> alloc_ptr; // 每次 new 之傳回值
public:
    // whatever..
};

 

 

只要每次新增了 10 個 node 時,便將 new 之傳回值放入 alloc_ptr ,在 ctor 時只需對 alloc_ptr 逐一做釋放即可,這樣 list 不就可再支援足標運算子( subscript operator ) 了?重點是如果要循訪每個元素,用 node->nxt 這方式慢到爆 (當然我知道有些情況就是非得這樣跑沒錯),直接算記憶體位置不是比較快? 優點的話... 嗯,node swap 、pop_front 成本較低,其它的暫時想不出來。

創作者介紹
創作者 edisonx 的頭像
edisonx

Edison.X. Blog

edisonx 發表在 痞客邦 留言(2) 人氣()