[Development] Dropping QT_NO_STL (was: The future of QtAlgorithms)

[André Pönitz]

On Monday 30 January 2012 23:03:22 ext Thiago Macieira wrote:
> On Monday, 30 de January de 2012 18.38.56, João Abecasis wrote:
> > On 30. jan. 2012, at 17.25, ext Thiago Macieira wrote:
> > > My point here and below with "the containers themselves" is that we don't
> > > want to use those containers in our code nor in our API.
> > 
> > What's wrong with using them in our code, as long as they stay out of the
> > API/ABI?
> > 
> > std::vector is perfectly fine for a non-shared dynamically allocated array.
> 
> I'd like our containers to be good enough for that, to be honest. And avoid 
> subtle mistakes if the behaviour differs.

The problem is that QVector is _not_ "good enough" for some cases, mostly due 
to the sharing overhead.

Using std::vector in  _p.h or .cpp where it makes sense seems perfectly fine 
to me, (as would tackling the sharing problem)

In .h I'd rather avoid it though, even the #include <vector>

> But where it makes sense, sure. Roberto used STL in the his C++ parser. 
> 
> Just avoid "template bloat": out-of-line copies of identical code because the 
> compiler can't figure out two functions do the same. It's hard to measure.

But it _is_ measurable, and when you do it you'll come to the result that
straightforward QVector using code (i.e. using at() or even operator[] instead
of .data() plus pointer[index]) expands to significantly more code than 
std::vector. An awful lot of std::vector code expands to a handful instructions
while QVector access has all kind of indirections and conditional execution.

I went through that exercise two years with Symbian, I don't have the 
results around anymore, but getting a rough idea is easily done:

---------------------------------------- main.cpp ----------------------------------------
#include <QVector>
#include <vector>

extern QVector<int> q1();
extern std::vector<int> s1();
extern int q2();
extern int s2();

int main()
{
    return q1().size() + s1().size() + q2() + s2();
}

---------------------------------------- q1.cpp ----------------------------------------
#include <QVector>

QVector<int> q1()
{
    QVector<int> v;
    v.append(1);
    v.append(2);
    v.append(3);
    v.append(4);
    return v;
}
    
---------------------------------------- q2.cpp ----------------------------------------
#include <QVector>

int q2()
{
    QVector<int> v;
    v.append(1);
    v.append(2);
    v.append(3);
    v.append(4);
    return v.size();
}
    
---------------------------------------- s1.cpp ----------------------------------------
#include <vector>

std::vector<int> s1()
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    return v;
}

---------------------------------------- s2.cpp ----------------------------------------
#include <vector>

int s2()
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    return v.size();
}

Instructions executed according to valgrind (x86, but the pattern
repeats on x86_64 and arm).

q1: 6042
q2: 2112

s1: 7194
s2: 1116


So QVector has an advantage when it is copied, but loses by
a factor of almost two in local access in this case.

I argue that local access happens more often than copying, 
so QVector is optimizing for the wrong use case.

Of course you can tweak the code at get better results, at the expense
of readability and convenience, and not all access pattern are _that_
bad. But the bottom line stays.

And now the interesting aspect, code sizes:

q1: 709 bytes
s1: 260 bytes

This means the QVector version is fatter by a factor of 2.7(!).
All inlined, in both cases, nothing that looks obviously "combinable"
that would conceptually change by having multiple instances, most
notably the 466 bytes for QVector<int>::realloc(int, int) are _not_
included in the q1 count.


If you/we want to have a "good enough" replacement with sane syntax 
and all the Qt container convenience, drop the sharing from QVector.

As the change would be essentially source compatible we do have
the chance to fix it in Qt 5.

Andre'
-------------- next part --------------
A non-text attachment was scrubbed...
Name: a.tgz
Type: application/x-compressed-tar
Size: 492 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/development/attachments/20120131/2593fb7d/attachment.bin>