Spatial complexity of std::vector after a call to reserve()

Question

I'm trying to understand the way std::vector spatial complexity evolve after a call to reserve().

Here is the code :

vector<SparseData<T_Indices, T_Values>> v1 = vector<SparseData<T_Indices, T_Values>>();
v1.reserve(341);
vector<SparseData<T_Indices, T_Values>> v2 = vector<SparseData<T_Indices, T_Values>>();
v2.reserve(342);

With SparseData containing 3 integers (4 Bytes each).

v1 cost is the theoritical cost O(v1) = 341*3*4 = 4092 Bytes. Fine.

My problem is v2 cost. I expected O(v2) = 342*3*4 = 4104 Bytes but the actual cost is 4151 Bytes. There's a 47 Bytes delta that I can't understand.

I'm measuring space using Visual Studio 2017 Community Diagnostic Tools (Snapshotting heap) which, I believe, is trustable.

What's the meaning of these 47 Bytes? What do they possibly represent?

Thanks in advance.

Edit : I've edited the initial post so that classes names match with the screenshots. Below, the measured values for v1 (resp. v2) after a call to reserve(341) (resp. reserve(342)). Notice that two elements are not having same "values" than others. Also, v2 contains 345 SparseData elements, giving an explanation for the first 4140 Bytes : fine, this is the or greater part from the documentation :

If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater).

Still looking for the 11 Bytes delta tho.

Run the code again for v3.reserve(343). Normally, the vector<> algorithm adds chunks of memory for storage. It is implemented as an array which grows dynamically in chunks. You should see that the increase for the next step will be zero or a smaller value, so you will see a step function for increases in size. — Gardener, Oct 24 '18 at 12:58
`reserve` increases capacity to the value _greater_ or equal than requested. You are not guaranteed that it'll allocate exactly `N` bytes. Just `>= N`. — Dan M., Oct 24 '18 at 13:01
Done, the measured cost for v3 is 4163 Bytes. Theoretical cost is 4116 (343*4*3) so we're still having a 47 Bytes delta. I tried with reserve(3000) and still measuring this 47 Bytes difference. — Wassim, Oct 24 '18 at 13:05
@Spazz do you have optimization on or off? It makes a big difference — Mgetz, Oct 24 '18 at 13:06
The increase from v2 to v3 is 4163 - 4151 = 12 which = 4*3. It looks like it only added 12 bytes, but carries a 47 byte overhead for keeping track of the array fields. That blows my chunk theory, but shows that they are not wasting overhead for each increase in size. — Gardener, Oct 24 '18 at 13:13
@Mgetz : I'm using the Debug configuration targeting x64 platform, I suppose there's no optimization. Still, I'd like to understand the meaning of these 47 Bytes since they are recurrent. — Wassim, Oct 24 '18 at 13:17
@Spazz the MSVC debug allocator is not the release allocator, I'd try again in release mode. The debug one tends to add guard pages and other heap debugging tools — Mgetz, Oct 24 '18 at 14:07
Related [MSVC Heap Debug Sentinel Values](https://stackoverflow.com/a/370362/332733) you'll notice that the values you're looking at correspond to `0xCDCDCDCD` or clean memory just allocated but not initialized. — Mgetz, Oct 24 '18 at 14:14

score 1 · Answer 1 · answered Oct 24 '18 at 13:01

There are a few things that could be happening

std::vector::reserve is allowed to over allocate space. This is because the allocator is allowed to over allocate space. So what you could be seeing is just what MSVC's allocator allocates when you ask for 4014 bytes.
Visual Studio 2017 Community Diagnostic Tools might not be fined grained enough and it not only sees the allocation for the vector but it also captures memory allocated from somewhere else.
a combination of 1 and 2.

It's also possible this is the debug allocator... and that's a guard page — Mgetz, Oct 24 '18 at 13:09

Gardener · Answer 2 · 2018-10-24T13:42:50.483

Based on your subsequent experiment

v2.reserve(342) = 4151 
v2.reserve(343) = 4163

4163 - 4151 = 12 which = 4*3, which is the expected increase with no overhead.

The difference between the two memory usage levels is 12 bytes. Hence, the 47 bytes may simply be the overhead that the compiler uses for keeping track of other details related to the vector.

It may be that reserve() allocates a specific memory amount and that actually adding elements will create the step-function increase in memory usage.

In any case, the reserve() should be set at the level you expect to not exceed. As the vector increases in size, the run-time must reallocate memory and copy the old vector to the new memory space. Hence, as I am sure you are already aware, reserve() should not be called incrementally.

It would be interesting to see a graph of reserve(n) calls from 1 - 1000 with memory usage compared to the adding of 1000 elements with memory usage amounts after each addition.

Spatial complexity of std::vector after a call to reserve()

2 Answers2