[Interest] Qtcontainerbench std::vector vs QVector

[Gunnar Roth]

Hi,
for whom it may concern i post my results for vector iterating using iterator and index plus insert via push_back.

the test code is at https://github.com/gunrot/qtcontainerbench <https://github.com/gunrot/qtcontainerbench> in branch vector. it runs over N containers where N=min(1,100000/countofelements)
on my OS X 10.10.5 xcode 3.6 13 inch retina apple notebook(2013)


Commandline was
LANG=C ./qtcontainerbench testCase_iterate_vector -csv

Time is in ms.



stdvector_fwd_it
5
0,13671875
stdvector_fwd_it
10
0,12890625
stdvector_fwd_it
20
0,126953125
stdvector_fwd_it
40
0,099609375
stdvector_fwd_it
50
0,083984375
stdvector_fwd_it
80
0,095703125
stdvector_fwd_it
100
0,0859375
stdvector_fwd_it
1000
0,072265625
stdvector_fwd_it
10000
0,08203125
stdvector_fwd_it
100000
0,076171875
stdvector_fwd_it
1000000
1,078125
QVector_fwd_it
5
0,23046875
QVector_fwd_it
10
0,20703125
QVector_fwd_it
20
0,23828125
QVector_fwd_it
40
0,234375
QVector_fwd_it
50
0,19921875
QVector_fwd_it
80
0,22265625
QVector_fwd_it
100
0,18359375
QVector_fwd_it
1000
0,1640625
QVector_fwd_it
10000
0,17578125
QVector_fwd_it
100000
0,18359375
QVector_fwd_it
1000000
1,65625
stdvector_fwd_idx
5
0,140625
stdvector_fwd_idx
10
0,107421875
stdvector_fwd_idx
20
0,09375
stdvector_fwd_idx
40
0,107421875
stdvector_fwd_idx
50
0,0947265625
stdvector_fwd_idx
80
0,107421875
stdvector_fwd_idx
100
0,1044921875
stdvector_fwd_idx
1000
0,0771484375
stdvector_fwd_idx
10000
0,0830078125
stdvector_fwd_idx
100000
0,080078125
stdvector_fwd_idx
1000000
1,03125
QVector_fwd_idx
5
0,203125
QVector_fwd_idx
10
0,21484375
QVector_fwd_idx
20
0,21484375
QVector_fwd_idx
40
0,189453125
QVector_fwd_idx
50
0,166015625
QVector_fwd_idx
80
0,16796875
QVector_fwd_idx
100
0,15234375
QVector_fwd_idx
1000
0,146484375
QVector_fwd_idx
10000
0,1796875
QVector_fwd_idx
100000
0,14453125
QVector_fwd_idx
1000000
1,75
stdvector_pushback
5
14
stdvector_pushback
10
11,25
stdvector_pushback
20
9,625
stdvector_pushback
40
7,625
stdvector_pushback
50
7
stdvector_pushback
80
6,75
stdvector_pushback
100
6,4375
stdvector_pushback
1000
5,4375
stdvector_pushback
10000
5,4375
stdvector_pushback
100000
5,6875
stdvector_pushback
1000000
55
QVector_pushback
5
14
QVector_pushback
10
14,5
QVector_pushback
20
13,75
QVector_pushback
40
11,625
QVector_pushback
50
10,375
QVector_pushback
80
11,875
QVector_pushback
100
10,125
QVector_pushback
1000
9,875
QVector_pushback
10000
10
QVector_pushback
100000
10,75
QVector_pushback
1000000
97


My conclusion from this is to use std::vector. Only if i really need the implicit sharing property , because i cannot move, i would choose QVector.

Regards,
Gunnar Roth

[Constantin Makshin]

"vector" branch is identical to "master".

Post by Gunnar Roth
Hi,
for whom it may concern i post my results for vector iterating using
iterator and index plus insert via push_back.
the test code is at https://github.com/gunrot/qtcontainerbench in
branch vector. it runs over N containers where
N=min(1,100000/countofelements)
on my OS X 10.10.5 xcode 3.6 13 inch retina apple notebook(2013)
Commandline was
LANG=C ./qtcontainerbench testCase_iterate_vector -csv
Time is in ms.
stdvector_fwd_it
5
0,13671875
stdvector_fwd_it
10
0,12890625
stdvector_fwd_it
20
0,126953125
stdvector_fwd_it
40
0,099609375
stdvector_fwd_it
50
0,083984375
stdvector_fwd_it
80
0,095703125
stdvector_fwd_it
100
0,0859375
stdvector_fwd_it
1000
0,072265625
stdvector_fwd_it
10000
0,08203125
stdvector_fwd_it
100000
0,076171875
stdvector_fwd_it
1000000
1,078125
QVector_fwd_it
5
0,23046875
QVector_fwd_it
10
0,20703125
QVector_fwd_it
20
0,23828125
QVector_fwd_it
40
0,234375
QVector_fwd_it
50
0,19921875
QVector_fwd_it
80
0,22265625
QVector_fwd_it
100
0,18359375
QVector_fwd_it
1000
0,1640625
QVector_fwd_it
10000
0,17578125
QVector_fwd_it
100000
0,18359375
QVector_fwd_it
1000000
1,65625
stdvector_fwd_idx
5
0,140625
stdvector_fwd_idx
10
0,107421875
stdvector_fwd_idx
20
0,09375
stdvector_fwd_idx
40
0,107421875
stdvector_fwd_idx
50
0,0947265625
stdvector_fwd_idx
80
0,107421875
stdvector_fwd_idx
100
0,1044921875
stdvector_fwd_idx
1000
0,0771484375
stdvector_fwd_idx
10000
0,0830078125
stdvector_fwd_idx
100000
0,080078125
stdvector_fwd_idx
1000000
1,03125
QVector_fwd_idx
5
0,203125
QVector_fwd_idx
10
0,21484375
QVector_fwd_idx
20
0,21484375
QVector_fwd_idx
40
0,189453125
QVector_fwd_idx
50
0,166015625
QVector_fwd_idx
80
0,16796875
QVector_fwd_idx
100
0,15234375
QVector_fwd_idx
1000
0,146484375
QVector_fwd_idx
10000
0,1796875
QVector_fwd_idx
100000
0,14453125
QVector_fwd_idx
1000000
1,75
stdvector_pushback
5
14
stdvector_pushback
10
11,25
stdvector_pushback
20
9,625
stdvector_pushback
40
7,625
stdvector_pushback
50
7
stdvector_pushback
80
6,75
stdvector_pushback
100
6,4375
stdvector_pushback
1000
5,4375
stdvector_pushback
10000
5,4375
stdvector_pushback
100000
5,6875
stdvector_pushback
1000000
55
QVector_pushback
5
14
QVector_pushback
10
14,5
QVector_pushback
20
13,75
QVector_pushback
40
11,625
QVector_pushback
50
10,375
QVector_pushback
80
11,875
QVector_pushback
100
10,125
QVector_pushback
1000
9,875
QVector_pushback
10000
10
QVector_pushback
100000
10,75
QVector_pushback
1000000
97
My conclusion from this is to use std::vector. Only if i really need the
implicit sharing property , because i cannot move, i would choose QVector.
Regards,
Gunnar Roth

[Gunnar Roth]

"vector" branch is identical to "master“.

Not anymore ;-)
Thanks for the information.

[Constantin Makshin]

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.

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.

The results, supposed to be displayed with a monospace font, are below.
I reordered them to make it easier to compare how two containers behave
in the same conditions.
g++ 4.9.2 on a Debian GNU/Linux desktop with Intel Core i5-3570 3.4 GHz

Test # of it. Original Modified
-------------------------------------------------------------
stdvector_fwd_it 5 0.0908203125 0.08984375
QVector_fwd_it 5 0.185546875 0.0888671875

stdvector_fwd_it 10 0.078125 0.0771484375
QVector_fwd_it 10 0.169921875 0.08203125

stdvector_fwd_it 20 0.06640625 0.0693359375
QVector_fwd_it 20 0.15625 0.0712890625

stdvector_fwd_it 40 0.0634765625 0.064453125
QVector_fwd_it 40 0.169921875 0.0634765625

stdvector_fwd_it 50 0.07421875 0.07421875
QVector_fwd_it 50 0.16015625 0.0771484375

stdvector_fwd_it 80 0.0712890625 0.072265625
QVector_fwd_it 80 0.15234375 0.0791015625

stdvector_fwd_it 100 0.0654296875 0.0654296875
QVector_fwd_it 100 0.1484375 0.0703125

stdvector_fwd_it 1000 0.0537109375 0.0537109375
QVector_fwd_it 1000 0.13671875 0.0537109375

stdvector_fwd_it 10000 0.052734375 0.052734375
QVector_fwd_it 10000 0.13671875 0.052734375

stdvector_fwd_it 100000 0.052734375 0.052734375
QVector_fwd_it 100000 0.13671875 0.052734375

stdvector_fwd_it 1000000 0.921875 0.921875
QVector_fwd_it 1000000 1.453125 0.921875

stdvector_fwd_idx 5 0.08984375 0.0908203125
QVector_fwd_idx 5 0.123046875 0.0888671875

stdvector_fwd_idx 10 0.083984375 0.083984375
QVector_fwd_idx 10 0.111328125 0.0888671875

stdvector_fwd_idx 20 0.0810546875 0.107421875
QVector_fwd_idx 20 0.099609375 0.0830078125

stdvector_fwd_idx 40 0.0927734375 0.0927734375
QVector_fwd_idx 40 0.111328125 0.08203125

stdvector_fwd_idx 50 0.0869140625 0.087890625
QVector_fwd_idx 50 0.103515625 0.0908203125

stdvector_fwd_idx 80 0.0791015625 0.0791015625
QVector_fwd_idx 80 0.0986328125 0.0849609375

stdvector_fwd_idx 100 0.072265625 0.0732421875
QVector_fwd_idx 100 0.0927734375 0.078125

stdvector_fwd_idx 1000 0.056640625 0.056640625
QVector_fwd_idx 1000 0.08203125 0.0595703125

stdvector_fwd_idx 10000 0.0556640625 0.0556640625
QVector_fwd_idx 10000 0.0810546875 0.060546875

stdvector_fwd_idx 100000 0.0546875 0.0546875
QVector_fwd_idx 100000 0.080078125 0.05859375

stdvector_fwd_idx 1000000 0.9375 0.9375
QVector_fwd_idx 1000000 1.03125 0.953125

stdvector_pushback 5 7 6.25
QVector_pushback 5 9 8.25

stdvector_pushback 10 6.625 5.6875
QVector_pushback 10 9.125 8.5

stdvector_pushback 20 6.3125 5.4375
QVector_pushback 20 9.25 8.5

stdvector_pushback 40 6 5.5
QVector_pushback 40 9.5 8.875

stdvector_pushback 50 5.5 5
QVector_pushback 50 9.25 8.375

stdvector_pushback 80 5.75 5.1875
QVector_pushback 80 9.625 8.75

stdvector_pushback 100 5.3125 4.75
QVector_pushback 100 9.25 8.375

stdvector_pushback 1000 4.8125 4.1875
QVector_pushback 1000 8.875 8

stdvector_pushback 10000 5.4375 4.9375
QVector_pushback 10000 9.125 8.75

stdvector_pushback 100000 6.875 6.125
QVector_pushback 100000 10 9.75

stdvector_pushback 1000000 63 58
QVector_pushback 1000000 97 96
-------------------------------------------------------------

Post by Gunnar Roth

"vector" branch is identical to "master“.

Not anymore ;-)
Thanks for the information.

[Gunnar Roth]

Hi Constantin.
Thank you for looking at my benchmark.

Post by Constantin Makshin
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?
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.

Post by Constantin Makshin
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.
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.

Regards,
Gunnar Roth

[Thiago Macieira]

Post by Gunnar Roth
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.

Note that the iteration itself has the exact same performance. The difference
you're seeing is overhead only.

A sufficiently large vector (which can be as small as 10 items) or sufficiently
complex action on iteration (a printf, for example) will completely offset the
overhead.

Both QVector and std::vector from libc++ have the exact same type for the
iterator and const_iterator

QVector:
typedef T* iterator;
typedef const T* const_iterator;

std::vector:
typedef pointer iterator;
typedef const_pointer const_iterator;

[Constantin Makshin]

Post by Gunnar Roth
Hi Constantin.
Thank you for looking at my benchmark.

Post by Constantin Makshin
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).

Post by Gunnar Roth
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.

Post by Constantin Makshin
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.

Post by Gunnar Roth
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.

Post by Gunnar Roth
Regards,
Gunnar Roth

[André Somers]

Post by Gunnar Roth
Hi Constantin.
Thank you for looking at my benchmark.

Post by Constantin Makshin
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?
If i search in a vector it should be sorted.

Not always true of course. You can only sort on one key. What if once in
awhile I need to search on another key? If usually my Employee objects
are in a vector sorted by id, I may still want to search by name once in
awhile. Of course, if you need to search frequently on a key, sort by it.

André

[Allan Sandfeld Jensen]

Post by Gunnar Roth
Hi Constantin.
Thank you for looking at my benchmark.

Post by Constantin Makshin
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? 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.

To process the values? This in my opinion the most common case, which is why
we have things such as foreach and recommend people to use const references
there

`Allan