Super haute performance C/C++ hash map (tableau, dictionnaire) [fermé]

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

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!

découvrez la LGPL d Judy tableaux . Jamais utilisé moi-même, mais a été annoncée pour moi à quelques reprises.

vous pouvez également essayer de référencer les conteneurs STL (std::hash_map, etc). En fonction de la plate-forme / implémentation et de la mise au point du code source (pré-allouer autant comme vous pouvez gestion de la mémoire dynamique est coûteux) ils pourraient être assez performant.

aussi, si la performance de la solution finale l'emporte sur le coût de la solution, vous pouvez essayer de commander le système avec suffisamment de RAM pour tout mettre dans des tableaux simples. La Performance de l'accès par index est imbattable.

les opérations add/delete sont beaucoup plus fréquentes (100x) que l'opération get.

qui suggère vous devriez vous concentrer sur l'amélioration des algorithmes. Si les données sont écrites, pas lues, alors pourquoi les écrire?

il suffit d'utiliser boost::unordered_map (ou tr1 etc) par défaut. Alors profile ton code et vois si ce code est le goulot d'étranglement. Ce n'est qu'alors que je suggérerais d'analyser précisément vos besoins pour trouver un substitut plus rapide.

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

aussi jeter un oeil à facebook bibliothèque de la folie , il a haute performance concurrent table de hachage et skip list .

à partir d'android sources (donc sous licence Apache 2)

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

regardez hashmap.c, choisir d'inclure ou d'cutils/table de hachage.h, si vous n'avez pas besoin de la sécurité du thread, vous pouvez supprimer le code mutex, un exemple d'implémentation se trouve dans libcutils/str_parms.c

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 également khash bat de nombreuses autres bibliothèques de hachage.

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

si non ...

cartes hachurées semble être la réponse définitive à votre exigence. Il fournit o(1) recherche basée sur les touches. La plupart des bibliothèques STL fournissent une sorte de hachage de nos jours. Utilisez donc celle fournie par votre plateforme.

une fois cette partie terminée, vous devez tester la solution pour voir si l'algorithme de hachage par défaut est assez bon performance sage pour vos besoins.

si ce n'est pas le cas, vous devriez explorer quelques bons algorithmes de hachage rapide trouvés sur le net

1. bon vieux premier numéro de multiplier 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 vous-même un module de hachage, qui corrige 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 Pouvez-vous simplifier en ayant votre clé comme un 64 bits num avec les bits élevés utilisés pour distinguer la carte à laquelle il appartient et ajouter toutes les valeurs clés correspondent à un hachage géant. J'ai vu des hachures qui ont des centaines de milliers de symboles fonctionner parfaitement bien sur l'algorithme de base de hachage de nombres premiers assez bien.

vous pouvez vérifier comment cette solution fonctionne par rapport à des centaines de cartes .. je pense que ça pourrait être mieux du point de vue du 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 la constante ajouter/supprimer de la mémoire (peut-il être évité?) et le profil d'utilisation du cache cpu qui pourrait être plus crucial pour les performances de votre application""

bonne chance

Essayez de tables de hachage à partir de Divers Conteneur des Modèles . Son closed_hash_map est à peu près à la même vitesse que le dense_hash_map de Google , mais est plus facile à utiliser (aucune restriction sur les valeurs contenues) et a d'autres avantages aussi.

je suggérerais uthash . Il suffit d'inclure #include "uthash.h" puis d'ajouter un UT_hash_handle à la structure et de choisir un ou plusieurs champs dans votre structure pour agir comme la clé. Un mot sur la performance ici .

http://incise.org/hash-table-benchmarks.html gcc a une très très bonne mise en œuvre. Toutefois, l'esprit qu'il doit respecter une très mauvaise décision standard:

si une reprise se produit, tous les itérateurs sont invalidés, mais les références et des pointeurs vers des éléments individuels restent valables. Si pas de ressasser qui se passe, pas de changements.

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

cela signifie essentiellement la norme dit que la mise en œuvre doit être basée sur des listes lié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 benchmarks seule la version dense surpasse la concurrence. Cependant, la version sparse surpasse toute concurrence dans l'utilisation de la mémoire. elle aussi n'ont pas de plateau, de la pure ligne droite wrt nombre d'éléments)