[Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Gunnar Roth
gunnar.roth at gmx.de
Sun Jul 12 15:05:51 CEST 2015
Hi Marc,
> Better provide a benchmark into which users can easily plug their own types
> and that plots relative performance of various containers at various sizes.
> Then they can use that on their platform, on their type, with their access
> patterns to determine which container to choose.
>
I tried to write a container benchmark for testing qt , std and boost containers. I did that already a while ago,
but had not collected enough energy to post about it until now . ;-)
This is not including QList because the benchmark is made to test how fast i can lookup something in a container.
It can be found at https://github.com/gunrot/qtcontainerbench <https://github.com/gunrot/qtcontainerbench>
I got irritating results from it , concerning all the praise i read on the qt mailings list for Vector instead of map or hash.
Running my tests on my Apple MacBook Pro Retina 13 <http://www.notebookcheck.com/Test-Apple-MacBook-Pro-Retina-13-Zoll-Late-2013.104688.0.html>Inch Notebook, having a 2.4 GHZ Core i5 4258U CPU, using OS X 10.10.4 with Xcode 6.4
and using Qt 5.5.0 Release.
i got these results for a double key and double value using 20 items:
Type WalltimeMilliseconds
QMap_find 0.0001678466796875
QMap_constFind 0.0001869201660156
QHash_find 0.0003662109375
QHash_constFind 0.0002479553222656
QVector_lowerbound 0.0001735687255859
stdvector_lowerbound 0.0001583099365234
stdmap_find 0.0001544952392578
stdunordered_find 0.0002250671386719
qfasthash_find 0.0005035400390625
boostunordered_find 0.0002021789550781
QFastHash is a class implemented by you , which i found at https://codereview.qt-project.org/#/c/105743/ <https://codereview.qt-project.org/#/c/105743/>
So the fastest here is std::map, with std::vector having nearly the same speed.
the slowest by more than 3 times than the fastest is QFastHash.
What is irritating that QMap_constFind is slower than QMap_find.
The other irritating thing is that Qt classes lose here all the way. Even QVector is losing against std::vector and i used std:lowerbound in both cases
( qlowerbound was also slower than std::lowerbound when i started making this benchmark)
For 5 Items the test shows these results:
Type WalltimeMilliseconds
QMap_find 3.480911254883e-05
QMap_constFind 3.910064697266e-05
QHash_find 9.1552734375e-05
QHash_constFind 7.057189941406e-05,
QVector_lowerbound 3.671646118164e-05
stdvector_lowerbound 3.385543823242e-05
stdmap_find 3.576278686523e-05
stdunordered_find 5.722045898438e-05
qfasthash_find 13.16070556641e-05
boostunordered_find 4.863739013672e-05
So for the Qmap anomaly is also apparent, but the winner is now std::vector followed closely by QMap::find and std::map. No reason to prefer it because it has not a actual find api and you need to keep it sorted etc.
The clear looser by far is QFastHash again.
So lets now have a look at 100 items:
Type WalltimeMilliseconds
QMap_find 0.001144409179688
QMap_constFind 0.00128173828125
QHash_find 0.001617431640625
QHash_constFind 0.0013427734375
QVector_lowerbound 0.001495361328125
stdvector_lowerbound 0.0010986328125
stdmap_find 0.001083374023438
stdunordered_find 0.001129150390625
qfasthash_find 0.002716064453125
boostunordered_find 0.001007080078125
So here i see that now boost unordered is the fastest, closely follow by the former winner std::map and std::vector, Qmap and std::unorderd is nearby.
QFastHash gain is far worse than anything else. What was the exact reason for this class , Marc?
I also don’t see an advantage in using a vector.
Well, maybe you noticed i used a double as key. So what result do we expect, when we use an int64 as key and as value. I naively thought they should not be much different.
So lets have a look a the results for 20 items using a int64_t as key and value:
Type WalltimeMilliseconds
QMap_find 0.0002021789550781
QMap_constFind 0.0001430511474609
QHash_find 0.0001869201660156
QHash_constFind 0.0001411437988281
QVector_lowerbound 0,0001659393310547
stdvector_lowerbound 0.000152587890625
stdmap_find 0.0001506805419922
stdunordered_find 0.0002021789550781
qfasthash_find 0.0003166198730469
boostunordered_find 0.0002021789550781
Well this is a change. Now at least constFind it faster than find.
As before QFastHAsh is the slowest one, but QHash ::constFind is king now, but QMap constfind and std::map and std::vector are not that far away.
So now look at the speed with 5 items:
Type WalltimeMilliseconds
QMap_find 3.957748413086e-05
QMap_constFind 3.862380981445e-05
QHash_find 4.673004150391e-05
QHash_constFind 4.005432128906e-05
QVector_lowerbound 3.528594970703e-05
stdvector_lowerbound 3.147125244141e-05
stdmap_find 3.862380981445e-05
stdunordered_find 5.531311035156e-05
qfasthash_find 8.678436279297e-05
boostunordered_find 5.531311035156e-05
std::vector wins here closely followed byQVector and QMap::constFind, but do you think the difference is worth choosing vector over map/qhash?
And with 20 items vector falls behind. ( Actually my tests show that vector with 10 items falls behind map/qhash already)
And for 100 items we have this results:
Type WalltimeMilliseconds
QMap_find 0.001144409179688
QMap_constFind 0.00128173828125
QHash_find 0.001617431640625
QHash_constFind 0.0013427734375
QVector_lowerbound 0.001495361328125
stdvector_lowerbound 0.0010986328125
stdmap_find 0.001083374023438
stdunordered_find 0.001129150390625
qfasthash_find 0.002716064453125
boostunordered_find 0.001007080078125
Hmm QMap constFind is again slower than find. The winner here is by a tiny amount boost::unordered, on par are std::map and std::vector.
So from this results , i would choose std::map for a container of about 100 items where i need fast lookup. For 1000 and more , QHash is getting faster and faster but not for double as key, as suppose thats because the qHash() for double is not implemented well, as std::unordered and boost::unordered do a lot better job here.
But doing all these measurements with an int key and an int value changes the picture.
5 items QHash_constFind 3,433227539062e-05 stdmap_find 3,194808959961e-05 stdvector_lowerbound 3,147125244141e-05
7 items QHash_constFind 4,863739013672e-05 stdmap_find 5,197525024414e-05 stdvector_lowerbound 4,196166992188e-05
10 items QHash_constFind 6,675720214844e-05 stdmap_find 6,961822509766e-05 stdvector_lowerbound 6,866455078125e-05
20 items QHash_constFind 0.0001335144042969 stdmap_find 0.0001544952392578 stdvector_lowerbound 0.000152587890625
100 items QHash_constFind 0.0006332397460938 stdmap_find 0.001113891601562 stdvector_lowerbound 0.001068115234375
So for a simple int as key QHash is faster starting from 7 Items and gains speed by increasing items, being considerably faster at 100 items.
So what I learn here that there is:
1. is a hight dependency on the key type for a container being slower or faster in lookup time.
2. Something with fast in its name can actually be lowest one by far.
> If you want to update the docs, as a first approximation, write that QVector
> is _the_ default seqential (and, if it wasn't so awkward to use, also _the_
> default associative) container (even though it's not currently reflected in
> the Qt API). All other containers (incl. QMap, QSet, ..., but maybe not QHash)
> should only be used after very careful profiling and QList should not be used
> by mere mortals at all.
>
So what does my benchmark measure wrong? Because if you are right in saying QVector should be the default associative container, then my benchmark must be wrong.
Best regards,
Gunnar Roth
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20150712/88cebfd2/attachment.html>
More information about the Development
mailing list