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
_______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
