Nous développons un logiciel très performant en C ++. Il nous faut une carte de hachage simultanée et une carte implémentée. Donc, nous avons écrit un test pour déterminer combien de temps notre carte de hachage simultanée est comparée avec std::unordered_map .

Mais std::unordered_map semble être incroyablement lent … Voici donc notre micro-test (pour la carte concurrente, nous avons créé un nouveau thread pour s’assurer que le locking n’est pas optimisé et que je n’insère jamais 0 car également référence avec google::dense_hash_map , qui nécessite une valeur nulle):

 boost::random::mt19937 rng; boost::random::uniform_int_dissortingbution dist(std::numeric_limits::min(), std::numeric_limits::max()); std::vector vec(SIZE); for (int i = 0; i < SIZE; ++i) { uint64_t val = 0; while (val == 0) { val = dist(rng); } vec[i] = val; } std::unordered_map map; auto begin = std::chrono::high_resolution_clock::now(); for (int i = 0; i < SIZE; ++i) { map[vec[i]] = 0.0; } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast(end - begin); std::cout << "inserts: " << elapsed.count() << std::endl; std::random_shuffle(vec.begin(), vec.end()); begin = std::chrono::high_resolution_clock::now(); long double val; for (int i = 0; i < SIZE; ++i) { val = map[vec[i]]; } end = std::chrono::high_resolution_clock::now(); elapsed = std::chrono::duration_cast(end - begin); std::cout << "get: " << elapsed.count() << std::endl; 

(EDIT: le code source complet peut être trouvé ici: http://pastebin.com/vPqf7eya )

Le résultat pour std::unordered_map est:

• Pourquoi le casting devrait-il être évité?
• Ce code de la section 36.3.6 de la quasortingème édition de «The C ++ Programming Language» a-t-il un comportement bien défini?
• Comment un programme avec une variable globale appelé main au lieu d’une fonction principale peut-il fonctionner?
• Nettoyer le code à printf size_t en C ++ (ou: équivalent le plus proche de% z de C99 en C ++)
• Pourquoi printf est-il obsolète avec un seul argument (sans les spécificateurs de conversion)?

 inserts: 35126 get : 2959 

Pour google::dense_map :

 inserts: 3653 get : 816 

Pour notre carte concurrente sauvegardée à la main (qui effectue le locking, bien que le benchmark soit mono-thread – mais dans un thread de spawn séparé):

 inserts: 5213 get : 2594 

Si je comstack le programme de référence sans le support de pthread et que je lance tout dans le thread principal, j’obtiens les résultats suivants pour notre carte concurrente:

 inserts: 4441 get : 1180 

Je comstack avec la commande suivante:

 g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc 

Donc, en particulier, les insertions sur std::unordered_map semblent être extrêmement coûteuses – 35 secondes contre 3-5 secondes pour les autres cartes. De plus, le temps de consultation semble être assez élevé.

Ma question: pourquoi est-ce? J’ai lu une autre question sur stackoverflow où quelqu’un demande, pourquoi std::tr1::unordered_map est plus lent que sa propre implémentation. La réponse la plus élevée indique que le std::tr1::unordered_map doit implémenter une interface plus compliquée. Mais je ne peux pas voir cet argument: nous utilisons une approche par google::dense_hash_map dans notre concurrent_map, std::unordered_map utilise également une approche par google::dense_hash_map ( google::dense_hash_map ne le fait pas, mais que std::unordered_map devrait être au moins aussi rapide que notre main) version protégée contre la concurrence?). En dehors de cela, je ne vois rien dans l’interface qui force une fonctionnalité qui fait que la carte de hachage fonctionne mal …

Donc ma question: est-il vrai que std::unordered_map semble être très lent? Si non: qu’est-ce qui ne va pas? Si oui: quelle en est la raison?

Et ma question principale: pourquoi insérer une valeur dans un std::unordered_map si terrible (même si nous réservons suffisamment d’espace au début, cela ne donne pas de meilleurs résultats – alors le rehashing semble ne pas être le problème)?

MODIFIER:

Tout d’abord: oui, le benchmark présenté n’est pas sans défaut – c’est parce que nous avons beaucoup joué avec et que c’est juste un hack (par exemple la dissortingbution uint64 pour générer des ints ne serait pas une bonne idée, exclure 0 dans un la boucle est un peu stupide, etc …).

Pour le moment, la plupart des commentaires expliquent que je peux rendre unordered_map plus rapide en pré-allouant suffisamment d’espace pour cela. Dans notre application, cela n’est tout simplement pas possible: nous développons un système de gestion de firebase database et avons besoin d’une carte de hachage pour stocker certaines données lors d’une transaction (par exemple, des informations de locking). Donc, cette carte peut être tout de 1 (l’utilisateur ne fait qu’un seul insert et valide) à des milliards d’entrées (si des parsings de table complètes ont lieu). Il est tout simplement impossible de pré-allouer suffisamment d’espace ici (et il suffit d’allouer beaucoup au début pour consumr trop de mémoire).

De plus, je m’excuse, que je n’ai pas énoncé ma question assez clairement: je ne suis pas vraiment intéressé à rendre unordered_map rapide (utiliser des cartes de hachage denses googles fonctionne bien pour nous), je ne comprends pas vraiment d’où proviennent ces énormes différences . Il ne peut pas s’agir simplement d’une préallocation (même avec suffisamment de mémoire pré-allouée, la carte dense est un ordre de grandeur plus rapide que unordered_map, notre carte concurrente à la main commence par un tableau de taille 64 – donc plus petit que unordered_map).

Alors, quelle est la raison de cette mauvaise performance de std::unordered_map ? Ou différemment: Peut-on écrire une implémentation de l’interface std::unordered_map qui est conforme à la norme et (presque) aussi rapide que la carte de hachage dense googles? Ou existe-t-il quelque chose dans la norme qui oblige le responsable de la mise en œuvre à choisir un moyen inefficace pour le mettre en œuvre?

EDIT 2:

En profilant, je constate que beaucoup de temps est utilisé pour les divions entières. std::unordered_map utilise des nombres premiers pour la taille du tableau, tandis que les autres implémentations utilisent des puissances de deux. Pourquoi std::unordered_map utilise-t-il des nombres premiers? Pour mieux performer si le hash est mauvais? Pour de bons hachages, cela ne fait aucune différence.

EDIT 3:

Ce sont les nombres pour std::map :

 inserts: 16462 get : 16978 

Sooooooo: pourquoi les insertions dans un std::map plus rapides que les insertions dans un std::unordered_map … je veux dire WAT? std::map a une plus mauvaise localité (tree vs array), doit faire plus d’allocations (par insert vs par rehash + plus ~ 1 pour chaque collision) et, plus important: a une autre complexité algorithmique (O (logn) vs O ( 1))!

• jeter new std :: exception vs throw std :: exception
• Colorer différentes parties d’une chaîne RichTextBox
• Comment puis-je faire une application WinForms go Full Screen
• Quel est le moyen le plus simple d’obtenir du XML en retrait avec des sauts de ligne à partir de XmlDocument?
• Pourquoi utiliser des assemblys nommés forts?

 inserts: 37728 get : 2985 

 inserts: 2531 get : 1565 

 template  void time_test (TEST t, const char *m) { struct tms start; struct tms finish; long ticks_per_second; times(&start); t(); times(&finish); ticks_per_second = sysconf(_SC_CLK_TCK); std::cout << "elapsed: " << ((finish.tms_utime - start.tms_utime + finish.tms_stime - start.tms_stime) / (1.0 * ticks_per_second)) << " " << m << std::endl; } 

 #define SIZE 10000000 #define DEPTH 3 std::vector vec(SIZE); boost::mt19937 rng; boost::uniform_int dist(std::numeric_limits::min(), std::numeric_limits::max()); std::unordered_map map(SIZE/DEPTH); void test_insert () { for (int i = 0; i < SIZE; ++i) { map[vec[i]] = 0.0; } } void test_get () { long double val; for (int i = 0; i < SIZE; ++i) { val = map[vec[i]]; } } int main () { for (int i = 0; i < SIZE; ++i) { uint64_t val = 0; while (val == 0) { val = dist(rng); } vec[i] = val; } time_test(test_insert, "inserts"); std::random_shuffle(vec.begin(), vec.end()); time_test(test_insert, "get"); } 

 #ifndef DEPTH #define DEPTH 10000000 #endif 

 elapsed: 7.12 inserts, elapsed: 2.32 get, -DDEPTH=10000000 elapsed: 6.99 inserts, elapsed: 2.58 get, -DDEPTH=1000000 elapsed: 8.94 inserts, elapsed: 2.18 get, -DDEPTH=100000 elapsed: 5.23 inserts, elapsed: 2.41 get, -DDEPTH=10000 elapsed: 5.35 inserts, elapsed: 2.55 get, -DDEPTH=1000 elapsed: 6.29 inserts, elapsed: 2.05 get, -DDEPTH=100 elapsed: 6.76 inserts, elapsed: 2.03 get, -DDEPTH=10 elapsed: 2.86 inserts, elapsed: 2.29 get, -DDEPTH=1 

 inserts: 9280 get: 3302 

 inserts: 23946 get: 24824 

 inserts: 7289 get: 1908 

 inserts: 19222 get: 19711