這陣子 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 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • novus
  • 只有初學者或者速度非主要考量的場合,才會使用每次 new 一個的方式實作 linked list。當然很多人平常沒有實作基礎資料結構的需求,在這方面只要具備入門的基本概念即可,有速度需求時再去深究。

    像我的話,如果是局部使用的小型 linked list,我會考慮用區域陣列一次配足上限,而比較複雜的情形會用 memory pool。

    STL 的容器都有提供一個 allocator 模板選項讓你作這方面的最佳化,而 boost 也有 intrusive container,本身只提供資料結構的機能,但不負責持有物件。

    一般來說,會考慮使用 linked list 通常都是面臨需要頻繁增刪節點、改變順序的情境,使用得當會比 vector 快上非常多。根據我的經驗,如果演算法本來就需要依序存取每個元素,用 node->next 和索引存取的差距其實微不足道。

    最終的 dll/exe 肥大大部分的責任在 linker 身上,要知道 VC6 那個時代要考慮的東西比現在少很多。
  • novus
  • 對了,不知道你在實驗 std::sort 時有沒有比較過這兩個技巧:

    實驗 1.
    bool Compare1(const T& a, const T& b);

    struct Compare2 {
    inline bool operator()(const T& a, const T& b);
    };

    std::sort( ..., Compare1 );
    std::sort( ..., Compare2() );

    實驗 2. 對於比較肥大的物件只排序指標。

    vector<T> objs;
    vector<T*> ptrs; // pointers of objects

    sort(ptrs.begin(), ptrs.end(), cmp);
  • 粗提一下我的實驗結果吧。

    實驗1 有做,但我測試時是用 int , 所以直接調用 std::less,測出來的結果,std::sort(ary, ary+nsize) 和 std::sort(ary, ary+nsize, std::less); 效果幾乎是一樣的。但如果是塞 function pointer 時,執行時間活生生多一倍。16M 整數大小來講,一個是 1468 tickcount, 另一個是 2859 tickcount。

    實驗二就真的沒做了,不過晚點有空就想拉來做了,謝謝 :D

    edisonx 於 2014/01/25 21:15 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼

【 X 關閉 】

【PIXNET 痞客邦】國外旅遊調查
您是我們挑選到的讀者!

填完問卷將有機會獲得心動好禮哦(注意:關閉此視窗將不再出現)

立即填寫取消