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

Question

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

我正在研究一种外部排序算法,它使用std::queue并且必须小心地限制其内存使用量.我注意到在合并阶段(使用几个std::queue固定长度),我的内存使用量增加到我预期的2.5倍左右.由于std::queue默认情况下使用std::deque它作为其底层容器,因此我运行了一些测试std::deque以确定其内存开销.以下是在发布模式下在VC++ 9上运行的结果,具有64位进程:

当向chara 添加100,000,000 s时std::deque,内存使用量增长到252,216K.请注意,100M chars(1字节)应占用97,656K,因此这是154,560K的开销.

我用doubles(8字节)重复测试,看到内存增长到1,976,676K,而100M doubles应该占用781,250K,开销为1,195,426K!

现在我明白这std::deque通常是作为"块"的链表实现的.如果这是真的,那么为什么开销与元素大小成比例(因为指针大小当然应该固定在8个字节)？为什么这么大呢？

任何人都可以解释为什么要std::deque使用如此多的危险记忆？我想我应该切换我的std::queue底层容器,std::vector因为没有开销(考虑到适当的大小reserve).我认为它的好处std::deque在很大程度上取决于它有如此巨大的开销(导致缓存未命中,页面错误等),并且std::vector鉴于整体内存使用情况,复制元素的成本可能会更低太低了.这只是std::deque微软的糟糕实现吗？

Answer 1

Dia*_*cus 14

查看_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) */

Run Code Online (Sandbox Code Playgroud)

如果元素更大,它会变小.只有大于8个字节的元素才能获得预期的行为(随着元素大小的增加,开销的百分比减少).

@Qwertie:我也喜欢这样一个事实:他们不是使用`deque <T>`的`static size_t const`成员,而是反复计算这个东西并依赖编译器来优化计算.它肯定会这样做,但这仍然是滥用宏观...... (4认同)
这是微软的代码吗？为什么他们会尝试使用只有16个字节的块？太疯狂了!这肯定会解释为什么开销非常糟糕!典型的内存管理器每块分配的开销为8-16字节; 调试版本和64位进程更糟糕.另外,如此多的分配(和解除分配)可能会很慢. (3认同)
它是 Dinkumware 的代码——微软 C++ 标准库的实现。 (2认同)

归档时间：	15 年前
查看次数：	2990 次
最近记录：	15 年前