Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ push_back vs Insert vs emplace

I'm currently making an application using vectors with C++.

I know how pre-optimization is the root of all evil.

But I really can't help being curious.

I'm adding parts of other vectors into another vector.
We'll say the vector will have a size that never changes of 300.

Since I always append to the end of the vector

Is it faster to do:
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

or would it be faster to loop through the vector I want to append and add each items individually(while still reserving beforehand) with push_back or emplace. (unsure which is faster)

Anyone can help me on this?

like image 503
Darkalfx Avatar asked Feb 21 '13 18:02

Darkalfx


People also ask

What is the difference between emplace and Push_back?

push_back: Adds a new element at the end of the container, after its current last element. The content of val is copied (or moved) to the new element. emplace_back: Inserts a new element at the end of the container, right after its current last element.

Is emplace better than insert?

Both are used to add an element in the container. The advantage of emplace is, it does in-place insertion and avoids an unnecessary copy of object. For primitive data types, it does not matter which one we use. But for objects, use of emplace() is preferred for efficiency reasons.

What is difference between emplace and insert?

The primary difference is that insert takes an object whose type is the same as the container type and copies that argument into the container. emplace takes a more or less arbitrary argument list and constructs an object in the container from those arguments.

Why emplace back is faster than Push_back?

because emplace_back would construct the object immediately in the vector, while push_back , would first construct an anonymous object and then would copy it to the vector.


2 Answers

Here's a general principle: when a library provides both do_x_once and do_x_in_batch, then the latter should be at least as fast as calling do_x_once in a simple loop. If it isn't, then the library is very badly implemented since a simple loop is enough to get a faster version. Often, such batch functions/methods can perform additional optimizations because they have knowledge of data structure internals.

So, insert should be at least as fast as push_back in a loop. In this particular case, a smart implementation of insert can do a single reserve for all the elements you want to insert. push_back would have to check the vector's capacity every time. Don't try to outsmart the library :)

like image 55
Fred Foo Avatar answered Sep 30 '22 01:09

Fred Foo


I guess it really depends on the compiler (library implementation), compiling options and architecture. Doing a quick benchmark in VS2005 without optimization (/Od) on Intel Xeon:

std::vector<int> a;
std::vector<int> b;

// fill 'a' with random values for giggles

timer.start()
// copy values from 'a' to 'b'
timer.stop()

I get these results for 10 000 000 items using these different methods of "copy values...":

  1. Reserve space for 'b', then for-loop using b.push_back(a[i]);: 0.808 sec
  2. Resize 'b', then for-loop using indices assignment b[i] = a[i];: 0.264 sec
  3. No re-sizing 'b', just b.insert(b.end(), a.begin(), a.end());: 0.021 sec (no significant difference with reserve first)
  4. std::copy(a.begin(), a.end(), std::back_inserter(b));: 0.944 sec (0.871 with reserve first)
  5. Resize 'b', then memcopy on the base pointers memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));: 0.061 sec

With optimizations turned on (/Ox) however, it's a different story. I had to increase the size to 100 000 000 to get more differentiation:

  1. push_back loop: 0.659 sec
  2. index loop: 0.482 sec
  3. insert: 0.210 sec (no significant difference with reserve first)
  4. std::copy: 0.422 sec with reserve first. Got a bad_alloc without it.
  5. memcpy: 0.329 sec

What's interesting to note is that with or without optimizations, the insert method scaled linearly. Other methods were clearly inefficient without optimizations but still couldn't get quite as fast with them. As James Kanze noted, it's different on g++. Run a test with your own platform to validate.

like image 22
OlivierD Avatar answered Sep 30 '22 01:09

OlivierD