[Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Marc Mutz
marc.mutz at kdab.com
Fri Jul 17 12:58:33 CEST 2015
On Friday 17 July 2015 11:18:06 Marc Mutz wrote:
> On Friday 17 July 2015 11:00:49 Marc Mutz wrote:
> [...]
>
> > I've attached my local version, which includes some Qt containers.
>
> [...]
>
> That version was some bitrot. Here's the one that works. It also varies the
> number of duplicates to be removed.
The exact operation performed is
sort | uniq
> This kind of benchmark, together with a nice visualisation, and more use-
> cases, is what I'd wish we had for our users.
Here are the results of running it on a Core-i7 Sandy Bridge pinned at 2.4GHz,
formatted as HTML. "Excesss dups" of 1 means no duplicates, 100 means 99%
dups.
It is instructive to look at the memory consumption, because the size printed
is the size of the *reduced* container, so the largest container size is 100
million elements, 1% of which are unique, 99% dups. That's 800M in vector,
qlist, qvector, deque, but _a lot_ more in std::list (2400M + allocator
overhead, on my machine 3.8G of resident memory), set, and multiset (3200M +
allocator overhead, on my machine 5.2G). Conseqently, don't run this without
at least 6G of RAM or reduce the max. working set size.
As you can see, the only algorithm that can hold up with
std::vector+std::sort+std::uniue is QSet+QList+std::osrt, but only at very
high number of duplicates (starts here for some medium sizes and 90% dups),
and even at its best, it's "only" 3x faster than std::vector, while it can be
an order of magnitude slower. I find it particularly interesting that at
100'000 elements and 99% dups, it's almost as slow as std::vector, and at
1'000'000 elements, slower again.
--
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 --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20150717/ea78eca2/attachment.html>
More information about the Development
mailing list