Vector Index Access Efficiency vs. Iterator Access

Question

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

I understand that an “iterator” is more efficient than “index access”. (I also think vector::end() more efficient than vector::size() ).

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

Index access cycle version (previously marked 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; } } 

Iterator loop code:

  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 faster. I used the time command to measure. The rooms were:

using g++ source.cpp (no optimization) index access

real 800 ms

access to iterator

real 2200ms

Do these numbers make sense? (I repeated runs several times) And I wondered what details I was missing and why I was wrong ...

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

iterator access, real time: ~ 200 ms

I repeated the tests on different platforms (amd64 w / g ++ and power7 w xlC) and I see that all the time when I used the optimized code, the sample programs have the same runtime.

modify the changed code to add values ​​( value += *iter ) instead of a simple assignment. Added information about the compiler options. Added new numbers to use -O2. * edit2 changed the header correcting "iterator performance" to "access performance".

Answer 1

Without seeing the test harnesses, compiler options, and how you measured the time, it's hard to say anything. In addition, a good compiler may be able to exclude a loop in one case or another, since the loop has no effect on the return value. However, depending on this, it would not surprise me that iterators are significantly faster than indexing (or vice versa).

As for your "understanding", the type of iterator and its performance. You can write forwarding iterators that are very fast or very slow, just as you can write random access iterators that are very fast or very slow. Globally, the data types of the structure that random access iterators will support are likely to have better than those that do not, which random access iterators can; but this is really not enough for any reasonable generalizations.

Answer 2

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

Then: your first program does not use iterators, it uses indexes. These are different concepts.

The second program actually uses random access iterators because this is what std::vector<T>::iterator . The restrictions on std::vector designed so that the iterator can be implemented as a simple pointer to a dynamic array that encapsulates vector .

begin should be as fast as size . The only difference between them in a typical std::vector implementation is that end may need to evaluate begin() + size() , although size can also be implemented as (roughly) end() - begin() . However, the compiler can optimize both in a loop.

Answer 3

In optimization, both codes should be (close) the same. Try -O2 .

Without optimization and added debugging information, your measurements will be quite misleading.

Answer 4

In the first example, you are looking for a single item using value = vec[idx]; , which causes the calculation of the offset element_size * index each time the element is accessed.

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

If you turn on optimization (try -O2 or -O3 ), however, the compiler will most likely optimize your loop in the first example in much the same way as in the second example, which makes the performance almost identical.

Answer 5

I found that iterators are faster. Try reorganizing your iterator loop to something like the following, and you can also see this:

 #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 computer, showing that iterators have a slight advantage:

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

It should be noted that I used the addition of rand (); this prevents the compiler from optimizing what it can compile at compile time. For compilers, it seems much easier to do this with inline arrays than with vectors, and this can be confusing for the advantages of an array over vectors.

I compiled above using "icpc -fast". slavik was right when he had to do anti-increment index calculations using iterators (ala pointers).