這個實驗在電腦裡躺了一段時間了,雖然不是很有價值的實驗,但想說既然做了不如就整理一下放上來吧。

大約兩個月前在 xkcd 上看到有位仁兄挑戰既有的資料結構常識「假使只查詢而不需要更新資料,使用排序陣列搭配二分搜尋,效能通常會勝過複雜精巧的二元搜尋樹」。這位仁兄很意外的發現,用 std::lower_bound 對排序過的 vector 做二分搜尋比 map 還慢。他提供的程式很快被網友點出兩個錯誤:

  • 他使用 rand() 產生 key。由於 map 只會保留獨一無二的 key,因此當資料量超過 rand() 重複週期之後,map 的元素明顯少於 vector。
  • 他使用 pair 預設的 operator<。但 pair 預設的 operator< 不只會比較 first,還會比較 second,因此 map 的比較運算比較廉價。

我認為他還有一個非常重要的缺失卻沒有人提起:他完全依序搜尋,但是對資料結構進行測速,順序會影響快取率(想想看,日常應用比較容易出現哪種順序)。 所以我才會做以下的實驗來印證想法。請注意本實驗的重點不在於測速,而是在於指出一般人測速時常忽略的現象,所以不要拿本篇作為選擇編譯器/資料結構的唯一依據。他的程式並不是很好讀,所以我做了改寫並額外增加以下部份:

  • 加入隨機搜尋作為依序搜尋的對照,這是本實驗的目的。
  • 加入了原生陣列作為 vector 的對照。
  • 加入以 string 為 Key 的部份
  • 實作了不同版本的二分搜尋。大家都知道二分搜尋有兩種實作方式,第一種是嚴格二分,第二種將等於也分成一類,通常第二種會比第一種少一些比較次數,但複雜度是同等級的。我的第一個二分搜尋直接抄自 GCC 的 std::lower_bound,這是一種嚴格二分搜尋,唯一的差別是將 advance 和 distance 改為直接指標運算。
  • 改掉依賴 C++11 的語法,並改寫輸出格式以便導出資料與繪圖自動化。

我在 32 位元 Win7 環境下分別以 GCC 和 VC++ 2008 進行實驗:GCC 的編譯選項是「-O2 -flto -fwhole-program -s」,VC++ 用的是 CMake 自動生成的 Release 組態。篇幅有限,一些實驗中發現的有趣現象就留給有心人去探索。這裡只提一點,在 GCC 下交叉套用演算法時,vector::iterator 效能和原生指標幾乎沒有差別;但是在 VC 下 vector::iterator 慢到了一種非常誇張的地步,不曉得是編譯器還是程式庫實作的問題。(我沒手動關閉 VC 的 checked iterator,但也有一些跡象讓我懷疑編譯器)

以下我讓 vector 套用嚴格二分搜尋,而原生指標採用考慮等號的二分搜尋,請記住在 GCC 下套用相同演算法時兩者幾乎是一樣的。部份實驗的結果如下,在隨機搜尋的情況下陣列明顯比 map 快,不過依序搜尋的情況下 map 有時會快很多,雖然我大概知道這是快取效應造成的,但並沒有繼續深究細部的原因。如果你覺得我的程式碼犯了哪些錯誤也歡迎提出來討論,雖然我最近不是很有空回應。

GCC-int gcc-string 

 

msvc9-int msvc9-string  


#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;

//#define USE_STRING_KEY 1

#ifdef USE_STRING_KEY
typedef string Key;
#else
typedef int Key;
#endif

typedef pair<Key, unsigned> Pair;
typedef map<Key, unsigned> Map;
typedef vector<Pair> Vector;

const int TEST_COUNT = 50000000;

struct Less1st {
    inline bool operator()(const Pair& lhs, const Pair& rhs) const {
        return lhs.first < rhs.first;
    }
};

struct TriComp1st {
    inline int operator()(const pair<string, unsigned>& lhs,
                          const pair<string, unsigned>& rhs) const {
        return strcmp(lhs.first.c_str(), rhs.first.c_str());
    }
    inline int operator()(const pair<int, unsigned>& lhs,
                          const pair<int, unsigned>& rhs) const {
        return lhs.first - rhs.first;
    }
};

template <class RandIter, class T, class Comp>
RandIter BinSearch1(RandIter first, RandIter last, const T& target, Comp cmp) {
    typedef typename iterator_traits<RandIter>::difference_type Diff;
    Diff len = last - first;

    while (len > 0) {
        Diff half = len >> 1;
        RandIter mid = first + half;

        if (cmp(*mid, target)) {
            first = mid;
            ++first;
            len = len - half - 1;
        } else {
            len = half;
        }
    }
    return (first != last && first->first == target.first)? first : last;
}

template <class RandIter, class T, class TriComp>
RandIter BinSearch2(RandIter first, RandIter last, const T& target, TriComp cmp) {
    RandIter notFound = last, mid;

    while (first <= last) {
        mid = first + ((last - first) >> 1);
        int r = cmp(*mid, target);
        if (r < 0) {
            first = mid + 1;
        } else if (r > 0) {
            last = mid - 1;
        } else {
            return mid;
        }
    }
    return notFound;
}

inline Pair* RawFind(Pair* first, Pair* last, const Pair& target) {
    return BinSearch2(first, last, target, TriComp1st());
}

inline Vector::const_iterator VecFind(const Vector& v, const Pair& target) {
    // return BinSearch2(v.begin(), v.end(), target, Less1st());
    Vector::const_iterator it = lower_bound(v.begin(), v.end(), target, Less1st());
    return (it != v.end() && it->first == target.first)? it : v.end();
}

inline Map::const_iterator MapFind(const Map& m, const Pair& target) {
    return m.find(target.first);
}

volatile unsigned nocheat;

clock_t TestRaw(const Vector& data) {
    Pair* raw = new Pair[data.size()];
    copy(data.begin(), data.end(), raw);
    sort(raw, raw + data.size(), Less1st());
    nocheat = 0;

    clock_t beg = clock(), end;
    for (int i = 0; i < TEST_COUNT; ++i) {
        const Pair& target = data[i % data.size()];
        Pair* found = RawFind(raw, raw + data.size(), target);
        nocheat += found->second;
    }
    end = clock();
    delete[] raw;
    fprintf(stderr, "%u\n", nocheat);
    return end-beg;
}

clock_t TestVec(const Vector& data) {
    typedef Vector::const_iterator citerator;
    Vector v(data.begin(), data.end());
    sort(v.begin(), v.end(), Less1st());
    nocheat = 0;

    clock_t beg = clock(), end;
    for (int i = 0; i < TEST_COUNT; ++i) {
        const Pair& target = data[i % data.size()];
        citerator found = VecFind(v, target);
        nocheat += found->second;
    }
    end = clock();
    fprintf(stderr, "%u\n", nocheat);
    return end-beg;
}

clock_t TestMap(const Vector& data) {
    typedef Map::const_iterator citerator;
    Map m(data.begin(), data.end());
    nocheat = 0;

    clock_t beg = clock(), end;
    for (int i = 0; i < TEST_COUNT; ++i) {
        const Pair& target = data[i % data.size()];
        citerator found = MapFind(m, target);
        nocheat += found->second;
    }
    end = clock();
    fprintf(stderr, "%u\n", nocheat);
    return end-beg;
}

int main(int ac, char* av[]) {
    const int dataSize  = (ac  > 1)? atoi(av[1]) : 1000;
    srand(8165);

    Vector data(dataSize);
    for (unsigned i = 0; i < data.size(); ++i) {
#ifdef USE_STRING_KEY
        unsigned j;
        for (j = i; j > 9; j /= 10) {
            data[i].first.push_back('0' + j % 10);
        }
        data[i].first.push_back('0' + j);
#else
        data[i].first = i;
#endif
        data[i].second = rand();
    }
    // random_shuffle(data.begin(), data.end());

    clock_t r = TestRaw(data);
    clock_t v = TestVec(data);
    clock_t m = TestMap(data);
    printf("%8u %8u %8u %8u\n", dataSize, r, v, m);
    return 0;
}

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


留言列表 (2)

發表留言
  • citywalker
  • 哇希 JAVA 掛的~~
  • damody
  • 一個感覺,一定要把vc內建的stl換成stlport之類的實作版本。
  • 我知道 STLPort 的一般容器優於 VC 內建,不過這個實驗不會牽涉到這些方面的問題。

    效能問題的原因之一在於 VC 不論 release 或 debug 都預設使用 checked iterator,也就是每次進行 iterator 操作都會檢查 iterator 是否已初始化、是否超出範圍等等,其他的 STL 實作至少不會在 release 還這麼雞婆。我上面的實驗沒有關閉 checked iterator,是因為我那時候還不知道在 release 也會預設啟用...

    另外有一些跡象讓我開始懷疑 VC 的最佳化能力,不過沒作嚴謹的實驗,憑感覺下結論是很危險的。

    ---

    對了,不知道你有沒有用過藝電出的 EA STL,據稱在編譯時間和執行效能方面有過人之處,但目前只有部份釋出。我自己是還沒試過。

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
    https://github.com/paulhodge/EASTL

    novus 於 2012/05/11 14:50 回覆