[Development] How bad QList really is

[Jean-Michaël Celerier]

> 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 <apoenitz at t-online.de> 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
> Development at qt-project.org
> https://lists.qt-project.org/listinfo/development
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20200428/81f25e9b/attachment-0001.html>