摘要訊息 : 寫不出和 std::vector 速度相近的 vector 讓我很煩惱...

0. 前言

https://github.com/Jonny0201/data_structure/blob/master/data_structure/vector.hpp 是我自己實作的 vector, 它首先展現是在《【資料結構】向量 (順序表)》的第 7 節中.

通過測試, 我發現對於一些非 POD 的型別, 我的 vector 其實比標準程式庫的還要快, 例如放入 std::string 等等. 這主要是由於標準樣板程式庫為了相容任何使用場景而對例外安全和記憶體配置這方面作了通用的處理, 而非 POD 的型別自身都會帶有一些需要手動去回收的資源. 我寫的 vector 只是為了鍛鍊我自己的編碼水平, 應用的場景並沒有那麼複雜, 所以根本不需要考慮地那麼深刻. 於是我可以進行更多的優化, 包括運用一些現代的 C++ 語法, 這確實可以讓我的 vector 快於 std::vector. 但是對於 POD 型別和比如 std::bitset 這樣的型別來說, std::vector 要比我自己寫的 vector 快一倍以上. 比較誇張的是, 在內建型別上, std::vector 比我的 vector 快十倍以上, 而且快的級別隨著向量中儲存元素數量的增加而增加.

這篇文章就是分析為什麼我寫的 vector 在簡單型別上的表現如此之差.

更新紀錄 :

• 2022 年 4 月 18 日進行第一次更新和修正.

1. 演算法優化

其實演算法沒有什麼可優化的地方. 畢竟對於向量的建構, 向量中元素的插入和移除, 就一種演算法. 況且如果演算法不正確的話, 最終導致的結果一個是我的 vector 中儲存的結果和 std::vector 中儲存的結果有所不同. 通過對比, 不論如何插入或者移除, 最終我的 vector 中儲存的元素和 std::vector 中儲存的結果完全相同. 這也就表明插入和移除演算法不存在問題. 更激進一點, 在《【資料結構】向量 (順序表)》中插入和移除元素的演算法是可以證明正確性的.

從另一個角度來說, 如果演算法不正確的話, 對於非 POD 型別, 我的 vector 的運作效能不可能超過 std::vector. 寫 std::vector 那群人什麼水平, 而我又是什麼水平? 根本都不在一個級別上.

2. 尋找原因

Apple Clang 提供的 C++ 標準樣板程式庫是 libc++, 所以我看的是這個版本的標準樣板程式庫. 在 libc++ 中, std::vector 的插入和移除操作對於 POD 型別都有特別的優化, 這個優化不是在 std::vector 中的. 因為 std::vector 中插入和移除操作實際上都委託給了來自標頭檔 <algorithm> 中的 std::copy 和 std::copy_backward. 這兩個函式針對 POD 型別使用了 std::memcpy 和 std::memmove 進行優化. 相比較於一個一個複製或者一個一個移動的操作, std::memcpy 和 std::memmove 要快得多. 這就是為什麼我寫的 vector 在 POD 型別上運作效能比不上 std::vector 的真正原因所在.

3. 快於 std::vector

那麼如果我們一定要寫一個快於 std::vector 的 vector 是否可能呢? 可能的. 因為 std::vector 是通用的, 專門定製的 vector 通常比通用的更快.

3.1 從增長係數出發

libc++ 中的 std::vector 採用的擴容方法是當 std::vector 中儲存的元素滿了, 向量需要擴容的時候, 擴容的大小是當前大小的兩倍. 當然, 如果兩倍都不夠的話, 就會使用插入元素數量加上向量中本身元素數量的總和. 如果在某個場景之下, 頻繁向一個向量中插入元素, 就會發生多次擴容. 多次擴容就代表著多次記憶體配置操作, 多次移動複製操作, 多次解構操作和多次記憶體回收操作. 這些多餘的操作都可以在特定場景下通過配置一個容量很大的向量來解決.

3.2 採用 std::realloc

我們可以自己寫一個 allocator 以替換 std::allocator, 並且採用 std::realloc. 如果作業系統發現一段記憶體後面的部分沒有被使用, 那麼使用 std::realloc 就可以將原始記憶體擴容到後面沒有用到的那一部分. 這樣, 前面那一部分的記憶體中的元素就不需要進行移動, 複製和解構.

更進一步地, 我們甚至可以直接省略掉空間配置器, 直接在 vector 中手寫記憶體操作.

3.3 忽略例外安全

儘管忽略例外安全雖然是危險的, 但是如果我們可以保證 vector 中的元素的所有操作都是例外安全的, 那麼我們在編寫 vector 的時候就不需要考慮例外安全, 從而省略掉 try-catch 區塊. 我在《【C++ Template Meta-Programming】認識樣板超編程 (TMP)》第 5.2 節中就提到過使用 if constexpr 來省略 try-catch 區塊.

另外, 部分類別的移動操作可能沒有保證是不擲出例外情況的, 還有一部分類別的 swap 操作也是這樣的. 在我們編寫的 vector 中, 我們可以直接果斷處理 : 只要提供了移動或者 swap 操作, 我們都預設其不擲出例外情況, 優先使用移動而不是複製. 如果我們採取了這樣果斷的處理方式, 那麼當移動或者 swap 操作擲出例外情況的時候, 我們可以直接使用 std::terminate 終結程式.

另外, 一旦我們保證不擲出例外情況, 所有函式都可以被 noexcept 標識, 編碼器可以進一步優化我們的程式碼. 當有例外情況發生的時候, 程式就會自動呼叫 std::terminate.