[Development] How bad QList really is
apoenitz at t-online.de
Mon Apr 27 23:35:35 CEST 2020
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%." 
> > 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
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.
> 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.
More information about the Development