Memory consumption by STL containers

Question

I am working on an application in which I am planning to use couple of STL containers. The application will take certain steps if memory consumption reaches a threshold. For that purpose I need to perform a close to accurate calculation on how much memory is used by STL containers.

vector<string> StringList
map<string, int> mapstring

This is how I am estimating memory:

For size of StringList, loop over all the elements of the vector and keep adding the string sizes.

string size = sizeof(string) + string.capacity()*sizeof(char)

Then finally add to this sizeof(StringList);

For size of mapstring, loop over all the keys of the container and keep adding the string sizes and then add the sizes of int which is mapstring.size()*sizeof(int). Then finally add to this sizeof(mapstring);

I guess a better approach would be specifying own allocator class and keeping track of memory usage inside it but writing one could be non-trivial. Does this estimation look good ?

Similar questions: http://stackoverflow.com/questions/2160300/how-to-find-the-memory-used-by-any-object http://stackoverflow.com/questions/720507/how-can-i-estimate-memory-usage-of-stlmap This is a reasonable way to get a rough lower bound, but there may be a lot more overhead than you think. For instance, a `std::map` element must contain various extra pointers, and information related to keeping it balanced, ... Valgrind tool massif keeps track of heap allocation, and may be of some help profiling your programs memory use. — BoBTFish, Aug 07 '12 at 07:48
it also depends on which STL implementation you are using. e.g. STLPort or gcc STL — weima, Aug 07 '12 at 07:50
"I guess a better approach would be specifying own allocator class and keeping track of memory usage inside it but writing one could be non-trivial." -- That is indeed the best approach, much better than second-guessing the STL implementation. — DevSolar, Aug 07 '12 at 07:51
Can't you just ask the OS how much memory the process is using? — jalf, Aug 07 '12 at 07:53

TemplateRex · Answer 1 · 2012-08-07T08:50:30.653

11

A std::vector<element> typically takes 3 machine words in total + sizeof(element) * capacity() of memory. For typical implementations, the overhead consist of pointers to the beginning, end and current size of the vector. The elements themselves are stored in contiguous memory. capacity() typically has room for up to twice the actual number of elements.

A std::map<element, int> typically takes about 2 machine words in total + 3 machine words per element + [ sizeof(element) +sizeof(int) ] * num_elements of memory. For typical implementations, the overhead consists of pointers to the stored elements. The elements themselves are stored in a binary tree, with pointers to its parent and two children.

With these rules of thumb, all you need to know is the average number of characters per string and the total number of strings to know total memory consumption.

edited Aug 07 '12 at 08:50

answered Aug 07 '12 at 07:50

TemplateRex

69,038
19
164
304

For `std::vector`, you should use `capacity`, not the number of elements. And if `std::map` uses a pool allocator (and a lot do), then it's likely allocating a lot more nodes than there are elements in the `map`. – James Kanze Aug 07 '12 at 08:03
@JamesKanze Tnx, updated for capacity() remark. So for `std::map`, is there a non-intrusive way (i.e. not logging the allocator) to get memory consumption? – TemplateRex Aug 07 '12 at 08:08
If you don't know the implementation, there's no way; if the allocator uses a pool of nodes, there may be no way, period. The simplest solution here is just to replace global `operator new` and `operator delete` with ones which keep track of allocations. (The default allocators are required to use `::operator new` to acquire the memory they allocate.) – James Kanze Aug 07 '12 at 08:19
Also, your comment concerning `capacity()` can have room for up to twice the actual number of elements isn't correct. There's no restriction what so ever on capacity, except that it grow by multiples. Typical multiples are 1.5 and 2, but larger (or smaller) are certainly allowed. – James Kanze Aug 07 '12 at 08:21
@JamesKanze I repeatedly mentiond "typical implementation", as there is no mandated implementation anyway. – TemplateRex Aug 07 '12 at 08:50
Exponential growth is mandatory. I'd guess that 1.5 is the most common factor, with 2 a close second. – James Kanze Aug 07 '12 at 09:06

score 11 · Accepted Answer · answered Aug 07 '12 at 08:02

For std::vector and std::string, capacity, rather than size, would be a better approximation. For node based containers (std::set, etc.), you'd want multiply the number of nodes (roughly the number of elements) times the size of each node. This only accurate, however, if the allocator doesn't use an optimized pool allocator for the nodes.

If you really want to know how much memory is being used, however, a better strategy would be to replace the global operator new and operator delete, and keep track of the actual allocations. Even more accurate would be to replace malloc and free. Formally, this is not allowed, but in practice, I've never encountered an implementation where it doesn't work. On the other hand, if you replace malloc and free, you have to implement the actual memory management yourself. If you replace operator new and operator delete, you can use malloc and free, which makes it fairly trivial.

Note too that each allocation has some fixed overhead. A 100000 allocations of 10 bytes each will consume significantly more memory than 10 allocations of 100000 bytes each.

Replacing new will give me the memory used during heap allocations. To this usage I Will have to add overhead of all containers i.e sizeof(vector) + sizeof(string) etc. ? — Frank Q., Aug 07 '12 at 19:28
It depends on what you are trying to measure. Replacing new will give you use of dynamic memory in C++ (but not in any C parts you might be using). This is what I would understand by "memory consumption". It will not count the three pointers in an `std::vector` which is a local variable on the stack, but it will count all of the memory used by all of the strings in such a vector (since all of the memory for the contents of a vector is dynamically allocated). — James Kanze, Aug 08 '12 at 08:18

Memory consumption by STL containers

2 Answers2

Linked

Related