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

[Marc Mutz]

On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote:
> 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.

It is not surprising that big-O _eventually_ wins. The point is that that 
"eventually" != "always". Few collections in Qt will have more than 100 
elements, and then, not all the time.

Binary search is not very cache-friendly, because it exhibits a semi-random 
memory access pattern that the hardware has trouble predicting.

If you want to see what I and others mean when we say that the node-based 
containers are slow, iterate over the containers. Search in large collections 
is what hash tables and rb-trees are optimized for, and of course they 
eventually win, with ever larger collections. But most collections are also 
iterated over, and then you better not have a node-based container in front of 
you if you do.

Related: there's a similar benchmark to yours, container_benchmark.cpp by 
Stroustrup and Stepanov, which performs duplicates removal using different 
containers. It hasn't been updated since 2003, but it's easy to add new tests. 
I already posted a link in this thread, but google will find it, too.

I've attached my local version, which includes some Qt containers.

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: container_benchmark.cpp
Type: text/x-c++src
Size: 10169 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/development/attachments/20150717/fa01bf96/attachment.cpp>