On Sun, Sep 22, 2013 at 4:42 PM, Konstantin Tokarev <annu...@yandex.ru>wrote:
>
> 22.09.2013, 13:24, "Etienne Sandré-Chardonnal" <etienne.san...@m4x.org>:
> > I don't, I have very only strong conviction from tests on a big large
> program. I was hoping that someone had an idea about the cause... Would
> this help to make one?
> > I did a quick test : inserting 10000000 items in a QMap<int32_t, int>
> and QMap<int64_t, int> using rand() for key and value, measuring the delay
> with QDateTime::currentMsecsSinceEpoch.
> > The int32 version took about 2100ms while the int64 took about 2300ms.
> >
> > So maybe this is only a memory cache issue. The difference is higher in
> my app (measured with a profiler), maybe because it decreases cache
> efficiency of other code parts.
> >
> > Using gcc 4.8.0 mingw64 rubenvb build, with Qt 4.8.1
> > Etienne
> >
>
> Now try std::map<int32_t, int> and std::map<int64_t, int> - red-black tree
> should work faster than QMap's skiplist.
>
Out of curiosity i tried measuring the insert, iteration and removal times
of QMap, QHash and std::map. The test included inserting numbers
(sequentially), iterating over all entries and then removing a random
number from it (Test app attached.).
Here are my results (g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3, Intel core
i7, 1.2GHz, 8 GB RAM).
$ ./qtvsstl 10000000
Timing insertion of 10000000 items...
QMap : 1737 msecs
QHash : 821 msecs
STL map : 5458 msecs
Timing iteration over 10000000 items...
QMap : 156 msecs
QHash : 202 msecs
STL map : 173 msecs
Timing removal of random item from 10000000 items...
Map : 0 msecs
Hash : 0 msecs
STL map : 0 msecs
STL map seems to be the slowest for insertion.
I don't have the data handy, but some ppl say that skip lists perform
better than RB tree's for large data sets and are more 'friendly' to
concurrent programming. I'm not sure if thats the reason why Qt containers
use skip lists instead of Rb/AVL trees.
HTH,
-mandeep
>
>
> --
> Regards,
> Konstantin
> _______________________________________________
> Interest mailing list
> Interest@qt-project.org
> http://lists.qt-project.org/mailman/listinfo/interest
>
#include <QCoreApplication>
#include <QMap>
#include <QHash>
#include <QTime>
#include <QDebug>
#include <map>
int main(int argc, char *argv[])
{
// QCoreApplication a(argc, argv);
int itemCount = 0;
bool ok = false;
if (argc > 1) {
itemCount = QString(argv[1]).toInt(&ok);
if (!ok) {
qWarning() << "\nError! Enter a valid number.";
qDebug() << "\nUsage:\n\t" << *argv << "<number of items for testing>\n";
return 1;
}
} else {
qDebug() << "\nUsage:\n\t" << *argv << "<number of items for testing>\n";
return 1;
}
//Qt containers
QMap<int, int> qmap;
QHash<int, int> qhash;
//STL containers
std::map<int, int> stlmap;
QTime timer;
qDebug() << "Timing insertion of" << itemCount << "items...";
timer.start();
for (int i=0; i<itemCount; i++) {
qmap.insert(i, i);
}
qDebug() << "QMap :" << timer.elapsed() << "msecs";
timer.start();
for (int i=0; i<itemCount; i++) {
qhash.insert(i, i);
}
qDebug() << "QHash :" << timer.elapsed() << "msecs";
timer.start();
for (int i=0; i<itemCount; i++) {
stlmap.insert(std::pair<int, int>(i, i));
}
qDebug() << "STL map :" << timer.elapsed() << "msecs";
qDebug() << "\nTiming iteration over" << itemCount << "items...";
int dummy = 0;
timer.start();
foreach (int val, qmap.values()) {
dummy += val;
}
qDebug() << "QMap :" << timer.elapsed() << "msecs";
dummy = 0;
timer.start();
foreach (int val, qhash.values()) {
dummy += val;
}
qDebug() << "QHash :" << timer.elapsed() << "msecs";
dummy = 0;
timer.start();
for (std::map<int, int>::iterator it=stlmap.begin(); it!=stlmap.end(); ++it) {
dummy += it->second;
}
qDebug() << "STL map :" << timer.elapsed() << "msecs";
qDebug() << "\nTiming removal of random item from" << itemCount << "items...";
int rand = qrand() % itemCount;
timer.start();
qmap.remove(rand);
qDebug() << "Map :" << timer.elapsed() << "msecs";
rand = qrand() % itemCount;
timer.start();
qhash.remove(rand);
qDebug() << "Hash :" << timer.elapsed() << "msecs";
rand = qrand() % itemCount;
timer.start();
stlmap.erase(rand);
qDebug() << "STL map :" << timer.elapsed() << "msecs";
// return a.exec();
return 0;
}
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest
