> As starters, there are 85 occurences of QList::takeFirst() in Qt Creator source code. Replacing these with QVector replaces a O(1) operation with an O(n) operation.
Apologies if I'm wrong, but isn't QList::erase (and anything derivative) always O(N) ? With a lower cost than std::vector for things with sizeof > 8, sure, but still. And, given that 98% of QList usage seems to fall into the "good" case of sizeof<= 8, wouldn't that make zero change when switching to QVector ? Best, Jean-Michaël On Mon, Apr 27, 2020 at 11:29 PM André Pönitz <[email protected]> wrote: > > On Mon, Apr 27, 2020 at 11:13:26AM -0400, Matthew Woehlke wrote: > > On 25/04/2020 10.49, André Pönitz wrote: > > > We all know the story that began with > > > > > > "We knew for a long time that QList is not a good default > > > container, despite what the documentation claims. The problem > > > boils down to the fact that for a lot of types T, QList<T> is > > > needlessly inefficient by allocating elements on the heap and > > > storing pointers to them instead of storing the elements > > > in-place, like e.g. QVector does. Sometimes, for large and > > > complex types, that might be exactly what you want, but a > > > conservative estimate would put that chance at less than 5%." [1] > > > > > > > > > I was curious how this "conservative" estimate of "less than 5%" > > > manifests in real QList object instances in a real world example. > > > > (Remainder elided) > > > > Thanks for the analysis! However, it seems the major take-away is that > > "when QList acts like QVector, all is well"? > > No. The major take-away is that in the first reality check on the topic > 98.5% of the cases QList behaves optimally, and in 1.4% the jury is still > out. > > Even if the jury comes back with a verdict that all the remaining cases > were better served by QVector (unlikely, see below) a shot-gun > replacement of QList would at best change 1 out of 70 instances, placing > the whole activity safely into micro-optimization land. > > > It would be interesting to see a comparison that ignores all instances > > where QList is behaving like QVector. > > This would indeed help us to understand how small the micro in this micro > optimization is, or whether we are actually looking at a pessimization. > > As starters, there are 85 occurences of QList::takeFirst() in Qt Creator > source code. Replacing these with QVector replaces a O(1) operation > with an O(n) operation. This may or may not be a problem in practice, > in any case, all such uses would need to be audited. Similarly removeAt, > removeOne and removeAll have a chance to degrade in performance. > > Andre' > > > PS: > > > The other problem is that performance isn't the only story. Sometimes, > > reference stability is desired. AFAIK, the only containers in Qt¹ that > > provide this currently are QLinkedList and QMap. > > (¹ I speak of Qt6, specifically. In Qt5, QHash could be added to that > list, > > but no more.) > > Sure, but that's a different topic. > > > _______________________________________________ > Development mailing list > [email protected] > https://lists.qt-project.org/listinfo/development >
_______________________________________________ Development mailing list [email protected] https://lists.qt-project.org/listinfo/development
