[Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO

[Marc Mutz]

On Sunday 12 July 2015 15:05:51 Gunnar Roth wrote:
> 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.

That's because your benchmark runs entirely in L1.

If you want to test containers of 10, 100, 1000 and 10000 elements each, then 
make
- one run over 1×N containers of 10000 elements each,
- one run over 10×N containers of 1000 elements each,
- one run over 100×N containers of 100 elements each,
- one run over 1000×N containers of 10 elements each.

You need to use a working set size large enough to not hit L1 all the time, 
because it's just not the usual case that a lookup table is completely in L1. 
But you can start with a small working set. As you increase the working set 
size, you should see how each individual test (at constant number of elements) 
increases in runtime. And you will see that the contiguous containers don't 
loose as much as the node-based.

About QFastHash: that is WIP. It's the very rudimentary beginnings of an open-
addressing hash container (a hash container using consecutive memory, not 
nodes).

> Running my tests on my  Apple MacBook Pro Retina 13 
> <http://www.notebookcheck.com/Test-Apple-MacBook-Pro-Retina-13-Zoll-Late-2
> 013.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

QHash is slower than std::unordered because std::hash<double> is inline and 
qHash(double) is out-of-line. QVector is slower than std::vector because it 
has a d-pointer, so construction of iterators is more complicated (see my blog 
post for disassembly of a simple QVector vs. std::vector iteration - the loops 
are identical, but QVector has more complex setup code).

Thanks,
Marc

-- 
Marc Mutz <marc.mutz at kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt Experts