Если огромный массив быстрее, чем хэш-карта для поиска?

Ответ 1

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

Сказав это, я буду вздрагивать в темноте: возможно, если вы сможете убедить свою ОС, чтобы ваш многогигабитный массив находился в физической памяти (это не всегда легко - подумайте над mlock и munlock syscalls), у вас будет относительно высокая производительность. Любой такой прирост производительности, который вы заметите (если он существует), скорее всего, будет в результате обхода стоимости хэш-функции и избежания накладных расходов, связанных с стратегиями распределения конфликтов и распределения памяти, используемыми в реализации хэш-карты.

Также стоит предупредить, что многие реализации хеш-таблиц имеют не постоянную сложность для некоторых операций (например, отдельная цепочка может ухудшиться до O(n) в худшем случае). Учитывая, что вы пытаетесь оптимизировать время ожидания, массив с очень агрессивной сигнализацией диспетчера памяти ОС (например, madvise и mlock), скорее всего, приведет к ближайшим к поискам с постоянной задержкой, которые вы можете получить на микропроцессор легко.

Ответ 2

Хотя единственный способ объективно ответить на этот вопрос - это тесты производительности, я буду спорить об использовании Hashtable Map. (Кэширование и доступ к памяти могут быть настолько полны сюрпризов, у меня нет опыта для размышлений о том, какой из них будет быстрее, и когда. Также подумайте, что локализованные различия в производительности могут быть маргинализированы другим кодом.)

Моя первая причина "изначального выбора" хэша основана на наблюдении, что есть 100M различных ключей, но только 0,1M активных записей. Это означает, что , если использовать массив, использование индекса будет только 0,1% - это очень разреженный массив.

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

Поскольку все ключи уже являются целыми числами, функция распределения (хеш) и может быть эффективно реализована - нет необходимости создавать хэш сложного типа/последовательности, поэтому "стоимость" эта функция должна приближаться к нулю.

Итак, мой простой предложенный хеш:

• Используйте линейное зондирование, поддерживаемое непрерывной памятью. Он прост, имеет хорошую локальность (особенно во время зонда) и избегает необходимости выполнять любую форму динамического распределения.
• Выберите подходящий начальный размер ковша; скажем, 2x (или 0,2 М ведра, загрунтованные). Даже не давайте хэш шанс изменить размер. Обратите внимание, что этот предложенный размер массива ковша составляет всего 0,2% от размера простого подхода к массиву и может быть дополнительно уменьшен, поскольку можно настроить настройку размера и скорости столкновения.
• Создайте хорошую функцию распределения для хэша. Он также может использовать знания о диапазоне идентификаторов.

Пока я представил специализированные правила хэш-таблицы, "оптимизированные" для данного случая, я бы начал с нормальной реализации карты (будь то хэш-таблица или дерево) и протестировал ее.. если стандартная реализация работает хорошо, почему использовать его?

Теперь испытайте разных кандидатов в ожидаемых и экстремальных нагрузках - и выберите победителя.

Ответ 3

Это зависит от кластеризации идентификаторов.

Если активные идентификаторы кластерируются уже подходящим образом, то без хеширования кэш OS и/или L2 имеет справедливый снимок при сохранении хороших данных и обеспечении его низкой задержки.

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

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

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

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

Ответ 4

Накладные расходы хэш-карты по сравнению с массивом почти отсутствуют. Я бы поставил на хэш-карту из 100 000 записей по массиву из 100 000 000, без сомнения.

Помните также, что, хотя вы "не заботитесь о памяти", это также означает, что вам лучше иметь память для резервного копирования - массив из 100 000 000 целых чисел займет до 400 МБ, даже если все они пустые, Вы рискуете поменять свои данные. Если ваши данные будут заменены, вы получите удар производительности на несколько порядков.

Ответ 5

Вы должны проверить и профиль, как говорили другие. Мой случайный удар в темноте, тем не менее: хеш-таблица с высоким коэффициентом загрузки станет для вас способом. Один огромный массив будет стоить вам пропусков TLB, а затем промаха кеша последнего уровня на каждый доступ. Это дорого. Хэш-таблица, учитывая размер рабочего набора, о котором вы упоминали, вероятно, будет стоить лишь некоторой арифметики и пропустить L1.

Опять же, испытайте обе альтернативы на типичных примерах. Мы все просто колоть в темноте.