Hash table faster in C# than C++?

Question

Here's a curiosity I've been investigating. The .NET Dictionary class performs ridiculously fast compared to the STL unordered_map in a test I keep running, and I can't figure out why.

(0.5 seconds vs. 4 seconds on my machine) (.NET 3.5 SP1 vs. Visual Studio 2008 Express SP1's STL)

On the other hand, if I implement my own hash table in C# and C++, the C++ version is about twice as fast as the C# one, which is fine because it reinforces my common sense that native machine code is sometimes faster. (See. I said "sometimes".) Me being the same person in both languages, I wonder what tricks was the C# coder from Microsoft able to play that the C++ coder from Microsoft wasn't? I'm having trouble imagining how a compiler could play such tricks on its own, going through the trouble of optimizing what should look to it to be arbitrary function calls.

It's a simple test, storing and retrieving integers.

C#:

const int total = (1 << 20);
int sum = 0;
Dictionary<int, int> dict = new Dictionary<int, int>();
for(int i = 0; i < total; i++)
{
    dict.Add(i, i * 7);
}

for(int j = 0; j < (1 << 3); j++)
{
    int i = total;
    while(i > 0)
    {
        i--;
        sum += dict[i];
    }
}
Console.WriteLine(sum);

C++:

const int total = (1 << 20);
int sum = 0;
std::tr1::unordered_map<int, int> dict;
for(int i = 0; i < total; i++)
{
    dict.insert(pair<int, int>(i, i * 7));
}

for(int j = 0; j < (1 << 3); j++)
{
    int i = total;
    while(i > 0)
    {
        i--;
        std::tr1::unordered_map<int, int>::const_iterator found =
            dict.find(i);
        sum += found->second;
    }
}
cout << sum << endl;

Answer 1

the two versions are not equivalent , your are constructing an iterator in each pass of your C++ while loop. that takes CPU time and throws your results.

Answer 2

There will be some differences at the code level: the fact that the unordered map takes a pair forces the construction of such object, when C# might be faster with passing two parameters in Add.

Another point is the implementation of the hashtables themselves: the implementation of the hashing function, or the way to deal with collisions, will cause different performance patterns.

Throw in alignment and caching, JIT-friendliness of some algorithms, and comparing two different implementations in two different languages becomes very difficult, and the only thing you can compare is the particular task at hand. Try with fewer or more elements, or try to access elements randomly instead of in sequence, and you might see very different results.

Answer 3

You are measuring the cost of explicit memory management. More statistics are available here. This is relevant too. And Chris Sells' attempt to add deterministic finalization to the CLR is notable.