Are const_iterators faster ?

Question

Our coding guidelines say prefer const_iterator, because they are little faster compared to normal iterator. It seems like compiler optimizes the code when you use the const _iterator.

Is it really correct ? If yes, what really happens internally to make const_iterator takes the edge?.

EDIT: I wrote small test to check const_iterator vs iterator and found a varying results:

for iterating 10,000 objects const_terator was taking few milliseconds(around 16 ms) less. But not always. There were iterations in which both were equal.

Answer 1

container<T>::const_iterator::operator* returns a const T& instead of T&, so the compiler can make the usual optimizations for const objects.

Answer 2

If nothing else, a const_iterator reads better, since it tells anyone reading the code "I'm just iterating over this container, not messing with the objects contained".

That's a great big win, never mind any performance differences.

Answer 3

I can't see why they would be - constness is a compile time check. But the obvious answer is to write a test.

Edit: Here is my test - it gives identical timings on my machine:

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


int main() {
    vector <int> v;
    const int BIG = 10000000;
    for ( int i = 0; i < BIG; i++ ) {
     v.push_back( i );
    }
    cout << "begin\n";
    int n = 0;
    time_t now = time(0);
    for ( int a = 0; a < 10; a++ ) {
     for( vector <int>::iterator it = v.begin(); it != v.end(); ++it ) {
      n += *it;
     }
    }
    cout << time(0) - now << "\n";
    now = time(0);
    for ( int a = 0; a < 10; a++ ) {
     for( vector <int>::const_iterator cit = v.begin(); cit != v.end(); ++cit ) {
      n += *cit;
     }
    }
    cout << time(0) - now << "\n";;

    return n != 0;

}

Answer 4

I my experience, the compiler does not do any measureable optimization when using const iterators. Althought the statement "it could" is true and references are not defined to be pointers in the standard.

However, you can have two references to the same object, so one can be const, one non-const. Then, I guess the answers in this thread on restrict pointers apply: The compiler cannot know whether the object is changed by another thread, for example, or by some interrupt handling code.

Answer 5

Our coding guidelines say prefer const_iterator

Have a look at this article by Scott Meyers here. He explains why one should prefer iterator over const_iterator.

Answer 6

The guideline we use is:

Always prefer const over non-const

If you tend to use const object, you get used to using only constant operations on the objects you get and that is as much as using *const_iterator* as much as possible.

Constness has a virical property. Once you get to use it, it propagates to all your code. Your non-mutating methods become constant, and that requires using only constant operations on the attributes, and passing constant references around, that itself forces only constant operations...

To me, the performance advantage of using constant iterators over non constant iterators (if any at all) is much less important than the improvement in the code itself. Operations meant (designed) to be non-mutating are constant.

Answer 7

"Const-ness", like access restriction (public, protected, private), benefits the programmer more than it assists with optimization.
Compilers can't actually optimize for as many situations involving const as one might think, for many reasons (such as const_cast, mutable data members, pointer/reference aliasing). The most relevant reason here though is that, just because a const_iterator doesn't allow modifying the data it refers to, doesn't mean that that data can't be changed via other means. And if the compiler can't determine that the data is read-only, then it can't really optimize much more than it would for the non-const iterator case.
More info and examples can be found at: http://www.gotw.ca/gotw/081.htm

Answer 8

Some libraries (OpenSG for one) use lack-of-const to flag data as dirty, so there it has real performance implications.'

Also, allowing you to access non-const member functions could have side-effects that you don't intend (in much the same way as above), so it could.

However, for most types I guess it won't matter.