雖然《資料結構》系列的文章一直沒有更新, 但是我一直都有在保持繼續寫程式碼. 其中, 我寫了很多次的 vector, 包括修改、重構等等. 我的程式碼一直放置於 GitHub, 大家有興趣可以直接測試一下 :

https://github.com/Jonny0201/data_structure/blob/master/data_structure/vector.hpp

通過測試, 大家可以發現, 對於一些非 POD 的型別, 我的 vector 其實比標準程式庫的還要快. 這主要是由於標準程式庫為了相容任何的程式碼以及任何的場景 (這其中包括了編碼器和運作環境) 而對例外安全和記憶體配置這方面作了通用的處理, 因為非 POD 的型別自身都會帶有一些需要手動去回收的資源. 而我們自己寫的 vector 只是為了鍛鍊我們的編碼水平, 應用的場景並沒有那麼複雜, 所以根本不需要考慮地那麼深刻, 於是我們可以進行更多的優化, 包括運用現代 C++ 的一些語法, 這確實可以讓我們的 vector 快於 STL 的 vector

另外, 對於 POD 型別和某一些如 bitset 等的型別來說, STL 的 vector 要快於我們自己實作的 vector 起碼一倍以上. 比較誇張的是, 對於內建型別來說, STL 的 vector 比我的 vector 要快 10 倍. 這些數字隨著測試數量級的增長, 還會更多

首先, 我從演算法角度進行了分析, 可以確定的是, 我的思想和寫法雖然和 STL 的寫法有些不一樣, 但是從我的角度來看, 這個演算法已經經過了深思熟慮, 而且加上了一些現代 C++ 的優化, 因此本來並不應該這麼慢. 上面我們也提到, 對於 string 這樣的物件來說, 我們的 vector 比標準程式庫的 vector 要快得多

排除演算法的原因, 接下來可能就是編碼器或者 STL 對於 POD 型別特別是內建型別進行了特別的優化

如果大家看過標準程式庫的 vector 實作 (我看的是 libc++), 大家就會發現標準程式庫對於 vector 的 inserteraseassign 三個主要的操縱元素的函式都運用了 copycopy_backwarderase 等等的外部函式, 而這些外部函式針對了 POD 型別進行了特別的優化, 也就是運用了 memmovememcopy 等函式, 相對於直接進行移動或者複製操作, 類似於 memmove 這樣的 C-Style 函式在操縱 POD 型別的時候要快得多. 這才是造成在 POD 型別的情況下, 比 STL 慢 3 - 10 倍的原因

如果針對 POD 型別運用這樣的優化, 那麼我們的 vector 就可以接近標準程式庫的速度

除此之外, 是否可以讓我們的 vector 更快於 STL 的 vector 呢? 答案是可以的 :

  • 忽略第二個樣板參數 allocator, 直接或者 realloc 這樣的能力. 這可以直接省略掉在 vector 的目前序列無法維持新進入的元素的情況下需要重新配置記憶體時需要移動 / 複製和銷毀的操作
  • 我們曾經詳細地討論過 C++ 的例外安全問題, 這個問題確實是會影響 vector 的運作效率的. 如果直接忽略例外安全, 甚至是有例外也直接忽略, 那麼這樣可以獲得更高的運作效率. 如果你的 vector 和 STL 的 vector 幾乎一致, 而你忽略了例外, 那麼你的 vector 是一定會比 STL 的 vector 更快
  • vector 的增長係數如果設置不當, 也會影響 vector 的運作效率, 比較常見的是每次以 1.5 倍 (MSVC 自帶的標準程式庫) 或者 2 倍 (Clang 自帶的標準程式庫) 的速率增長
  • 從特定的場景進行優化, 針對特定的場景省略一些通用的操作

經過這些的研究之後, 從 C++ 的角度來說, 我已經可以確定我的 vector 已經足夠快, 雖然改用 C-Style 可能會更快, 但是短時間內我應該不會再更改了. 而上面所說的也幾乎不太現實, 因為一旦忽略樣板參數, 我們的 vector 就完全不符合標準了

最後放上測試的結果, 測試在 Apple Clang 下進行, 自帶的標準庫未更換, 版本為 10.0.1 (Apple Clang 和 Clang 的版本號不同). 測試運用了 clock() 函式 :

class Foo {

public:

    int a;

    char b;

    char32_t  c;

    long d;

    double e;

    std::deque<int> deq;

};

對於這樣的物件, 我的 vector 比標準庫的 vector 慢 1 倍. 如果把 deque 替換為 bitset 或者 vector, 也會有類似的結果

如果去掉 deque, 那麼我的 vector 比標準庫的 vector 慢 1 倍到 1.5 倍

對於 int 這樣的內建型別, 我的 vector 比標準庫的 vector 要慢 10 倍

以上的速度, 隨著測試數量級的增長, 倍數也會增長. 我的測試數據大概在 100 萬到 200 萬左右