Is std::push_back relatively expensive to use?

Question

I want to improve the performance of the following code. What aspect might affect the performance of the code when it's executed?

Also, considering that there is no limit to how many objects you can add to the container, what improvements could be made to “Object” or “addToContainer” to improve the performance of the program?

I was wondering if std::push_back in C++ affects performance of the code in any way? Especially if there is no limit to adding to list.

struct Object{
    string name;
    string description;
};

vector<Object> container;
void addToContainer(Object object) {
    container.push_back(object);
}

int main() {
    addToContainer({ "Fira", "+5 ATTACK" });
    addToContainer({ "Potion", "+10 HP" });
}

Answer 1

Before you do ANYTHING profile the code and get a benchmark. After you make a change profile the code and get a benchmark. Compare the benchmarks. If you do not do this, you're rolling dice. Is it faster? Who knows.

Profile profile profile.

With push_back you have two main concerns:

1. Resizing the vector when it fills up, and
2. Copying the object into the vector.

There are a number of improvements you can make to the resizing cost cost of push_back depending on how items are being added.

Strategic use of reserve to minimize the amount of resizing, for example. If you know how many items are about to be added, you can check the capacity and size to see if it's worth your time to reserve to avoid multiple resizes. Note this requires knowledge of vector's expansion strategy and that is implementation-specific. An optimization for one vector implementation could be a terribly bad mistake on another.

You can use insert to add multiple items at a time. Of course this is close to useless if you need to add another container into the code in order to bulk-insert.

If you have no idea how many items are incoming, you might as well let vector do its job and optimize HOW the items are added.

For example

void addToContainer(Object object) // pass by value. Possible copy 
{
    container.push_back(object); // copy
}

Those copies can be expensive. Get rid of them.

void addToContainer(Object && object) //no copy and can still handle temporaries
{
    container.push_back(std::move(object)); // moves rather than copies 
}

std::string is often very cheap to move.

This variant of addToContainer can be used with

addToContainer({ "Fira", "+5 ATTACK" });
addToContainer({ "Potion", "+10 HP" });

and might just migrate a pointer and as few book-keeping variables per string. They are temporaries, so no one cares if it will rips their guts out and throws away the corpses.

As for existing Objects

Object o{"Pizza pop", "+5 food"};
addToContainer(std::move(o));

If they are expendable, they get moved as well. If they aren't expendable...

void addToContainer(const Object & object) // no copy
{
    container.push_back(object); // copy
}

You have an overload that does it the hard way.

Tossing this one out there

If you already have a number of items you know are going to be in the list, rather than appending them all one at a time, use an initialization list:

vector<Object> container{
    {"Vorpal Cheese Grater", "Many little pieces"},
    {"Holy Hand Grenade", "OMG Damage"}
};

Answer 2

push_back can be extremely expensive, but as with everything, it depends on the context. Take for example this terrible code:

std::vector<float> slow_func(const float* ptr)
{
   std::vector<float> v;
   for(size_t i = 0; i < 256; ++i)
     v.push_back(ptr[i]);
   return v;
}

each call to push_back has to do the following:

1. Check to see if there is enough space in the vector
2. If not, allocate new memory, and copy the old values into the new vector
3. copy the new item to the end of the vector
4. increment end

Now there are two big problems here wrt performance. Firstly each push_back operation depends upon the previous operation (since the previous operation modified end, and possibly the entire contents of the array if it had to be resized). This pretty much destroys any vectorisation possibilities in the code. Take a look here:

https://godbolt.org/z/RU2tM0

The func that uses push_back does not make for very pretty asm. It's effectively hamstrung into being forced to copy a single float at a time. Now if you compare that to an alternative approach where you resize first, and then assign; the compiler just replaces the whole lot with a call to new, and a call to memcpy. This will be a few orders of magnitude faster than the previous method.

std::vector<float> fast_func(const float* ptr)
{
   std::vector<float> v(256);
   for(size_t i = 0; i < 256; ++i)
     v[i] = ptr[i];
   return v;
}

BUT, and it's a big but, the relative performance of push_back very much depends on whether the items in the array can be trivially copied (or moved). If you example you do something silly like:

struct Vec3 {
   float x = 0;
   float y = 0;
   float z = 0;
};

Well now when we did this:

std::vector<Vec3> v(256);

The compiler will allocate memory, but also be forced to set all the values to zero (which is pointless if you are about to overwrite them again!). The obvious way around this is to use a different constructor:

std::vector<Vec3> v(ptr, ptr + 256);

So really, only use push_back (well, really you should prefer emplace_back in most cases) when either:

1. additional elements are added to your vector occasionally
2. or, The objects you are adding are complex to construct (in which case, use emplace_back!)

Answer 3

without any other requirements, unfortunately this is the most efficient:

 void addToContainer(Object) { } 

to answer the rest of your question. In general push_back will just add to the end of the allocated vector O(1), but will need to grow the vector on occasion, which can be amortized out but is O(N)

also, it would likely be more efficient not to use string, but to keep char * although memory management might be tricky unless it is always a literal being added