动机

STL是C++的标准库，它承载了大部分C++程序员的日常。

然而除了STL，业内也发展了大量的容器可供程序员使用。

对于各式各样的容器，可能他们提供的API功能是一样的，但是他们内部微妙的内部实现，却会极大程度的影响程序的性能。

本文将通过数据展示的方式，来比较相同功能下，各容器性能几何，并在一定程度上提供各容器的使用建议。

时间复杂度与Big O

container-big-O

• 程序代码的性能，我们通常以时间复杂度来估计
• 然而通过big O的方式来估计只是在理想模型下的估计，代码真实运行的性能估计会更加复杂，它可能由于数据集大小而呈现出不同的性能，它可能由于在不同的硬件特性下呈现出很大的差别。
• 因此big O，并不能真实的体现程序的性能

算法复杂度的知识回顾

• 数组元素的随机访问 O(1)

container-array-index

• 遍历数组元素或者链表元素 O(n)

container-traver

• 二分查找数组元素或者平衡二叉树元素 O(lg n)

container-binary-search

• 在数组的随机位置插入一个元素 O(n)

container-array-insert

• 在链表的随机位置插入一个元素 O(pos) + O(1)

container-link-insert

• 在平衡二叉树中插入一个元素 O(lg n)

container-tree-insert

数据实验

遍历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)

我们来看看实验数据

container-traver-con

Why？

我们来看看他们的内部实现

std::list的内存结构

container-cpu-cache

在遍历的过程中，通过next指针，获取下一个节点的信息并处理

内存布局是非连续的

std::vector的内存结构

container-array

在遍历的过程中，通过将当前指针+pos来获取下一个节点的信息

内存布局是连续的

内存访问与CPU Cache

container-cpu-cache

• CPU不会直接操作内存，当CPU需要加载内存中的数据时，CPU会把内存的数据以cache line为单位先加载到L1/L2/L3 cache，再加载到寄存器，再进行数据的计算
• CPU访问寄存器是最快的，其次是L1 cache，接着是L2 cache和L3 cache
• 当CPU发现数据不再cache中，便会产生一次cache miss，把数据从主存中加载到cache。而读主存的性能会比读L1 cache的性能差几十倍
• 因为CPU加载数据到cache是以cache line形式加载的，一个cache line大小为64 bytes，因此当CPU读取一个内存数据，他会把附近的数据拼成一个cache line，一起加载到cache中。换个方式说cache有局部性和顺序性的特点

vector和list在cache中如何布局

container-cache-vector-list

• vector由于内存的连续性，它很自然的适配cache的加载方式，达到一个加速的效果
• list由于内存的不连续性，它可能每次访问下一个节点的时候，都会发生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);
}

根据时间复杂度分析

vector的头插入的时间复杂度是O(n*n)

list的头插入时间复杂度是O(1)

list的性能在理想情况下是远远超越vector的

我们来看看实验数据

container-vector-list-insert-front

左边的图，没有意外，list的性能远胜于vector。

然而我更关注右边的图，在小数据集的时候，vector的头插入竟然超越的list

这说明了list的cache不亲和性带来的overhead，在小数据集的情况下，比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());

把头插入改为未插入，最后批量操作完，再倒置数组

那么它的时间复杂度是O(n)+O(n/2)

看看实验数据：

container-vector-list-rever

新算法的vector的性能远远超越list的头插入

• vector的尾插入，不会带来数组元素的后移，通过预留数组空间，尾插入的时间复杂度是O(1)，最后倒置数组，时间复杂度是O(n)，由于vector的cache亲和性非常好，因此性能达到了一个新高
• list的时间复杂度和vector尾插入的时间复杂度相同，但是由于cache不亲和，导致性能比不上vector的尾插入算法

并行倒置数组

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引入了并行算法，尝试在倒置数组时加入并行算法，看看性能提高多少？

container-parallel-array-insert

出乎意料，并行算法没有使程序性能更高，反而更差了。

这是因为par算法，是通过启动多线程来执行并行算法的，这就带来了启动线程和销毁线程的overhead

而且在swap的过程中，不同线程swap的元素有可能在同一个cache line中，发生了伪共享，这也是性能下降的另外一个原因

头插入大对象（512 bytes）

container-insert-big-object

我们又有新发现了

这次大对象的插入，list的性能是最高的

因为大对象把cache line都沾满了

那么vector通过 cache line的加速效果就不明显了

而且vector的reverse操作带来的overhead也体现出来了

插入有序序列

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有序的红黑树，一个是插入有序的数组std::vector

std::set的算法复杂度是O(n*log n)

std::vector的算法复杂度是O(n*n)

在理想模型下，std::set是优于std::vector的

我们来看看数据

container-sorted-seq

左边的图，在大数据集的情况下，没有意外，std::set优于std::vector

右边的图，在小数据集的境况下，std::vector优于std::set

原因是std::set的链表结构的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());

看看数据

container-sorted-seq-opt

在优化有的vector算法比std::set要优胜很多

而在大数据集下，并行排序算法也发挥除了应该有的优势

固定大小的set

eastl::fixed_set ：通过预分配节点内存，来提高std::set的性能

container-sorted-seq-fix-set

在数据上，fixed_set的性能略高于std::set

上面我们讲了这么多的有序vector，其实有一个库正好就是有序vector的功能，它提供set的api，底层通过vector来实现

他们是boost的容器： flat_set ，flat_multiset，flat_map，flat_multimap

flat set

下面是几组数据

search性能：

container-sorted-seq-flat-set

遍历：

container-sorted-seq-flat-tra

delete：

container-sorted-seq-flat-set-delete

• search的性能，三个容器的性能相差无几，这是优于二分查找，在vector，并没有很好的cache亲和
• 遍历的性能，flat_set的性能优胜于基于链表的std::set，这也是cache亲和发挥的作用
• delete的性能，优于flat_set在删除完元素后，需要迁移元素，复杂度为O(n)，这导致在大数据集下，性能并不如意；但小数据集下，优于cache亲和，flat_set的性能优于set

无序集合

hash结构，delete insert search的算法复杂度是O(1)

container-unorder-set

典型的容器有

std:: unordered_set std:: unordered_set

absl::flat_hash_set absl::flat_hash_map

看看下面几组数据：

insert：

container-unorder-insert

search：

container-unorder-search

遍历：

container-unorder-tra

delete：

container-unorder-delete

分析：

• insert算法，由于flat_hash_set的算法复杂度为O(1)而且更加cache亲和，所以它的性能最优
• search算法，unordered_set在小数据集不如flag容器，由于链表带来的overhead造成；在大数据集下，由于flat_hash_set的优良设计，性能稳居第一
• 遍历算法，flat set由于数据密集分布，而flat_hash_set稀疏分布，所以flat set的性能是最优的
• delete算法，flat_hash_set再次因为优良的设计和cache亲和，再次稳居第一