Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Benchmark for Qt's Vector/List/Map iterators vs simple arrays
#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";
}
@ejahandar

This comment has been minimized.

Copy link
Owner Author

@ejahandar ejahandar commented Mar 14, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.