[Development] [SPAM] How bad QList really is

Giuseppe D'Angelo giuseppe.dangelo at kdab.com
Tue Apr 28 15:45:52 CEST 2020


Il 28/04/20 11:16, Kevin Kofler ha scritto:
> * or the SSO gets reverted.

It's not SSO.

> Is there any actual evidence that it is a win in practice? 

Yes. But it's not SSO.

> And on what hardware?

Enough to justify the adoption in all std::string implementations and in 
3rd party ones as well (e.g. Folly).

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

Even more.

> And what about older hardware that is still in use?

Right, let's establish the foundations for the Qt 6 lifetime (2020-2035) 
by looking at 2002 hardware.

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

But: is copying less AND allocating better than just 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.

Good.

While we're at empirical evidence, do you want evidence of the contrary? 
Endless other users don't. Qt examples contain several instances of 
QList<Foo> with Foo untagged and too big to fit anyhow.

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

Can be != will be. Those examples have been around for a decade.

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

And the evidence for this need is?

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

That's why I didn't provide numbers, but still pointed out that the 
result, alone, is wrong.

-- 
Giuseppe D'Angelo | giuseppe.dangelo at kdab.com | Senior Software Engineer
KDAB (France) S.A.S., a KDAB Group company
Tel. France +33 (0)4 90 84 08 53, http://www.kdab.com
KDAB - The Qt, C++ and OpenGL Experts

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4329 bytes
Desc: Firma crittografica S/MIME
URL: <http://lists.qt-project.org/pipermail/development/attachments/20200428/7c3d20c8/attachment.bin>


More information about the Development mailing list