3

I'm coding an computationally expensive application (NLP machine learning task) which is in a need of optimization.

Since my code has a lot of for-loops, I've used the Parallel.For (and variants) to parallelize the outer-most loops. I've also used arrays and Dictionarys to build a few indices which cut the cost considerably.

VS2010's profiler indicated that the application spends most of it's time in Dictionary.TryGetValue() (which is a side-product of indices).

This begs the question whether I can do better? And how?

My first question is whether there is general consensus that ConcurrentDictionary.TryGetValue performs any better than Dictionary.TryGetValue in my scenario -- many readers, no writers?

I'm not motivated to code my own hashmap as it will probably fare worse than .NET's collections. But are there any libraries out there that guarantee faster lookups for my scenario?

Perhaps the hashcode implementation is slowing things down?

4

3 回答 3

9

根据 MSDN, Dictionary.TryGetValue已经得到了很好的优化:

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

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

于 2013-05-16T07:21:08.543 回答
4

我的第一个问题是,是否有普遍共识ConcurrentDictionary.TryGetValueDictionary.TryGetValue我的场景表现更好——有很多读者,没有作者?

我尚未对其进行测试,但我通常希望并发实现会产生额外的开销,总体上会稍微慢一些。当您需要同步访问时,差异就出现了——即,如果您的以读取为中心的代码需要lock字典,那么并发版本(没有锁)可能会更快。既然您提到您的代码没有编写器,我猜您没有使用locks,因此没有任何理由查看一个实现而不是另一个实现。也就是说,可能值得对其进行分析,但即使它更快(再说一次:我希望它会稍微慢一点),我只希望它稍微更快 - 因此不太可能显着改变性能。

于 2013-05-16T07:21:18.583 回答
1

在查看声称方法对大部分执行时间负责的分析器结果时,弄清楚是否是因为:

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

如果 TryGetValue 由于调用次数过多而占大多数时间,则可能表明您需要降低索引/查找算法的复杂性,以便可以减少调用 TryGetValue 的频率。

只有在每次调用TryGetValue需要很长时间时,才值得进一步研究该方法。然而,正如 Pavel 所提到的,它本身已经进行了很好的优化。很可能是由 调用的方法,可以被您覆盖的方法,应该受到指责。通常你需要注意和方法。调用时都会调用它们。可以多次调用。我的经验是,由于某些框架结构的内置相等比较涉及反射,因此该方法通常更有可能成为问题。TryGetValue TryGetValueGetHashCodeEqualsTryGetValueEqualsEquals

于 2014-07-16T03:58:38.190 回答