title: c++_benchMark_vector_list_deque
date: 2015-08-01 22:32:39

作者：titer1 + ZhangYu
出处：www.drysaltery.com + csdn博客同步
联系：1307316一九六八（仅接受短信）
声明：本文採用下面协议进行授权： 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 。转载请注明作者及出处。

翻译来源：c++ benmark series

c++_benchMark_vector_list_deque

上周，我在不同的工作负载下 比較了std :: vector和std ::vector 的基准。

这之前的文章收到了非常多用于改进的意见和建议本文章是对前一篇文章的进一步展开。

在这篇文章中。我们将在几个不同的工作负载下，利用不同的数据类型。比較 std :: vector、std :: list和std :: deque的表现。这篇文章中，我所称呼的list、vector和deque都是标准库的相应函数

按常识来说。当实行随机的插入和删除的时候，应该使用链表。由于此时对于数组和双向队列来说。他们的相关复杂度的是O(n),而前者则是O(1)假设我们仅仅看复杂性，在这两个数据结构(vector/deque)线性搜索的规模应该是等价的，复杂性为O（n）之中。当数组(vector)或双端队列(deque)中进行随机插入/替换操作时。全部的兴许数据须要被移动，因此各元素也将被复制。这就是在进行比較这两个数据结构时为什么数据类型的大小是一个重要的因素。由于数据类型的大小将在复制元素的开销上发挥了重要作用。

然而。在实践中。对于存储器快速缓存的使用存在着巨大的差异。全部数组（vector)数据是连续的，而所在的列表（list)则为每一个元素单独分配内存。这个在实际当中是怎样的结果，我们将拭目以待。

双端队列是针对具有以上两个数据结构的长处没有他们缺点的数据结构，我们将看到它怎样在实践中怎样表现。复杂度分析并没有考虑到存储器的层次结构（memory hierarchy）我相信，在实践中。存储器层级和复杂度分析一样重要。

请记住，这里的全部測试都是基于数据（vector）、链表(list)和双向队列(deque)，即使其它的数据结构在给予的负载下有更好的表现。

在下面图和正文中，n是指集合的元素数。

全部的測试，都是基于 Intel Core i7 Q 820 @ 1.73GHz. 代码使用gcc在64位环境下编译,使用參数是 -02 和 -march=native. 哦，代码也支持c++ 11 的标准。

对于每一个曲线图中，垂直轴表示来运行操作的的必要时间，所以值越小越好。横轴始终是集合的元素数。对于一些图形。对数刻度能够更清晰。图下方提供一个button。用于改变每一个图的垂直刻度为相应的对数刻度。

类型不同大小的数据，他们持有多头的数组，数组的大小变化来改变数据类型的大小。那些非标准的数据类型，在不平庸的数据类型是由两个多头。具有非常愚蠢的赋值操作符和拷贝构造函数，仅仅是做了一些数学（全然没有意义的。但昂贵的）。可能有人会觉得是不是一个普通的拷贝构造函数,既没有共同的赋值操作符和一个将是正确的，可是，这里最重要的一点是。它是昂贵的运营商这是足以让这个基准。

填充操作

所运行的第一个測试是填充数据结构，详细就是通过将元素加入（用push_back）到容器的尾部。这里将会使用两种数组（vector), 当中vector_pre是一种使用vector:reserve在一開始就分配内存的标准vector，它分配的结果是整个过程中近分配内存一次。

首先让我们看看。使用一个非常小的数据类型(8字节）填充的结果

预分配的数组fill是最快的。与vector/deque之间有非常小的差距。然后list比其它三种类型慢3倍。

假设我们考虑更大的大小类型（4k)：

这次vector 和list 表现类似，deque比list/vector快一点。预分配的数组明显是赢家，deque和vector之间的差异非常有可能是我系统引起的，在我的机器上在同一时间不可能分配那么多内存。

（此段翻译等待代码来解释）

最后，我们将会尝试一个非普通的类型：

全部的数据表现差异不大，当中 vector_pre是最快的。
对于push_back操作， 预分配的vector是一个非常好的选择假设事先知道分配的大小。。其它数据结构表现差异不大。
我更喜欢预分配的数组（ Pre-allocated),假设某些人发现这些小差距的原因。请告诉我，我非常有兴趣。

线性查找

第一个操作将会在查找中測试，这个容器将会填充0到N之间的随机数字。当中。能够使用std:find来进行简单的线性查找来查询0到N的每一个数字。

理论上，依据复杂度，全部的数据结构应该表现一致。

8 bytes

明显，list在查找方面表现非常差，他的时间开销的增长比vector/deque都大。

128 bytes

唯一的原因是由于缓冲行的使用。当一个数据被訪问时。这个数据将会从主存取到缓冲。

不仅仅是訪问的数据被取到，另一整个缓冲行被取到。 由于vector中的数据都是连续的，当一訪问当中的一个数据，临近的元素将自己主动放到cache中。

由于主存的訪问速度慢缓存一个数量级，因此产生巨大的差异。

对于链表的情况。处理器花费全部的时间等待数据从主存取到缓冲中。对于每一次取数据操作，处理器都取到大量差点儿没用的不必要的数据。

双向队列deque比vector慢一点，这是逻辑上说的过去，由于分段（segmented part)的存在，导致很多其它的缓存命不中。

下面尝试更大的数据类型，

链表比其它类型慢非常多。可是有趣的是 双向队列和数组之间的间歇在变小，下一步我们尝试4KB
大小的数据类型。

4096 bytes

链表的表现 依然表现非常差，可是与其它之间的差距在变小。有趣点是双向队列比vector更快，
我不太确定这个结果发生的原因。非常有可能是这个特别大小的数据大小。

一件事是确定的。
数据单元的尺寸越大，处理器发生的缓冲行命不中的机会越多，由于元素在缓冲中没有。

对于查找来说。链表是明显的慢。同一时候deque和vector有类似的表现，看起来deque比vector在
大尺寸的查找操作而言更快。

随机查找（+线性查找）

8 bytes

32 bytes

128bytes

4096bytes

non-trival 16bytes

随机删除

8

http://drysaltery.qiniudn.com/2015-08-02_002644.png

128

http://drysaltery.qiniudn.com/2015-08-02_002658.png

4096

http://drysaltery.qiniudn.com/2015-08-02_002710.png

non-trival 16bytes

http://drysaltery.qiniudn.com/2015-08-02_002723.png

前插

8bytes

http://drysaltery.qiniudn.com/2015-08-02_002823.png

排序

8bytes

http://drysaltery.qiniudn.com/2015-08-02_002859.png

128bytes

http://drysaltery.qiniudn.com/2015-08-02_002908.png

1024 bytes

not 4096bytes here

http://drysaltery.qiniudn.com/2015-08-02_002923.png

non-trival 16bytes

http://drysaltery.qiniudn.com/2015-08-02_002945.png

销毁操作

8 bytes

http://drysaltery.qiniudn.com/2015-08-02_003055.png

128 bytes

http://drysaltery.qiniudn.com/2015-08-02_003105.png

4096 bytes

http://drysaltery.qiniudn.com/2015-08-02_003121.png

…

这一次。我们能够看出，deque 比vector 慢三倍。而且list 比vector 慢三个数量级！可是，性能差异在降低

当用数据结构进行測试：

list 和deque的性能没有多大差别。vector是仍然比他们快两倍。。

尽管vector始终快于即使list 和 deque，可是这是由于析构函数代价非常小。微秒便可运行完。

这个仅仅影响那些对时间非常敏感的程序，然而大多程序对时间那么不敏感。此外，每一个数据结构仅仅析构一次。所以析构函数并非一种非常重要的操作。

数字运算（Number Crunching）

最后，我们将測试Number Crunching。这里，随机元素被插入有序容器。

意思是。在插入之前，会先搜索出插入的位置。。这里的number crunching中測试的元素为8个字节。

即使仅仅有100,000元素。list 已经比其它两个数据结构慢一个数量级。结果曲线显示，数据量越大，list表现越糟糕。

list的空间局部性太差， 所以并不适合number crunching操作。

结论

最后，对于之前的数据结构，我们能够得到下面事实：

• std ::list 由于极差的空间局部性（spatial locality） 。 使得list进行集合的遍历过程十分缓慢。
• std :: vector和std :: deque 对小数据来说 性能总是比std：：list要好
• std ::list 适用于处理大型数据结构
• std::deque 在随机插入 方面 要比std::vector 好。特别是插入时有大量的push_front。
• std :: deque的和std ::vector 对复杂的数据类型支持不好， 由于复制和赋值的代价太高

我们能够得出使用这些数据结构的理想情形：

• Number crunching：使用std :: vector 或std :: deque
• 线性搜索（Linear search）：使用std ::向量或std :: deque
• 随机插入/删除（Random Insert/Remove）：
  
  • 小型数据：使用std ::vector
  • 大型数据：使用std ::list 仅仅要没有大量的搜索操作。
• 复杂数据类型（对象）：使用std ::list。仅仅要不须要进行大量的搜索。

  但。当我们要对容器改动多次。list 将会变得非常慢。

• 前插：使用std :: deque或std ::list

我坦白，在写本文之前，我并不知道的std :: deque。

但，std::deque 是一个非常好的数据结构。无论是将元素插入到队列之前、之后还是中间，std::deque 都有非常好的性能，而且拥有非常好的空间局部性（spatial locality）。所以。 即使有时性能比vector要差，整体上能够说我们优先选择deque而不是vector 。 尤其是操作中等大小的数据结构的时候。

假设你有时间，在实践中，决定最好的办法是始终基准每一个版本号。甚至能够尝试另一种数据结构。

两个操作具有同样大O的复杂性在实践中全然不同的表演。

我希望本文对你有所帮助。假设您有不论什么意见或建议。

请不要犹豫。马上发表评论。

源码： https://github.com/wichtounet/articles/blob/master/src/vector_list/bench.cpp