novus log

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

大約兩個月前在 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 有時會快很多，雖然我大概知道這是快取效應造成的，但並沒有繼續深究細部的原因。如果你覺得我的程式碼犯了哪些錯誤也歡迎提出來討論，雖然我最近不是很有空回應。

#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;
}