哈希表在C#中比C++更快？

Question

这是我一直在调查的好奇心.与我继续运行的测试中的STL unordered_map相比,.NET Dictionary类的执行速度非常快,我无法弄清楚原因.

(我的机器上0.5秒对4秒)(.NET 3.5 SP1与Visual Studio 2008 Express SP1的STL)

另一方面,如果我在C#和C++中实现自己的哈希表,那么C++版本的速度大约是C#版本的两倍,这很好,因为它强化了我的常识,即本机代码有时更快.(参见.我说"有时候".)我是两种语言中的同一个人,我想知道微软的C#编码器能够扮演微软的C++编码器的伎俩是什么？我无法想象编译器如何能够自己发挥这样的技巧,经历了优化应该将其视为任意函数调用的麻烦.

这是一个简单的测试,存储和检索整数.

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

这两个版本不等价,你在C++ while循环的每次传递中构造一个迭代器.占用CPU时间并抛出结果.

Answer 2

您正在测量显式内存管理的成本.这里有更多统计数据. 这也是相关的. 和克里斯·塞尔斯的企图,以确定终止添加到CLR是显着的.