[Development] Container refactor update

[André Pönitz]

On Thu, Jun 21, 2012 at 01:06:16AM +0200, Marc Mutz wrote:
> On Thursday June 21 2012, André Pönitz wrote:
> > On Wed, Jun 20, 2012 at 08:52:55AM +0200, Marc Mutz wrote:
> > > Hi Thiago,
> > >
> > > [you knew this would be coming, I don't let you down]
> > >
> > > On Monday June 18 2012, Thiago Macieira wrote:
> > > > * port QList
> > >
> > > Before actually porting QList (esp. as I take the above to mean
> > > that QList won't be bound to void* slots anymore): Is there
> > > than *anything* in QList that QVector doesn't do at least as
> > > good or that could be ported over to QVector (reserving space
> > > in front for prepends comes to mind, though I'd argue that code
> > > that uses this a lot is broken by design anyway).
> >
> > Inserting in the middle of a container of complex data.  In both
> > cases O(n), but a simple move of a block of pointers in one case
> > but not on the other.
> 
> So that's a corner case of a corner case QList is optimized for. C++98 throw 
> specifications would still be alive and kicking if that was a valuable 
> goal :)

QList::append is not a corner case in my world.

> > Same for an append() that triggers 
> > re-allocation actually.
> >
> > Contrary to popular believe the constant hidden in big-O _does_
> > matter in practice...
> 
> Sorry, I was assuming familiarity with 
> http://marcmutz.wordpress.com/effective-qt/containers/#the-data
> which suggests that QList doesn't outperform QVector even in its own sweet 
> spot (QString, QByteArray).

I am afraid your randomly selected use case does not match my 
randomly selected use case.

At least the results differ.

For, say, 

#include <QList>
#include <QVector>
#include <math.h>

struct A
{
    A() : a(sin(12)) {}
    A(const A &b) : a(sin(b.a) + cos(b.a)) {}
    int a;
};

struct Foo
{
    A a[100];
};

int list()
{
    QList<Foo> f;
    for (int i = 0; i != 10000; ++i)
        f.append(Foo());
    return f.size();
}

int vector()
{
    QVector<Foo> f;
    for (int i = 0; i != 10000; ++i)
        f.append(Foo());
    return f.size();
}

int main()
{
    return list() + vector();
}

callgrind just came up with a 3:1 advantage _in favour_ of QList.

And that ratio can be made look arbitrarily worse by adding more load
to the copy constructor.

> Then it should be called QArrayList and the QList name freed for an 
> implementation with less surprising memory layout (ie. QVector).
> 
> Anyway, the rally point for my post was Thiago's observation that 
> QList<QString> with the new QString of 3*sizeof(void*) - I quote - "will be 
> horrible". If you change QList to be efficient for QString again, what else 
> do you have but a QVector?

> 
> > > I haven't seen a single Qt developer team (Qt devs not
> > > excepting) that is fully aware of the performance
> > > characteristics and memory layout of QList.
> >
> > That's an interesting observation that does not _fully_
> > seem to match mine ;-}
> 
> Case in point: QList<QModelIndex>, QList<QVariant> and QList<bool>. The first 
> two copy-construct all elements onto the heap, the latter wastes 87.5% (on 
> 64bit) of the allocated memory on padding.
> 
> What's the rationale for preferring QList here? Wouldn't you agree that these 
> would have better used QVector? Wouldn't you agree that changing QList to 
> QVector all over Qt 5 is a bit too source-incompatible and that therefore 
> backing QList by QVector would be a decent thing to do?

Replacing QList by QVector internally in cases where is makes sense is a no-brainer.
Making them equivalent, less so...

Andre'