With or Without Qt

Published Monday August 24th, 2009 | by

I wanted to do a certain bit of benchmarking for quite a while – years actually – but triggered by one of those friendly discussions on the ##c++ channel on FreeNode I finally figured I should sit down and actually do it. I was expecting some interesting results, but the not at the scale that we will see below.

If you ask the resident channel bot on ##c++ how to tokenize a std::string you’ll get offered the following (slightly compacted) code snippet:

  #include <sstream>
  #include <vector>
  #include <string>

  std::string str("abc:def");
  std::istringstream split(str);
  std::vector<std ::string> tokens;
  for (std::string each; std::getline(split, each, ':'); tokens.push_back(each));

Obviously, that’s the “Without Qt” version: Clean Standard C++, as straight-forward as it can get. The contender “With Qt” is:

  #include <QString>
  #include <QStringList>

  QString str("abc:def");
  QStringList tokens = str.split(':');

From the source alone we can collect a few numbers:

Property   Without Qt   With Qt   Ratio
Code to type   3 lines   1 line   3.0
  147 char   35 chars   4.2
Code usable as sub-expression   no   yes
Size of compilation unit [1]   22215 lines   7590 lines   2.9
Compile time [2]   1.64s   1.02s   1.6

To compare performance I use a benchmark that I just checked into the Qt source base, under tests/benchmark/qstringlist. It basically consists of running the above mentioned snippets on a string “unit:unit:unit:….” with 10, 100, 1000, and 10000 “unit” chunks and record callgrind’s “instruction loads per iteration” as follows:

Chunk count   Without Qt   With Qt   Ratio
10 chunks     18,455   9,827   1.9
100 chunks     134,578   71,008   1.9
1000 chunks     1,244,425   641,174   1.9
10000 chunks     13,161,115   7,053,633   1.9

In this case, bigger numbers mean more time needed to execute. Interesting, isn’t it?

After reading Thiago’s latest posts I got the impression that people like conclusions. The verbose version of a conclusion might be something along the lines of

Using Qt’s functions to split a string you need about a third of the effort to write code, and get a 47% performance boost at runtime.

Or shorter (Qt way): “Code less, create more”.

André

[1] Counted with “g++ -E -DQT_NO_STL -I$QTDIR/include/QtCore -I$QTDIR/include qt.cpp | wc” using g++ Ubuntu 4.3.3-5ubuntu4.

[2] Fastest result of “real” time, out of 20 runs each. “user” times in both scenarios smaller, with similar ratio.

Did you like this? Share it:

Posted in Qt

19 comments to With or Without Qt

Nils says:

Oh, you forgot that QString is fully Unicode. While this is great, you should also take the memory overhead in account which I assume is higher than with clean Standard C++.

Also std::getline works with any stream. So it would be more fair to compare this with QTextStream, but this class doesn’t offer the functionality at all.

A comparison with boost::tokenizer would be interesting too.

Tim says:

Interesting. Any idea why the pure C++ version is slower?

Tim says:

And how does it compare to a hand-written std::string method using string::find() and string::substr()?

Harald Fernengel says:

@Nils: Given that a lot of devices are not latin1, and UTF-8 has similar, sometimes higher memory penalty than UTF-16, I assume that Qt will also perform better memory-wise.

Marat says:

This is incorrect comparison: std::string (often) isn’t CoW (as QString is) and QStringList hasn’t vector nature (as std::vector).
So You’ve to make comparison with:
1) boost::tokenizer
2) std::list
3) boost::shared_ptr
Totally it will have larger code (in code lines) and will contain std::list >
This will dramatically change performance measurement results.

Marat says:

… and will contain std::list >

Marat says:

This is incorrect comparison: std::string (often) isn’t CoW (as QString is) and QStringList hasn’t vector nature (as std::vector).
So You’ve to make comparison with:
1) boost::tokenizer
2) std::list
3) boost::shared_ptr<std::string>
Totally it will have larger code (in code lines) and will contain std::list<boost::shared_ptr<std::string> >
This will dramatically change performance measurement results.

André says:

@Nils: No, I did not forget about Unicode. It’s just not interesting in this case as I wanted to compare the “natural” solutions of the “platforms”, and that happens to be “std::string” and “QString”.

I know that QByteArray is more similar to std::string (i.e. it also does not know in what encoding the contents is), and I could have used QList QByteArray::split(char sep) const. Doing that
(I just did…) improves the performance of the Qt version by another 10%.

But the “natural” representation of a string in Qt is QString, not QByteArray. It is so much easier and more robust to handle strings in a well-defined encoding (and only convert on input and output) than to pass opaque bunches of characters around, with encoding information only present implicitly.

Regarding “std::getline works with any stream”: The task was to split a string on a character, because that’s the question that pops up on ##c++ regularily, and it’s the task the channel bot’s code solves. There’s no need to apply a generic algorithm for a task as simple as that. In the rare cases you do need to read from a stream, you can do that in Qt as well. No need to pay for that kind of flexibility in the common use case, though.

André says:

@Marat: Why should I compare with boost? Boost is not part of “Standard C++ without Qt”. You could argue that I could have compared “C++ with boost” and “C++ with Qt”, but that’s another ballpark. I can do that next time, when I compare rendering performance of list views containing simple strings…

[Apart from that I am _really_ glad that I do not have to write “std::list >” when I need a bunch of strings]

Anyway, as I said the reply to Nils above: This comparison is about the _natural_ way to split a string at a character. If you think nolyc’s tokenization scheme is “not natural”, please give a more natural alternative. To me it looks pretty good, and it is what I would use if I had no Qt around.

Btw: What’s a ‘vector nature’ that QStringList does not have? Confused by QLinkedList?

spinynorman says:

That’s not a fair comparison since you’re using a library function for the Qt version, but handicapping the non-Qt version by limiting it to the shortest possible inline code. How about benchmarking Qt’s QString::Split vs a more real-world std::string version:

typedef std::list StringList;

void Split(const std::string &str, const std::string &sep, StringList &tokens)
{
tokens.clear();
int sepLength = sep.length();
if (sepLength == 0) {tokens.push_back(str); return;}
int start = 0;
int end;
while ((end = str.find(sep, start)) != str.npos) {
tokens.push_back(str.substr(start, end-start));
start = end + sepLength;
}
tokens.push_back(str.substr(start));
}

André says:

@spinynorman: C++ comes already with a library, the Standard Library. That’s what the “Without Qt” version uses. I am basically comparing that to the QtCore library. You are suggesting that in order to use the Standard Library to solve a simple problem efficiently I have to create a ten-line wrapper function, and if I don’t do that I have to accept a three line “inline” solution and a performance drop by a factor of 1.9. That certainly does not fit my conception of “simplicity”.

Even accepting your wrapper function as a solution this still leaves (a) the inconvenience of adding that to every project that happens to need to split a string (or, do as Qt does, put it into some library…) and (b) the factor 1.6 compile time overhead.

Sylvain Pointeau says:

You are using a vector in the C++ version,
this is why you are faster with a list in Qt.

Please use a std::list, you will certainly see a big improvement.

std::vector is not a good choice when you are adding a lot of element,
unless you can reserve the approx capacity.

spinynorman says:

Andre, let’s compare apples to apples.

If the C++ version is in a library, as the Qt version is, then where is the overhead in terms of lines of code, or compile time?

Since the focus of your post is about benchmarking, then the real question is which one is faster? QString::split() or the std::string() version?

Although a bit offtopic, it would be interesting to measure whether “usable as a sub-expression” (i.e. tokens as return type vs reference parameter) costs anything in terms of performance.

Nishant says:

oh man i am happy to see conclusions in blogs nowadays hehehehe..

JoeNotCharles says:

Others have pointed out that using std::list is just as natural STL, and closer to the Qt code. But the other big difference in this code is that the “natural” STL way is not necessarily to shove the results into a list – it depends on what you want to do with them. You may well want to process each immediately without the overhead of storing them in a list. Can you benchmark a version that, say, writes each token to stdout?

BeGo says:

Sorry for being off topic, and sorry for being rude.

Isn’t Qt is the streamlined version off C++ language? Just like comparing child hamster to mother hamster (which off course, Qt is simpler because it is newer)? Aren’t both shall be compiled to a same program, when they are compiled in the same environment)?

I used to hate C++, but love Qt the after a few moment after it is introduced to me by colleagues (IMHO, from my eyes, it actually closer to Java than C++ in term of programming logic).

Anyway, thanks for the update, Andre.

Marc says:

I fail to see why verifying that if one string class has a split() member function (aware of the internal representation of the string) and the other one has not (relying instead on generic algorithms instead), the one that has it is faster and takes less characters to type than the one that has not, is so sensational that you had to write a blog about it.

If you want a shootout between fat classes and generic algorithms, riddle me this:

How do I place QVector/QMap/QString’s data into QSharedMemory? :o

I’ll take the flexible one, thanks :)

André says:

[I try to make that the last response from my side. If there’s more interest in discussion, join #qt on FreeNode]

@spinynorman: I did not benchmark your “library code”, but as it is pretty much the same code that QByteArray::split() uses I would expect pretty similar results. But that’s not the point: The run time benchmark (second table) is there to prove that using a library like Qt does not mean your users will suffer bad performance. That it performs a bit better than the canonical “plain” version is more or less accidental, and that was not the reason to write the blog. The reason was the first table: Less code to write, easier to use, faster to compile. As this point went unchallenged so far I’ll simply assume there’s some truth to it…

@JoeNotCharles, Sylvain, Marat, spinynorman: Sorry, I have to dispel _that_ myth, too: No, std::list is not “closer” to the Qt Code. QStringList gives O(1) random access, O(1) accumulated push_back(), so it’s pretty close to std::vector which has the same properties, less so to std::list which does not have O(1) random access. A QList is _not_ a linked list, that’s what the (rarely used) QLinkedList is for.

Anyway, I spent now an additional hour tweaking optimization parameters and such. This buys
a percent or two, but does not change the full picture:

QList<QByteArray> 65,855 instr. loads per iteration
QList<QString> 70,074 instr. loads per iteration
std::vector<std::string> 132,865 instr. loads per iteration
std::vector<std::wstring> 136,214 instr. loads per iteration
std::list<std::string> 155,316 instr. loads per iteration

Note that the std::list based version is worst, probably due to the allocation overhead for the list nodes. I would expect that to get (relatively) better when chunks are made bigger. So next time I want to filter
500-character user names out of /etc/passwd and I can’t use Qt for that, I will use std::list. Promised ;-)

Philippe says:

I don’t really understand the “negative” posts. The essence of André’s thread is to recall Qt can solve problems with a solution that is both elegant and performant. And this is the main reason why many like Qt, I guess.

Commenting closed.