Sneak Preview: QList considered harmful


[[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 these ads

About marcmutz
Marc Mutz is a Senior Software Engineer, Trainer, and Consultant with KDAB.

14 Responses to Sneak Preview: QList considered harmful

  1. Christoph Bartoschek says:

    It is very rare that std::list performs better than std::vector. In our huge codebase we have only one use for std::list.

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

  3. Thomas McGuire says:

    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.

  4. pvandewyngaerde says:

    can we have a Krazy check for this ?

  5. Mariusz Ceier says:

    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.

  6. Mariusz Ceier says:

    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.

  7. oldium says:

    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.

  8. Aaron Seigo says:

    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.

    • marcmutz says:

      Depending on the platform and the compiler, QList ranges from “slightly slower” to “slower by a factor of >3″ (appending, Solaris/32bits, double payload). The only scenario I have found so far in which QList outperforms QVector in appending is QList<QString>, on Solaris. Note that middle and front insertions are home turf for QList, but they’re very rare compared to appends. The final Effective Qt column will have more measurements; this is just a sneak preview.

  9. dantti says:

    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…

    • marcmutz says:

      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;
      }
      
  10. Pingback: Grantlee pairs up with the “other” template system « Steveire's Blog

  11. Jan Struhár says:

    The statemenet is valid for Qt 4.x, but
    no longer holds in Qt5.1 according to my tests.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: