[Development] [SPAM] How bad QList really is

[Kevin Kofler]

Giuseppe D'Angelo via Development wrote:
> 1) First and foremost, in Qt 6 QString, QByteArray, QVector, are bigger
> than a pointer (3 times a pointer size). So, in Qt 6:
> 
> * either QList stays unchanged, and now we heap allocate each element
> for those cases too (thus it's necessary to know how the above
> statistics change); or
> 
> * QList gets adapted so that its internal array allocates 3 *
> sizeof(void*) per element, so that e.g. Q6StringList won't require a
> per-item allocation. This would then also avoid allocations for other
> datatypes, e.g. QStringView, QImage, maybe QVariant and QColor; but of
> course waste a ton of space for the ones which remain small (most of Qt
> implicitly shared datatypes).

* or the SSO gets reverted.

Is there any actual evidence that it is a win in practice? And on what 
hardware? It is very hardware-dependent whether copying several bytes is 
faster than incrementing one atomic. That may well be the case on today's 
hardware, but what about tomorrow's? And what about older hardware that is 
still in use?

The rule of thumb should be that copying less is better than copying more.

> The confirmation bias comes from the fact that Qt datatypes are designed
> to work nicely with QList; this for at least two good reasons:
> 
> a) Qt value types are normally pimpled (because of refcounting, or ABI
> stability) so they fit exactly in QList's array slots, but user-defined
> types aren't necessarily pimpled. Thus the bet: they're almost always
> the wrong size for QList.
> 
> b) We've spent an awful amount of time reviewing Qt's source code and
> tagging down every value type as movable (where it made sense). And I'd
> like to extend a big thank you to Sérgio for clazy, Marc for tirelessly
> fixing the code, Thiago for giving us relocatable types before Qt 6 in
> QVector-but-not-QList-as-that's-BIC. Users simply forget the dreaded
> typeinfo macro and so, for their types, QList is always in
> array-of-pointers mode no matter the size of the datatype.

I use implicitly-shared types and Q_MOVABLE_TYPE annotations in my code.

These can also usually be added later when needed. User code is not bound by 
as strict binary compatibility rules as Qt itself.

> In conclusion, if QList is a good choice for Qt's own types, and even if
> we then expose it at the API level as the Qt container of choice, its
> only advantage then over QVector is going to be prepending? How often is
> that a use case to justify the semantic burden of this extra container?

The prepending optimization alone is a necessary feature. Replacing QList 
with an unmodified QVector, without that prepending optimization, is 
entirely unacceptable.

> This cannot be claimed as a closed result: for insertion, it's ignoring
> the cost of the individual allocation of the newly inserted item, that
> needs to be traded off the moving of more bytes in memory.

That is highly dependent on the hardware, the operating system, and the 
malloc implementation (where there is more than one for the operating 
system). So the results you obtain will depend on what you run the benchmark 
on.

        Kevin Kofler