std::vector is indexes always faster?

Question

When using std::vector is it always faster when going trough all vector's elements via indexes than using of iterators?

I wrote simple stupid test, VS 2010, optimization is disabled

#include <vector>
#include <iostream>
#include <ctime>

const int SIZE = 100000;    

int main()
{    
    std::vector<int> vInt;
    int i, temp;
    srand(time(0));
    for(i = 0; i<SIZE; i++)
        vInt.push_back(rand());

    time_t startTime, endTime;
    std::vector<int>::iterator it = vInt.begin(), itEnd = vInt.end();
startTime = clock();
for( ; it != itEnd; it++)
        temp = *it;
    endTime = clock();
    std::cout<<"Result for iterator: "<<endTime - startTime;

    i = 0;
    int size = vInt.size();
    startTime = clock();
    for(; i<size; i++)
        temp = vInt[i];
    endTime = clock();
    std::cout<<"\nResult for index: "<<endTime - startTime;    

    return 0;
}

DEBUG mode:

Without optimization results are

Result for iterator: 143
Result for index: 5

for const int SIZE = 1000;

Result for iterator: 0
Result for index: 0

for const int SIZE = 10000;

Result for iterator: 15
Result for index: 2

for const int SIZE = 1000000;

Result for iterator: 1377
Result for index: 53

With /O2 flag

for const int SIZE = 10000;

Result for iterator: 0 - 2
Result for index: 0

for const int SIZE = 100000;

Result for iterator: 12 - 15
Result for index: 0

for const int SIZE = 1000000;

Result for iterator: 133 - 142
Result for index: 0 - 3

So it is better always to use indexes with vector?

UPDATE:

RELEASE MODE

With /O2 flag all results are 0.

When optimization is disabled /Od indexes are faster

for const int SIZE = 100000000;

Result for iterator: 2182
Result for index: 472

for const int SIZE = 1000000;

Result for iterator: 22
Result for index: 5

for const int SIZE = 100000;

Result for iterator: 2 - 3
Result for index: 0 - 1

Answer 1

The first thing is that you should use whatever is idiomatic for your use case. If you are iterating I would use iterators, if you are performing random access, then indices.

Now to the actual question. Performance is hard, even measuring performance is a hard problem and it requires that you have a clear idea of what you want to measure, how you are going to measure and how different things will affect your test. Ideally you want to isolate the test so that the measurement is as precise as possible, and then run the test multiple times to verify that the results are consistent. You should never even think on measuring performance with other than fully optimized code, and ideally with a real program. If you are in debug mode and the program is slow, the best optimization is just compiling in release mode, incrementing the optimization levels, reducing debug constructs from the libraries. All of those improvements come for free.

In your test there are too many unknowns and variables to actually make anything out of it. The compiler flags and options can have a great impact so learn how to make your compiler produce the faster code. A simple implementation of an iterator for a vector is a plain pointer, so you can use this to get a base measurement:

int *it=&v[0], *end=it+v.size();
for (; it!=end; ++it) temp=*it;

This should give you a base line to which compare your iterator. Any difference in performance between the iterator and this base line is due to extra checks that you compiler/library vendor is using for debugging. Read the docs on how to disable them. Also note that your step (it++) requires creating one copy of it, in the pointer case that basically has no effect, but if the iterator maintains any state at all, the cost of it++ will dominate the whole loop. Always prefer ++it.

The next thing is what You want to measure and what the compiler thinks you need. You want to measure iteration, but the compiler does not know it, it only sees your code, and the optimizer will do its best to produce equivalent code that is as fast as possible. Taking just one of the loops, the compiler can realize that the whole iteration has no side effects other than setting temp to v[v.size()-1] and in the worst case (for your measurement) it can actually perform that transformation, removing the loops completely, which leads us to the next point:

The devil is in the details. My guess is that your intention is measuring the relative costs of iteration in the general case, but your program is measuring the cost of iterating over a vector of constant size. Why does this matter? Compilers perform loop unrolling to avoid the cost of the test whenever they can. If the compiler knows that your loop will always contain a multiple of X iterations, then it can test for loop completion in only one of each X steps. Optimizations are not guaranteed, and in the general case of an application, the compiler will not know the number of iterations, so you should ensure that the test does not provide the compiler with more chances to optimize than it will have in your real program. In these two cases, you want to make sure that the compiler does not have extra information that it would not have in the real case, that is, you want to hide knowledge of the test and force it to focus on the problem. I would suggest that you move the loops into functions in a different translation unit, that you pass the vector by reference, and that you ensure that it cannot avoid looping (take an integer as argument and apply a binary operator with the temporary and each element in the vector, return the result of all the operations to the caller; while processing that function, the compiler will hopefully not be able to do anything too smart)

But above all, I must refer you back to the first paragraph, do what's idiomatic. Compilers are optimized for idiomatic code, and when/if performance is needed, they will do the right thing. The performance of the loop in this answer, or the two loops in the question is the same with unchecked iterators in an optimized build, not that the cost of the iteration itself will usually have any impact at all in the performance of your application.

Answer 2

No, it depends on the compiler and optimizations flags set for compilation.

Even if you find that your compiler always produces faster code for indexes, you should not conclude that iterators are useless. The advantage of iterators is that they provide unified interface to all STL containers, which means you can write a generic template functions which, by accepting a pair of iterators, are able to work with not only vectors, but linked lists and other containers.

Also, you should use pre-increment operator instead of post-increment, this should be faster:

for( ; it != itEnd; ++it)

Answer 3

The comparison is not fair due to cache effect.

First, compile in "Release" mode if you're using VS. Or -O2 in gcc.

After access the array elements using iterator, most of them will be cached. So when you immediately access them using index, the cache has already "warmed up". Try to do it in two separate run: one only using iterator, and another just using index. Also, try a more large data set, say 1GB. Since clock is not a very fine grained timer, you may want to use rdtsc as well.

FYI, here is a thread talking about stl:vector iterator vs. index.

Answer 4

i think your iterator times in debug mode show you the overhead of extensive iterator validation.

Without this validation overhead, but also without optimization i think iterators should be slightly slower.

You can think of iterators as a direct pointer into the internal array of the vector, so they would need only one dereference to get at the data, while to lookup by index you would need to first add, and then dereference. But after the optimizer is done, you are unlikely to notice a difference. What does matter though, is that if you change your code to use another container type, you may have to use iterators anyway.