40

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

Is this really correct? If yes, what really happens internally that makes const_iterator faster?.

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

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

Improve this question
4
  • 1
    In your measurement, did you measure wall time? Commented Apr 16, 2009 at 11:05
  • Yes. The code looks similar to what @Neil Butterworth has posted. I used GetTickCount() for time measurement Commented Apr 16, 2009 at 14:59
  • In doing your tests, you should take into account possible issues like caching that can easily make the first-run test slower, but can even make it faster (if you happen to have populated the container's elements closer to begin() last). It's a good idea to have the program set up the data, do a pass with each iterator (discard those timings), then do a lot of passes with each and report on the results). Minimum values are more meaningful than averages. Make sure the passes aren't being optimised out (e.g. use the iterators to touch some volatile variables). Commented Apr 28, 2011 at 3:17
  • 1
    16 ms is too small to be significant. Run the test for 5-10 secs to get some comparable results. Commented May 17, 2013 at 7:03

11 Answers 11

Reset to default
85

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.

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

2 Comments

And in any case, the const_iterator will not perform worse. Heads you win, tails you do not lose.
Does not answer the question though, does it?
27

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

Improve this answer

Comments

19

They are for non-trivial containers/iterators. Get your habits straight and you won't lose performance when it does matter.

Also, there are several reasons to prefer const_iterator, no matter what:

  1. Use of const expresses code intent (i.e. reading only, no mutating of these objects).
  2. Use of const(_iterator) prevents accidental modification of data. (see above)
  3. Some libraries use lack-of-const begin() to flag data as dirty (i.e. OpenSG) and will send it to other threads/over-network on sync, so there it has real performance implications.
  4. 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), for instance detaching copy-on-write containers from shared data. Qt for one, does exactly that.

As an example of the last point above, here's an excerpt from qmap.h in Qt:

inline iterator begin() { detach(); return iterator(e->forward[0]); } inline const_iterator begin() const { return const_iterator(e->forward[0]); }

Even if iterator and const_iterator are practically equivalent (except for the const), detach() creates a new copy of the data if there are two or more objects using it. This is completely useless if you're just going to read the data, which you indicate by using const_iterator.

Of course, there are data points in the other direction:

  1. For STL containers and and many simple-copy-semantic containers it won't matter for performance. The code is equivalent. However, the able to write clear code and avoid bugs wins out.
  2. Const is viral, so if you're working in a legacy code base where const is poorly (or simply not) implemented, you might have to work with non-const iterators.
  3. Apparently, some pre C++0x STL has a bug where const_iterators couldn't be used to erase() elements from containers.
Improve this answer

Comments

16

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; }
Improve this answer

1 Comment

for std::vector<> and most of STL, that holds true. For other libraries, things may differ.
7

It depends on the container and implementation you use.

Yes, const_iterator may perform better.

For some containers the implementation of const iterators and mutable iterators may differ. A first example I can think of is the SGI's STL rope container. The mutable iterator has additional pointer to the parent rope in order to support updates. This implies additional resources wasted for reference counting updates + memory for the pointer to the parent rope. See the implementation notes here.

However, as others said, the compiler cannot use const by itself to do optimization. const just grants read-only access to the referenced object rather than saying that it is immutable. For a container like std::vector, whose iterators are usually implemented as a simple pointers, there won't be any difference.

Improve this answer

2 Comments

+1 for the STL rope example (although not Standard, and if you open the question to non-Standard containers obviously a speed differential in either direction's possible).
@Tony: a C++03 standard example: string::iterator. For implementations that use copy-on-write (which becomes non-standard with C++0x), the mutable iterator implies checking uniqueness while const_iterator does not.
6

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.

Improve this answer

6 Comments

Although interesting, speed is not an argument in that article.
That is a rather old article, from back in 2001 and before the 2003 standard. I wonder if the author still has taht opinion, and my guess is that he does not.
IMO Meyers is wrong. He is basically arguing that since you cannot convert a const_iterator to an iterator and therefore not make changes through const_iterator you should prefer iterator. But that is in fact why you should use const_iterator -- to express that you won't try to make changes through it.
@John Dibling <--That Myers article makes no sense, he may as well say never use const as you can't change const objects... which is the whole point.
The article is outdated. The erase/insert non-const iterators were a bug in the standard which is now fixed in C++0x.
|
4

They should be identical, as constness is a compile-time check.

To prove to myself there were no quirks, I took anon's code, modified it to use clock_gettime, added an outer loop to avoid caching biases, and ran it many times. Results were surprisingly inconsistent - up and down by 20% (no idle boxes available) - but minimum times for both iterator and const_iterator were practically identical.

I then got my compiler (GCC 4.5.2 -O3) to generate assembly output and visually compared the two loops: identical (except that the order of a couple register loads was reversed)

iterator loop

 call clock_gettime movl 56(%esp), %esi movl $10, %ecx movl 60(%esp), %edx .p2align 4,,7 .p2align 3 .L35: cmpl %esi, %edx je .L33 movl %esi, %eax .p2align 4,,7 .p2align 3 .L34: addl (%eax), %ebx addl $4, %eax cmpl %eax, %edx jne .L34 .L33: subl $1, %ecx jne .L35 leal 68(%esp), %edx movl %edx, 4(%esp) leal 56(%esp), %esi movl $1, (%esp)

const_iterator loop:

 movl 60(%esp), %edx movl $10, %ecx movl 56(%esp), %esi .p2align 4,,7 .p2align 3 .L38: cmpl %esi, %edx je .L36 movl %esi, %eax .p2align 4,,7 .p2align 3 .L37: addl (%eax), %ebx addl $4, %eax cmpl %eax, %edx jne .L37 .L36: subl $1, %ecx jne .L38 leal 68(%esp), %edx movl %edx, 4(%esp) leal 56(%esp), %esi movl $1, (%esp)
Improve this answer

Comments

2

when you benchmark any of this, make sure to use an appropriate optimization level -- you'll get wildly different timings using "-O0" versus "-O" and such.

Improve this answer

Comments

1

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

Improve this answer

1 Comment

There are no usual optimizations for const objects (not in this context).
1

"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

Improve this answer

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.