Are const_iterators faster?

Question

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.

Answer 1

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)

Answer 2

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 3

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 4

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

Answer 5

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.

Answer 6

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.