Контейнеры на основе хэш-таблицы - это очень быстрый ассоциативный массив (например, 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.
return (size_t)(val);return '(size_t)(val) >> 3;uintptr_t ad = (uintptr_t)val;
return (size_t)((13 * ad) ^ (ad >> 15));uintptr_t ad = (uintptr_t)val;
return (size_t)(ad ^ (ad >> 16));код:
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*:
Тест 1 - 4K_class*:
Update2:
Победителем пока является шаблонная хэш-функция (Hash5). Лучший уровень производительности для скорости для различных размеров блоков.
Обновление 3: Добавлена хэш-функция по умолчанию для базовой линии. Оказывается, это далеко не оптимально.
Предоставив этот вопрос на некоторое время, я покажу свою лучшую хэш-функцию для указателей:
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;
}
};
Это высокая производительность для различных размеров блоков.
Если у кого-то есть лучшая функция, я изменю принятый ответ.
Правильный ответ с теоретической точки зрения: "Используйте std::hash, который, вероятно, специализируется так же хорошо, как и он, и если это не применимо, используйте хорошую хэш-функцию, а не быструю. скорость хеш-функции не имеет значения, так как ее качество".
Практический ответ: "Используйте std::hash, который является бедным, но тем не менее работает на удивление хорошо".
TL; DR
После того, как я стал заинтригован, я провел около 30 часов тестов за выходные. Среди прочего, я попытался получить средний случай против худшего случая и попытался принудить std::unordered_map к худшему поведению, дав ему намеренно плохие намеки на подсчет веток в отношении установленного размера.
Я сравнивал бедные хэши (std::hash<T*>) с общеизвестными хэшами общего назначения общего хорошего качества (djb2, sdbm), а также с изменениями из них, которые учитывают очень короткую длину ввода, и к хэшам, которые явно считаются для использования в хэш-таблицах (murmur2 и murmur3), а также хеши-бедняки, которые на самом деле хуже, чем не хеширование вообще, поскольку они выбрасывают энтропию.
Поскольку самые низкие 2-3 бита всегда равны нулю в указателях из-за выравнивания, я счел целесообразным проверить простой сдвиг вправо как "хеш", поэтому будет использоваться только ненулевая информация, если хэш-таблица, например. используются только младшие N бит. Оказалось, что для разумных сдвигов (я также пробовал необоснованные сдвиги!) Это действительно хорошо работает.
Некоторые из моих выводов были хорошо известны и неудивительны, другие очень удивительны:
std::unordered_map на плохое поведение. Даже если умышленно плохие намеки на подсчет веток, которые заставят несколько повторных хэшей, общая производительность не намного хуже. Только самые худшие хеш-функции, которые отбрасывают большую часть энтропии почти смехотворным образом, способны значительно влиять на производительность более чем на 10-20% (например, right_shift_12, что практически приводит к 12 только хэш-значениям для 50 000 входов Неудивительно, что хеш-карта в этом случае работает в 100 раз медленнее - мы в основном выполняем поиск по произвольному доступу в связанном списке.).std::hash<T*> является откровенно жалкой для GCC (простой reinterpret_cast). Смешно, функтор, который делает то же самое, последовательно работает быстрее при вставках и медленнее при произвольном доступе. Разница небольшая (дюжина миллисекунд при 8-10-секундном тестовом прогоне), но это не шум, она постоянно присутствует - вероятно, связана с переупорядочением команд или конвейерной обработкой. Поразительно, как точно такой же код (который также является не-оператором) последовательно выполняет по-разному в двух разных сценариях.std::hash. Обычно они приземляются в верхней части 3-4.Тестирование проводилось не только с 4-байтовыми или 8-байтовыми (или любыми) выровненными значениями, но и для фактических адресов, получаемых из распределения полного набора элементов в куче, и хранения адресов, предоставленных распределителем в std::vector (объекты были удалены, они не нужны).
Адреса были вставлены во вновь выделенный std::unordered_map для каждого теста в порядке, хранящемся в векторе, один раз в исходном порядке ( "последовательный" ) и один раз после применения a std::random_shuffle на векторе.
Тесты выполнялись для наборов из 50 000 и 1 000 000 объектов размером 4, 16, 64, 256 и 1024 (результаты для 64 опущены здесь для краткости, они как и ожидалось где-то посередине между 16 и 256 - StackOverflow позволяет отправлять только 30 тыс. Символов).
Набор тестов выполнялся 3 раза, результаты варьировались на 3 или 4 миллисекунды здесь и там, но в целом одинаковы. Результаты, опубликованные здесь, являются последним прогоном.
Порядок вставки в "случайном" тесте, а также шаблон доступа (в каждом тесте) является псевдослучайным, но точно идентичным для каждой хэш-функции в тестовом прогоне.
Тайминги в хеш-тестах предназначены для суммирования 4 000 000 000 хэш-значений в целочисленной переменной.
Столбец insert - это время в миллисекундах для 50 итераций создания std::unordered_map, вставляя соответственно 50 000 и 1,000,000 элементов и уничтожая карту.
Столбец access - это время в миллисекундах, чтобы выполнить 100 000 000 поисков псевдослучайного элемента в "векторе", за которым следует поиск этого адреса в unordered_map.
Это время включает в себя в среднем один тайник кэша для доступа к случайному элементу в vector, по крайней мере для большого набора данных (небольшой набор данных полностью помещается в L2).
Все тайминги на 2,66 ГГц Intel Core2, Windows 7, gcc 4.8.1/MinGW-w64_32. Гранулярность таймера @1 мс.
Исходный код доступен в Ideone, опять же из-за ограничения количества символов Stackoverflow 30k.
Примечание. Запуск полного набора тестов занимает более 2 часов на настольном ПК, поэтому будьте готовы совершить прогулку, если хотите воспроизвести результаты.
Benchmarking hash funcs...
std::hash 2576
reinterpret_cast 2561
djb2 13970
djb2_mod 13969
sdbm 10246
yet_another_lc 13966
murmur2 11373
murmur3 15129
simple_xorshift 7829
double_xorshift 13567
right_shift_2 5806
right_shift_3 5866
right_shift_4 5705
right_shift_5 5691
right_shift_8 5795
right_shift_12 5728
MyTemplatePointerHash1 5652
BasileStarynkevitch 4315
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 421 6988
reinterpret_cast 408 7083
djb2 451 8875
djb2_mod 450 8815
sdbm 455 8673
yet_another_lc 443 8292
murmur2 478 9006
murmur3 490 9213
simple_xorshift 460 8591
double_xorshift 477 8839
right_shift_2 416 7144
right_shift_3 422 7145
right_shift_4 414 6811
right_shift_5 425 8006
right_shift_8 540 11787
right_shift_12 1501 49604
MyTemplatePointerHash1 410 7138
BasileStarynkevitch 445 8014
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 443 7570
reinterpret_cast 436 7658
djb2 473 8791
djb2_mod 472 8766
sdbm 472 8817
yet_another_lc 458 8419
murmur2 479 9005
murmur3 491 9205
simple_xorshift 464 8591
double_xorshift 476 8821
right_shift_2 441 7724
right_shift_3 440 7716
right_shift_4 450 8061
right_shift_5 463 8653
right_shift_8 649 16320
right_shift_12 3052 114185
MyTemplatePointerHash1 438 7718
BasileStarynkevitch 453 8140
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 8945 32801
reinterpret_cast 8796 33251
djb2 11139 54855
djb2_mod 11041 54831
sdbm 11459 36849
yet_another_lc 14258 57350
murmur2 16300 39024
murmur3 16572 39221
simple_xorshift 14930 38509
double_xorshift 16192 38762
right_shift_2 8843 33325
right_shift_3 8791 32979
right_shift_4 8818 32510
right_shift_5 8775 30436
right_shift_8 10505 35960
right_shift_12 30481 91350
MyTemplatePointerHash1 8800 33287
BasileStarynkevitch 12885 37829
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 12183 33424
reinterpret_cast 12125 34000
djb2 22693 51255
djb2_mod 22722 51266
sdbm 15160 37221
yet_another_lc 24125 51850
murmur2 16273 39020
murmur3 16587 39270
simple_xorshift 16031 38628
double_xorshift 16233 38757
right_shift_2 11181 33896
right_shift_3 10785 33660
right_shift_4 10615 33204
right_shift_5 10357 38216
right_shift_8 15445 100348
right_shift_12 73773 1044919
MyTemplatePointerHash1 11091 33883
BasileStarynkevitch 15701 38092
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 415 8243
reinterpret_cast 422 8321
djb2 445 8730
djb2_mod 449 8696
sdbm 460 9439
yet_another_lc 455 9003
murmur2 475 9109
murmur3 482 9313
simple_xorshift 463 8694
double_xorshift 465 8900
right_shift_2 416 8402
right_shift_3 418 8405
right_shift_4 423 8366
right_shift_5 421 8347
right_shift_8 453 9195
right_shift_12 666 18008
MyTemplatePointerHash1 433 8191
BasileStarynkevitch 466 8443
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 450 8135
reinterpret_cast 457 8208
djb2 470 8736
djb2_mod 476 8698
sdbm 483 9420
yet_another_lc 476 8953
murmur2 481 9089
murmur3 486 9283
simple_xorshift 466 8663
double_xorshift 468 8865
right_shift_2 456 8301
right_shift_3 456 8302
right_shift_4 453 8337
right_shift_5 457 8340
right_shift_8 505 10379
right_shift_12 1099 34923
MyTemplatePointerHash1 464 8226
BasileStarynkevitch 466 8372
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 9548 35362
reinterpret_cast 9635 35869
djb2 10668 37339
djb2_mod 10763 37311
sdbm 11126 37145
yet_another_lc 11597 39944
murmur2 16296 39029
murmur3 16432 39280
simple_xorshift 16066 38645
double_xorshift 16108 38778
right_shift_2 8966 35953
right_shift_3 8916 35949
right_shift_4 8973 35504
right_shift_5 8941 34997
right_shift_8 9356 31233
right_shift_12 13831 45799
MyTemplatePointerHash1 8839 31798
BasileStarynkevitch 15349 38223
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 14756 36237
reinterpret_cast 14763 36918
djb2 15406 38771
djb2_mod 15551 38765
sdbm 14886 37078
yet_another_lc 15700 40290
murmur2 16309 39024
murmur3 16432 39381
simple_xorshift 16177 38625
double_xorshift 16073 38750
right_shift_2 14732 36961
right_shift_3 14170 36965
right_shift_4 13687 37295
right_shift_5 11978 35135
right_shift_8 11498 46930
right_shift_12 25845 268052
MyTemplatePointerHash1 10150 32046
BasileStarynkevitch 15981 38143
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 432 7957
reinterpret_cast 429 8036
djb2 462 8970
djb2_mod 453 8884
sdbm 460 9110
yet_another_lc 466 9015
murmur2 495 9147
murmur3 494 9300
simple_xorshift 479 8792
double_xorshift 477 8948
right_shift_2 430 8120
right_shift_3 429 8132
right_shift_4 432 8196
right_shift_5 437 8324
right_shift_8 425 8050
right_shift_12 519 11291
MyTemplatePointerHash1 425 8069
BasileStarynkevitch 468 8496
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 462 7956
reinterpret_cast 456 8046
djb2 490 9002
djb2_mod 483 8905
sdbm 482 9116
yet_another_lc 492 8982
murmur2 492 9120
murmur3 492 9276
simple_xorshift 477 8761
double_xorshift 477 8903
right_shift_2 458 8116
right_shift_3 459 8124
right_shift_4 462 8281
right_shift_5 463 8370
right_shift_8 458 8069
right_shift_12 662 16244
MyTemplatePointerHash1 459 8091
BasileStarynkevitch 472 8476
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 9756 34368
reinterpret_cast 9718 34897
djb2 10935 36894
djb2_mod 10820 36788
sdbm 11084 37857
yet_another_lc 11125 37996
murmur2 16522 39078
murmur3 16461 39314
simple_xorshift 15982 38722
double_xorshift 16151 38868
right_shift_2 9611 34997
right_shift_3 9571 35006
right_shift_4 9135 34750
right_shift_5 8978 32878
right_shift_8 8688 30276
right_shift_12 10591 35827
MyTemplatePointerHash1 8721 30265
BasileStarynkevitch 15524 38315
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 14169 36078
reinterpret_cast 14096 36637
djb2 15373 37492
djb2_mod 15279 37438
sdbm 15531 38247
yet_another_lc 15924 38779
murmur2 16524 39109
murmur3 16422 39280
simple_xorshift 16119 38735
double_xorshift 16136 38875
right_shift_2 14319 36692
right_shift_3 14311 36776
right_shift_4 13932 35682
right_shift_5 12736 34530
right_shift_8 9221 30663
right_shift_12 15506 98465
MyTemplatePointerHash1 9268 30697
BasileStarynkevitch 15952 38349
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 421 7863
reinterpret_cast 419 7953
djb2 457 8983
djb2_mod 455 8927
sdbm 445 8609
yet_another_lc 446 8892
murmur2 492 9090
murmur3 507 9294
simple_xorshift 467 8687
double_xorshift 472 8872
right_shift_2 432 8009
right_shift_3 432 8014
right_shift_4 435 7998
right_shift_5 442 8099
right_shift_8 432 7914
right_shift_12 462 8911
MyTemplatePointerHash1 426 7744
BasileStarynkevitch 467 8417
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 452 7948
reinterpret_cast 456 8018
djb2 489 9037
djb2_mod 490 8992
sdbm 477 8795
yet_another_lc 491 9179
murmur2 502 9078
murmur3 507 9273
simple_xorshift 473 8671
double_xorshift 480 8873
right_shift_2 470 8105
right_shift_3 470 8100
right_shift_4 476 8333
right_shift_5 468 8065
right_shift_8 469 8094
right_shift_12 524 10216
MyTemplatePointerHash1 451 7826
BasileStarynkevitch 472 8419
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 10910 38432
reinterpret_cast 10892 38994
djb2 10499 38985
djb2_mod 10507 38983
sdbm 11318 37450
yet_another_lc 11740 38260
murmur2 16960 39544
murmur3 16816 39647
simple_xorshift 16096 39021
double_xorshift 16419 39183
right_shift_2 10219 38909
right_shift_3 10012 39036
right_shift_4 10642 40284
right_shift_5 10116 38678
right_shift_8 9083 32914
right_shift_12 9376 31586
MyTemplatePointerHash1 8777 30129
BasileStarynkevitch 16036 38913
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 16304 38695
reinterpret_cast 16241 39641
djb2 16377 39533
djb2_mod 16428 39526
sdbm 15402 37811
yet_another_lc 16180 38730
murmur2 16679 39355
murmur3 16792 39586
simple_xorshift 16196 38965
double_xorshift 16371 39127
right_shift_2 16445 39263
right_shift_3 16598 39421
right_shift_4 16378 39839
right_shift_5 15517 38442
right_shift_8 11589 33547
right_shift_12 11992 49041
MyTemplatePointerHash1 9052 30222
BasileStarynkevitch 16163 38829
Результат, возвращаемый хэш-функцией, имеет тип size_t, но он преобразуется в "индекс ведра" контейнером, идентифицируя правильное ведро для поиска объекта.
Я думаю, что это преобразование не указано в стандарте: но я бы ожидал, что это обычно операция Modulo N, где N - количество ведер - и что N обычно имеет силу в два раза, так как удваивает количество ковша это хороший способ увеличить размер, когда слишком много хитов. Операция Modulo N будет означать, что - для указателей - наивная хэш-функция использует только часть ковшей.
Реальная проблема заключается в том, что "хороший" хэш-алгоритм для контейнеров должен основываться на знании размера ведра и значений, которые вы хешируете. Например, если объекты, которые вы хранили в таблице, имели размер 1024 байта, возможно, что младшие 10 бит каждого указателя могут быть одинаковыми.
struct MyOneKStruct x[100]; //bottom 10 bits of &x[n] are always the same
Таким образом, "лучший" хэш для любого приложения, вероятно, потребует большого количества проб и ошибок и измерений, а также знаний о распределении значений, которые вы хешируете.
Однако вместо того, чтобы просто сдвигать указатель вниз на N бит, я бы попробовал что-то вроде XORing верхнего слова в нижнем. Как @BasileStarynkevich ответ.
Предложение о добавлении хеш-таблиц делает интересное чтение. Мой акцент в пункте ниже: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
Невозможно написать полностью общую хеш-функцию, которая действительна для всех типов. (Вы не можете просто преобразовать объект в необработанную память и хэш-байты; среди прочего, эта идея терпит неудачу из-за padding.) Из-за этого, а также потому, что хорошая хеш-функция только хорошо в контексте конкретной модели использования, это важно чтобы пользователи могли предоставлять свои собственные хеш-функции.
Очевидно, что ответ зависит от системы и процессора (в частности, из-за размера страницы и размера слова). Я предлагаю
struct MyVoidPointerHash {
size_t operator()(const void* val) const {
uintptr_t ad = (uintptr_t) val;
return (size_t) ((13*ad) ^ (ad >> 15));
}
};
Понимание заключается в том, что во многих системах размер страницы часто составляет 4 Кбайта (т.е. 2 12), поэтому правый сдвиг >>15 помещает значимые части адреса в младшие биты. 13* в основном для удовольствия (но 13 является простым) и перетасовывать больше бит. Эксклюзивный или ^ - это биты смешения и очень быстрые. Таким образом, младшие биты хэша представляют собой смесь многих бит (как высоких, так и низких) указателя.
Я не утверждаю, что поставил много "науки" в такие хэш-функции. Но они часто работают очень хорошо. YMMV. Я бы предположил, что вам следует избегать деактивации ASLR!
Невозможно побить ваше решение на беговой дорожке производительности (ни для char, ни для 1024 struct), но в смысле правильности есть некоторые улучшения:
#include <iostream>
#include <new>
#include <algorithm>
#include <unordered_set>
#include <chrono>
#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <cmath>
namespace
{
template< std::size_t argument, std::size_t base = 2, bool = (argument < base) >
constexpr std::size_t log = 1 + log< argument / base, base >;
template< std::size_t argument, std::size_t base >
constexpr std::size_t log< argument, base, true > = 0;
}
struct pointer_hash
{
template< typename type >
constexpr
std::size_t
operator () (type * p) const noexcept
{
return static_cast< std::size_t >(reinterpret_cast< std::uintptr_t >(p) >> log< std::max(sizeof(type), alignof(type)) >);
}
};
template< typename type = std::max_align_t, std::size_t i = 0 >
struct alignas(alignof(type) << i) S
{
};
int
main()
{
constexpr std::size_t _16M = (1 << 24);
S<> * p = new S<>[_16M]{};
auto latch = std::chrono::high_resolution_clock::now();
{
std::unordered_set< S<> *, pointer_hash > s;
for (auto * pp = p; pp < p + _16M; ++pp) {
s.insert(pp);
}
}
std::cout << std::chrono::duration_cast< std::chrono::milliseconds >(std::chrono::high_resolution_clock::now() - latch).count() << "ms" << std::endl;
delete [] p;
return EXIT_SUCCESS;
}