std::unordered_map very high memory usage

Question

Yesterday i tried to use std::unordered_map and this code confused me how much memory it used.

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;
}

All this parts of code was compiled in MS VS2010 in debug mode. What I've been seen in my task manager was about 1200 kb of "clean" process, but after filling hash_map it uses 8124 kb of memory. Is it normal behavior of unordered_map? Why so much memory used?

Just wanted to note that a unordered map can hold up to hundreds of megabytes even when no item is stored inside (when you erase via iterators, because if the map rehash the iterator become invalid) see this bug report (wich may as well not affect microsoft implementation): https://svn.boost.org/trac/boost/ticket/11419 — CoffeDeveloper, Jun 27 '15 at 03:46

score 11 · Accepted Answer · answered Feb 21 '12 at 10:01

The unordered_map structure is designed to hold large numbers of objects in a way that makes adds, deletes, lookups, and orderless traverses efficient. It's not meant to be memory-efficient for small data structures. To avoid the penalties associated with resizing, it allocates many hash chain heads when it's first created.

Tony Delroy · Answer 2 · 2012-09-21T10:17:09.337

That's roughly 6MB for ~20k objects, so 300 bytes per object. Given the hash table may well be sized to have several times more buckets than current entries, each bucket may itself be a pointer to a list or vector of colliding objects, each heap allocation involved in all of that has probably been rounded up to the nearest power of two, and you've got debug on which may generate some extra bloat, it all sounds about right to me.

Anyway, you're not going to get sympathy for the memory or CPU efficiency of anything in debug build ;-P. Microsoft can inject any slop they like in there, and the user has no right of expectations around performance. If you find it's bad in an optimised build, then you've got something to talk about.

More generally, how it scales with size() is very important, but it's entirely legitimate to wonder how a program would go with a huge number of relatively small unordered maps. Worth noting that below a certain size() even brute force searches in a vector, binary searches in a sorted vector, or a binary tree may out-perform an unordered map, as well as being more memory efficient.

@Andrew: the main performance pros of sorted vectors are contiguous memory usage and in-place values, whereas `unordered_map` implementations tend to dynamically allocate distinct nodes and have to follow pointers to them during operations; operations in both binary trees and sorted vectors involve O(log₂N) '`<`' comparisons, whereas `unordered_map operations require a hash function call (which can be expensive but is only done once per operation, and can be orchestrated to happen once per value) and `==` comparisons. As always, measure for your actual data and usage when you care. — Tony Delroy, Oct 20 '17 at 21:13

score 7 · Answer 3 · edited Feb 04 '15 at 06:47

This doesn't necessarily mean that the hash map uses so much memory, but that the process has requested that much memory from the OS.

This memory is then used to satisfy malloc/new requests by the program. Some (or most, I am not sure about this) memory allocators require more memory from the OS than needed at that point in time for efficiency.

To know how much memory is used by the unordered_map I would use a memory profiler like perftools.

std::unordered_map very high memory usage

3 Answers3

Linked