std::deque的内存开销到底是怎么回事？

Question

我正在开发一种使用std::queue的外部排序算法，并且必须仔细限制其内存使用量。我注意到在合并阶段（使用几个固定长度的std::queue），我的内存使用量增加到了预期的2.5倍左右。由于std::queue默认使用std::deque作为其底层容器，因此我对std::deque进行了一些测试，以确定其内存开销。以下是在VC++ 9上运行的结果，在发布模式下，使用64位进程：

向std::deque中添加100,000,000个char时，内存使用量增长到252,216K。请注意，100M个char（1个字节）应占用97,656K，因此这是154,560K的开销。

我重复了使用double（8个字节）进行的测试，并观察到内存增长到1,976,676K，而100M个double应占用781,250K，因此开销为1,195,426K!!

现在我明白了，std::deque通常实现为“块”的链表。如果这是真的，那么为什么开销与元素大小成比例（因为指针大小当然应该固定为8个字节）？为什么它这么大呢？

有人可以解释一下为什么std::deque会占用这么多内存吗？我在考虑将std::queue的底层容器切换到std::vector，因为它没有额外开销（只要适当地调用reserve即可）。 我认为std::deque的好处很大程度上被其巨大的开销抵消了（导致缓存未命中，页面故障等），而且考虑到总体内存使用量如此之低，复制std::vector元素的成本可能会更小。 这只是Microsoft对std::deque实现不佳吗？

- Tabber33

---

第一个问题。你是如何确定内存使用量的？因为有些方法不如其他方法准确。 - Martin York

@Martin，我只是在任务管理器中观察进程的“峰值工作集”值。 - Tabber33

@Martin，我刚刚测试了一下。 它会逐渐增加内存使用量，然后我暂停等待用户输入。 然后我释放它（通过使用一个额外的代码块）。 然后再次暂停等待用户输入，内存降至几K，正如预期的那样。 顺便说一句，“峰值工作集”默认不显示。 您必须在任务管理器中显示该列（我正在使用Windows 7）。 - Tabber33

我认为我已经足够熟悉Windows虚拟内存系统，可以说当内存被释放（在C++中使用delete时），它确实会返回给操作系统。在Windows中，内存可以“保留”和“提交”。当进程的物理内存使用量不足以需要交换文件时，“峰值工作集”显示了该进程生命周期内使用的最大物理内存量，这等同于“提交”的虚拟内存量。我已经确认，使用delete释放内存会将该内存释放到操作系统，并相应地减少工作集大小。在我的简单测试中... - Tabber33

没有释放内存。在循环中，内存使用量稳步增加。与std::vector不同的是，后者确实会分配一个新的连续块，比现有的块更大（这反映在“峰值工作集”和“工作集”之间的差异中），复制元素，然后释放原始块，但是std::deque不会这样做。它以16字节的增量增长（由下面的帖子确定），并且永远不会在插入时释放内存。 - Tabber33

Answer 1

看一下_DEQUESIZ（每个块的元素数量）的代码：

#define _DEQUESIZ   (sizeof (_Ty) <= 1 ? 16 \
    : sizeof (_Ty) <= 2 ? 8 \
    : sizeof (_Ty) <= 4 ? 4 \
    : sizeof (_Ty) <= 8 ? 2 : 1)    /* elements per block (a power of 2) */

如果元素更大，它会变小。只有对于大于8字节的元素，您才会获得预期的行为（随着元素大小的增加，开销的百分比减少）。

- Dialecticus

---

这是微软的代码吗？为什么他们要使用仅有16个字节的块？这太疯狂了！这肯定能解释为什么开销极大！通常每个分配的块会有8-16个字节的开销；调试版本和64位进程则更差。此外，这样频繁的分配（和回收）会很慢。 - Qwertie

这是Dinkumware的代码 - 实现了Microsoft的C++标准库。 - Tabber33

我也喜欢这个事实：deque<T>没有使用静态的size_t const成员，而是选择了反复计算并依赖于编译器来优化计算。虽然这样做肯定没问题，但仍然觉得这是对宏的滥用... - Matthieu M.

另外，我忘了提到你需要存储指向每个块的指针的4个字节开销。顺便说一下，当用户分配大量相同大小的小块时，内存管理器可以实现小的开销（0-4字节）...我知道这一点，因为我专门为此编写了一个内存管理器。但是我不会假设Microsoft提供高效的内存管理器，我听说调试版本每个块有36字节的开销，并且总大小向上舍入到下一个16字节；请参见http://www.nobugs.org/developer/win32/debug_crt_heap.html。 - Qwertie

“低碎片堆”如何影响每个分配的字节开销？ - Qwertie

Answer 2

你是否在运行Debug二进制文件？100M字符需要252MB的存储空间似乎有点多了...

你可以使用umdh检查这个问题，先对程序进行快照，然后再比较两次结果，或许可以解释为什么它比你预期的要大。

编辑： FYI - 当我在VS2010上在调试器外运行此程序时，使用char类型，我得到的结果是181MB。

deque<char> mydequeue;
for (size_t i = 0; i < 100 * 1024 * 1024; ++i)
{
  mydequeue.push_back(char(i));
}

编辑：支持@Dialecticus的另一个答案，这给我与double相同的占用空间：

struct twoInt64s
{
public:
    twoInt64s(__int64 _a, __int64 _b) : a(_a), b(_b) {}

    __int64 a;
    __int64 b;
};

编辑：将_DEQUESIZ修改为所示（每个块128个字符），现在100M个字符占用113M内存。

我的结论是，您看到的剩余开销是由于deque块的管理结构造成的，其中包括16个字符的数据，加上deque的控制信息以及堆管理器的更多控制信息。

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 128 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

道德 - 如果你真的想为你的特殊目的进行优化，那就准备好使用 <deque>。它的行为在很大程度上取决于你的元素大小，以及预期的使用模式。

编辑：根据您对队列大小的了解，您可以将 boost::circular_buffer 作为 std::queue 容器的替代品。我敢打赌这会更符合您的预期。

- Steve Townsend

---

@Steve，"attribution"是什么意思？ - Tabber33

你还可以在IDE中使用环境变量_NO_DEBUG_HEAP=1来禁用调试堆。 - MSN

@Tabber33 - 提醒一下，boost::circular_buffer<char> 中有 100000000 个元素的 Private Bytes = 98056K。 - Steve Townsend

哼，其他1944000个元素藏在哪里呢？ - Tabber33

@Tabber33 - 98056K = 98056 * 1024 - Steve Townsend

Answer 3

如果不看您使用的实际 std::queue 实现，我猜它的内存分配大概是这样的：

if (new element won't fit) {
    double the size of the backing storage
    realloc the buffer (which will probably copy all elements)
}

选择翻倍而不是更保守的原因是，您希望queue.push_pack操作具有O（1）的平均时间。由于重新分配可能会复制现有元素，如果仅按需增长数组（每次增加1个元素），则将是O（n ^ 2），因为您最初将所有值推入队列。我将把将翻倍版本如何提供恒定平均时间作为读者的练习。

由于您引用了整个过程的大小，因此您估计在推送略多于2的幂次方（2 ^ 26 <100MM <2 ^ 27）的元素时，额外开销约为2倍，这似乎是合理的。尝试在2 ^（n-1）处停止，测量，然后推送一些元素并再次测量。

- Ben Jackson

---

“queue” 是一个默认使用“deque”的适配器。但是，“deque”的工作方式不是这样的——它会分块分配内存，并保持它们之间的链式关系来表示整个容器。“vector” 更可能做到你在这里描述的操作。 - Steve Townsend

你所描述的对于 std::vector 在没有调用 reserve 的情况下有些准确，但对于 std::deque 则完全不准确。 - Tabber33