我正在开发一种使用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
实现不佳吗?
delete
时),它确实会返回给操作系统。在Windows中,内存可以“保留”和“提交”。当进程的物理内存使用量不足以需要交换文件时,“峰值工作集”显示了该进程生命周期内使用的最大物理内存量,这等同于“提交”的虚拟内存量。我已经确认,使用delete
释放内存会将该内存释放到操作系统,并相应地减少工作集大小。在我的简单测试中... - Tabber33std::vector
不同的是,后者确实会分配一个新的连续块,比现有的块更大(这反映在“峰值工作集”和“工作集”之间的差异中),复制元素,然后释放原始块,但是std::deque
不会这样做。它以16字节的增量增长(由下面的帖子确定),并且永远不会在插入时释放内存。 - Tabber33