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 ..

Improve this question
6
  • 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... Commented Oct 17, 2010 at 3:41
  • See [ Using arrays or std::vectors in C++, what's the performance gap? ](stackoverflow.com/questions/381621/…). The accepted answer shows generated assembly with essentially no difference between a vector and an array, with g++ and -O3. Commented Oct 17, 2010 at 3:45
  • @ajay, what compiler flags (incl. optimization settings)? Also, that's a pretty old version. Commented Oct 17, 2010 at 3:51
  • 1
    "I thought both takes constant [...] time" -> Impossible. Iterating over a sequence takes longer as the sequence grows bigger. This is called linear time. Commented Oct 17, 2010 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. Commented Oct 18, 2010 at 3:20

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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 ..?
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*.
@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.
5

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.

Improve this answer

Comments

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.

Improve this answer

3 Comments

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.
Hmm, that's good to know. I retract my previous statement. +1
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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.