[Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Knoll Lars
Lars.Knoll at theqtcompany.com
Mon Jul 20 16:53:04 CEST 2015
On 13/07/15 10:34, "Giuseppe D'Angelo" <giuseppe.dangelo at kdab.com> wrote:
>Il 12/07/2015 23:19, Alejandro Exojo ha scritto:
>> El Sunday 12 July 2015, Thiago Macieira escribió:
>>> On Sunday 12 July 2015 16:16:07 Smith Martin wrote:
>>>> I can see by your explanation that QVector is almost always more
>>>> efficient than QList. But sometimes the difference doesn't matter.
>>>
>>> If it doesn't, then why not choose QVector?
>>
>> I've carefully read the thread, and I think the issue Martin or others
>>might
>> have is:
>>
>> * Documentation and the common know how about Qt containers tells that
>>QList
>> is a reasonable middle ground choice (sometimes is like a vector,
>>sometimes
>> like a linked list/vector hybrid). Is what the docs say, what the Qt
>>Quarterly
>> article says (which is old, but Olivier gave a recent explanation on
>> containers on 2012's devdays), what is being used in the API as return
>>type,
>> etc.
>
>Nitpicking: it's never like a linked list. It's either an array of T or
>an array of T*. Access is always O(1) (with potentially a big factor
>hidden due to the indirection), insertion in the middle always O(N)
>(with potentially a smaller factor than QVector, esp. for big Ts, due to
>the indirection), etc.
>
>Then, yes, QList is the recommended generic sequential container, and
>the one used all around in Qt APIs. And that's the problem which started
>this discussion.
Yes, I think pretty much everybody agrees that QList does not work as
advertised. In the ideal case it’s performance is about as good as a
QVector, in most other cases (with a few exceptions) it’s a lot worse. So
Marc is completely right that we should be using QVector by default in any
new code and in our implementations (as long as we don’t need QList
compatibility with existing API).
Most likely, we should change QList in Qt 6 to simply share it’s
implementation with QVector and make them both compatible, but we
unfortunately can’t do this right now.
>
>> * Marc has been criticizing what the docs says, but even being a
>>significant
>> contributor to Qt, did not propose to change that.
>
>And I actually disagree with that, given that QVector is faster than
>QList in the majority of the cases (and std::vector could be even faster
>and/or expand to less code). Having false statements in the docs is not
>good. I would like to see them changed.
Yes, we can’t complain about people using Qt wrongly (and even our own
developers and contributors), if our docs are wrong. Let’s fix them to say
that you should use QVector if possible and not QList.
>
>> * According to Martin's explanations, he did send a patch for qdoc that
>> replaced a wrong choice of container, but the change did not have any
>>apparent
>> effect.
>
>Which has been pointed out to be irrelevant to the purposes of this
>discussion (I have no idea of qdoc internals, has anyone profiled it?
>Maybe 99% of the time is spent on I/O or parsing C++ files and QVector
>over QList gives an advantage in nanoseconds for that particular use
>case?).
>
>But the totality of the other points in the first message stay, and
>noone has so far challenged them...
>
>> * We are having a large thread with a heated discussion, and Marc said
>>things
>> like "and the resulting code will be highly fragile and/or extremely
>> inefficient". People might felt a bit offended by that. Is something
>>being
>> said about their work, after all.
>
>Please do not make this an ad-hominem. It's an argument about the code.
>
>When you spot an unwarranted usage of a QList in some code, what it is
>about? Pick:
>
>A) Premature pessimization (you could've used QVector instead, but you
>picked QList because it's the "default" container -- it's documented
>that way!)
>
>B) You want amortized fast prepend
>
>C) Your type is "bad" and you want to rely on validity of references
>when the container gets modified
>
>(There's no "I want to call a function taking a QList" because that's
>totally justified).
>
>Experience tells that you're in A) 99% of the time ("extremely
>inefficient"). B) or C) count for "highly fragile", because you may
>break the code (or make it way more inefficient) by refactoring it.
>We've had cases of that. IIRC, this was a case of C) (refactoring from
>QList to QVector):
>
>>
>>https://codereview.qt-project.org/#/c/10878/9/src/corelib/kernel/qcoreapp
>>lication.cpp
>
>
>> To summarize:
>>
>> I not sure whether you (plural) think that no container should be
>>advised as
>> the preferred one, or if it should be QVector, though.
>
>IMHO it should be advised to be QVector. We have an excessive usage of
>QList in Qt APIs which makes people think QList is a good default, and
>this thread is all about why it's not a good default.
Fully agree. Let’s at least fix the docs. It won’t keep people from
choosing QList because the type is so pervasive in Qt’s API, but at least
we’re then giving better advice.
Cheers,
Lars
More information about the Development
mailing list