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 <[email protected]> | 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 _______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
