[Development] How bad QList really is

[André Pönitz]

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.