Updated January 29, 2014, 4:42 pm

std::vector reserve

The vector class in C++ handles memory allocations for you which is great, however if you are going to add a lot of elements and if you know how many elements the vector will have before it is a good idea to call vector.reserve to preallocate the required memory.

One example is the vertices of a big terrain. Let's assume we have a Vertex structure like this :

struct Vertex
{
	Vertex(float x, float y, float z) : x(x), y(y), z(z) {}
	float x, y, z;
	float r, g, b;
};

Now we can fill out a vector of these as follows :

int terrainSize = 1025;
float spacing = 10.0f;

std::vector<Vertex> vector1;

for (int i = 0; i < terrainSize; ++i)
{
	for(int k=0; i< terrainSize; ++k)
	{
		vector1.emplace_back(k * spacing, 0.0f, i * spacing);
	}
}

This code will fill out the vector1, the downside to this is that every time a new element is added to the vector it might have to allocate more memory. The vector class keeps all its elements in a continuous block of memory, when you add new elements if there isn't enough room to add the element the vector will allocate enough memory to fit all it's elements and copy everything to this new memory. This can lead to slowness as we are calling emplace_back 1050625 times. There will be less allocations than this number as most implementations are smart enough to not make allocations on each insertion, usually they increase the capacity by double, but this is implementation defined.

What we can do to increase performance is we can call reserve() to allocate all the required memory. Once we allocate enough memory to hold all the elements emplace_back will no longer need to make allocations.

Here is the code with the addition of reserve. Notice how that is the only change I made :

int terrainSize = 1025;
float spacing = 10.0f;

std::vector<Vertex> vector2;
vector2.reserve(terrainSize * terrainSize);
for (int i = 0; i < terrainSize; ++i)
{
	for(int k=0; i< terrainSize; ++k)
	{
		vector2.emplace_back(k * spacing, 0.0f, i * spacing);
	}
}

So how much of an effect does this have on performance?

without reserve 55.6633ms
with reserve 10.2495ms

Using reserve is 5 times faster on my machine. So if you know how many elements you are going to need use reserve. Even if you have a rough idea of how many elements you will need you can still use reserve. Once the vector fills up it will keep allocating memory.

Full code :

#include <iostream>
#include <vector>
#include "Profiler.h"

struct Vertex
{
	Vertex(float x, float y, float z) : x(x), y(y), z(z) {}
	float x, y, z;
	float r, g, b;
};

int main()
{
	int terrainSize = 1025;
	float spacing = 10.0f;
	std::vector<Vertex> vector1;
	std::vector<Vertex> vector2;
	
	Profiler::begin("without reserve");
	for (int i = 0; i < terrainSize; ++i)
	{
		for (int k = 0; k < terrainSize; ++k)
		{
			
			vector1.emplace_back(k * spacing, 0.0f, i * spacing);
		}
	}
	Profiler::TimeData* td1 = Profiler::end("without reserve");
	
	Profiler::begin("with reserve");
	vector2.reserve(terrainSize * terrainSize);
	for (int i = 0; i < terrainSize; ++i)
	{
		for (int k = 0; k < terrainSize; ++k)
		{
			vector2.emplace_back(k * spacing, 0.0f, i * spacing);
		}
	}
	Profiler::TimeData* td2 = Profiler::end("with reserve");

	std::cout << td1->name << " " << td1->elapsedTime << "ms\n";
	std::cout << td2->name << " " << td2->elapsedTime << "ms\n";

	return 0;
}