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' _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development