C++容器性能大比拼

動機

STL是C++的標準庫，它承載了大部分C++程序員的日常。

然而除了STL某残，業(yè)內(nèi)也發(fā)展了大量的容器可供程序員使用鸡挠。

對于各式各樣的容器，可能他們提供的API功能是一樣的舌厨，但是他們內(nèi)部微妙的內(nèi)部實現(xiàn)，卻會極大程度的影響程序的性能。

本文將通過數(shù)據(jù)展示的方式狰挡，來比較相同功能下，各容器性能幾何释涛，并在一定程度上提供各容器的使用建議加叁。

時間復雜度與Big O

container-big-O

程序代碼的性能，我們通常以時間復雜度來估計
然而通過big O的方式來估計只是在理想模型下的估計唇撬，代碼真實運行的性能估計會更加復雜它匕，它可能由于數(shù)據(jù)集大小而呈現(xiàn)出不同的性能，它可能由于在不同的硬件特性下呈現(xiàn)出很大的差別窖认。
因此big O豫柬，并不能真實的體現(xiàn)程序的性能

算法復雜度的知識回顧

數(shù)組元素的隨機訪問 O(1)

container-array-index

遍歷數(shù)組元素或者鏈表元素 O(n)

container-traver

二分查找數(shù)組元素或者平衡二叉樹元素 O(lg n)

container-binary-search

在數(shù)組的隨機位置插入一個元素 O(n)

container-array-insert

在鏈表的隨機位置插入一個元素 O(pos) + O(1)

container-link-insert

在平衡二叉樹中插入一個元素 O(lg n)

container-tree-insert

數(shù)據(jù)實驗

遍歷std::vector和std::list

std::vector<int> container(N);
... //insert into vector
auto const result = std::accumulate(container.begin(), container.end(), 0u);

std::list<int> container;
... //insert into list
auto const result = std::accumulate(container.begin(), container.end(), 0u);

一個大家都知道的事實告希，上面這兩個代碼片段的時間復雜度都是 O(n)

我們來看看實驗數(shù)據(jù)

container-traver-con

非常令人意外，vector的性能無論在小數(shù)據(jù)集還是大數(shù)據(jù)集都大大超過list烧给！

Why燕偶？

我們來看看他們的內(nèi)部實現(xiàn)

std::list的內(nèi)存結(jié)構(gòu)

[圖片上傳失敗...(image-6a9cc1-1670576472918)]

container-cpu-cache

在遍歷的過程中，通過next指針础嫡，獲取下一個節(jié)點的信息并處理

內(nèi)存布局是非連續(xù)的

std::vector的內(nèi)存結(jié)構(gòu)

container-array

在遍歷的過程中指么，通過將當前指針+pos來獲取下一個節(jié)點的信息

內(nèi)存布局是連續(xù)的

內(nèi)存訪問與CPU Cache

container-cpu-cache

CPU不會直接操作內(nèi)存，當CPU需要加載內(nèi)存中的數(shù)據(jù)時榴鼎，CPU會把內(nèi)存的數(shù)據(jù)以cache line為單位先加載到L1/L2/L3 cache伯诬，再加載到寄存器，再進行數(shù)據(jù)的計算
CPU訪問寄存器是最快的巫财，其次是L1 cache盗似，接著是L2 cache和L3 cache
當CPU發(fā)現(xiàn)數(shù)據(jù)不再cache中，便會產(chǎn)生一次cache miss平项，把數(shù)據(jù)從主存中加載到cache赫舒。而讀主存的性能會比讀L1 cache的性能差幾十倍
因為CPU加載數(shù)據(jù)到cache是以cache line形式加載的，一個cache line大小為64 bytes葵礼，因此當CPU讀取一個內(nèi)存數(shù)據(jù)号阿，他會把附近的數(shù)據(jù)拼成一個cache line，一起加載到cache中鸳粉。換個方式說cache有局部性和順序性的特點

vector和list在cache中如何布局

container-cache-vector-list

vector由于內(nèi)存的連續(xù)性扔涧，它很自然的適配cache的加載方式，達到一個加速的效果
list由于內(nèi)存的不連續(xù)性届谈，它可能每次訪問下一個節(jié)點的時候枯夜，都會發(fā)生cache miss，導致需要不斷的讀主存艰山，導致性能遠遠不如vector

std::vector和std::list頭插入

std::vector<uint32_t> container;
for (auto const& it : data_to_insert) {
 container.insert(container.begin(), it);
}

std::list<uint32_t> container;
for (auto const& it : data_to_insert) {
 container.insert(container.begin(), it);
}

根據(jù)時間復雜度分析

vector的頭插入的時間復雜度是O(n*n)

list的頭插入時間復雜度是O(1)

list的性能在理想情況下是遠遠超越vector的

我們來看看實驗數(shù)據(jù)

container-vector-list-insert-front

左邊的圖湖雹，沒有意外，list的性能遠勝于vector曙搬。

然而我更關注右邊的圖摔吏，在小數(shù)據(jù)集的時候，vector的頭插入竟然超越的list

這說明了list的cache不親和性帶來的overhead纵装，在小數(shù)據(jù)集的情況下征讲，比vector的O(n*n)更壞

修改vector的頭插入算法

std::vector<uint32_t> container;
for (auto const& it : data_to_insert) {
 container.push_back(it);
}
std::reverse(container.begin(), container.end());

把頭插入改為未插入，最后批量操作完橡娄，再倒置數(shù)組

那么它的時間復雜度是O(n)+O(n/2)

看看實驗數(shù)據(jù)：

container-vector-list-rever

新算法的vector的性能遠遠超越list的頭插入

vector的尾插入诗箍，不會帶來數(shù)組元素的后移，通過預留數(shù)組空間挽唉，尾插入的時間復雜度是O(1)滤祖，最后倒置數(shù)組筷狼，時間復雜度是O(n)，由于vector的cache親和性非常好匠童，因此性能達到了一個新高
list的時間復雜度和vector尾插入的時間復雜度相同埂材，但是由于cache不親和，導致性能比不上vector的尾插入算法

并行倒置數(shù)組

std::vector<uint32_t> container;
for (auto const& it : data_to_insert) {
 container.push_back(it);
}
std::reverse(std::execution::par, container.begin(), container.end());

C++17引入了并行算法俏让，嘗試在倒置數(shù)組時加入并行算法楞遏，看看性能提高多少茬暇？

container-parallel-array-insert

出乎意料首昔，并行算法沒有使程序性能更高，反而更差了糙俗。

這是因為par算法勒奇，是通過啟動多線程來執(zhí)行并行算法的，這就帶來了啟動線程和銷毀線程的overhead

而且在swap的過程中巧骚，不同線程swap的元素有可能在同一個cache line中赊颠，發(fā)生了偽共享，這也是性能下降的另外一個原因

頭插入大對象（512 bytes）

container-insert-big-object

我們又有新發(fā)現(xiàn)了

這次大對象的插入劈彪，list的性能是最高的

因為大對象把cache line都沾滿了

那么vector通過 cache line的加速效果就不明顯了

而且vector的reverse操作帶來的overhead也體現(xiàn)出來了

插入有序序列

std::set<uint32_t> container;
for (auto const& it : random_data) {
 container.insert(it);
}

std::vector<uint32_t> container; // will contain unique sorted values
for (auto const& it : random_data) {
 auto const position
 = std::lower_bound(container.begin(), container.end(), it);
 if (position == container.end() || *position != it)
 container.insert(position, it);
}

上面兩段代碼竣蹦，一個是插入std::set有序的紅黑樹，一個是插入有序的數(shù)組std::vector

std::set的算法復雜度是O(n*log n)

std::vector的算法復雜度是O(n*n)

在理想模型下沧奴，std::set是優(yōu)于std::vector的

我們來看看數(shù)據(jù)

container-sorted-seq

左邊的圖痘括，在大數(shù)據(jù)集的情況下，沒有意外滔吠，std::set優(yōu)于std::vector

右邊的圖纲菌，在小數(shù)據(jù)集的境況下，std::vector優(yōu)于std::set

原因是std::set的鏈表結(jié)構(gòu)的cache不親和性帶來的overhead比std::vector的n方更糟糕

修改下vector的算法

預分配空間

std::vector<uint32_t> container; // will contain unique sorted values
container.reserve(random_data.size());
for (auto const& it : random_data) {
 auto const position
 = std::lower_bound(container.begin(), container.end(), it);
 if (position == container.end() || *position != it)
 container.insert(position, it);
}

尾插入疮绷，后排序

std::vector<uint32_t> container;
for (auto const& it : random_data) {
 container.push_back(it);
}
std::sort(container.begin(), container.end());

尾插入翰舌，后并行排序

std::vector<uint32_t> container;
for (auto const& it : random_data) {
 container.push_back(it);
}
std::sort(std::execution::par, container.begin(), container.end());

看看數(shù)據(jù)

container-sorted-seq-opt

在優(yōu)化有的vector算法比std::set要優(yōu)勝很多

而在大數(shù)據(jù)集下，并行排序算法也發(fā)揮除了應該有的優(yōu)勢

固定大小的set

eastl::fixed_set ：通過預分配節(jié)點內(nèi)存冬骚，來提高std::set的性能

container-sorted-seq-fix-set

在數(shù)據(jù)上椅贱，fixed_set的性能略高于std::set

上面我們講了這么多的有序vector，其實有一個庫正好就是有序vector的功能只冻，它提供set的api庇麦，底層通過vector來實現(xiàn)

他們是boost的容器： flat_set ，flat_multiset属愤，flat_map女器，flat_multimap

flat set

下面是幾組數(shù)據(jù)

search性能：

container-sorted-seq-flat-set

遍歷：

container-sorted-seq-flat-tra

delete：

container-sorted-seq-flat-set-delete

search的性能，三個容器的性能相差無幾住诸，這是優(yōu)于二分查找驾胆，在vector涣澡，并沒有很好的cache親和
遍歷的性能，flat_set的性能優(yōu)勝于基于鏈表的std::set丧诺，這也是cache親和發(fā)揮的作用
delete的性能入桂，優(yōu)于flat_set在刪除完元素后，需要遷移元素驳阎，復雜度為O(n)抗愁，這導致在大數(shù)據(jù)集下，性能并不如意呵晚；但小數(shù)據(jù)集下蜘腌，優(yōu)于cache親和，flat_set的性能優(yōu)于set

無序集合

hash結(jié)構(gòu)饵隙，delete insert search的算法復雜度是O(1)

container-unorder-set

典型的容器有

std:: unordered_set std:: unordered_set

absl::flat_hash_set absl::flat_hash_map

看看下面幾組數(shù)據(jù)：

insert：

container-unorder-insert

search：

container-unorder-search

遍歷：

container-unorder-tra