C++ - STL vector question

Question

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

In order for the tests to do the same amount of work, the `carray` test needs a `for(std::size_t idx=0; idx<10000000; ++idx) new_a[idx]=0;` in there. Once that's in, I doubt you'll find significant changes. — sbi, Jun 23 '10 at 11:26
I suggest using a profiler and only if the performance is low optimize. The above code is not probably present in a normal application. You wouldn't do such things normally. Probably the best way is to create your own array class to have more control. — INS, Jun 23 '10 at 11:26
@Iulian: This is one of those comments for which I want to be able to down-vote comments. Why on earth would you want to create your own array? Have you actually tried to implement `std::vector`? You'll find that this is surprisingly hard to come up with a veryion that's both correct and fast. — sbi, Jun 23 '10 at 11:30
@sbi Such "benchmarks" are irrelevant in my opinion. This is why one must test on real application rather then making such kind of benchmarks - it will probably result that performance is **OK** event with the "slow" std::vector. If he finds performance problems in these places then he can think of rewriting parts used from the std::vector to waste less CPU cycles. Furthermore I believe that the code above is unlikely yo exist in a **real** application. My principle is first make it work, then make it better/faster. — INS, Jun 23 '10 at 11:42
@lulian: which is a good principle. however @sbi is totally on the mark here. The stl is a well thoughtout, well designed library that (if used properly) will yield performance nearly as good as their bothersome C counterparts. Creating your own array class will result in more time spent debugging than it would have possibly saved over the lifetime of the codebase. — Alan, Jun 23 '10 at 13:23

score 11 · Accepted Answer · edited May 23 '17 at 10:32

11

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:

std::vector reserve() and push_back() is faster than resize() and array index, why?

edited May 23 '17 at 10:32

Community

1
1

answered Jun 23 '10 at 11:12

Goz

61,365
24
124
204

Correct, the `carray` version isn't doing the *exact* same thing as the vector counteparts. std::vector::reserve() is the answer here – rubenvb Jun 23 '10 at 12:16

score 2 · Answer 2 · answered Jun 23 '10 at 11:04

2

There's boost::array.

answered Jun 23 '10 at 11:04

Amir Rachum

76,817
74
166
248

Unfortunately, it's stack based, and, for example, you can't even allocate a huge array of 1 million ints without changing the stack size. – Yippie-Ki-Yay Jun 23 '10 at 11:05
A `std::auto_ptr>` would do the job. – JoeG Jun 23 '10 at 11:14
@HardCoder1986: If you want an heap-based array, `std::vector` is what you want. Fix your test and you will see that it is exactly as fast as manually fiddling with dynamically allocated C arrays. – sbi Jun 23 '10 at 11:32

score 2 · Answer 3 · answered Jun 23 '10 at 13:17

2

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.

answered Jun 23 '10 at 13:17

B.A. Baracus

21
1

score 1 · Answer 4 · answered Jun 23 '10 at 13:27

1

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?

answered Jun 23 '10 at 13:27

Viktor Sehr

12,825
5
58
90

score 1 · Answer 5 · answered Jun 24 '10 at 11:21

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.

C++ - STL vector question

5 Answers5