By Denis Ermolin


2012-02-21 09:56:46 8 Comments

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?

3 comments

@dmeister 2012-02-21 10:04:06

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.

@Tony Delroy 2012-02-21 11:09:02

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 2017-10-15 22:53:51

Can you give reason for the last sentence?

@Tony Delroy 2017-10-20 21:13:26

@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<sub>2</sub>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.

@David Schwartz 2012-02-21 10:01:27

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.

Related Questions

Sponsored Content

25 Answered Questions

[SOLVED] How to convert std::string to lower case?

43 Answered Questions

[SOLVED] What's the best way to trim std::string?

  • 2008-10-19 19:23:07
  • Milan Babu┼íkov
  • 673268 View
  • 795 Score
  • 43 Answer
  • Tags:   c++ trim stdstring

37 Answered Questions

[SOLVED] Why is "using namespace std;" considered bad practice?

20 Answered Questions

12 Answered Questions

[SOLVED] Is there any advantage of using map over unordered_map in case of trivial keys?

2 Answered Questions

[SOLVED] C++ unordered_map using a custom class type as the key

8 Answered Questions

[SOLVED] How to convert a std::string to const char* or char*?

  • 2008-12-07 19:30:56
  • user37875
  • 912524 View
  • 877 Score
  • 8 Answer
  • Tags:   c++ string char const

12 Answered Questions

[SOLVED] std::wstring VS std::string

Sponsored Content