J@ArangoDB

{ "subject" : "ArangoDB", "tags": [ "multi-model", "nosql", "database" ] }

How Much Memory Does an STL Container Use?

Ever wondered how much heap memory will be used by STL containers, and in what chunks they will allocate it?

Here is the answer for some frequently used containers types containing uint64_t values (an 8 byte type). For the associative containers I also used uint64_t as the key type.

All results are for the STL implementation I had ready at hand (g++5.3 on Ubuntu 16.04, x86_64, libstdc++.so.6.0.22, with default allocator). The results may be completely different for other platforms and/or other data types.

The following containers are compared:

  • std::vector<uint64_t>
  • std::map<uint64, uint64_t>
  • std::set<uint64_t>
  • std::unordered_map<uint64, uint64_t>
  • std::unordered_set<uint64_t>
  • std::deque<uint64_t>

The containers themselves are creared on the stack. To store the elements, the containers will need to use heap memory. The number of elements in the containers (n) is increased exponentially from 0 (empty) to 512 in the tests. The memory usage pattern should be quite clear by then.

Reported are the amount of heap memory allocated by the container after all elements have been inserted, the total number of heap memory allocated by the container during its whole lifetime (i.e. the sum of all its mallocs), plus the number of calls to malloc and free the container issued.

heap allocation results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

n =     0
---------
vector         =>     0 bytes allocd at end,  total:     0 bytes mallocd,    0 malloc(s), 0 free(s)
map            =>     0 bytes allocd at end,  total:     0 bytes mallocd,    0 malloc(s), 0 free(s)
set            =>     0 bytes allocd at end,  total:     0 bytes mallocd,    0 malloc(s), 0 free(s)
unordered_map  =>     0 bytes allocd at end,  total:     0 bytes mallocd,    0 malloc(s), 0 free(s)
unordered_set  =>     0 bytes allocd at end,  total:     0 bytes mallocd,    0 malloc(s), 0 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =     1
---------
vector         =>     8 bytes allocd at end,  total:     8 bytes mallocd,    1 malloc(s), 0 free(s)
map            =>    48 bytes allocd at end,  total:    48 bytes mallocd,    1 malloc(s), 0 free(s)
set            =>    40 bytes allocd at end,  total:    40 bytes mallocd,    1 malloc(s), 0 free(s)
unordered_map  =>    40 bytes allocd at end,  total:    40 bytes mallocd,    2 malloc(s), 0 free(s)
unordered_set  =>    32 bytes allocd at end,  total:    32 bytes mallocd,    2 malloc(s), 0 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =     2
---------
vector         =>    16 bytes allocd at end,  total:    24 bytes mallocd,    2 malloc(s), 1 free(s)
map            =>    96 bytes allocd at end,  total:    96 bytes mallocd,    2 malloc(s), 0 free(s)
set            =>    80 bytes allocd at end,  total:    80 bytes mallocd,    2 malloc(s), 0 free(s)
unordered_map  =>    88 bytes allocd at end,  total:   104 bytes mallocd,    4 malloc(s), 1 free(s)
unordered_set  =>    72 bytes allocd at end,  total:    88 bytes mallocd,    4 malloc(s), 1 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =     4
---------
vector         =>    32 bytes allocd at end,  total:    56 bytes mallocd,    3 malloc(s), 2 free(s)
map            =>   192 bytes allocd at end,  total:   192 bytes mallocd,    4 malloc(s), 0 free(s)
set            =>   160 bytes allocd at end,  total:   160 bytes mallocd,    4 malloc(s), 0 free(s)
unordered_map  =>   136 bytes allocd at end,  total:   152 bytes mallocd,    6 malloc(s), 1 free(s)
unordered_set  =>   104 bytes allocd at end,  total:   120 bytes mallocd,    6 malloc(s), 1 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =     8
---------
vector         =>    64 bytes allocd at end,  total:   120 bytes mallocd,    4 malloc(s), 3 free(s)
map            =>   384 bytes allocd at end,  total:   384 bytes mallocd,    8 malloc(s), 0 free(s)
set            =>   320 bytes allocd at end,  total:   320 bytes mallocd,    8 malloc(s), 0 free(s)
unordered_map  =>   280 bytes allocd at end,  total:   336 bytes mallocd,   11 malloc(s), 2 free(s)
unordered_set  =>   216 bytes allocd at end,  total:   272 bytes mallocd,   11 malloc(s), 2 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =    16
---------
vector         =>   128 bytes allocd at end,  total:   248 bytes mallocd,    5 malloc(s), 4 free(s)
map            =>   768 bytes allocd at end,  total:   768 bytes mallocd,   16 malloc(s), 0 free(s)
set            =>   640 bytes allocd at end,  total:   640 bytes mallocd,   16 malloc(s), 0 free(s)
unordered_map  =>   568 bytes allocd at end,  total:   712 bytes mallocd,   20 malloc(s), 3 free(s)
unordered_set  =>   440 bytes allocd at end,  total:   584 bytes mallocd,   20 malloc(s), 3 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =    32
---------
vector         =>   256 bytes allocd at end,  total:   504 bytes mallocd,    6 malloc(s), 5 free(s)
map            =>  1536 bytes allocd at end,  total:  1536 bytes mallocd,   32 malloc(s), 0 free(s)
set            =>  1280 bytes allocd at end,  total:  1280 bytes mallocd,   32 malloc(s), 0 free(s)
unordered_map  =>  1144 bytes allocd at end,  total:  1472 bytes mallocd,   37 malloc(s), 4 free(s)
unordered_set  =>   888 bytes allocd at end,  total:  1216 bytes mallocd,   37 malloc(s), 4 free(s)
deque          =>   576 bytes allocd at end,  total:   576 bytes mallocd,    2 malloc(s), 0 free(s)


n =    64
---------
vector         =>   512 bytes allocd at end,  total:  1016 bytes mallocd,    7 malloc(s), 6 free(s)
map            =>  3072 bytes allocd at end,  total:  3072 bytes mallocd,   64 malloc(s), 0 free(s)
set            =>  2560 bytes allocd at end,  total:  2560 bytes mallocd,   64 malloc(s), 0 free(s)
unordered_map  =>  2312 bytes allocd at end,  total:  3016 bytes mallocd,   70 malloc(s), 5 free(s)
unordered_set  =>  1800 bytes allocd at end,  total:  2504 bytes mallocd,   70 malloc(s), 5 free(s)
deque          =>  1088 bytes allocd at end,  total:  1088 bytes mallocd,    3 malloc(s), 0 free(s)


n =   128
---------
vector         =>  1024 bytes allocd at end,  total:  2040 bytes mallocd,    8 malloc(s), 7 free(s)
map            =>  6144 bytes allocd at end,  total:  6144 bytes mallocd,  128 malloc(s), 0 free(s)
set            =>  5120 bytes allocd at end,  total:  5120 bytes mallocd,  128 malloc(s), 0 free(s)
unordered_map  =>  4664 bytes allocd at end,  total:  6144 bytes mallocd,  135 malloc(s), 6 free(s)
unordered_set  =>  3640 bytes allocd at end,  total:  5120 bytes mallocd,  135 malloc(s), 6 free(s)
deque          =>  1600 bytes allocd at end,  total:  1600 bytes mallocd,    4 malloc(s), 0 free(s)


n =   256
---------
vector         =>  2048 bytes allocd at end,  total:  4088 bytes mallocd,    9 malloc(s), 8 free(s)
map            => 12288 bytes allocd at end,  total: 12288 bytes mallocd,  256 malloc(s), 0 free(s)
set            => 10240 bytes allocd at end,  total: 10240 bytes mallocd,  256 malloc(s), 0 free(s)
unordered_map  =>  9416 bytes allocd at end,  total: 12488 bytes mallocd,  264 malloc(s), 7 free(s)
unordered_set  =>  7368 bytes allocd at end,  total: 10440 bytes mallocd,  264 malloc(s), 7 free(s)
deque          =>  2624 bytes allocd at end,  total:  2624 bytes mallocd,    6 malloc(s), 0 free(s)


n =   512
---------
vector         =>  4096 bytes allocd at end,  total:  8184 bytes mallocd,   10 malloc(s), 9 free(s)
map            => 24576 bytes allocd at end,  total: 24576 bytes mallocd,  512 malloc(s), 0 free(s)
set            => 20480 bytes allocd at end,  total: 20480 bytes mallocd,  512 malloc(s), 0 free(s)
unordered_map  => 18872 bytes allocd at end,  total: 25216 bytes mallocd,  521 malloc(s), 8 free(s)
unordered_set  => 14776 bytes allocd at end,  total: 21120 bytes mallocd,  521 malloc(s), 8 free(s)
deque          =>  4752 bytes allocd at end,  total:  4816 bytes mallocd,   11 malloc(s), 1 free(s)

I have intentionally not done any optimizations such as calling reserve() on the containers before inserting the individual elements, in order to reflect some real-word scenarios in which it is unclear how much elements will be added to the containers during program execution.

The test program for reproduction is here. Compile and run it with:

compiling and executing the test program
1
2

g++ -std=c++11 -O0 containers.cpp -o containers
for i in 0 1 2 4 8 16 32 64 128 256 512; do ./containers "$i"; done