Alex Rivera | Logout

Hash table faster in C# than C++?

Asked 2009-12-13T21:21:11.107
18

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;
Edit
Report

1 Answer

5

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.

answered 2009-12-13T21:47:10.857

Your Answer