[Development] Container refactor update

[Marc Mutz]

On Thursday June 21 2012, André Pönitz wrote:
> 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.

You were talking about inserting in the middle, not append here.

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

Except that my "randomly selected usecases" appear all over the place in Qt 
APIs and yours doesn't, I agree.

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

The problem I have with QList is that the user needs to work hard not to make 
QList suck memory and speed-wise (mark it movable, be of the correct size) 
whilst the cases where its indirection really do give a benefit are, indeed, 
corner cases.

A specialised container is suggested as a good default container _and_ has the 
most attractive name, and in 95% of all use-cases, a QVector would have been 
preferable.

This is bad API design.

If you want to preserve the semantics of QList, do so, but don't call it a 
good default container and don't give it the most attractive name :)

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