[Development] Container refactor update

[Marc Mutz]

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 :)

> 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).

> > So, can we please just have the equivalent of template
> > <typename T> using QList = QVector<T>; after moving the members
> > that QList has but QVector lacks over to QVector?
>
> -1. QList serves a purpose.

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?

Thanks,
Marc

-- 
Marc Mutz <marc.mutz at kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
www.kdab.com || Germany +49-30-521325470 || Sweden (HQ) +46-563-540090
KDAB - Qt Experts - Platform-Independent Software Solutions