[Development] How bad QList really is

[André Pönitz]

On Tue, Apr 28, 2020 at 12:25:32AM +0200, Jean-Michaël Celerier wrote:
>    > 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) ?

Not in 5.x

https://codereview.qt-project.org/gitweb?p=qt/qtbase.git;a=blob;f=src/corelib/tools/qlist.cpp;h=5d5da20752aa3d21e06330094095702019f53c93;hb=refs/heads/5.15.0#l272

For offset == 0 the memmove is of length 0, only d->begin is bumped.

>    With a lower cost than std::vector for things with sizeof > 8, sure,
>    but still.

Even when inserting in the middle, where both QList and QVector insertion
is formally O(n), QList on large data only memmoves size/2 pointers,
QVector's size/2 operations can be arbitrarily expensive, depending on the
exact nature of the stored items.

>    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
>    ?

There would be no difference in those cases if the premise were right.
But it isn't.

If you have ideally movable items in the QVector case (i.e. item move
costs equal to one pointer move, and the move loop optimized the same
as the explicit memmove), and choose a random position in the container
to insert from a uniform distribution, the expected cost of item shuffling
due to the insertion is for QList only half the cost as for QVector.

This ratio decreases further, i.e. becomes even more in favour of
QList, when the items are not ideally movable.

Andre'