How to measure Memory Usage of std::unordered_map

Question

We know that hash table based container implementations like std::unordered_map use a lot memory but I don't know how much is how much?

Apart from space complexity notations, and not considering if a container element is a pointer to a larger object:

Is there any way to figure out how many bytes is being used by such a container during run-time?

Is there a way to tell, at runtime, how much memory any container uses?

Answer 1

There's no portable way to tell how many bytes are in use. What you can find out is:

• size() indicates how many data elements have been inserted into the container
• bucket_count() indicates how many buckets the underlying hash table has, each of which can be expected to host a linked list to the associated elements

Now:

• bytes actually used for element storage will be m.size() * sizeof(M::value_type)

• bytes used for the hash table buckets depends on the way the internal lists are stored - std::unordered_map::bucket_size has constant complexity so we might reasonably guess that there'll be a size() and head pointer per bucket, so m.bucket_count() * (sizeof(size_t) + sizeof(void*)) is a reasonable guess, though it may be that there's only constant amortised complexity due to the load_factor() being bounded and no size stored per bucket (I'd prefer implementing it this way myself)

• if each of the inserted elements is part of the list, they'll need a next pointer, so we can add another m.size() * sizeof(void*)

• each memory allocation may be rounded up to a size convenient for the memory allocation library's management - e.g. the next power of two, which approaches 100% worst case inefficiency and 50% average, so let's add 50%, just for the list nodes as the buckets are likely powers of two given size_t and a pointer: 50% * size() * (sizeof(void*) + sizeof((M::value_type))

• especially in debug mode, there may be any amount of implementation-specific housekeeping and error-detection data

You can explore this further by creating a number of large tables and seeing how top or Process Manager reports different memory usage.