Why is QMap (and also std::map) significantly slower than MS .Net Dictionary class?

[grayfox]

I have the following C++ program:


#include <map>
#include <string>
#include <QDebug>
#include <QMap>
#include <QElapsedTimer>

using namespace std;

int main()
{
QElapsedTimer t;

qint64 e;
const int COUNT = 1000000;

// using std::map
t.start();
map<int,string> m;
for(int i = 0; i < COUNT; i++)
m[i] = "HI";

e = t.elapsed();
qDebug() << e;

// using Map
t.restart();
QMap<int,string> m2;
for(int i = 0; i < COUNT; i++)
m2[i] = "HI";
e = t.elapsed();
qDebug() << e;

return 0;
}

Compiled in release mode, the std::map version gives me a result of 208 ms, while the QMap version gives me a result of 220 ms.
But the .Net version is much faster


using System;
using System.Collections.Generic;
using System.Diagnostics;
internal class Program
{
private static void Main()
{
Stopwatch w = Stopwatch.StartNew();
Dictionary<int, string> dic = new Dictionary<int, string>();
long e;
const int COUNT = 1000000;

for (int i = 0; i < COUNT; i++)
{
dic[i] = "HI";
}
w.Stop();
e = w.ElapsedMilliseconds;
Console.WriteLine(e);
}
}

This gives me a result of 60 ms!
Am I doing something wrong? Or the result is actually normal? :confused:

[Kangs]

Replace QMap by QHash : http://doc.qt.nokia.com/4.7/qhash.html#details
It's perhaps more similar of Dictionnary

[SixDegrees]

Kangs is correct. QMap and std::map both use binary-tree based structures. QHash (there is no STL analogue) uses an actual hash table that will be limited predominantly by the hashing function, which should be very fast for int-type keys.

Note, also, that your choice of populating the containers - a series of sequential integers used as keys - guarantees worst-case insertion and retrieval performance in many implementations, as you wind up with tree as deep as the number of items, resulting in O(n) performance. A more realistic test would be to generate a set of random keys outside the timing loop, then use these to populate the container.

You should also test retrieval speed. It is common to populate such containers once, then retrieve information from them many times, so retrieval speed is often the more important metric. In fact, there isn't much point in storing data in a container if it will never be accessed, or will only be accessed once.

[grayfox]

Replace QMap by QHash : http://doc.qt.nokia.com/4.7/qhash.html#details
It's perhaps more similar of Dictionnary

I replaced QMap by QHash, and the result boost to 112 ms instead of 220 ms using QMap, but still, why is the .Net version run so much faster (60 ms)??

[SixDegrees]

Different hashing algorithm. As already noted, you're only testing insertion, so the only difference will be due to how the value is hashed, with some smaller difference attributable to the precise structure of the hash bins.

If you want more details, you'll need the code for both algorithms. Honestly, I don't see much difference. Are you really going to care if a million inserts takes 0.05 seconds longer? Particularly when it's much more likely to be retrieval rather than insertion speed which is more important?

[stampede]

I agree with SixDegrees. If you want to measure container performance, then test only this, with random data. There is almost no point in measuring the container allocation time, construct a test case which is closer to real life - test the insertion and retrieval time with random data instead (if you really need to).
In real-life application the performance can be killed by, for instance, slow window manager or wrong/slow algorithm or thousands other things. Fast dictionary wont help you in that case.

[MarekR22]

I suspect that problem is also in use of string "HI". Note that for .net this string is representing object at compile time and no conversion is required. In Qt/C++ code this string is a C-string which is converted to QString or std::string and this will give performance penalty.
Try define a const value of std::string or QString before start measurement.