Edison.X. Blog

這陣子 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 成本較低，其它的暫時想不出來。