A Benchmark for Qt's Vector/List/Map iterators vs simple arrays

IteratorBenchmark.cpp

#include <QDateTime>
#include <QMap>
#include <QVector>
#include <QList>
#include <QDebug>

#define SIZE	10000000
int array[SIZE];

int main(){
	QMap<int, int> map;
	QVector<int> vec;
	QList<int> list;

	int nbIterations = 100;
	int size = SIZE;
	volatile int sum = 0;
	int * arrayPtr = (int*) malloc(sizeof(int) * size);

	for(int i = 0; i<size; ++i){
		int randomInt = qrand()%128;
		array[i] = randomInt;
		arrayPtr[i] = randomInt;
	}

	// Simple Array [Stack]
	qint64 start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int i=0;i<size; i++){
			sum += array[i];
		}
	}
	qint64 end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Simple Stack Array : \t" << (end-start) << " ms";

	// Simple Array [Heap]
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int i=0;i<size; i++){
			sum += arrayPtr[i];
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Simple Heap Array : \t" << (end-start) << " ms";

	// More Optimized Stack Array ( Reducing Pipeline flush )
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int i=0;i<size; i+=10){
			sum += array[i];
			sum += array[i+1];
			sum += array[i+2];
			sum += array[i+3];
			sum += array[i+4];
			sum += array[i+5];
			sum += array[i+6];
			sum += array[i+7];
			sum += array[i+8];
			sum += array[i+9];
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Optimized Stack Array : \t" << (end-start) << " ms";

	// More More Optimized Stack Array
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int i=0;i<size; i+=10){
			sum += array[i] +
				   array[i+1] +
					array[i+2] +
					array[i+3] +
					array[i+4] +
					array[i+5] +
					array[i+6] +
					array[i+7] +
					array[i+8] +
					array[i+9];
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "More More Optimized Stack Array : \t" << (end-start) << " ms";

	free(arrayPtr);

	for(int i = 0; i<size; ++i){
		int randomInt = qrand()%128;
		map[i] = randomInt;
		vec.append(randomInt);
		list.append(randomInt);
	}

	// Vector
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int j : vec){
			sum += j;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Vector Iterator: \t" << (end-start) << " ms";

	// Vector Const iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(const int &j : qAsConst(vec)){
			sum += j;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Vector Const Iterator: \t" << (end-start) << " ms";


	// List iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(int j : list){
			sum += j;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "List Iterator : \t" << (end-start) << " ms";

	// List const iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		for(const int &j : qAsConst(list)){
			sum += j;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "List const iterator : \t" << (end-start) << " ms";


	// QMap::values()
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		QList<int> values = map.values();
		for(int k : values){
			sum += k;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "QMap::values() : \t" << (end-start) << " ms";


	// QMap::values() with const iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		QList<int> values = map.values();
		for(const int &k : qAsConst(values)){
			sum += k;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "QMap::values() with const iterator: \t" << (end-start) << " ms";


	// Java style iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		QMapIterator<int, int> it(map);
		while (it.hasNext()) {
			it.next();
			sum += it.value();
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "Java style iterator : \t" << (end-start) << " ms";


	// STL style iterator
	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		QMap<int, int>::const_iterator it = map.constBegin();
		auto end = map.constEnd();
		while (it != end) {
			sum += it.value();
			++it;
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "STL style iterator : \t" << (end-start) << " ms";


	start = QDateTime::currentMSecsSinceEpoch();
	for(int i = 0; i<nbIterations; ++i){
		sum = 0;
		auto end = map.cend();
		for (auto it = map.cbegin(); it != end; ++it)
		{
			sum += it.value();
		}
	}
	end = QDateTime::currentMSecsSinceEpoch();
	qDebug() << "STL style iterator v2 : \t" << (end-start) << " ms";
}

adopted from : https://stackoverflow.com/questions/8517853/iterating-over-a-qmap-with-for/31226494#31226494

for 1M items and 100 iterations

Simple Stack Array : 325 ms
Simple Heap Array : 362 ms
Optimized Stack Array : 232 ms
More More Optimized Stack Array : 112 ms
Vector Iterator: 417 ms
Vector Const Iterator: 393 ms
List Iterator : 1182 ms
List const iterator : 1200 ms
QMap::values() : 10649 ms
QMap::values() with const iterator: 14089 ms
Java style iterator : 11987 ms
STL style iterator : 4120 ms
STL style iterator v2 : 4046 ms