C++ - STL vector question

Question

Hello!

Is there any way to make std::vector faster on reserving + resizing?

I would like to achieve the performance which would be somewhat equivalent to plain C arrays.

See the following code snippets:

TEST(test, vector1) {
   for (int i = 0; i < 50; ++i) {
      std::vector<int> a;
      a.reserve(10000000);
      a.resize(10000000);
   }
}

TEST(test, vector2) {
   for (int i = 0; i < 50; ++i) {
      std::vector<int> a(10000000);
   }
}

TEST(test, carray) {
   for (int i = 0; i < 50; ++i) {
      int* new_a = new int[10000000];
      delete[] new_a;
   }
}

First two tests are two times slower (4095 ms vs 2101 ms) and, obviously, that happens because std::vector is nulling the elements in it. Any ideas on how this could be avoided?

Or probably there is some standard (boost?) container that implements a fixed-size and heap-based array?

Thank you

Answer 1

There's boost::array.

Answer 2

Well naturally the first 2 tests are slower. They explicitly go through the entire vector and call "int()" on each element. Edit: This has the effect of setting all the elements to "0".

Just try reserving.

There is some very relevant info to your question in this question i asked a while back:

http://stackoverflow.com/questions/1461276/stdvector-reserve-and-push-back-is-faster-than-resize-and-array-index-wh

Answer 3

Were your tests performed in debug or release mode? I know the microsoft compiler adds a lot of debug checks that can really slow down performance.

Answer 4

Maybe you could use a boost::scoped_array, but if this really is that performance critical, maybe you should try putting the initialization/allocation outside the innermost loop somehow?

Answer 5

I'm going to give you the benefit of the doubt and assume you've already done some profiling and determined the use of vector in this fashion to be a hotspot. If not, it's a bit premature to consider the differences unless you're working at a very tight, small-scale application where every clock cycle counts in which case it's even easier to use a profiler and there's just as much of a reason to do so.

boost::scoped_array is one solution. There's no way to get vector to not initialize the elements it stores. Another one is std::deque if you don't need a contiguous memory block. deque can be significantly faster than vector or a dynamically-allocated array with the same number of elements as it creates as it creates smaller memory blocks which operating systems tend to deal with better along with being cache-friendly.