Created
March 14, 2018 17:49
-
-
Save ejahandar/3b5db3a7f3d1e746103671ef003d4fe5 to your computer and use it in GitHub Desktop.
A Benchmark for Qt's Vector/List/Map iterators vs simple arrays
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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"; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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