std :: unordered_map非常高的内存使用率

Question

昨天我试图使用std::unordered_map,这段代码混淆了我使用了多少内存.

typedef list<string> entityId_list;
struct tile_content {
   char cost;
   entityId_list entities;
};
unordered_map<int, tile_content> hash_map;

for (size_t i = 0; i < 19200; i++) {
   tile_content t;
   t.cost = 1;
   map[i] = t;
}

所有这些代码部分都是在MS VS2010中以调试模式编译的.我在任务管理器中看到的是大约1200 kb的"干净"过程,但填充后hash_map它使用了8124 kb的内存.这是正常的行为unordered_map吗？为什么要使用这么多内存？

Answer 1

该unordered_map结构旨在以一种使添加,删除,查找和无序遍历高效的方式保存大量对象.对于小型数据结构而言,这并不意味着内存效率.为了避免与调整大小相关的惩罚,它在首次创建时分配了许多哈希链头.

Answer 2

对于~20k对象,这大约是6MB,因此每个对象有300个字节.鉴于哈希表的大小可能比当前条目的桶多几倍,每个桶本身可能是指向碰撞对象列表或向量的指针,所有这些中涉及的每个堆分配可能已经四舍五入到最近两个的力量,你有调试可能会产生一些额外的膨胀,这听起来对我来说是正确的.

无论如何,你不会对调试版本中的任何内存或CPU效率表示同情;-P.微软可以在那里注入他们喜欢的任何slop,并且用户无权对性能有所期望.如果你发现它在优化版本中很糟糕,那么你就有话要说了.

更一般地说,它如何扩展size()是非常重要的,但是想知道一个程序如何使用大量相对较小的无序地图是完全合理的.值得注意的是,size()在向量中搜索某个甚至强力搜索,在排序向量中进行二进制搜索,或者二叉树可能超出无序映射,以及更高的内存效率.

Answer 3

这并不一定意味着哈希映射使用了如此多的内存,但是进程已经从操作系统请求了大量内存.

然后,该存储器用于满足程序的malloc/new请求.一些(或大多数,我不确定)内​​存分配器需要来自OS的更多内存,而不是在那个时间点为了提高效率.

要知道unordered_map使用了多少内存,我会使用像perftools这样的内存分析器.