Quelle est la fonction de hachage la plus rapide pour les pointeurs?
Les conteneurs à base de table de hachage sont des tableaux associatifs très rapides (par exemple unordered_map, unordered_set).
Leur performance dépend fortement de cette fonction de hachage utilisée pour créer un index pour chaque entrée. Au fur et à mesure que les tables de hachage se développent, les éléments sont ressaisis encore et encore.
Les pointeurs sont de type simple, essentiellement une valeur de 4/8 octet qui identifie de manière unique un objet. Le problème est que l'utilisation d'une adresse à la suite de la fonction de hachage n'est pas efficace en raison de plusieurs LSB zéro.
Exemple:
struct MyVoidPointerHash {
size_t operator()(const void* val) const {
return (size_t)val;
}
};
Une implémentation plus rapide consiste à perdre quelques bits:
struct MyVoidPointerHash2 {
size_t operator()(const void* val) const {
return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
}
};
Ce dernier a produit une augmentation des performances de 10 à 20% sur une grande application qui utilise des jeux de hachage et des cartes avec des dizaines de milliers d'éléments qui sont fréquemment construits et effacés.
Quelqu'un peut-il offrir un meilleur schéma pour les pointeurs de hachage?
, La fonction doit être:
- vite! et doit bien inline.
- offrir une distribution raisonnable, rare les collisions sont autorisées.
Mise à jour-résultats de référence
J'ai couru deux ensembles de tests, un pour int* et pour un pointeur de classe qui a une taille de 4KB. Les résultats sont très intéressants.
J'ai utilisé std::unordered_set pour tous les tests avec une taille de données de 16 Mo qui a été allouée dans un seul appel new. Le premier algorithme s'est exécuté deux fois pour s'assurer que les caches sont aussi chauds que possible et que le processeur fonctionne à pleine vitesse.
Configuration: VS2013 (x64), i7-2600, Windows 8.1 x64.
- VS2013 fonction de hachage par défaut
- 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):
Code:
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;
}
};
Essai 1 - int*:
- VS2013 par défaut a pris 1292ms
- Hash1 a pris 742ms
- Hash2 a pris 343ms
- Hash3 a pris 1008ms
- Hash4 a pris 629ms
- hash5 a pris 350ms
Essai 1 - 4K_class*:
- VS2013 par défaut a pris 0.423 ms
- Hash1 a pris 23.889 ms
- Hash2 a pris 6.331 ms
- Hash3 a pris 0.366 ms
- Hash4 a pris 0.390 ms
- Hash5 a pris 0.290 ms
Update2:
Le gagnant jusqu'à présent est la fonction de hachage templated (hash5). Meilleur niveau de performances de vitesse pour différentes tailles de bloc.
Mise à Jour 3: Ajout du hachage par défaut la fonction de base. S'avère que c'est loin d'être optimale.
5 réponses
La bonne réponse d'un point de vue théorique est: "utilisez std::hash qui est probablement spécialisé pour être aussi bon qu'il obtient, et si cela n'est pas applicable, utilisez une bonne fonction de hachage plutôt qu'une fonction rapide. La vitesse de la fonction de hachage n'a pas tant d'importance que sa qualité".
La réponse pratique est: "Use std::hash, qui est pauvre en Pisse, mais qui fonctionne néanmoins étonnamment bien."
TL;DR
Après avoir pris intrigué, j'ai couru environ 30 heures de benchmarks au cours du week-end. Entre autres choses, j'ai essayé d'obtenir un cas moyen par rapport au pire des cas et j'ai essayé de forcer std::unordered_map dans le pire des cas en lui donnant délibérément de mauvais indices sur le nombre de compartiments en ce qui concerne la taille de l'ensemble inséré.
J'ai comparé des hachages médiocres (std::hash<T*>) à des hachages généraux bien connus de bonne qualité globale (djb2, sdbm) ainsi qu'à des variations de ceux-ci qui tiennent compte de la longueur d'entrée très courte, et à des hachages qui sont explicitement pensé pour être utilisé dans les hashtables (murmur2 et murmur3), et les hachages pauvres en Pisse qui sont en fait pires que ne pas hacher du tout car ils jettent l'entropie.
Puisque les 2-3 bits les plus bas sont toujours nuls sur les pointeurs en raison de l'alignement, j'ai jugé utile de tester un simple décalage à droite comme "hash", donc seules les informations non nulles seraient utilisées, au cas où la table de hachage n'utiliserait que les N bits les plus bas. S'est avéré que pour des modifications raisonnables (j'ai aussi essayé déraisonnable les quarts!) ce fait assez bien.
Résultats
Certaines de mes découvertes étaient bien connues et sans surprise, d'autres sont très surprenantes:
- Il est difficile de prédire ce qu'est un "bon" hachage. Écrire de bonnes fonctions de hachage est difficile. Pas surprenant, fait bien connu, et une fois de plus prouvé.
- Aucun hachage unique ne surpasse de manière significative tous les autres dans tous les scénarios. Aucun hachage unique ne surpasse même de manière significative tous les autres 80% du temps. Première résultat attendu, le second est néanmoins surprenant.
- Il est vraiment difficile d'appuyer sur
std::unordered_mappour se comporter mal. Même lorsqu'on donne délibérément de mauvaises indications au nombre de compartiments qui forceront plusieurs re-hachages, la performance globale n'est pas bien pire. Seules les fonctions de hachage les pires qui jettent la plupart de l'entropie d'une manière presque ridicule sont capables d'avoir un impact significatif sur les performances de plus de 10-20% (commeright_shift_12, ce qui n'entraîne pratiquement que 12 fonctions distinctes valeurs de hachage pour 50 000 entrées! Il n'est pas surprenant que la carte de hachage tourne environ 100 fois plus lentement dans ce cas - nous faisons essentiellement une recherche d'accès aléatoire sur une liste liée.). - certains résultats "drôles" sont sûrement dus aux détails de la mise en œuvre. Mon implémentation (GCC) utilise un nombre de seau premier légèrement supérieur à 2^N, et insère des valeurs avec des hachages indentiques head-first dans des listes liées.
- La spécialisation de
std::hash<T*>est carrément pathétique pour GCC (un simplereinterpret_cast). Curieusement, un foncteur qui fait la chose identique effectue systématiquement plus rapidement aux insertions et plus lentement à l'accès aléatoire . La différence est petite (une douzaine de millisecondes sur un test de 8-10 secondes), mais ce n'est pas du bruit, il est constamment présent-probablement lié à la réorganisation des instructions ou à la canalisation. Il est étonnant de voir comment le même code (qui est également un no-op) consistenly fonctionne différemment dans deux scénarios différents. - hachages pathétiques ne pas effectuer significativement pire que les" bons " hachages ou les hachages explicitement conçus pour les tables de hachage. En effet, la moitié du temps, ils sont les plus performants, ou parmi les 3 premiers.
- Les" meilleures " fonctions de hachage aboutissent rarement, voire jamais, aux meilleures performances globales.
- les hachages affichés comme réponses dans cette question SO sont généralement corrects. Ils sont bons moyens, mais pas supérieurs à
std::hash. Habituellement, ils atterriront dans le top 3-4. - les hachages pauvres sont quelque peu vulnérables à l'ordre de insertion (moins performante sur l'insertion aléatoire et la recherche aléatoire après l'insertion aléatoire) alors que les" bons " hachages sont plus résistants à l'impact de l'ordre d'insertion (peu ou pas de différence), mais les performances globales sont encore légèrement plus lentes.
Configuration D'Essai
Les tests n'ont pas été effectués uniquement sur des valeurs alignées de 4 ou 8 octets (ou autre), mais sur des adresses réelles obtenues en allouant l'ensemble complet des éléments sur le tas et en stockant les adresses comme suit fournis par l'allocateur dans un std::vector (les objets ont ensuite été supprimés, ils ne sont pas nécessaires).
Les adresses ont été insérées dans un std::unordered_map nouvellement alloué pour chaque test dans l'ordre stocké dans le vecteur, Une fois dans l'ordre d'origine ("séquentiel") et une fois après l'application d'un std::random_shuffle sur le vecteur.
Des Tests ont été effectués pour des ensembles de 50 000 et 1 000 000 objets de taille 4, 16, 64, 256 et 1024 (les résultats pour 64 omis ici pour des raisons de concision, ils sont comme vous pouvez vous y attendre quelque part entre 16 et 256 -- StackOverflow ne permet que 30k caractères affichés).
La suite de tests a été réalisée 3 fois, les résultats variant de 3 ou 4 millisecondes ici et là, mais globalement identiques. Les résultats affichés ici sont la dernière course.
L'ordre des insertions dans le test "aléatoire" ainsi que le modèle d'accès (dans chaque test) est pseudo-aléatoire, mais exactement identique pour chaque fonction de hachage dans un test.
Les timings sous les benchmarks de hachage sont pour résumer 4 000 000 000 de hachage valeurs dans une variable entière.
La colonne {[13] } est le temps en millisecondes pour 50 itérations de création d'un std::unordered_map, d'insertion de 50 000 et 1 000 000 d'éléments respectivement, et de destruction de la carte.
La colonne {[15] } est le temps en millisecondes pour effectuer 100 000 000 recherches d'un élément pseudorandom dans le' vecteur ' suivi de la recherche de cette adresse dans le unordered_map.
Ce calendrier comprend en moyenne un cache misse pour accéder à un élément aléatoire dans le vector, au moins pour le grand jeu de données (le petit jeu de données s'intègre complètement dans L2).
Tous les timings sur un 2.66 GHz Intel Core2, Windows 7, gcc 4.8.1 / MinGW-w64_32. Granularité de la minuterie @ 1ms.
Code Source
Le code Source est disponible sur Ideone , encore une fois en raison de la limite de 30k caractères de Stackoverflow.
Remarque: L'exécution de la suite de tests complète prend bien plus de 2 heures sur un PC de bureau, alors soyez prêt à faire une promenade si vous voulez reproduire le résultat.
Résultats Des Tests
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
Après avoir laissé cette question poser pendant un moment, je posterai ma meilleure fonction de hachage pour les pointeurs jusqu'à présent:
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;
}
};
Il est très performant pour différentes tailles de blocs.
Si quelqu'un a une meilleure fonction, je vais changer la réponse acceptée.
Le résultat retourné par la fonction de hachage a le type size_t, mais il est converti en un' index de compartiment ' par le conteneur, identifiant le compartiment correct pour localiser l'objet.
Je pense que cette conversion n'est pas spécifiée dans la norme : mais je m'attends à ce qu'il s'agisse généralement D'une opération Modulo N, où N est le nombre de compartiments - et que N est généralement une puissance de deux, car doubler le nombre de compartiments est un bon moyen d'augmenter la taille quand il y a trop Le Modulo N de l'opération cela signifierait que-pour les pointeurs - la fonction de hachage naïve n'utilise qu'une fraction des compartiments.
Le vrai problème est qu'un ' bon ' algorithme de hachage pour les conteneurs doit être basé sur une connaissance de la taille du compartiment et des valeurs que vous Hachez. Par exemple, si les objets que vous stockiez dans la table étaient tous de taille 1024 octets, il est possible que les 10 bits de faible ordre de chaque pointeur soient les mêmes.
struct MyOneKStruct x[100]; //bottom 10 bits of &x[n] are always the same
Donc, un hachage "meilleur" pour n'importe quelle application est susceptible de nécessiter beaucoup d'essais et d'erreurs de mesure, et la connaissance de la distribution des valeurs que vous êtes de hachage.
Cependant, plutôt que de simplement déplacer le pointeur vers le bas N bits, j'essaierais quelque chose comme XORing le " mot " supérieur dans le bas. Tout comme la réponse de @ BasileStarynkevich.
La proposition d'ajouter des tables de hachage rend la lecture intéressante. Mon accent dans le paragraphe ci-dessous: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
Il est impossible d'écrire entièrement générales fonction de hachage valide pour tous les types. (Vous ne pouvez pas simplement convertir un objet en mémoire brute et hachez les octets; entre autres raisons, cette idée échoue à cause de padding.) À cause de cela, et aussi parce que une bonne fonction de hachage est seulement bon dans le contexte d'un modèle d'utilisation spécifique, c'est essentiel pour permettre aux utilisateurs de fournir leurs propres fonctions de hachage.
Évidemment, la réponse dépend du système et du processeur (en particulier, en raison de la taille de la page et de la taille du mot). Je propose
struct MyVoidPointerHash {
size_t operator()(const void* val) const {
uintptr_t ad = (uintptr_t) val;
return (size_t) ((13*ad) ^ (ad >> 15));
}
};
L'idée est que sur de nombreux systèmes, la taille de la page est souvent 4Kbytes (c'est-à-dire 212) ainsi, le décalage droit >>15 mettra des parties d'adresse significatives dans les bits inférieurs. Le 13* est surtout pour le plaisir (mais 13 est premier) et pour mélanger plus de bits. L'exclusif or ^ mélange des bits et est vraiment rapide. Donc, les bits inférieurs du hachage est un mélange de plusieurs bits (haut et bas) du pointeur.
je ne prétends pas avoir mis beaucoup de "science" dans ces fonctions de hachage. Mais ils fonctionnent souvent très bien. YMMV. Je suppose que vous devriez éviter de désactiver ASLR !
Ne peut pas battre votre solution sur le circuit de performance (ni pour char, ni pour la taille 1024 struct), mais dans le sens de l'exactitude, il y a quelques améliorations:
#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;
}