1

Possible Duplicates:
Using arrays or std::vectors in C++, what's the performance gap?
std::vector is so much slower than plain arrays?

memory is vector of 1000 elements array[] is an integer array of 1000 elements

for (iteration = 0; iteration < numiterations; iteration++) {
    for (j = 1; j < numints; j++) {
       memory[j] += memory[j - 1];
       //array[j] += array[j - 1];
    }
}

If I compare the time of the for loop after running 100 iterations, time required for accessing is very much small compared to that of vector

why is the case ? because I thought both takes constant and nearly same time ..

Community
  • 1
  • 1
ajayreddy
  • 83
  • 1
  • 1
  • 8
  • 3
    Can you tell us more about the platform you tested this on? Compiler, optimization/build type, that sort of thing? Often, `vector` is slower in debug builds, but the same speed as a raw array in release builds... – Doug Oct 17 '10 at 03:41
  • See [ Using arrays or std::vectors in C++, what's the performance gap? ](http://stackoverflow.com/questions/381621/using-arrays-or-stdvectors-in-c-whats-the-performance-gap). The accepted answer shows generated assembly with essentially no difference between a vector and an array, with g++ and -O3. – Matthew Flaschen Oct 17 '10 at 03:45
  • @ajay, what compiler flags (incl. optimization settings)? Also, that's a pretty old version. – Matthew Flaschen Oct 17 '10 at 03:51
  • Thank You guys for your time, its really awesome ,after using level 3 optimization flags -O3 iam getting same time.But can you please enlighten me with the reasons ..? – ajayreddy Oct 17 '10 at 04:03
  • 1
    "I thought both takes constant [...] time" -> Impossible. Iterating over a sequence takes longer as the sequence grows bigger. This is called *linear* time. – fredoverflow Oct 17 '10 at 13:54
  • 1
    @Fred: what i meant was accessing a particular element and not the whole array or vector, anyway here in the present context, both array and vector are of fixed size 1000 elements. – ajayreddy Oct 18 '10 at 03:20

3 Answers3

5

Since most (if not all) implementations of std::vector use a T* array internally, there should be no performance difference at all between accessing a vector element and a C-array element using the [] operator when optimization flags are set. Try your test again using your compiler's optimization flags.

However, this may not be the case using the std::vector<T>::at function, since this function will perform a bounds check.

Charles Salvia
  • 52,325
  • 13
  • 128
  • 140
  • You're absolutely right, with level 3 optimization iam getting the same times for both mechanisms ..but can you please explain me the reasons or point me to the resources containing the reasons ..? – ajayreddy Oct 17 '10 at 04:06
  • 1
    The optimized build is probably hoisting the `T*` to a register before the loop and just using that pointer directly from the register. The same thing would happen if you just passed a plain old array (address would be in the register). In a non-optimized build, the inner loop is probably reloading that `T*`. – Jim Buck Oct 17 '10 at 04:39
  • @ajayreddy, take a look at Jerry Coffin's answer. The reason for the speed-up is likely related to the fact that the `operator []` function gets inlined by the optimizer. – Charles Salvia Oct 17 '10 at 08:22
4

This will typically depend (almost entirely) upon whether you've set the compiler to inline functions. std::vector uses a function (named operator[]) to address items. If that function isn't generated inline, the overhead of calling the function will add a substantial amount to the time taken to address an item in the array. If you set the compiler to generate inline functions, you normally won't be able to measure a meaningful difference between the two.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
0

True, they both are constant time. However, a vector is an object and there is a penalty for redirecting function calls. Consider this your first experience with C++ operator overloading. The vector class overloads the [] operator to achieve similar semantics with a real array.

SapphireSun
  • 9,170
  • 11
  • 46
  • 59
  • 3
    That's wrong, I'm sorry. An instance of a `std::vector` is an object only in the source code level. Once compiled there is no trace whatsoever to the fact it's an object. It's as flat as plain array. The only difference left is that a `std::vector` allocates memory dynamically, whereas a primitive array is compiled-in with all its glorious data. This is necessary for allowing dynamic resizing. It's the only penalty you should see, and you pay it only once at construction time, not at access time. If you create a C array that can grow then `std::vector` has exactly 0 (zero, nada, nil) overhead. – wilhelmtell Oct 17 '10 at 03:46
  • Hmm, that's good to know. I retract my previous statement. +1 – SapphireSun Oct 17 '10 at 03:54
  • Interestingly, I've seen small performance *gains* by converting C-style procedural code into more object-oriented code. I think the reason for this is that putting things in objects tells the compiler more about the lack of possible aliasing - sort-of like putting `restrict` on pointers in C99. In the end, the objects "disappear" as wilhelmtell says, but the extra information still helps the optimizer. – Doug Oct 17 '10 at 04:08