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

[Gunnar Roth]

Hi Marc.
> 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.
> 

Ok as this is a valid point you made, i changed my code ( https://github.com/gunrot/qtcontainerbench <https://github.com/gunrot/qtcontainerbench> ) to do this, i create N=min(1,10000/testcout) containers for the tests.
I iterate over the N container looking up 1 in all N containers then 2 and so on.

> 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.
> 

Actually in my test node based container win with increasing number of elements against vector.

These are the results, i sorted by speed, fastest is first. The time is what it takes to iterate over N container looking up an int32 values, while doing this for every value between 1 and  testcount.

5 elements ( 2000 containers)

"stdvector_lowerbound -- 5 „,	"WalltimeMilliseconds",0.5859375
"QVector_lowerbound -- 5 „,	"WalltimeMilliseconds",0.8359375
"QMap_constFind -- 5 „,		"WalltimeMilliseconds“,1.15625
"stdmap_find -- 5 „,		"WalltimeMilliseconds",1.328125
"QHash_constFind -- 5 „,	"WalltimeMilliseconds",1.59375
"stdunordered_find -- 5 „,	"WalltimeMilliseconds“,2,128
"qfasthash_find -- 5 „,		"WalltimeMilliseconds",3.75
"boostunordered_find -- 5 „,	"WalltimeMilliseconds",2.65625


This test has a clear winner std::vector, being more than double as fast as nee base container.
QVector is quite a bit slower but still faster than any other.

20 elements (500 containers)
"stdvector_lowerbound -- 20 „,	"WalltimeMilliseconds",1.0625
"QMap_constFind -- 20 „,	"WalltimeMilliseconds“,1.140625
"QVector_lowerbound -- 20 „,	"WalltimeMilliseconds“,1.453125
"stdunordered_find -- 20 „,	"WalltimeMilliseconds",1.71875
"stdmap_find -- 20 „,		"WalltimeMilliseconds“,1.84375
"boostunordered_find -- 20 „,	"WalltimeMilliseconds",1.875
"QHash_constFind -- 20 „,	"WalltimeMilliseconds",2.0625
"qfasthash_find -- 20 „,	"WalltimeMilliseconds",3.5625


Again std:vector is the winner here, but closely followed by QMap ( much more close than QVector was in the case before) , QVector lost track here already.

50 elements (200 containers)
"QMap_constFind -- 50 „,	"WalltimeMilliseconds“,1.359375
"stdvector_lowerbound -- 50 „,	"WalltimeMilliseconds",1.375
"QHash_constFind -- 50 „,	"WalltimeMilliseconds“,1.53125
"QVector_lowerbound -- 50 „,	"WalltimeMilliseconds“,1.8125
"stdmap_find -- 50 „,		"WalltimeMilliseconds“,2.25
"stdunordered_find -- 50 „,	"WalltimeMilliseconds“,2.46875
"qfasthash_find -- 50 „,	"WalltimeMilliseconds“,4.625

Here QMap is now the winner, but so closely followed by std::vector that i call it even.  Vector falls even more behind in is now only 4th place.

100 elements (100 containers)

"stdvector_lowerbound -- 100 „,	"WalltimeMilliseconds",1.46875
"QHash_constFind -- 100 „,	"WalltimeMilliseconds",1.625
"QMap_constFind -- 100 „,	"WalltimeMilliseconds“,1.78125
"stdunordered_find -- 100 „,	"WalltimeMilliseconds“,1.78125
"boostunordered_find -- 100 „,	"WalltimeMilliseconds",1.875
"QVector_lowerbound -- 100 „,	"WalltimeMilliseconds“,2.28125
"stdmap_find -- 100 „,		"WalltimeMilliseconds“,2.65625
"qfasthash_find -- 100 „,	"WalltimeMilliseconds“,4.9375

std::vector is comeback kid here. But QVector loses more and more ground.


1000 elements (10 containers)

"QHash_constFind -- 1000 „,	"WalltimeMilliseconds“,1.15625
"stdunordered_find -- 1000 „,	"WalltimeMilliseconds“,1.625
"boostunordered_find -- 1000 „,	"WalltimeMilliseconds",1.8125
"stdvector_lowerbound -- 1000 „,"WalltimeMilliseconds“,1.875
"QMap_constFind -- 1000 „,	"WalltimeMilliseconds",2.5
"QVector_lowerbound -- 1000 „,	"WalltimeMilliseconds“,3.3125
"stdmap_find -- 1000 „,		"WalltimeMilliseconds",3.5
"qfasthash_find -- 1000 „,	"WalltimeMilliseconds“,4.15625

std::vector also falls behind now being 60% slower than the winner QHash,Vector is even nearly 2 times slower than std::vector.

10000 elements (1 container)

"QHash_constFind -- 10000 „,	 "WalltimeMilliseconds“,1.15625
"boostunordered_find -- 10000 „, "WalltimeMilliseconds",1.578125
"stdunordered_find -- 10000 „,	   "WalltimeMilliseconds“,1.609375
"qfasthash_find -- 10000 „,	   "WalltimeMilliseconds",2.03125
"stdvector_lowerbound -- 10000 ","WalltimeMilliseconds",3.4375
"QMap_constFind -- 10000 „,	 "WalltimeMilliseconds“,3.9375
"stdmap_find -- 10000 „,	   "WalltimeMilliseconds",4.1875
"QVector_lowerbound -- 10000 „,  "WalltimeMilliseconds",4.1875

The vector classes are now very bad in this case. QHash is considerable better than any other.
 
So I deduce from this test that for a container with up to 100 elements , std::vector is the best choice , if you want fastest lookup, but Vector should be avoided. For larger container QHash should be used for best lookup performance.


> 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).
> 
What was the idea behind it? Is so much slower than any other that I can just see why anyone should want to have this? What is the advantage?
> 
> QHash is slower than std::unordered because std::hash<double> is inline and 
> qHash(double) is out-of-line.
May I ask why? 
Is this valid for all qHash()?


> 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).
> 

Well Vector is considerable slower than std::vector in my test. QVector has no advantage  over  hash based container,
while std::vector has for small sets.

Regards,
Gunnar Roth

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20150716/0be43dcc/attachment.html>