[Interest] Qtcontainerbench std::vector vs QVector

Constantin Makshin cmakshin at gmail.com
Tue Jul 28 07:57:31 CEST 2015


On 07/27/2015 10:42 PM, Gunnar Roth wrote:
> Hi Constantin.
> Thank you for looking at my benchmark.
> 
>> Am 24.07.2015 um 08:57 schrieb Constantin Makshin <cmakshin at gmail.com>:
>>
>> Well, after looking at the code I can say that the was you wrote this
>> benchmark "abuses" the QVector's copy-on-write semantic, making it
>> somewhat biased towards std::vector — you use only non-const versions of
>> QVector::begin(), QVector::end() and indexing methods. That leads to a
>> lot of [obviously non-free] checks for sharing and possible detachment.
> 
> Actually imo this is the most important case. Why should i iterate over a vector and not change the values?
Then it's better to do one of these:
1) use range-based for;
2) use std::for_each();
3) "cache" the value returned by std::end() or corresponding container's
method
   for (auto it = std::begin(m[x]), end = std::end(m[x]); it != end; ++it)
   {
       // ...
   }

The "classic" approach, which is used in your benchmark,
for (auto it = std::begin(m[x]); it != std::end(m[x]); ++it)
{
    // ...
}
creates unnecessary overhead due to excessive sharing checks in
non-const QVector::end(). To be honest, I think that the 3 items listed
above (particularly the range-based for because it's also the shortest
one :) ) are good for all container classes with STL-compatible API
because all these iteration methods minimize the dependency on
[possible] inefficiencies/drawbacks of specific container implementation
(e.g. constant complexity of std::vector::end() doesn't say anything
about its actual performance, adding a sleep(10000) call to it won't
violate the standard requirements).

> If i search in a vector it should be sorted. The sorted case was tested in the other tests together with map, but not the const case, so i added that now, but there is not much of a difference here.
> 
>> A few modifications (see the attachment) made the difference in
>> read-only access negligible, in some tests QVector gave slightly better
>> results than std::vector. QVector_fwd_it became more than 2x faster.
>
> You also change the order when inserting, so instead of jumping from container to container, you insert in a row, but i did that intentionally to minimize L1 cache effect.
Oh, didn't think about that and lack of comments in the code didn't give
any hints. Anyway, adding several values to a container in one batch
seems to be a more common use-case than switching between different
containers for each value.

> The other iteration tests i added additionally.
> 
> But the results show still a 50% better performance for std::vector when inserting and 2 times better performance when iteration non const. In the other cases QVector is on par with std::vector.
> So i still say choose QVector only when you really need the implicit sharing.
Nobody says that Qt containers are perfect or just good for
*everything*. That have their pros (very cheap passing by value, for
example) and cons (e.g. extra overhead in non-const methods), STL
containers have theirs (e.g. STL allocator API makes it [nearly]
impossible to do in-place memory reallocations so even something like
std::vector<int> will have to copy data every time its capacity changes).
Also, as Thiago notes, operations performed on container values are
likely to make sharing checks overhead much less apparent so it's better
to measure performance of actual code instead of making decisions by
looking at synthetic benchmarks. Especially since Qt and STL containers
have the same "core" API so switching between these two container
implementations shouldn't be very difficult.

> Regards,
> Gunnar Roth

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20150728/5a0d1ea5/attachment.sig>


More information about the Interest mailing list