Iterator performance

[giantdragon]

Many times I have read that using "for(int i=0; i<size; i++)" to iterate list is bad idea and we must use STL or Java style iterators. I decided to make my own research and calculate processing time for each iterating method. I made 5 trials and calculated average time.



QList<int> list;
int size = 100000000;
for(int i = 0; i < size; i++)
list.append(1);
int sum = 0;
qint64 begin = QDateTime::currentMSecsSinceEpoch();

//Simplest method
for(int i = 0; i < size; i++)
sum += list.at(i);

//Java-style iterator
QListIterator<int> it(list);
while(it.hasNext())
sum += it.next();

//STL-style iterator
QList<int>::iterator i;
for(i = list.begin(); i != list.end(); ++i)
sum += *i;

qint64 time = QDateTime::currentMSecsSinceEpoch() - begin;
qDebug() << "Time: " << time;

Results surprised me. Simplest "stupid" method took 85 ms, Java-style iterator 111 ms and STL-iterator 260 ms. It seems that for simple iteration over all list's elements "for(int i=0; i<size; i++)" method will be the fastest.

[SixDegrees]

It's very hard to beat the performance of a simple pointer increment. This operation is normally available right on the CPU hardware and executes in a clock cycle (or less, in some circumstances).

Iterators are nice because they provide a level of abstraction between the operation and the implementation; this brings several advantages, including the ability to swap in a new implementation without disturbing existing code, and the provision of a consistent interface for similar functionality across a broad range of objects. But like all things, abstraction comes at a cost, and often incurs a performance penalty. Which is more important - raw performance or maintainability - is up to the programmer.

Honestly, though, the cost of loop overhead is normally very, very small in comparison with the time spent performing the actual workings within the loop. You will usually get much more benefit using the clearer, more portable abstractions and simply kicking the compiler's optimization setting up a notch or two than you'll gain by other means.

Note, also, that your tests are not valid. In the STL case, you call list.end() on each iteration of the loop, incurring an unnecessary function call. You also mix direct dereference with calls to list.at(), two very different accessor methods. These inconsistencies make your results meaningless.

[wysota]

What is fastest depends on the implementation of the operator used to reach the data. A dumb for loop will usually be fastest, provided that the reaching operator (QList::at() in the first case, next() and * operator in remaining cases) doesn't introduce any unnecessary overhead.

[nightghost]

The good about the iterators is not the performance, but the save and easy use and the good readability (well except for the stl style imho).

Here the Benchmark from Qt for different iteration styles: http://labs.qt.nokia.com/2009/01/23/iterating-efficiently/ I personally prefer the foreach macro, because most time its enough and its very simple to use.

[giantdragon]

Note, also, that your tests are not valid. In the STL case, you call list.end() on each iteration of the loop, incurring an unnecessary function call.
Tried to use

QList<int>::iterator i;
QList<int>::iterator end = list.end();
for(i = list.begin(); i != end; ++i)
sum += *i;

and processing time decreased to 84 ms. But if try

for(int i = 0; i < list.size(); i++)
or


int size = list.size();
for(int i = 0; i < size; i++)

results are the same. It seems that compiler optimizes this function call.

[wysota]

What if you declare size as "const int"? Does it change anything?

[giantdragon]

What if you declare size as "const int"? Does it change anything?
The same time - 84 ms.

[squidge]

So a well structured stl-style iterator is just as fast as the simplest method ?

[MarekR22]

Most important question is how did you build it?
Is it in release mode or in debug mode? I suspect that in debug mode (most developers are using it as default)!
I wouldn't be surprised if results in alternative build mode would be much different.

[giantdragon]

Most important question is how did you build it?
Is it in release mode or in debug mode? I suspect that in debug mode (most developers are using it as default)!
I wouldn't be surprised if results in alternative build mode would be much different.
It was built in release mode.