Carte de hachage C/C++ super haute performance (table, dictionnaire)

Question

J'ai besoin de mapper des clés primitives (int, peut-être longues) à des valeurs de structure dans une structure de données de hachage haute performance.

Mon programme aura quelques centaines de ces cartes, et chaque carte aura généralement au plus quelques milliers d'entrées. Cependant, les cartes seront «rafraîchissantes» ou «bouillonnantes» en permanence; Imaginez le traitement de millions de messageset delete par seconde.

Quelles bibliothèques en C ou C++ ont une structure de données qui correspond à ce cas d'utilisation? Ou, comment recommanderiez-vous de construire le vôtre? Merci!

Answer 1

Je vous recommande d'essayer Google SparseHash (ou la version C11 Google SparseHash-c11) et de voir si cela répond à vos besoins. Ils ont une implémentation de mémoire efficace ainsi qu'un optimisé pour la vitesse. J'ai fait un benchmark il y a longtemps, c'était la meilleure implémentation de hashtable disponible en termes de vitesse (mais avec des inconvénients).

Answer 2

Quelles bibliothèques dans C ou C++ ont une structure de données qui correspond à ce cas d'utilisation? Ou, comment recommanderiez-vous de construire le vôtre? Merci!

Consultez la LGPL 0d Judy arrays. Je ne me suis jamais utilisé, mais il m'a été annoncé à plusieurs reprises.

Vous pouvez également essayer de référencer des conteneurs STL (std :: hash_map, etc.). En fonction de la plate-forme/de l'implémentation et du réglage du code source (préallouer autant que possible la gestion dynamique de la mémoire est onéreuse), ils peuvent être suffisamment performants. En outre, si les performances de la solution finale l'emportent sur le coût de la solution, vous pouvez essayer de commander le système avec suffisamment de RAM pour tout mettre en réseau. La performance de l'accès par indice est imbattable.

Les opérations d'ajout/suppression sont beaucoup plus fréquentes (100x) que l'opération get.

Cela laisse entendre que vous pourriez vous concentrer sur l'amélioration des algorithmes en premier. Si les données sont seulement écrites, pas lues, alors pourquoi les écrire?

Answer 3

Utilisez simplement boost::unordered_map (ou tr1 etc.) par défaut. Ensuite, profilez votre code et voyez si ce code est le goulot d'étranglement. Alors seulement je suggérerais d'analyser précisément vos besoins pour trouver un substitut plus rapide.

Answer 4

Vérifiez d'abord si des solutions existantes comme libmemcache répondent à vos besoins.

Sinon ...

cartes Hash semble être la réponse définitive à votre exigence. Il fournit une recherche o (1) basée sur les clés. La plupart des bibliothèques STL fournissent une sorte de hachage ces jours-ci. Utilisez donc celui fourni par votre plate-forme. Une fois cette partie terminée, vous devez tester la solution pour voir si l'algorithme de hachage par défaut est suffisamment performant pour vos besoins.

Dans le cas contraire, vous devriez explorer quelques bons algorithmes de hachage rapide trouvées sur le net

1. bon vieux nombre premier se multiplient algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

Si ce n'est pas suffisant, vous pouvez lancer un module de hachage e par vous-même, cela résout le problème que vous avez vu avec les conteneurs STL que vous avez testés, et l'un des algorithmes de hachage ci-dessus. Assurez-vous de poster les résultats quelque part. Oh et c'est intéressant que vous ayez plusieurs cartes ... peut-être vous pouvez simplifier en ayant votre clé en 64 bits avec les bits élevés utilisés pour distinguer à quelle carte il appartient et ajouter toutes les paires de valeur de clé à un géant hacher. J'ai vu des hachages qui ont une centaine de milliers de symboles qui fonctionnent parfaitement bien sur l'algorithme de hachage des nombres premiers de base.

Vous pouvez vérifier cette solution effectue par rapport à des centaines de cartes .. Je pense que cela pourrait être mieux d'un point de vue de profilage de la mémoire ... s'il vous plaît ne postez les résultats quelque part si vous obtenez de faire cet exercice

Je crois que plus que l'algorithme de hachage, il pourrait être l'ajout/suppression de la mémoire constante (peut-il être évité?) et le profil d'utilisation du cache de cpu qui pourrait être plus cruciale pour la performance de votre application

bonne chance

Answer 5

Essayez les tables de hachage de Miscellaneous Container Templates. Son closed_hash_map est à peu près à la même vitesse que Google dense_hash_map, mais est plus facile à utiliser (aucune restriction sur les valeurs contenues) et a également d'autres avantages.

Answer 6

de sources Android (ainsi Apache 2 sous licence)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

regard sur hashmap.c, choisissez Include/cutils/hashmap.h, si vous n'avez pas besoin de sécurité de fil que vous pouvez supprimer le code mutex , un exemple d'implémentation se trouve dans libcutils/str_parms.c

Answer 7

Si vous avez un programme multithread, vous pouvez trouver des tables de hachage utiles dans intel thread building blocks library. Par exemple, tbb :: concurrent_unordered_map a la même API que std :: unordered_map, mais ses fonctions principales sont thread safe.

Également jeter un oeil à folly library de facebook, il a hash table de haute performance concurrente et skip list.

Answer 8

http://incise.org/hash-table-benchmarks.html gcc a une très bonne implémentation. Cependant, l'esprit qu'il doit respecter une décision norme très mauvaise:

Si une nouvelle mouture arrive, tous les itérateurs sont invalidés, mais les références et des pointeurs vers des éléments individuels restent valables. Si aucun rehash réel se produit, aucun changement.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Cela signifie essentiellement la norme dit que la mise en œuvre doit être fondée sur des listes chaînées. Il empêche l'adressage ouvert qui a de meilleures performances.

Je pense que google sparse utilise l'adressage ouvert, bien que dans ces cas-là, seule la version dense surpasse la concurrence. Cependant, la version clairsemée surpasse toute concurrence dans l'utilisation de la mémoire. (aussi il n'a aucun plateau, ligne droite pure par rapport au nombre d'éléments)

Answer 9

Je suggérerais uthash. Ajoutez simplement #include "uthash.h" puis ajoutez un UT_hash_handle à la structure et choisissez un ou plusieurs champs dans votre structure pour agir en tant que clé. Un mot sur la performance here.

Answer 10

khash est très efficace. Il y a le benchmark détaillé de l'auteur: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ et il montre aussi le khash bat beaucoup d'autres bibliothèques de hash.