С# Dictionary Performance: строка по умолчанию Comparer GetHashCode() выделяет память в нарушение правил, что приводит к разрушению производительности?

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

Тем не менее, это то, что я вижу, что я просматриваю свое приложение, которое использует System.Collections.Generic.Dictionary

Углубление в очень узкой петле. В моих результатах профилирования я нахожу следующее:

  • [3.47%] TryGetValue (TKey, TValue &) (... Словарь)
    • [3.47%] FindEntry (TKey) (... Словарь)
      • [3.47%] GetHashCode (строка) (System.CultureAwareComparer)
        • [3.46%] GetHashCodeOfString (String, CompareOptions) (System.Globalization.CompareInfo)
          • [3.39%] [Сбор мусора]
          • [0.01%] [Thread Suspendended]

То, что весь подсчет дерева от профилировщика.

Я не опытный эксперт в этой конкретной работе, поэтому я мог бы неправильно читать эти чайные листья. Но мне кажется, что GetHashCodeOfString "должно быть" выделение памяти и приглашение сборщика мусора прерывать мою программу в середине этого цикла. Я хочу ДЕЙСТВИТЕЛЬНО НАСТРОИТЬ И ТЯЖЕЛО, и это объясняет огромную часть стоимости этого цикла.

В стороне, вот еще один пример доказательства того, что этот код выделяет память

Следующим шагом будет инициализация словаря с помощью порядкового сравнения и повторного запуска моих тестов.

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

Может ли кто-нибудь предложить правильный способ использования словаря со строковыми ключами, который позволяет избежать этой проблемы?

Конкретные вопросы, которые у меня есть:

  • Если я использую порядковый сравнитель, уйдет ли распределение?
  • Если нет, мне нужно написать свой собственный сравнитель и будет ли это делать увольнение?
  • Если я сделаю компаратор ушел, могу ли я действительно ожидать реального улучшения, в соответствии с рекомендацией по ссылке MSFT, с которой я начал?

EDIT: Crud, мой плохой, но это не со свойствами сравнения по умолчанию, мы установили для него ignoreCase. Не уверен, что это повлияет на результаты, но поскольку ignoreCase повлияет на равенство, оно должно иметь определенное влияние на хэш.

UPDATE: повторите еще одно испытание с использованием порядкового сравнения (по-прежнему с IgnoreCase) и переработайте исходный результат на 100% cost = TryGetValue, чтобы было больше яблок для яблок

Оригинал:

  • 100% TryGetValue
    • 100% FindEntry
      • 99.5% CultureAwareComparer.GetHashCode
        • 99.5% CompareInfo.GetHashCodeOfString
          • 95.86% [Сбор мусора]
          • 3.31% [Тема приостановлена]
      • 0.5% CultureAwareComparer.Equals
        • 0.5% Сравнить
          • 0.5% [сбор мусора]

Порядковый:

  • 100% TryGetValue
    • 100% FindEntry
      • 47.22% CultureAwareComparer.Equals
        • 47.22% [Сбор мусора]

Также наблюдалось резкое снижение общего времени в TryGetValue. Я не был осторожен, чтобы убедиться, что все остальное было равным, но на этот счет приходилось 46 секунд из 10-минутного стресс-теста в первом прогоне, а в ординальном прогоне он составлял 252 миллисекунды. Подумайте об этом, а не об ожидаемой относительной стоимости.

Похоже, что вся стоимость хэша, которая раньше составляла 99% от стоимости, теперь настолько "свободна", что она даже не появляется в профилировщике, который, как мне кажется, работает в режиме выборки.

Я думаю, это секундное слово на улице, что вы должны использовать порядковое сравнение.

Я все еще не могу доказать себе, почему стоимость GC очень сильно влияет на результат первого профиля, но из комментариев ниже я полагаю, что я должен полагать, что он НЕ выделяет управляемую память кучи, а потому, что он медленный, он имеет тенденцию быть функцией, которая "случайно" GCed другими действиями в других потоках, так как этот процесс действительно использует режим сервера gc.

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

Ответы

Ответ 1

По умолчанию, когда вы используете клавиши string, используется string.GetHashCode(). Этот метод не выделяет никакой памяти в куче и должен быть довольно быстрым.

Но поскольку вы используете случай игнорирования, вместо этого используется CultureAwareComparer.GetHashCode(). Этот метод вызывает (как видно из результатов вашего профиля) CompareInfo.GetHashCodeOfString(), который, в свою очередь, вызывает неуправляемую функцию InternalGetGlobalizedHashCode(). Ни один из двух управляемых методов не делает никаких распределений кучи (как вы можете видеть, смотрите ли вы на них в декомпиляторе). Я не могу сказать, что делает InternalGetGlobalizedHashCode(), но поскольку он неуправляемый, я сомневаюсь, что он делает какие-либо выделения на управляемой куче. В любом случае он должен быть намного сложнее, чем вычисление кода хэш-кода по умолчанию, тем более, что он осведомлен о культуре и должен иметь в виду такие проблемы, как Турецкая İ.

Это означает, что у вас, вероятно, есть другой код, который выделяет память в куче, что вызывает сбор мусора.

И если вы собираетесь достичь максимальной производительности, вам следует избегать "игнорировать дело" и, в особенности, его варианты, ориентированные на культуру.