Efficiency of vector index access vs iterator access

Question

I have question to correct my understanding of efficiency of accessing elements of a vector by using index access (with operator []) or using an iterator.

My understanding is "iterator" is more efficient than "index access". (also I think vector::end() is more efficient than vector::size()).

Now I wrote sample code measure it (under Windows 7 using Cygwin, with g++ 4.5.3)

The index access loop version (formerly labeled as random access):

int main()
{
  std::vector< size_t > vec ( 10000000 );
  size_t value = 0;

  for( size_t x=0; x<10; ++x )
  {
    for ( size_t idx = 0; idx < vec.size(); ++idx )
    {
      value += vec[idx];
    }
    return value;
  }
}

The iterator loop code is this:

    for (std::vector< size_t >::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        value = *iter;
    }

I am surprised to see that the "index access" version is much quicker. I used the time command to "measure". The numbers were :

results using g++ source.cpp (no optimizations) index access

real 800ms

iterator access

real 2200ms

Do these numbers make sense? (I repeated the runs multiple times) And I wondered what details I miss and why I am mistaken...

results using g++ -O2 index access, time real: ~200ms

iterator access, time real: ~200ms

I repeated tests on different platform (amd64 w/ g++ and power7 w xlC) and see that all the time I used optimized code the example programs have similar execution time.

edit changed code to add values ( value += *iter ) instead of just using assignment. Added details about compiler options. Added new numbers for using -O2. *edit2 changed title correcting "iterator efficiency" to "accesses efficiency".

Answer 1

Without seeing the test harnesses, the compiler options, and how you measured the time, it's hard to say anything. Also, a good compiler may be able eliminate the loop in one case or the other, since the loop has no effect on the value returned. Still, depending on the implementation, it wouldn't surprise me to see iterators significantly faster than indexing (or vice versa).

With regards to your "understanding", there's nothing inherent about the type of iterator and its performance. You can write forward iterators which are very fast, or very slow, just as you can write random access iterators which are very fast or very slow. Globally, the types of data structures which will support random access iterators are likely to have better locality than those which don't, which might work in favor of random access iterators; but that's really not enough to be able to make any reasonable generalizations.

Answer 2

When I compile both programs with -O2 (Linux, GCC 4.6.1), they run equally fast.

Then: your first program is not using iterators, it is using indices. These are different concepts.

Your second program is in fact using random access iterators, because that is what std::vector<T>::iterators are. The restrictions on std::vector are designed in such a way that an iterator can be implemented as a simple pointer into the dynamic array that a vector encapsulates.

begin should be just as fast as size. The only difference between the two in a typical implementation of std::vector is that end might need to compute begin() + size(), though size might also be implemented as (roughly) end() - begin(). The compiler might optimize both away in the loop, though.

Answer 3

With optimizations the two codes should be (near) identical. Try -O2.

Without optimizations and added debug information your measurements will be quite misleading.

Answer 4

I have found iterators to be faster, actually. Try refactoring your iterator loop to something like the following and you may see this as well:

#include <ctime>
#include <vector>
#include <iostream>
using namespace std;

int main()
{   
  std::vector< size_t > vec ( 1000000 );
  size_t value = 0;
  srand ( time(NULL) );
  clock_t start,stop;
  int ncycle = 10000;

  start = std::clock();
  for( size_t x=0; x<ncycle; ++x ) { 
    for ( size_t idx = 0; idx < vec.size(); ++idx )
      vec[idx] += rand();
  }   
  stop = std::clock();
  cout << start << " " << stop << endl;
  cout << "INDEX: " << (double((stop - start)) / CLOCKS_PER_SEC) / ncycle << " seconds per cycle" << endl;

  start = std::clock();
  for( size_t x=0; x<ncycle; ++x ) { 
    for (std::vector< size_t >::iterator iter = vec.begin(), end = vec.end(); iter != end; ++iter)
        *iter += rand();
  }   
  stop = std::clock();
  cout << "ITERATOR: " << (double((stop - start)) / CLOCKS_PER_SEC) / ncycle << " seconds per cycle" << endl;
}   

The result is the following on my pc, showing that iterators have a slight lead:

INDEX: 0.012069 seconds per cycle
ITERATOR: 0.011482 seconds per cycle

You should note that I used an addition of rand(); this prevents the compiler from optimizing out something that it can calculate at compile time. Compilers seem to have a much easier time doing so with intrinsic arrays than with vectors, and that can misleadingly give arrays an advantage over vectors.

I compiled the above with "icpc -fast". slavik was right on about having to do calculations on indices vs incrementing when using iterators (ala pointers).

Answer 5

In your first example, you dereference each individual item using value = vec[idx];, which causes an offset of element_size * index to be calculated each time you access an element.

Since a vector consists of elements lined up in a continuous block of memory, a vector iterator is usually just implemented as a simple pointer, so iterating through a vector (like in your second example) just involves advancing the pointer one element after each iteration.

If you enable optimizations (try -O2 or -O3), however, the compiler will likely optimize your loop in the first example to something similar to the second example, making the performance nearly identical.