boost :: flat_map et ses performances par rapport à map et unordered_map

Il est de notoriété publique dans la programmation que la localisation de la mémoire améliore considérablement les performances en raison des accès au cache. J'ai récemment découvert boost::flat_mapquelle est une implémentation vectorielle d'une carte. Il ne semble pas être aussi populaire que le vôtre map/ unordered_mapje n'ai donc pas pu trouver de comparaisons de performances. Comment se compare-t-il et quels sont les meilleurs cas d'utilisation?

Merci!

J'ai réalisé très récemment un benchmark sur différentes structures de données dans mon entreprise, donc je sens que je dois laisser tomber un mot. Il est très compliqué de comparer correctement quelque chose.

Benchmarking

Sur le Web, nous trouvons rarement (voire jamais) une référence bien conçue. Jusqu'à aujourd'hui, je n'ai trouvé que des repères qui ont été faits à la manière des journalistes (assez rapidement et balayant des dizaines de variables sous le tapis).

1) Vous devez tenir compte du réchauffement du cache

La plupart des personnes exécutant des tests de performance ont peur des écarts de minuterie, par conséquent, elles exécutent leurs affaires des milliers de fois et prennent tout le temps, elles font juste attention à prendre le même millier de fois pour chaque opération, puis considèrent cela comme comparable.

La vérité est que dans le monde réel, cela n'a pas de sens, car votre cache ne sera pas chaud et votre opération ne sera probablement appelée qu'une seule fois. Par conséquent, vous devez effectuer une analyse comparative en utilisant RDTSC et chronométrer les choses en les appelant une seule fois. Intel a rédigé un article décrivant comment utiliser RDTSC (en utilisant une instruction cpuid pour vider le pipeline, et en l'appelant au moins 3 fois au début du programme pour le stabiliser).

2) mesure de précision RDTSC

Je recommande également de faire ceci:

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

Il s'agit d'un mesureur de discordance, et il faudra le minimum de toutes les valeurs mesurées, pour éviter d'obtenir de temps en temps un -10 ** 18 (premières valeurs négatives de 64 bits).

Notez l'utilisation d'intrinsèques et non d'assemblage en ligne. Le premier assemblage en ligne est rarement pris en charge par les compilateurs de nos jours, mais bien pire que tout, le compilateur crée une barrière de commande complète autour de l'assemblage en ligne car il ne peut pas analyser de manière statique l'intérieur, c'est donc un problème pour comparer les choses du monde réel, en particulier lors de l'appel de choses juste une fois que. Donc, un intrinsèque convient ici, car il ne rompt pas le réordonnancement des instructions du compilateur.

3) paramètres

Le dernier problème est que les gens testent généralement trop peu de variations du scénario. Les performances d'un conteneur sont affectées par:

1. Allocateur
2. taille du type contenu
3. coût de mise en œuvre de l'opération de copie, opération d'affectation, opération de déplacement, opération de construction, du type contenu
4. nombre d'éléments dans le conteneur (taille du problème)
5. type a des opérations 3. triviales
6. le type est POD

Le point 1 est important parce que les conteneurs allouent de temps en temps, et il importe beaucoup s'ils allouent en utilisant le CRT "nouveau" ou une opération définie par l'utilisateur, comme l'allocation de pool ou une liste libre ou autre ...

( pour les personnes intéressées par pt 1, rejoignez le fil mystère sur gamedev sur l'impact sur les performances de l'allocateur système )

Le point 2 est que certains conteneurs (disons A) perdront du temps à copier des éléments, et plus le type est gros, plus la surcharge est importante. Le problème est que lorsqu'on compare à un autre conteneur B, A peut l'emporter sur B pour les petits types et perdre pour les plus grands types.

Le point 3 est le même que le point 2, sauf qu'il multiplie le coût par un facteur de pondération.

Le point 4 est une question de gros O mélangée à des problèmes de cache. Certains conteneurs de mauvaise complexité peuvent largement surpasser les conteneurs de faible complexité pour un petit nombre de types (comme mapvs. vector, car leur emplacement de cache est bon, mais mapfragmente la mémoire). Et puis à un certain point de croisement, ils perdront, car la taille globale contenue commence à «fuir» vers la mémoire principale et provoque des erreurs de cache, cela en plus du fait que la complexité asymptotique peut commencer à se faire sentir.

Le point 5 concerne les compilateurs capables d'éliminer les éléments vides ou triviaux au moment de la compilation. Cela peut grandement optimiser certaines opérations, car les conteneurs sont basés sur des modèles, chaque type aura donc son propre profil de performances.

Point 6 comme le point 5, les POD peuvent bénéficier du fait que la construction de copie n'est qu'un memcpy, et certains conteneurs peuvent avoir une implémentation spécifique pour ces cas, en utilisant des spécialisations partielles de modèle, ou SFINAE pour sélectionner des algorithmes en fonction des traits de T.

À propos de la carte à plat

Apparemment, la carte plate est un wrapper vectoriel trié, comme Loki AssocVector, mais avec quelques modernisations supplémentaires à venir avec C ++ 11, exploitant la sémantique de déplacement pour accélérer l'insertion et la suppression d'éléments uniques.

Ceci est toujours un conteneur commandé. La plupart des gens n'ont généralement pas besoin de la partie commande, donc de l'existence de unordered...

Avez-vous pensé que vous avez peut-être besoin d'un flat_unorderedmap? qui serait quelque chose comme google::sparse_mapou quelque chose comme ça - une carte de hachage d'adresse ouverte.

Le problème des cartes de hachage à adresse ouverte est qu'au moment où rehashelles doivent tout copier sur le nouveau terrain plat étendu, alors qu'une carte standard non ordonnée doit simplement recréer l'index de hachage, tandis que les données allouées restent là où elles sont. L'inconvénient est bien sûr que la mémoire est fragmentée comme l'enfer.

Le critère d'un rehash dans une carte de hachage d'adresse ouverte est lorsque la capacité dépasse la taille du vecteur de compartiment multiplié par le facteur de charge.

Un facteur de charge typique est 0.8; par conséquent, vous devez vous en soucier, si vous pouvez pré-dimensionner votre carte de hachage avant de la remplir, toujours pré-dimensionnée à: intended_filling * (1/0.8) + epsiloncela vous donnera la garantie de ne jamais avoir à tout refaire et recopier de manière erronée pendant le remplissage.

L'avantage des cartes d'adresses fermées ( std::unordered..) est que vous n'avez pas à vous soucier de ces paramètres.

Mais le boost::flat_mapest un vecteur ordonné; par conséquent, il aura toujours une complexité asymptotique log (N), qui est moins bonne que la carte de hachage d'adresse ouverte (temps constant amorti). Vous devriez en tenir compte également.

Résultats de référence

Il s'agit d'un test impliquant différentes cartes (avec intclé et __int64/ somestructcomme valeur) et std::vector.

informations sur les types testés:

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

Insertion

ÉDITER:

Mes résultats précédents incluaient un bug: ils ont en fait testé l'insertion ordonnée, qui présentait un comportement très rapide pour les cartes plates.
J'ai laissé ces résultats plus tard sur cette page car ils sont intéressants.
C'est le bon test:

J'ai vérifié la mise en œuvre, il n'y a pas de tri différé implémenté dans les cartes à plat ici. Chaque insertion trie à la volée, donc ce benchmark présente les tendances asymptotiques:

map: O (N * log (N))
hashmaps: O (N)
vector et flatmaps: O (N * N)

Attention : ci-après les 2 tests pour std::mapet les deux flat_mapsont bogués et testent en fait l' insertion ordonnée (vs l'insertion aléatoire pour d'autres conteneurs. Oui c'est déroutant désolé):

Nous pouvons voir que l'insertion ordonnée entraîne une poussée arrière et est extrêmement rapide. Cependant, à partir des résultats non représentés de mon benchmark, je peux également dire que ce n'est pas près de l'optimalité absolue pour une insertion arrière. À 10k éléments, une optimalité parfaite de réinsertion est obtenue sur un vecteur pré-réservé. Ce qui nous donne 3 millions de cycles; on observe ici 4,8M pour l'insertion ordonnée dans le flat_map(donc 160% de l'optimum).

Analyse: rappelez-vous qu'il s'agit d'une «insertion aléatoire» pour le vecteur, donc le milliard de cycles massif vient du fait d'avoir à décaler la moitié (en moyenne) des données vers le haut (un élément par un élément) à chaque insertion.

Recherche aléatoire de 3 éléments (horloges renormalisées à 1)

en taille = 100

en taille = 10000

Itération

au-dessus de la taille 100 (uniquement de type MediumPod)

au-dessus de la taille 10000 (uniquement de type MediumPod)

Grain final de sel

Au final je voulais revenir sur "Benchmarking §3 Pt1" (l'allocateur système). Dans une expérience récente que je fais autour des performances d' une carte de hachage d'adresse ouverte que j'ai développée , j'ai mesuré un écart de performance de plus de 3000% entre Windows 7 et Windows 8 sur certains std::unordered_mapcas d'utilisation ( discutés ici ).
Ce qui me donne envie d'avertir le lecteur des résultats ci-dessus (ils ont été réalisés sur Win7): votre kilométrage peut varier.

meilleures salutations

D'après la documentation, il semble que ce soit analogue à celui Loki::AssocVectordont je suis un utilisateur assez intensif. Puisqu'il est basé sur un vecteur il a les caractéristiques d'un vecteur, c'est-à-dire:

• Les itérateurs sont invalidés chaque fois que se sizedéveloppe au-delà capacity.
• Quand il dépasse, capacityil doit réallouer et déplacer des objets, c'est-à-dire que l'insertion n'est pas garantie à temps constant sauf dans le cas particulier de l'insertion à endquandcapacity > size
• La recherche est plus rapide qu'en std::mapraison de la localité du cache, une recherche binaire qui a les mêmes caractéristiques de performance que par std::mapailleurs
• Utilise moins de mémoire car ce n'est pas un arbre binaire lié
• Il ne rétrécit jamais à moins que vous ne le lui disiez de force (car cela déclenche une réallocation)

La meilleure utilisation est lorsque vous connaissez le nombre d'éléments à l'avance (vous pouvez donc à l' reserveavance), ou lorsque l'insertion / suppression est rare mais la recherche est fréquente. L'invalidation d'itérateur la rend un peu lourde dans certains cas d'utilisation, de sorte qu'ils ne sont pas interchangeables en termes d'exactitude du programme.