Оптимизация Dictionary.TryGetValue()

Question

Я кодирую вычислительно дорогое приложение (задача обучения машинам NLP), которая нуждается в оптимизации.

Поскольку в моем коде есть много петель, я использовал Parallel.For (и варианты), чтобы распараллелить самые внешние петли. Я также использовал массивы и Dictionary s, чтобы построить несколько индексов, которые значительно сократили стоимость.

Профилировщик VS2010 указал, что приложение проводит большую часть времени в Dictionary.TryGetValue() (что является побочным продуктом индексов).

Это задает вопрос, могу ли я сделать лучше? И как?

Мой первый вопрос: существует ли общее мнение, что ConcurrentDictionary.TryGetValue работает лучше, чем Dictionary.TryGetValue в моем сценарии - много читателей, нет писателей?

Я не мотивирован, чтобы закодировать свой собственный хэшмап, поскольку он, вероятно, будет хуже, чем коллекции .NET. Но есть ли там библиотеки, которые гарантируют быстрый поиск моего сценария?

Возможно, реализация hashcode замедляет работу?

Answer 1

Dictionary.TryGetValue уже очень хорошо оптимизирован, в соответствии с MSDN:

Этот метод приближается к O (1) операцию.

Вы не упомянули, что ключи от вашего словаря, если вы используете пользовательский тип, убедитесь, что вы реализовали свой GetHashCode метод правильно, так как словари и хэш-таблицы полагаться на него и использовать его широко.

Answer 2

Мой первый вопрос, есть ли общее мнение, что ConcurrentDictionary.TryGetValue выполняет лучше, чем Dictionary.TryGetValue в моем сценарии - многие читатели, не писатели?

Я не проверял, но я обычно ожидать одновременная реализации иметь дополнительные накладные расходы, будучи немного медленнее в целом. Разница возникает, когда вам нужно синхронизировать доступ - то есть, если ваш код, ориентированный на чтение, должен иметь словарь lock, то параллельная версия (без блокировок) может быть быстрее. Поскольку вы упоминаете, что у вашего кода нет писателей, я предполагаю, что вы не используете lock s, и поэтому не будет никаких оснований рассматривать одну реализацию по сравнению с другой. Тем не менее, это может быть стоит профилирование, но даже если он был быстрее (и снова: я ожидаю, что это будет немного медленнее), я бы только ожидать, что она будет немного быстрее - так вряд ли значительно измените производительность.

Answer 3

При взгляде на результат профилировщика, который утверждает метод несет ответственность за большую часть времени выполнения, также важно, чтобы выяснить, если это происходит потому, что:

1. Метод был назван слишком много раз, или
2. один вызов метода занимает много времени

Если TryGetValue составляет большую часть времени, потому что это называется слишком много раз, это, вероятно, является признаком того, что вам нужно, чтобы уменьшить complexit y вашего алгоритма индексирования/поиска, чтобы TryGetValue можно было вызывать реже.

Достаточно продолжить исследование метода TryGetValue, если он занимает долгое время за вызов. Однако, как отметил Павел, TryGetValueсам уже хорошо оптимизирован. Весьма вероятно, что метод (ы) вызывается TryGetValue, метод (ы), который может быть переопределен вами, должен быть обвинен. Обычно вам необходимо обратить внимание на метод GetHashCode и Equals. Оба они будут вызываться при вызове TryGetValue. Equals может быть вызван более одного раза. Мой опыт заключается в том, что метод Equals обычно имеет больше шансов стать проблемой, поскольку встроенное сравнение равенства определенной структуры структуры включает отражение.