System.Collections.Generic.Dictionary = Максимальная производительность?

Question

Я пишу цель для Haxe C # и изучаю различия в производительности для библиотеки std Haxe, чтобы мы могли обеспечить максимальную производительность благодаря кроссплатформенному коду.

Один очень хороший пример -код хеш-таблицы.Я немного неохотно пользовался словарем .NET, так как он кажется громоздким (структуры для пар ключ / значение могут занимать огромный объем памяти из-за проблем с выравниванием памяти, помимо ненужной информации, хранящейся в нем), а также из-за stdВ библиотеке нет такого понятия, как хэш объекта, я действительно думал, что смогу немного снизить производительность, не вызывая GetHashCode и вставляя его все время.

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

Итак, мы начали реализовывать наше собственное решение, начиная с IntHash (словарь). Сначала мы реализовали хеширование Hopscotch , но оно действительно неполучилось очень хорошо, но было очевидно, что он не очень хорошо поддерживал бы огромные хеш-таблицы, поскольку обычно H - машинное слово, а с увеличением H / Length производительность ниже.

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

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

Итак, мой вопрос: это лучшее, что у нас есть для C #?Я пытался найти любое нестандартное решение, и, похоже, его почти нет.Существует общая коллекция C5, но код настолько перегружен, что я даже не тестировал.И я также не нашел эталон.

Итак ... Это так?Должен ли я просто обернуть вокруг Dictionary<>?

Answer 1

Я обнаружил, что .NET Dictionary работает хорошо, если не исключительно хорошо, в большинстве ситуаций. Это хорошая реализация общего назначения. Проблема, с которой я чаще всего сталкиваюсь, это ограничение в 2 гигабайта. В 64-разрядной системе вы не можете добавить в словарь более 89,5 миллионов элементов (когда ключ является целым числом или ссылкой, а значение является ссылкой). Похоже, что словарь занимает 24 байта на элемент.

Этот предел проявляется очень странным образом. Кажется, что Dictionary увеличивается вдвое - когда он заполняется, он увеличивает емкость до следующего простого числа, которое, по крайней мере, удваивает текущий размер. Из-за этого словарь вырастет примерно до 47 миллионов, а затем выдаст исключение, поскольку при попытке удвоения (до 94 миллионов) распределение памяти завершается неудачно (из-за ограничения в 2 гигабайта). Я обошёл проблему, предварительно выделив Dictionary (то есть вызов конструктора, который позволяет вам указать емкость). Это также ускоряет заполнение словаря, потому что он никогда не должен расти, что влечет за собой выделение нового массива и повторное хеширование всего.

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

Мы написали наш собственный класс BigDictionary, чтобы преодолеть ограничение в 2 гигабайта, и обнаружили, что простая схема открытой адресации с линейным зондированием дает достаточно хорошую производительность. Это не так быстро, как Dictionary, но может обрабатывать сотни миллионов элементов (миллиарды, если бы у меня была память).

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

Answer 2

Есть много вещей, которые необходимо учитывать при определении "лучшей" хеш-таблицы. Одна из причин того, что пользовательские подходы, которые вы пробовали, были медленнее или не лучше, чем .NET Dictionary, заключается в том, что очень часто производительность хеш-таблицы очень сильно зависит от:

• Хешируемые данные
• Производительность хеш-функции
• Коэффициент загрузки стола
• Количество столкновений против без столкновений
• Алгоритм разрешения коллизий
• Количество данных в таблице и как они хранятся (по указателю / ссылке или непосредственно в контейнерах)
• Шаблоны доступа к данным
• Количество вставок / удалений против поиска
• Необходимость изменения размера в реализации закрытого хеширования / открытой адресации
• и многие другие факторы ...

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

Следовательно, нет. .NET Dictionary не является окончательной хэш-таблицей для каких-либо конкретных целей. Но, учитывая частоту использования словаря, я уверен, что команда Microsoft BCL (Base Class Library) выполнила огромное количество профилирования, чтобы выбрать подход, который они выбрали для общего случая.