Drakosha
Drakosha

Reputation: 12155

How can i estimate memory usage of std::map?

For example, I have a std::map with known sizeof(A) and sizeof(B), while map has N entries inside. How would you estimate its memory usage? I'd say it's something like

(sizeof(A) + sizeof(B)) * N * factor

But what is the factor? Different formula maybe?

Maybe it's easier to ask for upper bound?

Upvotes: 49

Views: 49461

Answers (7)

abhiarora
abhiarora

Reputation: 10430

I was also looking for something to calculate the size of the std::map. I have tried what was explained in Diomidis Spinellis's answer and expanded his answer over here which could be helpful to others.

I am expanding on his answer by adding few lines of code.

#include <bits/stl_tree.h>
int main(int argc, char *argv[])
{
    std::cout << sizeof(std::_Rb_tree_node_base) << std::endl;
    return 0;
}

Outputs (On my ARM Cortex A-9 iMX6Solo-X processor running Linux [4.9.175] and compiler: arm-fslc-linux-gnueabi-gcc (GCC) 7.3.0):

16

Considering std::map<A, B>, I am interested in size of ELEMENT_OVERHEAD as it grows linearly with the number of elements present in the map. ELEMENT_OVERHEAD was found to be equivalent of sizeof(std::_Rb_tree_node_base) as hence has a value of 16 for my system.

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

Upvotes: 0

user2548100
user2548100

Reputation: 4661

I recently needed to answer this question for myself, and simply wrote a small benchmark program using std::map I compiled under MSVC 2012 in 64-bit mode.

A map with 150 million nodes soaked up ~ 15GB, which implies the 8 byte L, 8 byte R, 8 byte int key, and 8 byte datum, totaling 32 bytes, soaked up about 2/3rds of the map's memory for internal nodes, leaving 1/3rd for leaves.

Personally, I found this to be surprisingly poor memory efficiency, but it is what it is.

Hope this makes for a handy rule-of-thumb.

PS: The overhead of a std::map is that of a single node's size AFAICT.

Upvotes: 11

Diomidis Spinellis
Diomidis Spinellis

Reputation: 19335

The estimate would be closer to

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

There is an overhead for each element you add, and there is also a fixed overhead for maintaining the data structure used for the data structure storing the map. This is typically a binary tree, such as a Red-Black Tree. For instance, in the GCC C++ STL implementation ELEMENT_OVERHEAD would be sizeof(_Rb_tree_node_base) and CONTAINER_OVERHEAD would be sizeof(_Rb_tree). To the above figure you should also add the overhead of memory management structures used for storing the map's elements.

It's probably easier to arrive at an estimate by measuring your code's memory consumption for various large collections.

Upvotes: 38

dirkgently
dirkgently

Reputation: 111130

If you really want to know the runtime memory footprint, use a custom allocator and pass it in when creating the map. See Josuttis' book and this page of his (for a custom allocator).

Maybe it's easier to ask for upper bound?

The upper bound will depend on the exact implementation (e.g. the particular variant of balanced tree used). Maybe, you can tell us why you need this information so we can help better?

Upvotes: 16

Xavier Nodet
Xavier Nodet

Reputation: 5085

You could use MemTrack, by Curtis Bartley. It's a memory allocator that replaces the default one and can track memory usage down to the type of allocation.

An example of output:

-----------------------
Memory Usage Statistics
-----------------------

allocated type                        blocks          bytes  
--------------                        ------          -----  
struct FHRDocPath::IndexedRec          11031  13.7% 2756600  45.8%
class FHRDocPath                       10734  13.3%  772848  12.8%
class FHRDocElemPropLst                13132  16.3%  420224   7.0%
struct FHRDocVDict::IndexedRec          3595   4.5%  370336   6.2%
struct FHRDocMDict::IndexedRec         13368  16.6%  208200   3.5%
class FHRDocObject *                      36   0.0%  172836   2.9%
struct FHRDocData::IndexedRec            890   1.1%  159880   2.7%
struct FHRDocLineTable::IndexedRec       408   0.5%  152824   2.5%
struct FHRDocMList::IndexedRec          2656   3.3%  119168   2.0%
class FHRDocMList                       1964   2.4%   62848   1.0%
class FHRDocVMpObj                      2096   2.6%   58688   1.0%
class FHRDocProcessColor                1259   1.6%   50360   0.8%
struct FHRDocTextBlok::IndexedRec        680   0.8%   48756   0.8%
class FHRDocUString                     1800   2.2%   43200   0.7%
class FHRDocGroup                        684   0.8%   41040   0.7%
class FHRDocObject * (__cdecl*)(void)     36   0.0%   39928   0.7%
class FHRDocXform                        516   0.6%   35088   0.6%
class FHRDocTextColumn                   403   0.5%   33852   0.6%
class FHRDocTString                      407   0.5%   29304   0.5%
struct FHRDocUString::IndexedRec        1800   2.2%   27904   0.5%

Upvotes: 20

anon
anon

Reputation:

The formula is more like:

(sizeof(A) + sizeof(B) + factor) * N

where factor is the per entry overhead. C++ maps are typically implemented as red-black trees. These are binary trees, so there will be at least two pointers for the left/right nodes. There will also be some implementation stuff - probably a parent pointer and a "colour" indicator, so factor may be something like

(sizeof( RBNode *) * 3 + 1) / 2

However, all this is highly implementation dependent - to find out for sure you really need to examine the code for your own library implementation.

Upvotes: 0

Cătălin Pitiș
Cătălin Pitiș

Reputation: 14341

The size of the map really depends on the implementation of the map. You might have different sizes on different compilers/platforms, depending on which STL implementation they are providing.

Why do you need this size?

Upvotes: -2

Related Questions