Optimizing C++ vector for 2x performance !
Tags: cpp, optimization, programming, stl
Published: 2022-08-01 06:08:00

**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. 


```c++

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) );
```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iou9kyvebprsohic9nk7.png)


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](https://en.cppreference.com/w/cpp/container/vector/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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j86u15ci3ylwgxs3yvi1.png)

 
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

```c++
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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ck384l0bze5dc8lzp4tg.png)

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_**](https://en.cppreference.com/w/cpp/container/vector/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

```c++
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 );
```
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/boue8zo4f55v2alpuu2z.png)

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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xg6jpsiawkc9uvjyspn5.png)

732483 ticks

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

 
Now using emplace and reserve 
 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eoorl3xdgypn7sqbzzy7.png)
 
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. 

### Credits

This video by "The Cherno" on Youtube was the source of inspiration for this post. 

**_[https://www.youtube.com/watch?v=HcESuwmlHEY](https://www.youtube.com/watch?v=HcESuwmlHEY)_**


This channel has lots of neat tips and tricks for C++. Please like this video and subscribe to his channel.  

[The Cherno - YouTube ](https://www.youtube.com/c/TheChernoProject)