%%%
STL 容器空间利用率的简单探究
Fifnmar edited 3 年，11 月前
最近在一个场景中对使用 std::deque 还是 std::forward_list 作为小对象分配器的问题产生了思考。首先，抛去内存使用量的问题，deque 一定是更胜一筹。不如说，本来这个容器就是被设计为可以用作 batch 化的小对象容器的。另一方面，deque 支持常数时间内随机访问，如果不另用什么索引容器的话，几乎只能用它了。
我当时对 deque 的空间占用起了兴趣。因为 deque 内的元素按 page 分散地存储，再加上内部维持了一个小型的映射表，所以其空间利用率可能不高，这就是我的猜想。当然 list 的空间占用应该是很大的，因为要维护大量的结点及指针。另一方面内存碎片的问题也可能加剧内存占用大的问题。deque 按 page 存储的特点使用内存碎片的问题弱化了。
查资料
我首先去查了不同标准库实现中关于几个 STL 容器的空间利用率的资料。事实上它们不同实现来看变化很大，所以没有太大的参考价值。
实验数据
我用了四个容器对比。它们分别是 deque, list, vector, forward_list。在样本数量很小的时候比较没有意义。我探究的 size 为 999'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 的空间利用率是比较高的。对大对象而言，几个容器的空间占用几乎没有什么差别（这种情况或许需要别的设施？）。
得出结论：都用 deque，list 再见！
（惊恐）大佬说笑了