Est-ce que gcc std::unordered_map implémentation lente ? Dans l’affirmative - pourquoi ?

Question

Nous développons une très critique pour les performances du logiciel en C++. Là, nous avons besoin d'un simultanées de hachage de la carte et mis en œuvre. Nous avons donc réalisé un test de comprendre comment beaucoup plus lent nos simultanées de hachage carte est comparé avec d' std::unordered_map.

Mais, std::unordered_map semble être incroyablement lent... Donc, c'est notre micro-indice de référence (pour la concurrente de la carte nous avons donné naissance à un nouveau thread pour s'assurer que le verrouillage n'obtient pas optimisé loin et notez que je n'ai jamais inser 0 parce que j'ai aussi de se comparer avec d' 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 en entier peut être trouvé ici: http://pastebin.com/vPqf7eya)

Le résultat pour l' std::unordered_map est:

inserts: 35126
get    : 2959

Pour google::dense_map:

inserts: 3653
get    : 816

Pour notre part soutenu simultanée de la carte (qui fait la fermeture, bien que l'indice de référence est mono-thread - mais dans un autre spawn fil):

inserts: 5213
get    : 2594

Si je compile le programme de test sans le support de pthread et tout faire dans le thread principal, j'obtiens les résultats suivants pour notre part soutenu simultanée de la carte:

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

Donc, en particulier inserts std::unordered_map semblent être extrêmement coûteux - 35 secondes vs 3 à 5 secondes pour les autres cartes. Aussi la recherche du temps 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 son propre mise en œuvre. Il y a la plus haute cote de réponse états, que l' std::tr1::unordered_map des besoins pour mettre en œuvre une plus compliqué de l'interface. Mais je ne peux pas voir cet argument: nous utilisons un seau dans notre concurrent_map, std::unordered_map utilise un seau-l'approche de trop (google::dense_hash_map n'est pas, mais qu' std::unordered_map doit être au moins aussi rapide que celle de notre part soutenu de l'accès concurrentiel version?). En dehors de cela je ne peux pas voir quoi que ce soit dans l'interface que la force d'une fonction qui fait la valeur de hachage de la carte de mal fonctionner...

Donc ma question: est-il vrai qu' std::unordered_map semble être très lent? Si non: quel est le problème? Si oui: quelle est la raison de cela.

Et ma question principale: pourquoi est-insertion d'une valeur dans un std::unordered_map si terrible cher (même si nous nous réservons un espace suffisant au début, il n'est pas beaucoup mieux donc ressasser ne semble pas être le problème)?

EDIT:

Tout d'abord: oui, la référence n'est pas parfaite - c'est parce que nous avons joué beaucoup avec elle et c'est juste un hack (par exemple l' uint64 de la distribution de générer des ints serait, en pratique, être pas une bonne idée, d'en exclure les 0 dans une boucle est une sorte de stupide, etc...).

Au moment où la plupart des commentaires expliquer, que je peux faire de la unordered_map plus rapide par preallocating assez d'espace pour lui. Dans notre application, c'est juste pas possible: nous sommes le développement d'un système de gestion de base et ont besoin d'une carte de hachage pour stocker des données au cours d'une transaction (par exemple le verrouillage de l'information). Si cette carte peut être tout à partir de 1 (l'utilisateur fait juste un insert et s'engage) à des milliards d'entrées (si des analyses de tables complètes). Il est tout simplement impossible de préallouer assez d'espace ici (et seulement allouer beaucoup dans le début, vont consommer trop de mémoire).

En outre, je m'en excuse, que je n'ai pas d'état, ma question assez clair: je ne suis pas vraiment intéressé à faire de unordered_map rapide (à l'aide de google dense de hachage carte fonctionne très bien pour nous), je ne sais vraiment pas d'où cette énorme performance différences viennent. Il ne peut pas être juste preallocation (même avec assez de préaffectés mémoire, la densité de la carte est d'un ordre de grandeur plus rapide que unordered_map, notre main adossés à des concurrentes de la carte commence par un tableau de taille 64 - donc un plus petit que unordered_map).

Quelle est donc la raison de cette mauvaise performance de l' std::unordered_map? Ou différemment demandé: Peut-on écrire une implémentation de l' std::unordered_map interface qui est un standard conforme et (presque) aussi vite que googles dense de hachage de la carte? Ou est-il quelque chose dans la norme qui impose à l'opérateur de choisir un moyen inefficace pour la mettre en œuvre?

EDIT 2:

Par profilage je vois que beaucoup de temps est utilisé pour entier divions. std::unordered_map utilise des nombres premiers pour la taille de la matrice, tandis que les autres implémentations de l'utilisation des puissances de deux. Pourquoi est - std::unordered_map utiliser le premier nombre? Pour effectuer mieux si le hachage est mauvais? Pour une bonne hache à mon humble avis ne pas faire de différence.

EDIT 3:

Ce sont les chiffres de l' std::map:

inserts: 16462
get    : 16978

Sooooooo: pourquoi s'insère dans un std::map plus rapide que les inserts en std::unordered_map... je veux dire, WAT? std::map a un pire localité (arbre vs array), doit faire plus d'allocations (par insérer vs par resucée + ~1 pour chaque collision) et, le plus important: a une autre complexité algorithmique (O(logn) vs O(1))!

Answer 1

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

Avec gcc-4.7

Avec gcc-4.6

Si `` 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 sous debian testing).

Je présenterai un rapport de bogue... d’ici là : ne pas utiliser `` avec gcc 4.7 !

Answer 2

Je devine que vous n'avez pas correctement de la taille de votre unordered_map, comme Ylisar suggéré. Lorsque les chaînes de grandir trop longtemps, en unordered_map, le g++ mise en œuvre sera automatiquement resucée d'une grande table de hachage, et ce serait une grosse glisser sur la performance. Si je me souviens bien, unordered_map par défaut (plus petit premier plus grand que) 100.

Je n'ai pas eu chrono sur mon système, j'ai donc chronométré avec l' 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 SIZE de 10000000, et a dû changer un peu les choses pour ma version de boost. A noter également, je l'ai pré-taille de la table de hachage pour correspondre SIZE/DEPTHoù DEPTH est une estimation de la longueur de la benne de la chaîne en raison de collisions de hachage.

Edit: Howard me signale dans les commentaires que le max du facteur de charge unordered_map est 1. Ainsi, l' DEPTH contrôle le nombre de fois où le code sera réchauffé.

#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");
}

Edit:

J'ai modifié le code pour que je puisse changer de DEPTH plus facilement.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Donc, par défaut, le pire de la taille de la table de hachage est choisi.

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 le premier de la table de hachage de taille autre que de le rendre égal à la totalité du nombre prévu de unique insertions. Aussi, je ne vois pas l'ordre de grandeur de différence de performances que vous êtes en train d'observer.