Sudden memory spike at 700,000 vector elements

Question

So I was running a memory usage test in my program where I was adding 20 elements each to two separate vectors each frame (~60fps). I expected that at some point I would start seeing a memory leak, but instead memory usage remained constant until a certain critical point. Around 700,000 elements total it spiked and then leveled off again at the new plateau.

I have a feeling this has something to do with the allocation of the vectors being automatically increased at that point, but I'm not sure and can't find anything online. It also wouldn't really explain why so much extra memory was allocated at that point (Private Bytes on the CPU jumped from ~800 to ~900, and System GPU Memory jumped from ~20 to ~140). Here are the Process Explorer graphs for both CPU and GPU:

Note: the dips in both CPU and GPU usage are from me pausing the program after seeing the spike.

Can anyone explain this to me?

Edit: Here's a simpler, more general test:

The total usage is obviously a lot lower, but same idea.

Answer 1

When you add an element to an empty vector, it will allocate enough space via new for several elements. Like 16 maybe. It does this because resizing the array to a larger buffer is slow, so it allocates more than it needs. If it allocates room for 16 elements, that means you can push back 15 more before it needs to bother with another call to new. Each time it grows significantly more. If you have 500 elements (and it's out of room) and you push back one more, it may allocate room for 750. Or maybe even 1000. Or 2000. Plenty of room.

It turns out that when you (or the vector) call new, you get this from the program's memory manager. If the program's memory manager doesn't have enough memory available, it will ask the operating system for a HUGE amount of memory, because operating system calls are themselves slow, and messing with page mappings is slow. So when vector asks for room for 200 bytes, the program's memory manager may actually grab like 65536 bytes, and then give the vector only 200 of that, and save the remaining 65336 bytes for the next call(s) to new. Because of this, you (or vector) can call new many many times before you have to bother the operating system again, and things go quickly.

But this has a side effect: The operating system can't actually tell how much memory your program is really using. All it knows is that you allocated 65536 from it, so it reports that. As you push back elements in the vector, eventually the vector runs out of capacity, and asks more from the program's memory manager. And as it does that more and more, and the operating system reports the same memory usage, because it can't see. Eventually the memory manager runs out of capacity, and asks for more from the operating system. The operating system allocates another huge block (65536? 131072?) and you see a sudden large spike in memory usage.

The vector size at which this happens isn't set, it depends on what else has also been allocated, and what order they were allocated and deallocated. Even the things that you deleted still affect things, it's pretty darn complicated. Also, the rate at which vector grows depending on your library implementation, and the amount of memory the program's memory manager grabs from the OS also varies depending on factors even I don't know about.

I have no idea why the GPU's memory would spike, it depends on what you were doing with your program. But note that there is less GPU memory total, it's entirely possible it grew by a smaller amount than "private bytes".

Answer 2

Vectors use a dynamically allocated array to store their elements.This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container. Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). This explains your plateaus. The capacity enlargement is done by doubling the current one. It may be the case that after a finite number of doubling, its quadrupling the capacity. Which will explain your spike.

Answer 3

Vector Size and Capacity

For good performance by allocating more memory than ever needed.

size()

Returns the current number of elements

empty()

Returns whether the container is empty (equivalent to 0==size() but faster)

capacity()

Returns the maximum possible number of elements without reallocation

reserve(num)

Enlarges capacity, if not enough yet

The capacity of a vector is important, because Reallocation invalidates all references, pointers, and iterators for elements. Reallocation takes time by moving all elements to new heap location. Reallocation size increment depends on the actual vector implementation.

Code example for using reserve(num):

std::vector<int> v1;  // Create an empty vector    
v1.reserve(80);       // Reserve memory for 80 elements