[Development] QList

[Olivier Goffart]

Am Donnerstag, 18. Mai 2017, 10:58:23 CEST schrieb Ville Voutilainen:
> [...] the QUIP is here for review:
> https://codereview.qt-project.org/#/c/194984/

Thanks, 
(Sorry for not replying to the QUIP, but discussions on gerrit are not so easy 
to follow)

Here are what  what are the characteristics of QList:

a. Amortized O(1) append
b. Amortized O(1) prepend
c. Relatively fast insert even if elements are expensive to copy/move
d. Implicitly shared (copy-on-write)
e. Should expand to less binary code than QVector or other container because 
most operation are done in qlist.cpp, common for very type. (I don't think 
this was mentioned before)
f. The pointers to elements are kept valid on append/prepend/insert if the 
list is not shared (detach) and the type is big enough.
g. It is inefficient because of the many allocations and bad cache behaviour.


In Qt 4.0, QList was made the default container for most purposes because of 
the points a,b,c,d,e which where believed to be good characteristics for a 
default sequence containers. I don't think f was an intended characteristic. 
(Actually, I believe that people who rely on it just rely on an accidental 
implementation detail / undefined behavior.)
And g was somehow ignored for some reason, or maybe it was tough that c was 
more important for the default container.

The question is what to do in Qt 5.x and in Qt 6?

QList being used everywhere means people might rely on any of these point.

It was suggested to simply replace making QList being an alias to QVector in 
Qt6. But we'd loose characteristics b,c,e,f.   
We could get b. back if we make it possible for QVector to reserve memory in 
front on prepend.
We could ignore c. as this might be less of a problem with move semantic 
nowadays. We could also ignore e.
But not having f. might introduce nasty bugs that might not be seen easily in 
big project while porting. So Marc suggested adding a QArrayList alias to 
annotate code today that we know are relying on f. as a porting aide.

I think QArrayList does not solve the problem because I'd say most people will 
not use it, they might not even know they rely on it. Their code works now, 
and if we replace QList by QVector it will introduce subtle bugs anyway.

Another solution could be to keep QList as it, but deprecate it, and use 
QVector everywhere in the API. We'd need to introduce implicit conversion 
between QList and QVector to reduce the amount of source incompatibilities.

An alternative could be to develop a new data structure that keep the 
good part of QList, while keeping good cache behavior. Maybe something modeled 
around std::deque. 


In my opinion for Qt6, we should make prepend, takeFirst amortized O(1) in 
QVector. And change the API to use QVector everywhere, with QList being a 
deprecated alias to it. Ignore the fact that people can keep pointers to the 
items. (Small behavior change that should not impact many usages.)

(For functions that do not take ownership of the vector, I'd make a new a 
QArrayView.)

-- 
Olivier

Woboq - Qt services and support - https://woboq.com - https://code.woboq.org