Контейнеры на основе хэш-таблицы - это очень быстрый ассоциативный массив (например, unordered_map, unordered_set).
Их производительность сильно зависит от этой хэш-функции, используемой для создания индекса для каждой записи. По мере роста хеш-таблиц элементы снова и снова повторяются.
Указатели - это простой тип, в основном значение 4/8 байт, которое однозначно идентифицирует объект. Проблема в том, что использование адреса в результате хэш-функции неэффективно из-за того, что несколько LSB равны нулю.
Пример:
struct MyVoidPointerHash {
size_t operator()(const void* val) const {
return (size_t)val;
}
};
Более быстрая реализация - потерять несколько бит:
struct MyVoidPointerHash2 {
size_t operator()(const void* val) const {
return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
}
};
Последнее произвело увеличение производительности на 10-20% для большого приложения, которое использует хэш-множества и карты с десятками тысяч элементов, которые часто создаются и очищаются.
Может ли кто-нибудь предложить лучшую схему для указателей хеширования?
Функция должна быть:
- Быстро! и должен хорошо встраиваться.
- Предлагаем разумное распределение, разрешены редкие столкновения.
Обновление - результаты тестов
Я выполнил два набора тестов, один для int* и для указателя класса, размер которого составляет 4 КБ. Результаты очень интересны.
Я использовал std::unordered_set для всех тестов с размером данных, равным 16 МБ, который был выделен в одном вызове new. Первый алгоритм работал дважды, чтобы убедиться, что кеши настолько горячие, насколько это возможно, и процессор работает на полной скорости.
Настройка: VS2013 (x64), i7-2600, Windows 8.1 x64.
- VS2013 хэш-функция по умолчанию
- Hash1:
return (size_t)(val); - Hash2:
return '(size_t)(val) >> 3; - Hash3 (@BasileStarynkevitch):
uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15)); - Hash4 (@Roddy):
uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16)); - Hash5 (@egur):
код:
template<typename Tval>
struct MyTemplatePointerHash1 {
size_t operator()(const Tval* val) const {
static const size_t shift = (size_t)log2(1 + sizeof(Tval));
return (size_t)(val) >> shift;
}
};
Тест 1 - int*:
- VS2013 по умолчанию занял 1292мс
- Hash1 взял 742ms
- Hash2 взял 343ms
- Hash3 взял 1008 мс
- Hash4 взял 629ms
- Hash5 взял 350 мс
Тест 1 - 4K_class*:
- VS2013 по умолчанию занял 0.423мс
- Hash1 занял 23.889мс
- Hash2 занял 6.331мс
- Hash3 взял 0.366мс
- Hash4 взял 0.390ms
- Hash5 взял 0.290ms
Update2:
Победителем пока является шаблонная хэш-функция (Hash5). Лучший уровень производительности для скорости для различных размеров блоков.
Обновление 3: Добавлена хэш-функция по умолчанию для базовой линии. Оказывается, это далеко не оптимально.
