c# - System.Collections.Generic.Dictionary = 终极性能？

Question

我正在编写一个 Haxe C# 目标，并且我一直在研究 Haxe 的标准库的性能差异，以便我们可以通过其跨平台代码提供最佳性能。

一个很好的例子是哈希表代码。我不太愿意使用 .NET 的字典，因为它看起来很笨重(除了它持有的不必要信息之外，由于内存对齐问题，键/值对的结构会占用大量内存)，而且由于在 std 上库中没有对象哈希之类的东西，我真的认为我可以通过不必调用 GetHashCode 并一直内联它来压缩一点性能。

另外很明显，Dictionary 实现使用链表来处理冲突，这远非理想。

所以我们开始实现自己的解决方案，从 IntHash (Dictionary) 开始我们首先实现了Hopscotch hashing ，但结果确实不是很好，但很明显它不能很好地支持巨大的哈希表，因为 H 通常是一个机器字，并且随着 H/Length 的增加，性能越差。

然后我们跳转到实现 khash启发算法。这个有很大的潜力，因为它的基准测试令人印象深刻，并且它可以处理同一阵列上的冲突。它也有一些很棒的东西，比如调整大小而不需要两倍于我们需要的内存。

基准测试令人失望。当然，不用说我们的实现比 Dictionary 的内存使用要低得多。但我也希望能获得不错的性能提升，但不幸的是，事实并非如此。它并没有低于太远 - 不到一个数量级 - 但对于 set 和 get，.NET 的实现仍然表现更好。

所以我的问题是:这是我们拥有的最好的 C# 吗？我尝试寻找任何自定义解决方案，但似乎几乎没有。有那个 C5 泛型集合，但代码太乱了，我什至没有测试。而且我也没有找到基准。

那么……是吗？我应该环绕 Dictionary<> 吗？ ？

Answer 1

我发现 .NET Dictionary 在大多数情况下表现良好，即使不是特别好。这是一个很好的通用实现。我最常遇到的问题是 2 GB 的限制。在 64 位系统上，您不能向字典中添加超过 8950 万个项目(当键是整数或引用，值是引用时)。字典开销似乎是每个项目 24 个字节。

这个限制以一种非常奇怪的方式为人所知。 Dictionary 似乎通过加倍增长——当它变满时，它会增加下一个至少是当前大小两倍的素数的容量。因此，字典将增长到大约 4700 万，然后抛出异常，因为当它试图加倍(到 9400 万)时，内存分配失败(由于 2 GB 的限制)。我通过预先分配 Dictionary(即调用允许您指定容量的构造函数)来解决这个问题。这也加快了字典的填充速度，因为它永远不必增长，这需要分配一个新数组并重新散列所有内容。

是什么让您说 Dictionary 使用链表来解决冲突？我很确定它使用开放寻址，但我不知道它是如何进行探测的。我想如果它进行线性探测，那么效果类似于您使用链表获得的效果。

我们编写了自己的 BigDictionary 类来突破 2 GB 的限制，并发现使用线性探测的直接开放寻址方案可提供相当不错的性能。它不如 Dictionary 快，但它可以处理数亿个项目(如果我有内存的话可以处理数十亿个)。

也就是说，您应该能够编写一个更快的特定于任务的哈希表，它在某些情况下优于 .NET 字典。但对于通用哈希表，我认为您很难做得比 BCL 提供的更好。