10

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?

Darkalfx
  • 259
  • 3
  • 12
  • 5
    "Effective STL" Item 5: Prefer range member functions to their single-element counterparts – Cubbi Feb 21 '13 at 18:19
  • Go for the cleaner code, use what STL provides you... don't iterate unless you have to. Reusing code in most cases will trump hand-tailored versions of simple operations like this. Those functions were designed with efficiency in mind. – eazar001 Feb 21 '13 at 18:22
  • 6
    The `insert` might be faster, or it might be about the same, but (short of a criminally bad library implementation) will never be any worse than a loop. – Jerry Coffin Feb 21 '13 at 18:23
  • You could easily write a short program to test the relative speeds. I suggest you start there. Opinions take a back seat to something so easily measurable. – Paul Beckingham Feb 21 '13 at 18:28
  • 2
    I prefer `std::copy(b.begin(), b.end(), std::back_inserter(a))` which is another equivalent way of doing this. – ipc Feb 21 '13 at 18:29

3 Answers3

10

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 :)

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • That actually really helps me. I'm relatively new to C++. What do you mean by a single reserve for all the element I want to insert? Think you could give me more details? – Darkalfx Feb 21 '13 at 19:13
  • 1
    @Darkalfx: for some types of iterators, `insert` can compute the number of elements to be inserted using `b.begin() - b.end()`. When it knows the number of elements, it can make space in the vector for exactly that number in one operation. – Fred Foo Feb 21 '13 at 19:30
5

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.

OlivierD
  • 362
  • 1
  • 10
4

As larsmans says, the more you do in a single library call, the more likely it is to be more efficient. In the case of insert into a vector, the library will normally do at most a single re-allocation, and to copy each shifted element at most once. If you use a loop and push_back, it could reallocate several times, which could be significantly slower (like an order of magnitude).

Depending on the type, however, it may also be faster to do something like: 

a.resize( 300 );
std::copy( b.begin(), b.end(), a.end() - 300 );

I've found this to be faster for simple scalar types (like int) using g++ on an Intel machine.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • As a side note: `resize` should never be called inside a loop (even inside a function that's inside a loop) as `push_back` (and I assume `insert`) is required to be amortized constant time (exponential growth steps) and a conservative `resize` breaks this. – BCS Sep 26 '13 at 23:00
  • 1
    @BCS The `resize` will normally be called before the loop, not in the loop. The issue here is `resize` + `[]` vs. `reserve` + `push_back`. – James Kanze Sep 27 '13 at 08:32