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

Question

我一直在调查一个有趣的问题。在我的测试中，.NET Dictionary类的性能比STL unordered_map快得惊人，但我搞不清楚为什么。

(在我的机器上，.NET 3.5 SP1和Visual Studio 2008 Express SP1的STL，分别是0.5秒和4秒)

另一方面，如果我在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;

- Matthew

---

本地机器码比什么更快？你认为 C# 运行的是什么？ - David M

你如何衡量性能？ - stefanB

想知道你是否在发布版中运行代码。由于进行了许多额外的检查，因此 MS STL实现在调试版本中非常慢。请问您是在发布版本中运行代码吗？ - imaginaryboy

哇，真是巧合，我也有同样的观察。本来想写一个问题，但既然你已经写了完全相同的东西，那我就说声谢谢吧！ - Carlos

另外，std::map 是有序的，不像 Dictionary<T>。 - baltermia

Answer 1

这两个版本不等价，你在每次 C++ while 循环中都构造了一个迭代器。这会占用 CPU 时间并导致结果出错。

- Alon

---

同意 - 尝试用 "dict[i] = i * 7;" 替换 "dict.insert(pair<int, int>(i, i * 7));"，少一层麻烦。 - Chris Tonkinson

那还有，C#版本中使用了数组操作符，而C++版本则使用了find()方法。 - Glen

@Glen： "数组运算符"是一种语法上的便利，它调用了FindEntry方法。它没有速度优势。 - Ben M

@Ben，在我的STL版本中没有FindEntry方法。此外，下标运算符和find方法的实现有很大不同，这让我相信其中一个可能表现得非常不同。我不确定哪个是正确的，但适当的性能测试应该很容易证明。 - Glen

@Ben，如果你指的是C#下标运算符，那么我很抱歉我理解错误了。然而，OP应该尝试在两种实现中编写正确的代码，而不是将好的C#代码与平均的C++实现进行比较。 - Glen

Answer 2

你正在测量显式内存管理的成本。更多统计数据在这里可用。 这也是相关的。而Chris Sells 尝试向 CLR 添加确定性终结时值得注意。

- Hans Passant

Answer 3

在代码层面上会有一些不同：无序映射使用对强制构建此类对象，而C#可能通过添加两个参数来更快地传递。

另一个要点是哈希表本身的实现：哈希函数的实现或处理冲突的方式将导致不同的性能模式。

加入对齐和缓存、某些算法的JIT友好性，比较两种不同语言中的两种不同实现变得非常困难，你唯一可以比较的就是手头的特定任务。尝试少量或更多元素，或尝试随机访问元素而不是按顺序访问，你可能会看到非常不同的结果。

- small_duck