STL 容器空间利用率的简单探究

Deuchie edited 9 月前

最近在一个场景中对使用 std::deque 还是 std::forward_list 作为小对象分配器的问题产生了思考。首先,抛去内存使用量的问题,deque 一定是更胜一筹。不如说,本来这个容器就是被设计为可以用作 batch 化的小对象容器的。另一方面,deque 支持常数时间内随机访问,如果不另用什么索引容器的话,几乎只能用它了。

我当时对 deque 的空间占用起了兴趣。因为 deque 内的元素按 page 分散地存储,再加上内部维持了一个小型的映射表,所以其空间利用率可能不高,这就是我的猜想。当然 list 的空间占用应该是很大的,因为要维护大量的结点及指针。另一方面内存碎片的问题也可能加剧内存占用大的问题。deque 按 page 存储的特点使用内存碎片的问题弱化了。

查资料

我首先去查了不同标准库实现中关于几个 STL 容器的空间利用率的资料。事实上它们不同实现来看变化很大,所以没有太大的参考价值。

实验数据

我用了四个容器对比。它们分别是 deque, list, vector, forward_list。在样本数量很小的时候比较没有意义。我探究的 size999'999,即百万级别。以下每个实验都重复了三次取平均值(然而实际上从 MiB 的数量级而言并没有差别了)。

使用 MSVC (v14.25) 编译器的 Release x64 模式。由于一些问题,测得的数据量要偏大一些。换句话说,实际上这些容器的效率是比表格里的高一些的。不过,因为这个实验只是想定性地对比一下所以没有影响。

实验有一个对照组,使用的是 new Elem[size]

4 bytes

首先使用的是 uint32_t。数据量接近 4 MiB。我得到的结果如下:

容器 占用空间 利用率 相对利用率
std::list 37 MiB 10.31% 13.51%
std::deque 11 MiB 34.68% 45.46%
std::vector 6 MiB 63.58% 83.34%
std::forward_list 35 MiB 10.90% 14.29%
new Elem[size] 5 MiB 76.29% 100.00%

可见 deque 还是很能战的,利用率为 vector 的一半。

8 bytes

然后使用的是 uint64_t,数据量接近 8 MiB。我得到的结果如下:

容器 占用空间 利用率 相对利用率
std::list 37 MiB 20.62% 24.32%
std::deque 22 MiB 34.68% 40.91%
std::vector 17 MiB 44.88% 52.94%
std::forward_list 18 MiB 42.39% 50.01%
new Elem[size] 9 MiB 84.77% 100.00%

吃惊的是 list 占用率没有变,也不知道是内存碎片的问题还是什么其它因素。

8 x 16 = 128 bytes

然后使用的是这个:

struct BigElem {
    uint64_t data[16];
};

这样一般可以规避内存对齐的问题(容器内部的 page 一般也是 128 的倍数)。

数据量接近 128 MiB。结果如下(算错了,但是差不太多,懒得改了):

容器 占用空间 利用率 相对利用率
std::list 174 MiB 73.56% 77.59%
std::deque 165 MiB 77.58% 81.82%
std::vector 144 MiB 88.89% 93.75%
std::forward_list 154 MiB 83.12% 87.66%
new Elem[size] 135 MiB 94.81% 100.00%

实验分析

首先我这个实验只是做个大概,也没有很严谨地控制变量、没有找其它编译器。不过可以看到,对小对象而言, deque 的空间利用率是比较高的。对大对象而言,几个容器的空间占用几乎没有什么差别(这种情况或许需要别的设施?)。

得出结论:都用 dequelist 再见!

Comments

kingno

%%%

Deuchie

(惊恐)大佬说笑了

Deuchie

勘误:在「查资料」那部分中,「不同实现来看变化很大」错了,我想说的是我只找到了复杂度相关的信息,没找到常数方面的对比。

你当前正在回复 博客/题目
存在问题!