优化字典的TryGetValue()方法

Question

我正在编写一个计算密集型应用程序（自然语言处理机器学习任务），需要进行优化。

由于我的代码有很多for循环，我使用了Parallel.For（以及其变体）并行化最外层的循环。我还使用数组和Dictionary来构建一些索引，这大大降低了成本。

VS2010的分析器显示，该应用程序在Dictionary.TryGetValue()中花费了大部分时间（这是索引的副产品）。

这引出了一个问题：我能否做得更好？如何做到更好呢？

我的第一个问题是，在我的情况下，是否有普遍共识，即ConcurrentDictionary.TryGetValue比Dictionary.TryGetValue表现更好 - 读取者众多，但没有写入者？

我没有动力编写自己的哈希映射，因为它可能不如.NET的集合。但是是否有任何库保证我的情况下查找速度更快？

也许哈希码实现会拖慢速度？

- Howie

Answer 1

Dictionary.TryGetValue已经非常优化，根据MSDN的说明：

该方法接近O(1)操作。

您没有提到字典的键是什么，如果使用自定义类型，请确保已正确实现其GetHashCode方法，因为字典和哈希表依赖于它并广泛使用它。

- Pavel Vladov

---

O(1)并不完全等同于“非常优化”。我可以在一个方法的开头加入Thread.Sleep(60000)，仍然可以合理地声称它是O(1)。;p - Marc Gravell

可以，但如果你追求最大的性能，你可能不会这样做；我的意思是说，TryGetValue 方法不太可能导致速度变慢，但 GetHashCode 方法如果编码不当可能会导致速度减缓。 - Pavel Vladov

我已经对GetHashCode方法进行了分析，程序在其中花费的时间不到0.1％。我想我需要以不同的方式解决这个瓶颈问题。 - Howie

Answer 2

我的第一个问题是，在我的情况下，有没有普遍的共识认为ConcurrentDictionary.TryGetValue比Dictionary.TryGetValue更有效？即许多读取器，没有写入者？

我没有进行测试，但我通常会预期并发实现具有额外的开销，整体上略微较慢。区别在于当您需要同步访问时——即如果您的读取中心代码需要锁定字典，则不使用锁定的并发版本可能更快。由于您提到您的代码没有编写者，因此我猜测您不使用锁定，因此没有任何理由查看其中一个实现。尽管如此，这可能值得分析一下，但即使它更快（再次强调：我预计它会稍微慢一些），我也只会预计它会稍微快一些，因此不太可能显着改变性能。

- Marc Gravell

Answer 3

当查看分析器结果时，如果有一个方法占据了大部分的执行时间，那么弄清楚是因为以下哪个原因就变得很重要：

1. 该方法被调用的次数太多，或
2. 单次调用该方法需要很长时间

如果 TryGetValue 占用了大部分时间，因为它被调用的次数太多，那么这可能表明您需要减少索引/查找算法的复杂度，以便可以更少地调用 TryGetValue。

如果每次调用需要很长时间，那么进一步研究TryGetValue方法才有价值。然而，正如Pavel所提到的，TryGetValue本身已经经过了良好的优化。很可能是由TryGetValue调用的方法（可以被您重写的方法）出了问题。通常情况下，您需要注意GetHashCode和Equals方法。在调用TryGetValue时，这两个方法都将被调用。Equals可能会被多次调用。我的经验是，Equals方法通常更容易成为问题，因为某些框架结构的内置相等比较涉及反射。

- Xinchao