Nous développons un logiciel critique hautement performant en C ++. Là, nous avons besoin d'une carte de hachage simultanée et d'une mise en œuvre. Nous avons donc écrit un benchmark pour déterminer à quel point notre carte de hachage simultanée est plus lente que cellestd::unordered_map .

Mais, std::unordered_mapsemble être incroyablement lent ... C'est donc notre micro-benchmark (pour la carte simultanée, nous avons engendré un nouveau thread pour nous assurer que le verrouillage ne soit pas optimisé et notez que je n'insère jamais 0 car je compare également avec google::dense_hash_map, qui a besoin d'une valeur nulle):

boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> 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<int, long double> 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<std::chrono::milliseconds>(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<std::chrono::milliseconds>(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:

inserts: 35126
get    : 2959

Pour google::dense_map :

inserts: 3653
get    : 816

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

inserts: 5213
get    : 2594

Si je compile 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 simultanée sauvegardée à la main:

inserts: 4441
get    : 1180

Je compile avec la commande suivante:

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

Alors surtout insère sur std::unordered_map semblent donc être extrêmement coûteuses - 35 secondes contre 3-5 secondes pour les autres cartes. De plus, le temps de recherche 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_mapest plus lent que sa propre implémentation. Là, la réponse la mieux notée indique que la std::tr1::unordered_mapnécessité d'implémenter une interface plus compliquée. Mais je ne vois pas cet argument: nous utilisons une approche bucket dans notre concurrent_map, std::unordered_maputilise également une approche bucket (google::dense_hash_map ne le fait pas, mais std::unordered_mapdevrait être au moins aussi rapide que notre version sécurisée par la concurrence?). A part ça, 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 cher (même si nous réservons suffisamment d'espace au début, cela ne fonctionne pas beaucoup mieux - donc le ressassement ne semble pas être le problème)?

ÉDITER:

Tout d'abord: oui, le benchmark présenté n'est pas parfait - c'est parce que nous avons beaucoup joué avec et c'est juste un hack (par exemple le uint64 distribution pour générer des ints ne serait en pratique pas une bonne idée, exclure 0 dans une boucle est un peu stupide etc ...).

Pour le moment, la plupart des commentaires expliquent que je peux rendre la carte unordered_map plus rapide en préallouant suffisamment d'espace pour elle. Dans notre application, ce n'est tout simplement pas possible: nous développons un système de gestion de base de données et avons besoin d'une carte de hachage pour stocker certaines données lors d'une transaction (par exemple, des informations de verrouillage). Ainsi, cette carte peut être de 1 (l'utilisateur ne fait qu'une insertion et s'engage) à des milliards d'entrées (si des analyses complètes de la table se produisent). Il est tout simplement impossible de préallouer suffisamment d'espace ici (et en allouer beaucoup au début consommera trop de mémoire).

De plus, je m'excuse de ne pas avoir formulé ma question assez clairement: je ne suis pas vraiment intéressé à rendre unordered_map rapide (l'utilisation d'une carte de hachage dense de googles fonctionne bien pour nous), je ne comprends tout simplement pas vraiment d'où viennent ces énormes différences de performances . Cela ne peut pas être juste 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 simultanée sauvegardée à la main commence avec un tableau de taille 64 - donc un plus petit que unordered_map).

Alors, quelle est la raison de cette mauvaise performance de std::unordered_map? Ou différemment demandé: pourrait-on écrire une implémentation dustd::unordered_map interface qui soit conforme au standard et (presque) aussi rapide que la carte de hachage dense de Google? Ou y a-t-il quelque chose dans la norme qui oblige le réalisateur à choisir une manière inefficace de l'implémenter?

MODIFIER 2:

En profilant, je vois que beaucoup de temps est utilisé pour les divions entiers. std::unordered_maputilise des nombres premiers pour la taille du tableau, tandis que les autres implémentations utilisent des puissances de deux. Pourquoi std::unordered_maputilise-t-on des nombres premiers? Pour mieux fonctionner si le hachage est mauvais? Pour les bons hachages, cela ne fait aucune différence.

MODIFIER 3:

Voici les chiffres pour std::map:

inserts: 16462
get    : 16978

Sooooooo: pourquoi les inserts dans un std::mapplus rapide que les inserts dans un std::unordered_map... je veux dire WAT? std::mapa une pire localité (arbre vs tableau), doit faire plus d'allocations (par insert vs par rehash + plus ~ 1 pour chaque collision) et, le plus important: a une autre complexité algorithmique (O (logn) vs O (1))!

J'ai trouvé la raison: c'est un problème de gcc-4.7 !!

Avec gcc-4.7

inserts: 37728
get    : 2985

Avec gcc-4.6

inserts: 2531
get    : 1565

Alors std::unordered_map dans gcc-4.7 est cassé (ou mon installation, qui est une installation de gcc-4.7.0 sur Ubuntu - et une autre installation qui est gcc 4.7.1 sur les tests Debian).

Je vais soumettre un rapport de bogue ... jusque-là: NE PAS utiliser std::unordered_mapavec gcc 4.7!

Je suppose que vous n'avez pas correctement dimensionné votre unordered_map, comme Ylisar l'a suggéré. Lorsque les chaînes deviennent trop longues unordered_map, l'implémentation de g ++ sera automatiquement modifiée en une table de hachage plus grande, ce qui réduirait considérablement les performances. Si je me souviens bien, la valeur par unordered_mapdéfaut est (plus petit premier plus grand que) 100.

Je n'avais pas chronosur mon système, alors j'ai chronométré avec times().

template <typename TEST>
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;
}

J'ai utilisé un SIZEde 10000000, et j'ai dû changer un peu les choses pour ma version de boost. Notez également que j'ai pré-dimensionné la table de hachage pour qu'elle corresponde SIZE/DEPTH, oùDEPTH est une estimation de la longueur de la chaîne de seaux due aux collisions de hachage.

Éditer: Howard me fait remarquer dans ses commentaires que le facteur de charge maximal pour unordered_mapest 1. Ainsi, le DEPTHcontrôle du nombre de fois que le code sera répété.

#define SIZE 10000000
#define DEPTH 3
std::vector<uint64_t> vec(SIZE);
boost::mt19937 rng;
boost::uniform_int<uint64_t> dist(std::numeric_limits<uint64_t>::min(),
                                  std::numeric_limits<uint64_t>::max());
std::unordered_map<int, long double> 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");
}

Éditer:

J'ai modifié le code pour pouvoir changer DEPTHplus facilement.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Ainsi, par défaut, la plus mauvaise taille pour la table de hachage est choisie.

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

Ma conclusion est qu'il n'y a pas beaucoup de différence de performances significative pour toute taille de table de hachage initiale autre que de la rendre égale au nombre total prévu d'insertions uniques. De plus, je ne vois pas l'ordre de grandeur de la différence de performance que vous observez.

J'ai exécuté votre code en utilisant un ordinateur 64 bits / AMD / 4 cœurs (2,1 GHz) et cela m'a donné les résultats suivants:

MinGW-W64 4.9.2:

Utilisation de std :: unordered_map:

inserts: 9280 
get: 3302

En utilisant std :: map:

inserts: 23946
get: 24824

VC 2015 avec tous les indicateurs d'optimisation que je connais:

Utilisation de std :: unordered_map:

inserts: 7289
get: 1908

En utilisant std :: map:

inserts: 19222 
get: 19711

Je n'ai pas testé le code en utilisant GCC mais je pense que cela peut être comparable aux performances de VC, donc si c'est vrai, alors GCC 4.9 std :: unordered_map est toujours cassé.

[ÉDITER]

Alors oui, comme quelqu'un l'a dit dans les commentaires, il n'y a aucune raison de penser que les performances de GCC 4.9.x seraient comparables aux performances de VC. Quand j'aurai le changement, je testerai le code sur GCC.

Ma réponse est simplement d'établir une sorte de base de connaissances pour d'autres réponses.