Performance de redimensionnement std:: vecteur>

la conception générale semble être que std::unique_ptr a pas de temps au-dessus par rapport à la propriété de pointeurs bruts correctement utilisés, donné une optimisation suffisante .

mais qu'en est-il de l'utilisation de std::unique_ptr dans les structures de données composées, en particulier std::vector<std::unique_ptr<T>> ? Par exemple, redimensionner les données sous-jacentes d'un vecteur, ce qui peut se produire pendant push_back . Pour isoler la performance, je boucle autour de pop_back , shrink_to_fit , emplace_back :

#include <chrono>
#include <vector>
#include <memory>
#include <iostream>

constexpr size_t size = 1000000;
constexpr size_t repeat = 1000;
using my_clock = std::chrono::high_resolution_clock;

template<class T>
auto test(std::vector<T>& v) {
    v.reserve(size);
    for (size_t i = 0; i < size; i++) {
        v.emplace_back(new int());
    }
    auto t0 = my_clock::now();
    for (int i = 0; i < repeat; i++) {
        auto back = std::move(v.back());
        v.pop_back();
        v.shrink_to_fit();
        if (back == nullptr) throw "don't optimize me away";
        v.emplace_back(std::move(back));
    }
    return my_clock::now() - t0;
}

int main() {
    std::vector<std::unique_ptr<int>> v_u;
    std::vector<int*> v_p;

    auto millis_p = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_p));
    auto millis_u = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_u));
    std::cout << "raw pointer: " << millis_p.count() << " ms, unique_ptr: " << millis_u.count() << " msn";
    for (auto p : v_p) delete p; // I don't like memory leaks ;-)
}

compilant le code avec -O3 -o -march=native -std=c++14 -g avec gcc 7.1.0, clang 3.8.0, et 17.0.4 sur Linux sur un Intel Xeon E5-2690 v3 @ 2.6 GHz (pas de turbo):

raw pointer: 2746 ms, unique_ptr: 5140 ms  (gcc)
raw pointer: 2667 ms, unique_ptr: 5529 ms  (clang)
raw pointer: 1448 ms, unique_ptr: 5374 ms  (intel)

la version brute de pointeur passe tout son temps dans un memmove optimisé (intel semble en avoir un bien meilleur que clang et gcc). Le code unique_ptr semble d'abord copier les données vectorielles d'un bloc de mémoire à l'autre et assignez l'original avec zéro-tout dans une boucle horriblement non optimisée. Et puis il boucle sur le bloc original de données à nouveau pour voir si l'un de ceux qui étaient juste Zéro est non zéro et doit être supprimé. Le détail sanglant complet peut être vu sur godbolt . La question n'est pas comment le code compilé diffère , c'est assez clair. La question Est pourquoi le compilateur ne parvient pas à optimiser ce qui est généralement considéré comme un pas d'abstraction extra-aérienne.

en essayant de comprendre comment la raison compilateurs sur la manipulation de std::unique_ptr , je regardais un peu plus de code isolé. Par exemple:

void foo(std::unique_ptr<int>& a, std::unique_ptr<int>& b) {
  a.release();
  a = std::move(b);
}

ou similaire

a.release();
a.reset(b.release());

aucun des compilateurs x86 ne semble être capable d'optimiser à l'extérieur l'insensé if (ptr) delete ptr; . Le compilateur Intel donne même 28% de chance à la suppression. Étonnamment, la suppression le contrôle est systématiquement omis pour:

auto tmp = b.release();
a.release();
a.reset(tmp);

ces bits ne sont pas l'aspect principal de cette question, mais tout cela me fait sentir que je manque quelque chose.

pourquoi divers compilateurs ne parviennent pas à optimiser la réallocation dans std::vector<std::unique_ptr<int>> ? Y a-t-il quelque chose dans la norme qui empêche de générer du code aussi efficace qu'avec des pointeurs bruts? Est-ce un problème avec la mise en œuvre de la bibliothèque standard? Ou sont les compilateurs tout simplement pas suffisamment assez intelligent (encore)?

que peut-on faire pour éviter l'impact de performance par rapport à l'utilisation de pointeurs bruts?

Note: supposons que T est polymorphe et coûteux à déplacer, donc std::vector<T> n'est pas une option.

32
demandé sur Zulan 2017-07-13 22:01:17

2 réponses

l'affirmation selon laquelle unique_ptr fonctionne aussi bien qu'un pointeur brut après optimisation s'applique principalement uniquement aux opérations de base sur un seul pointeur, telles que la création, le déréférencement, l'assignation d'un seul pointeur et la suppression. Ces opérations sont définies assez simplement pour qu'un compilateur d'optimisation puisse généralement effectuer les transformations nécessaires de sorte que le code résultant soit équivalent (ou presque) en performance à la version brute 0 .

un endroit qui tombe en morceaux est particulièrement higher level language-based optimizations sur les conteneurs à base de tableaux tels que std::vector , comme vous l'avez noté avec votre test. Ces conteneurs utilisent généralement niveau source optimisations qui dépendent des caractéristiques du type pour déterminer au moment de la compilation si un type peut être copié en toute sécurité en utilisant une copie byte sage comme memcpy , et déléguer à une telle méthode si oui, ou sinon, revenez à une boucle de copie par élément.

pour pouvoir être copié en toute sécurité avec memcpy un objet doit être trivialement copiable . Maintenant std::unique_ptr n'est pas trivialement copiable car en effet il ne répond pas à plusieurs des exigences comme avoir seulement la copie triviale ou supprimé et déplacer les constructeurs. Le mécanisme exact dépend de la bibliothèque standard concernée, mais en général une qualité std::vector la mise en œuvre finira par appeler une forme spécialisée de quelque chose comme std::uninitialized_copy pour les types trivialement-copiables qui délègue juste à memmove .

les détails typiques de la mise en œuvre sont assez torturés, mais pour libstc++ (utilisé par gcc ) vous pouvez voir la divergence de haut niveau dans std::uninitialized_copy :

 template<typename _InputIterator, typename _ForwardIterator>
 inline _ForwardIterator
 uninitialized_copy(_InputIterator __first, _InputIterator __last,
                    _ForwardIterator __result)
 {
        ...
   return std::__uninitialized_copy<__is_trivial(_ValueType1)
                                    && __is_trivial(_ValueType2)
                                    && __assignable>::
     __uninit_copy(__first, __last, __result);
 }

de là, vous pouvez prendre ma parole que beaucoup de les méthodes std::vector " mouvement "finissent ici, et que __uninitialized_copy<true>::__uinit_copy(...) appelle finalement memmove alors que la version <false> ne le fait pas - ou vous pouvez tracer à travers le code vous-même (mais vous avez déjà vu le résultat dans votre benchmark).

finalement alors, vous finissez avec plusieurs boucles qui effectuent les étapes de copie requises pour les objets non-triviaux, comme appeler le constructeur de déplacement de l'objet de destination, et ensuite appeler le destructeur de tous les objets de la source. Ce sont des boucles séparées et même les compilateurs modernes ne seront pas en mesure de raisonner sur quelque chose comme "OK, dans la première boucle j'ai déplacé tous les objets de destination de sorte que leur ptr membre sera nul, donc la deuxième boucle est un no-op". Enfin, pour égaler la vitesse des pointeurs bruts, non seulement les compilateurs devraient optimiser à travers ces deux boucles, ils devraient avoir une transformation qui reconnaît que l'ensemble peut être remplacé par memcpy ou memmove 2 .

donc une réponse à votre question Est que les compilateurs ne sont tout simplement pas assez intelligents pour faire cette optimisation, mais c'est en grande partie parce que la version" brute " a beaucoup d'aide de compilation pour sauter le besoin de cette optimisation entièrement.

"1519790920 Boucle" Fusion

tel que mentionné les implémentations existantes vector implémentent une opération de type redimensionnement dans deux boucles distinctes (en plus de Travaux hors boucle tels que l'attribution du nouveau stockage et la libération de l'ancien stockage):

  • copier les objets source dans le tableau de destination nouvellement attribué (en utilisant conceptuellement quelque chose comme le placement new appelant le constructeur move).
  • "1519840920 de" Détruire la source des objets dans l'ancienne région.

conceptuellement, vous pourriez imaginer une autre façon: faire tout cela en une boucle, copier chaque élément et immédiatement détruire. Il est possible qu'un compilateur puisse même remarquer que les deux boucles itèrent sur le même ensemble de valeurs et fusionnent les deux boucles en une seule. [Apparemment], howevever, ( https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html ) gcc ne pas faire "1519460920 boucle" fusion aujourd'hui, et à ne pas faire clang ou icc si vous croyez que ce test .

alors nous sommes laissés essayant de mettre les boucles ensemble explicitement au niveau de la source.

maintenant l'implémentation à deux boucles aide à préserver le contrat de sécurité d'exception de l'opération en ne détruisant aucun objet source jusqu'à ce que nous sachions que la partie construction de la copie est terminée, mais elle aide aussi à optimiser la copie et la destruction lorsque nous avons des objets respectivement trivialement-copiables et trivialement-destructibles. En particulier, avec des traits simples basés sur sélection Nous pouvons remplacer la copie par une memmove et la boucle de destruction peut être supprimée entièrement 3 .

ainsi l'approche à deux boucles aide quand ces optimisations s'appliquent, mais cela fait mal dans le cas général des objets qui ne sont ni trivialement copiables ou destructibles. Cela signifie que vous avez besoin de deux passes sur les objets et vous perdez l'occasion d'optimiser et d'éliminer le code entre la copie de l'objet et il est subséquent destruction. Dans le cas unique_ptr vous perdez la capacité pour le compilateur de propager la connaissance que la source unique_ptr aura un NULL interne ptr membre et donc sauter le if (ptr) delete ptr vérifier entièrement 4 .

Trivialement Mobile

maintenant, on peut se demander si nous pourrions appliquer les mêmes caractéristiques d'optimisation du temps de compilation au cas unique_ptr . Par exemple, on pourrait s'intéresser à la trivially copiable exigences et voir qu'ils sont peut-être trop strictes pour le commun move opérations dans std::vector . Bien sûr, un unique_ptr n'est évidemment pas trivialement copiable puisqu'une copie bit-wise laisserait à la fois la source et la destination objet dû le même pointeur( et le résultat de la double-suppression), mais il semble qu'il devrait être bit-wise mobile : si vous déplacez un unique_ptr d'une zone de mémoire à un autre, tel que vous ne considériez plus la source comme un objet vivant (et donc n'appellera pas son destructeur) il devrait "juste fonctionner", pour l'implémentation typique unique_ptr .

malheureusement, il n'existe pas de concept" trivial move", bien que vous puissiez essayer de lancer le vôtre. Il semble y avoir un débat ouvert à savoir si C'est UB ou non pour les objets qui peuvent être copiés byte-wise et ne dépendent pas de leur comportement du constructeur ou du destructeur dans le scénario de déplacement.

vous pouvez toujours implémenter votre propre concept trivialement mobile, qui serait quelque chose comme (a) l'objet a un constructeur de mouvements trivial et (b) lorsqu'il est utilisé comme argument source du constructeur de mouvements, l'objet est laissé dans un état où son destructeur n'a aucun effet . Notez qu'une telle définition est actuellement la plupart du temps inutile, car "trivial move constructor" (essentiellement au niveau des éléments) copie et rien d'autre) n'est pas cohérent avec la modification de l'objet source. Ainsi, par exemple, un constructeur trivial move ne peut pas définir le ptr membre de la source unique_ptr à zéro. Donc, vous auriez besoin de sauter à travers quelques cerceaux tels que l'introduction du concept d'une mouvement destructif opération qui laisse l'objet source détruit, plutôt que dans un état valide-mais-non spécifié.

vous pouvez trouver une discussion plus détaillée de ce" trivially movable "sur ce fil sur le groupe de discussion ISO C++ usenet. Dans le particulier, dans la réponse liée, la question exacte des vecteurs de unique_ptr est adressée:

Il s'avère que de nombreux pointeurs intelligents (unique_ptr et shared_ptr inclus) de ces trois catégories et en les appliquant vous pouvez ont vecteurs de pointeurs intelligents, pratiquement zéro frais généraux brut les pointeurs de même dans les constructions de débogage non optimisées.

Voir aussi la relocator proposal.


0 bien que les exemples non vectoriels à la fin de votre question montrent que ce n'est pas toujours le cas. Ici, il est en raison d'un possible alias comme zneak explique dans sa réponse . Les pointeurs bruts éviteront beaucoup de ces problèmes d'aliasing puisqu'ils manquent le unique_ptr A (E. g, vous passez un pointeur brut par valeur, plutôt qu'une structure avec un pointeur par référence) et peut souvent omettre le if (ptr) delete ptr vérifier entièrement.

2 c'est en fait plus difficile que vous pourriez le penser, parce que memmove , par exemple, a une sémantique subtilement différente d'une boucle de copie d'objet, lorsque la source et la destination se chevauchent. Bien sûr, le code de caractères de type de haut niveau qui fonctionne pour les points bruts sait (par contrat) qu'il n'y a pas de chevauchement, ou que le comportement de memmove est cohérent, même s'il y a chevauchement, mais prouver la même chose lors d'un passage ultérieur d'optimisation arbitraire peut être beaucoup plus difficile.

3 il est important de noter que ces optimisations sont plus ou moins indépendantes. Par exemple, de nombreux objets sont trivialement destructibles qui ne sont pas trivialement copiable.

4 bien que mon test ni gcc ni clang n'ont été en mesure de supprimer le contrôle, même avec __restrict__ appliqué, apparemment en raison d'une analyse d'alias insuffisamment puissante, ou peut-être parce que std::move supprime le qualificatif" restreindre " d'une façon ou d'une autre.

36
répondu BeeOnRope 2017-10-19 08:36:48

Je n'ai pas de réponse précise pour ce qui vous mord dans le dos avec des vecteurs; on dirait que BeeOnRope pourrait déjà en avoir un pour vous.

heureusement, je peux vous dire ce qui vous mord dans le dos pour votre micro-exemple impliquant différentes façons de réinitialiser les pointeurs: analyse d'alias. Plus précisément, les compilateurs ne sont pas en mesure de prouver (ou de ne pas vouloir inférer) que les deux références unique_ptr ne se chevauchent pas. Ils se forcent à recharger la valeur unique_ptr au cas où l'écriture au premier a modifié le second. baz n'en souffre pas parce que le compilateur peut prouver qu'aucun des deux paramètres, dans un programme bien formé, ne peut être alias avec tmp , qui a fonction-local de stockage automatique.

vous pouvez vérifier cela par en ajoutant le __restrict__ mot-clé (qui, comme le double soulignement implique quelque peu, n'est pas standard C++) à l'un ou l'autre unique_ptr paramètre de référence. Que keyword informe le compilateur que la référence est la seule référence à travers laquelle cette mémoire peut éventuellement être consultée, et qu'il n'y a donc aucun risque que quelque chose d'autre puisse s'alias avec elle. Lorsque vous le faites, les trois versions de votre fonction compilent le même code machine et ne vous embêtez pas à vérifier si le unique_ptr doit être supprimé.

8
répondu zneak 2017-10-09 06:23:26