Sneak Preview: QList considered harmful
2010-07-29 15 Comments
[[EDIT 2011-08-15: This has since been extended into a full Effective Qt column.]]
We knew for a long time that QList is not a good default container, despite what the documentation claims. The problem boils down to the fact that for a lot of types T, QList<T> is needlessly inefficient by allocating elements on the heap and storing pointers to them instead of storing the elements in-place, like e.g. QVector does. Sometimes, for large and complex types, that might be exactly what you want, but a conservative estimate would put that chance at less than 5%.
It never ceases to amaze me how people trained in the STL default to std::vector until a profiler tells them that they should use a std::list or std::deque instead, whereas people trained in Qt default to QList and not QVector.
Effective Qt will soon come out with all the gory details, but since KDE’s 4.5 and Qt’s 4.7 releases are imminent, I decided to give you a sneak preview of just how widespread this inefficiency is. In order to do that, I finally sat down and developed a patch that emits a warning when you try to add something to an inefficient QList (at least if you set your compiler to warn for signed/unsigned integer comparison warnings). It’s been developed and tested with GCC 4.3 and Qt 4.6.3, but should work for a lot of other compilers, too. Please send me warning generators for your compiler in comments.
The patch is binary-compatible, so you don’t have to recompile your Qt after applying it.
Here’s a (incomplete) list of inefficient uses of QList (in the following, T and S are arbitrary type):
QVariant(!!) is too large.QVector<T>isn’t marked as movable, even though it is.QSharedPointer<T>is too large.- Virtually any
QPair<T,S>is too large. - Enums not marked as movable.
Run, don’t walk, and fix your new API to not use QList, or mark your new types as movable (details are in the patch). Alas, both changes are binary incompatible, so you can’t do them if you need your code to stay BC. This might be one of the reasons why QPair and QVector aren’t “fixed” yet: doing so would change the layout of the QList instantiated with them :(.
But, at least for new code, there’s no excuse anymore: Just apply the patch.
About marcmutz
-Wmarc 
It is very rare that std::list performs better than std::vector. In our huge codebase we have only one use for std::list.
Any chance of a patch to fix QList? I, too, raised an eyebrow when I saw that QList allocates anything bigger than size_t (as I recall) on the heap. I would’ve set that threshold to at least 16 bytes, allowing 2 size_t on 64 platforms, and maybe I would’ve gone as far as 64 bytes. Worse, QList does not even use a trait class (again, as I recall), so there is no way to change this behaviour. After all, a small class might be expensive to copy or move, while a big one might be relatively inexpensive.
It’s a shame, because QList does a lot of things nicely, in that it avoids a lot of ugly cornercases. E.g., I love that it is growable in either end, so that I don’t have to “invert” lists to be efficient.
In the end, where performance matters, I increasingly find myself using the STL versions, as I find them much more flexible. They do require typedefs to avoid going insane, I admit.
I can also recommend to read http://doc.qt.nokia.com/qq/qq19-containers.html to someone who doesn’t know the container internals yet. And the header files of course, they are very interesting as well.
can we have a Krazy check for this ?
Short of hard-coding types in Krazy, I don’t think Krazy is powerful enough to detect this.
You could also make warnings much more verbose (e.g. not requiring -Wsign-compare on GCC ) by using warn_unused_result attribute (works only on GCC) and deprecated attribute ( should work with many compilers ):
#include
#define DECLARE_WARNING(name,description) template \
struct warning_##name { \
typedef unsigned int signed_or_unsigned; \
static void name() {}; \
}; \
template \
struct warning_##name { \
typedef signed int signed_or_unsigned; \
Q_DECL_DEPRECATED \
static signed int name() Q_REQUIRED_RESULT { \
return 0; \
} \
};
#define CUSTOM_CHECK(name,when,test) do { \
const typename warning_##name:: \
signed_or_unsigned a = 0; \
warning_##name::name(); \
const unsigned int b = 0; \
const bool c = (a!=b); \
Q_UNUSED(c); \
} while(0)
#define CHECK(name,test) CUSTOM_CHECK(name,true,test)
DECLARE_WARNING(use_qvector, "Port your code from QList to QVector for your T");
DECLARE_WARNING(add_movable_type, "Add Q_DECLARE_TYPEINFO(T, Q_MOVABLE_TYPE) iff your T is actually movable");
template
void tester() {
const bool titest=(QTypeInfo::isLarge || QTypeInfo::isStatic);
CHECK(use_qvector, titest && (sizeof(T) > sizeof(void*)) );
CHECK(add_movable_type, titest && (sizeof(T) <= sizeof(void*)) );
}
struct bigstruct {
int a,b,c,d;
void *ptr;
};
struct static_small_struct {
char c;
};
int main() {
tester(); // No warning
tester(); // No warning
tester(); // No warning
tester(); // use_qvector warning: deprecated function use_qvector, unused result of use_qvector, signed with unsigned comparison
tester(); // use_movable warning: deprecated function use_movable, unused result of use_moveable, signed with unsigned comparison
return 0;
};
I hope this code is readable enough, and this comment too – missing preview button.
You could also make warnings much more verbose (e.g. not requiring -Wsign-compare on GCC ) by using warn_unused_result attribute (works only on GCC) and deprecated attribute ( should work with many compilers ):
http://pastebin.com/1aBdMdYE
Sorry for double-comment.
It is always bad to misuse anything for other than the original reasons.
If you are able to tell – better than the developper – which version of container (QList/QVector) is more efficient, then create a type “QSmartContainer” that uses internally QList or QVector (or anything else) based on that decision. It is very confusing for developper to see completely unrelated warnings.
when you say it is needlessly inefficient, do you have any measurements of the impact of that inefficiency? e.g. if it isn’t significant except for data sets in excess of a certain size, that will impact what i decide to change and what isn’t worth changing due to the benefit being too small to justify the cost.
Depending on the platform and the compiler,
QListranges from “slightly slower” to “slower by a factor of >3” (appending, Solaris/32bits,doublepayload). The only scenario I have found so far in whichQListoutperformsQVectorin appending isQList<QString>, on Solaris. Note that middle and front insertions are home turf forQList, but they’re very rare compared to appends. The final Effective Qt column will have more measurements; this is just a sneak preview.I think most people defaults to QList simply because it’s far more convenient when you use Qt.
For example if you have a QHash and want all values or keys, the values() method does not return QVector, which ends up giving you a bit more work to do if you only want QVectors around…
s/a bit/minuscully/, yes :):
template <typename K, typename V> QVector<V> values( const QHash<K,V> & c ) { QVector<V> v; v.reserve( c.size() ); for ( typename QHash<K,V>::const_iterator it = c.begin(), end = c.end() ; it != end ; ++it ) v.push_back( it.value() ); return v; }Pingback: Grantlee pairs up with the “other” template system « Steveire's Blog
The statemenet is valid for Qt 4.x, but
no longer holds in Qt5.1 according to my tests.
Pingback: Uncovering 32 Qt best practices at compile time with clazy - KDAB