Adwait Thattey

Posted on Aug 1, 2022

Optimizing C++ vector for 2x performance !

#cpp #optimization #programming #stl

std::vector is perhaps one of the most used data structures in C++. It provides a dynamic array that is very easy to use.
But the simplicity comes at a slight performance cost that is often ignored. It is however really simple to optimize this data-structure and get a performance boost.

First lets look at the problem.

Here I am creating a simple class that keeps track of the constructor, destructor and the copy constructor calls.


class Sample
{
public:

Sample(int id)
{
     ++m_constructor_count;

      m_id = id;

}



~Sample()
{
     ++m_destructor_count;
}



Sample( const Sample& o)
{
      ++m_copy_constructor_count;
}



   int m_id = -1;

   static unsigned long m_constructor_count, m_destructor_count, m_copy_constructor_count;



};



// initialize counts to 0

unsigned long Sample::m_constructor_count = 0;
unsigned long Sample::m_destructor_count = 0;
unsigned long Sample::m_copy_constructor_count = 0;

Now lets create a vector , add 3 elements to it and print the calls

std::vector<Sample> vec;

vec.push_back( Sample(1) );
vec.push_back( Sample(2) );
vec.push_back( Sample(3) );

We have 3 Constructor calls but 6 Copy Calls and 9 Destructor calls !

Constructor calls are expected, we are creating 3 elements. But where are these copy and destructor calls coming from ??

Well, the destructor calls are just a sum of constructor and copy. So lets look at the copy calls.

This is due to 2 problems with std::vector

1. Copy while insertion

2. Copy while resizing

Lets look at 1st problem.

1. Copy while insertion

Look at this statement

vec.push_back( Sample(1) );

Here we are first creating an object of class Sample, then when it is inserted to the vector, it is copied to the vector's memory.

This is the source of 3 copy calls as we have 3 items.

Since we just want to insert element into vector, is there any way to directly create the object in vector's memory?

Yes there is!

std::vector provides another method emplace_back .

Using this method, we can directly pass the arguments that we would have passed to the constructor and the vector directly creates the object in its memory

vec.emplace_back( 1 );

Lets look at the results now

We have reduced 3 copy calls

What about the remaining 3 calls?

This brings us to the 2nd problem

2. Copy while resizing

A vector is a dynamic array. Meaning, the compiler doesn't know about it's size beforehand.

So the compiler starts with 1 and dynamically increases the capacity of vector as we add to it.

This means that every time the vector runs out of it's capacity, it needs to resize. This resize operation copies all the elements from 1 memory location to another.

Lets track how the 3 copies are happening

std::vector<Sample> vec;

// initialized with capacity 1



vec.push_back( Sample(1) );

// insert 1 element. capacity is 1, size is 1. 



vec.push_back( Sample(2) );

// exceeded capacity. Resize operation. Copy the 1 element in the vector to new location. New size and capacity is 2

// 1 Copy


vec.push_back( Sample(3) );

// exceeded size. Resize vector. Copy the 2 elements in the vector to new location. New size is 3

// 2 Copies



Total copies due to resize: 3

This is the source of 3 additional copy calls.

Does this mean that n copies will take place every time we insert a new element?

Well no. The system can allocate additional memory assuming that we are adding more elements.

While this can change compiler to compiler, memory is usually allocated in 2s power.

For example, when we add 3 elements, memory is allocated for 4, adding 5th allocates for 8, adding 9th allocates for 16, adding 17th for 32 and so on. Take a look at this

This means that not only are we causing unnecessary copy calls, we are also potentially using up additional memory that is not needed. For example in the above case, even if we had only 129 elements, we were using the memory for 256 elements.

So, is there a way to avoid this?

Yes there is.

We just need a way to tell the compiler how many elements we are planning to insert so that system can reserve the needed memory beforehand reducing the copy calls.

For this, std::vector provides another method. reserve

This allows us to specify how many elements we are planning to insert and causes the vector to allocate that much memory beforehand

Lets modify our code to use this

std::vector<Sample> vec;

vec.reserve(3); // specify we are going to insert 3 elements



vec.emplace_back( 1 );
vec.emplace_back( 2 );
vec.emplace_back( 3 );

We have successfully removed all the copy constructor calls.

Performance Improvement

Now as a final step, lets also see how much performance improvement can this lead to.

For this I am going to count the number of clock ticks utilized for inserting 10 million elements

First without using emplace and reserve

732483 ticks

(Also notice we have 26 million additional copy calls for just 10 million elements!)

Now using emplace and reserve

386635 ticks

That's more than 2x performance improvement. And best part , it did not require a lot of effort.

Summary

A copy operation takes place when we use push_back to insert into vector and multiple copy operations take place whenever the vector runs out of space and resize takes place.

Use emplace_back instead of push_back wherever possible.

If the number of elements we are going to insert is known before hand, use reserve to specify the capacity.

Even if exact size is not known, it might still be worthwhile to use reserve with some known lower bound for the number of elements.