[Interest] QMap<int64_t> significantly slower than QMap<int32_t>

[Mandeep Sandhu]

On Sun, Sep 22, 2013 at 4:42 PM, Konstantin Tokarev <annulen at yandex.ru>wrote:

>
> 22.09.2013, 13:24, "Etienne Sandré-Chardonnal" <etienne.sandre at m4x.org>:
> > I don't, I have very only strong conviction from tests on a big large
> program. I was hoping that someone had an idea about the cause... Would
> this help to make one?
> > I did a quick test : inserting 10000000 items in a QMap<int32_t, int>
> and QMap<int64_t, int> using rand() for key and value, measuring the delay
> with QDateTime::currentMsecsSinceEpoch.
> > The int32 version took about 2100ms while the int64 took about 2300ms.
> >
> > So maybe this is only a memory cache issue. The difference is higher in
> my app (measured with a profiler), maybe because it decreases cache
> efficiency of other code parts.
> >
> > Using gcc 4.8.0 mingw64 rubenvb build, with Qt 4.8.1
> > Etienne
> >
>
> Now try std::map<int32_t, int> and std::map<int64_t, int> - red-black tree
> should work faster than QMap's skiplist.
>

Out of curiosity i tried measuring the insert, iteration and removal times
of QMap, QHash and std::map. The test included inserting numbers
(sequentially), iterating over all entries and then removing a random
number from it (Test app attached.).

Here are my results (g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3, Intel core
i7, 1.2GHz, 8 GB RAM).

$ ./qtvsstl 10000000

Timing insertion of 10000000 items...
QMap : 1737 msecs
QHash : 821 msecs
STL map : 5458 msecs

Timing iteration over 10000000 items...
QMap : 156 msecs
QHash : 202 msecs
STL map : 173 msecs

Timing removal of random item from 10000000 items...
Map : 0 msecs
Hash : 0 msecs
STL map : 0 msecs

STL map seems to be the slowest for insertion.

I don't have the data handy, but some ppl say that skip lists perform
better than RB tree's for large data sets and are more 'friendly' to
concurrent programming. I'm not sure if thats the reason why Qt containers
use skip lists instead of Rb/AVL trees.

HTH,
-mandeep



>
>
> --
> Regards,
> Konstantin
> _______________________________________________
> Interest mailing list
> Interest at qt-project.org
> http://lists.qt-project.org/mailman/listinfo/interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20130923/e8b4e4a9/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cpp
Type: text/x-c++src
Size: 2426 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20130923/e8b4e4a9/attachment.cpp>