Understand the Qt Containers: The Data

This is just a short heads-up to those that have asked for quantitative measurements. I’ve begun updating “Understand the Qt Containers” with a section on data.

As of now, the memory and append performance is in. I’ll re-run the iteration test over the night once more (I’ve detected an anomaly that I’d like the verify first), and re-add them again, when done.


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.

Heise Developer: Dem Elfenbeinturm entreißen

A little belatedly, I guess, but here we go:

For you German speakers out there, my first Heise Developer article, “Dem Elfenbeinturm entreißen: Über den praxisrelevanten Einsatz der Template-Metaprogrammierung“, “just” went live on Heise’s site.

It shows how to use TMP to convert from QVariant to boost::variant<>. Even if you don’t speak German, you might be interested in the sample source code: ftp://ftp.heise.de/pub/ix/developer/elfenbein.zip.

From the article:

Als Ansatz für eine Konvertierungsfunktion lässt sich Folgendes schreiben.

template <typename T_Variant>
T_Variant qvariant2variant( const QVariant & qv ) {
  for( T : types(T_Variant) )
    if ( qv.type() == T )
      return T_Variant( qvariant_cast<T>( qv ) );
  throw bad_cast( "..." );

Es fehlen noch zwei Dinge, um aus dem Pseudocode “richtigen” Code zu erstellen: Erstens ein Weg, um einen Typ T auf den dazugehörigen QVariant-internen Diskriminator abzubilden. Das leistet das Funktions-Template qMetaTypeId() […].

Zweitens ein Weg, um “für jeden Typ T, den T_Variant enthalten kann”, abzubilden. Das lässt sich mit TMP lösen (Stichwort: Liste von Typen), was die Aufgabe für den Rest des Artikels sein wird.