Stratégies d'optimisation efficaces sur les compilateurs C++ modernes

je travaille sur un code scientifique qui est très critique pour la performance. Une première version du code a été écrite et testée, et maintenant, avec profiler en main, il est temps de commencer les cycles de rasage à partir des points chauds.

il est bien connu que certaines optimisations, comme le déroulage de boucle, sont de nos jours gérées beaucoup plus efficacement par le compilateur que par un programmeur qui se mêle à la main. Quelles techniques sont encore valables? Évidemment, je vais courir tout ce que j'essaie par le biais d'un profileur, mais s'il y a une sagesse conventionnelle quant à ce qui a tendance à fonctionner et ce qui ne fonctionne pas, cela me ferait gagner beaucoup de temps.

je sais que l'optimisation est très dépendante du compilateur et de l'architecture. J'utilise le compilateur C++ D'Intel qui cible Le Duo Core 2, mais je m'intéresse aussi à ce qui fonctionne bien pour gcc, ou pour "n'importe quel compilateur moderne."

voici quelques idées concrètes que je considère:

  • Est-il un avantage de remplacer les conteneurs/algorithmes STL par des conteneurs / algorithmes roulés à la main? En particulier, mon programme comprend une très grande file d'attente prioritaire (actuellement un std::priority_queue ) dont la manipulation prend beaucoup de temps total. Est-ce quelque chose qui mérite d'être étudié, ou est-ce que L'implémentation de STL est déjà probablement la plus rapide possible?
  • dans le même sens, pour std::vector s dont on ne connaît pas les dimensions nécessaires mais dont la limite supérieure est raisonnablement petite, est-il rentable de les remplacer par de manière statique les tableaux alloués?
  • j'ai constaté que l'allocation dynamique de la mémoire est souvent un goulot d'étranglement sévère, et que son élimination peut conduire à des accélérations significatives. En conséquence, je suis intéressant dans les compromis de performance de retour de grandes structures de données temporaires par valeur vs. retour par pointeur vs. passer le résultat par référence. Existe-t-il un moyen fiable de déterminer si le compilateur utilisera RVO pour une méthode donnée (en supposant que l'appelant n'a pas besoin pour modifier le résultat, bien sûr)?
  • Comment cache-aware ne compilateurs ont tendance à être? Par exemple, vaut-il la peine d'examiner la réorganisation des boucles emboîtées?
  • étant donné la nature scientifique du programme, les nombres à virgule flottante sont utilisés partout. Un goulot d'étranglement significatif dans mon code utilisé pour être des conversions de point flottant à entiers: le compilateur émettrait du code pour sauver le mode d'arrondi actuel, le changer, effectuer la conversion, puis restaurer l'ancien mode d'arrondi --- même si rien dans le programme a jamais changé le mode d'arrondi! Désactiver ce comportement a considérablement accéléré mon code. Y a-t-il des gotchas similaires à point flottant que je devrais connaître?
  • une conséquence du fait que C++ soit compilé et lié séparément est que le compilateur n'est pas capable de faire ce qui semble être des optimisations très simples, telles que des appels de méthode de déplacement comme strlen() hors des conditions de terminaison de boucle. Il y a aucune optimisation comme celui-ci que je devrais surveiller parce qu'ils ne peut pas être fait par le compilateur et doit être fait à la main?
  • de l'autre côté, y a-t-il des techniques que je devrais éviter parce qu'elles sont susceptibles d'interférer avec la capacité du compilateur d'optimiser automatiquement le code?

enfin, pour étouffer certains types de réponses dans l'œuf:

  • je comprends cette optimisation a un coût en termes de complexité, de fiabilité et de maintenabilité. Pour cette application particulière, une performance accrue vaut ces coûts.
  • je comprends que les meilleures optimisations sont souvent pour améliorer les algorithmes de haut niveau, et cela a déjà été fait.
45
demandé sur user168715 2010-05-29 01:04:30

19 réponses

Est-il un avantage pour le remplacement des conteneurs STL/algorithmes avec des roulés à la main? En particulier, mon programme inclut une très grande file d'attente prioritaire (actuellement une std::priority_queue) dont la manipulation prend beaucoup de temps total. Est-ce quelque chose qui mérite d'être étudié, ou est-ce que L'implémentation de STL est déjà probablement la plus rapide possible?

je suppose que vous savez que les conteneurs STL dépendent de la copie des éléments. Dans certains cas, cela peut être une perte importante. Stocker des pointeurs et vous pouvez voir une augmentation des performances si vous faites beaucoup de conteneur de manipulation. D'un autre côté, il peut réduire la localisation du cache et vous nuire. Une autre option consiste à utiliser des allocateurs spécialisés.

certains récipients (par exemple: map , set , list ) comptez sur beaucoup de manipulation de pointeur. Bien que contre-intuitif, il peut souvent conduire à un code plus rapide pour les remplacer par vector . Le l'algorithme résultant peut passer de O(1) ou O(log n) à O(n) , mais en raison de la localisation du cache, il peut être beaucoup plus rapide dans la pratique. Profil pour être sûr.

vous avez mentionné que vous utilisez priority_queue , ce qui, j'imagine, paie beaucoup pour réorganiser les éléments, surtout s'ils sont grands. Vous pouvez essayer de changer le conteneur sous-jacent (peut-être deque ou spécialisé). J'ai presque certainement stocker des pointeurs - encore une fois, profil pour en être sûr.

dans le même sens, pour un std::vecteurs dont les tailles nécessaires sont inconnues mais qui ont une limite supérieure raisonnablement petite, est-il rentable de les remplacer par des matrices statiques?

Encore une fois, cela peut aider un petit montant, selon le cas d'utilisation. Vous pouvez éviter l'allocation de tas, mais seulement si vous n'avez pas besoin de votre tableau de survivre à la pile... ou vous pouvez reserve() la taille dans le vector il y a donc moins de copie sur réattribution.

j'ai constaté que l'allocation dynamique de la mémoire est souvent un goulot d'étranglement sévère, et que son élimination peut conduire à des accélérations significatives. En conséquence, je suis intéressant dans les compromis de performance de retour de grandes structures de données temporaires par valeur vs. retour par pointeur vs. passer le résultat par référence. Existe-t-il un moyen fiable de déterminer si le compilateur utilisera RVO pour une méthode donnée? (en supposant que l'appelant n'a pas besoin de modifier le résultat, bien sûr)?

vous pouvez regarder l'assemblage généré pour voir si RVO est appliqué, mais si vous retournez pointeur ou référence, vous pouvez être sûr qu'il n'y a pas de copie. La question de savoir si cela vous aidera dépend de ce que vous faites - par exemple, vous ne pouvez pas renvoyer des références à des temporels. Vous pouvez utiliser des arènes à allouer et réutiliser des objets, pour ne pas payer une grosse pénalité.

How est-ce que les compilateurs ont tendance à être conscients du cache? Par exemple, vaut-il la peine d'examiner la réorganisation des boucles emboîtées?

j'ai vu dramatique (sérieux, dramatique) accélérations dans ce domaine. J'ai vu plus d'améliorations de ce que j'ai vu de multithreading mon code. Les choses peuvent avoir changé depuis cinq ans - une seule façon d'être sûr de profil.

de l'autre côté, y a-t-il des techniques I devrait éviter, car elles sont susceptibles d'interférer avec la capacité du compilateur d'optimiser automatiquement le code?

  • utilisez explicit sur vos constructeurs à argument unique. La construction et la destruction d'objets temporaires peuvent être cachées dans votre code.

  • soyez conscient des appels de copie cachés sur les gros objets. Dans certains cas, envisagez de remplacer par des pointeurs.

  • Profil, Profil, Profil. Accordez des zones qui sont des goulets d'étranglement.

25
répondu Stephen 2017-02-19 09:19:07

jetez un oeil à l'excellent pièges de la programmation orientée objet diapositives pour quelques informations sur le code de restructuration pour la localité. D'après mon expérience, l'amélioration de la localité est presque toujours la plus grande victoire.

procédé général:

  • apprendre à aimer la vue désassemblage dans votre débogueur, ou avoir votre système de construction de générer les fichiers d'assemblage intermédiaire (.s) si, à tous les possible. Gardez un oeil sur les changements ou pour les choses qui semblent flagrantes -- même sans familiarité avec une architecture d'ensemble d'instruction donnée, vous devriez être en mesure de voir certaines choses assez clairement! (J'ai parfois vérifier dans une série de .les fichiers correspondants .rpc/.c change, juste pour utiliser les jolis outils de mon SCM pour regarder le code et l'asm correspondante changer au fil du temps.)
  • Obtenir un profiler qui peut surveillez votre CPU compteurs de performance , ou peut au moins deviner que cache manque. (AMD CodeAnalyst, cachegrind, vTune, etc.)

Quelques autres choses:

  • comprendre l'alias strict. une fois que vous l'avez fait, utilisez restrict si votre compilateur l'a. (Examinez le désastre ici aussi!)
  • découvrez les différentes à virgule flottante "modes d'1519160920" sur votre processeur et compilateur. Si vous n'avez pas besoin de la gamme dénormalisée, le choix d'un mode sans cela peut entraîner de meilleures performances. (On dirait que vous avez déjà fait certaines choses dans ce domaine, en vous basant sur votre discussion des modes d'arrondissement.)
  • éviter définitivement les allocs: appeler reserve sur std::vector quand vous pouvez, ou utiliser std::array quand vous connaissez la taille au moment de la compilation.
  • Utilisation de la mémoire pools pour augmenter la localisation et diminuer les alloc/free overhead; aussi pour assurer l'alignement de la ligne de cachetage et prévenir le ping-ponging.
  • Utiliser un cadre d'allocateurs de si vous êtes l'allocation de choses dans des modèles prévisibles, et peuvent se permettre de libérer tout d'un coup.
  • Faire être conscient des invariants . Quelque chose que vous savez invariant peut ne pas être pour le compilateur, par exemple l'utilisation d'une structure ou membre de la classe dans une boucle. Je trouve que la façon la plus facile de tomber dans l'habitude correcte ici est de donner un nom à tout, et préfère nommer les choses en dehors des boucles. Par exemple: const int threshold = m_currentThreshold; ou peut-être Thing * const pThing = pStructHoldingThing->pThing; heureusement, vous pouvez généralement voir des choses qui ont besoin de ce traitement dans la vue de démontage. Cela aide aussi avec le débogage plus tard (rend la fenêtre watch/locals plus agréable dans les constructions de débogage)!
  • éviter écrit en boucles si possible -- accumuler d'abord, puis écrire, ou assembler quelques Écritures ensemble. YMMV, bien sûr.

WRT votre std::priority_queue question: l'insertion des choses dans un vecteur (le backend par défaut pour un priority_queue) tend à se déplacer beaucoup d'éléments qui nous entourent. Si vous pouvez diviser en phases, où vous insérez des données, puis les trier, puis les lire une fois qu'il est trié, vous serez probablement beaucoup mieux. Bien que vous allez certainement perdre localité, vous pouvez trouver un plus auto-ordonnancement la structure comme un std::map ou std::set valeur de la surcharge -- mais c'est vraiment dépend de vos habitudes d'utilisation.

20
répondu leander 2010-05-28 22:02:08

y a-t-il un avantage à remplacer les conteneurs/algorithmes STL par des conteneurs / algorithmes roulés à la main?

Je considère cela comme une dernière option. Les conteneurs STL et les algorithmes ont été testés en profondeur. La création de nouveaux sont coûteux en termes de temps de développement.

dans le même ordre d'idées, pour les vecteurs std::dont la taille nécessaire est inconnue mais dont la limite supérieure est relativement petite, est-il rentable de les remplacer par des tableaux statiques?

Tout d'abord, essayez de réserver de l'espace pour les vecteurs. Consultez la méthode std::vector::reserve . Un vecteur qui continue de croître ou de changer pour des tailles plus grandes va gaspiller la mémoire dynamique et le temps d'exécution. Ajouter du code pour déterminer une bonne valeur pour une limite supérieure.

j'ai constaté que l'allocation dynamique de la mémoire est souvent un goulot d'étranglement grave, et que son élimination peut conduire à des accélérations significatives. En conséquence, je suis intéressant dans les compromis de performance de retour de grandes structures de données temporaires par valeur vs. retour par pointeur vs. passer le résultat par référence. Y a-t-il un moyen de déterminer de manière fiable si le compilateur utilisera RVO pour une méthode donnée (en supposant que l'appelant n'ait pas besoin de modifier le résultat, bien sûr)?

Par principe, toujours passer de grandes structures par référence ou pointeur. Préférer passant par référence constante. Si vous utilisez des pointeurs, envisagez d'utiliser des pointeurs intelligents.

Comment cache-aware ne compilateurs ont tendance à être? Par exemple, vaut-il la peine d'examiner la réorganisation des boucles emboîtées?

les compilateurs modernes sont très conscients des caches d'instruction (pipelines) et essaient de les empêcher d'être rechargés. Vous pouvez toujours aider votre compilateur en écrivant du code qui utilise moins de branches (à partir de if , switch , loop construit et appels de fonction ).

vous pouvez voir un gain de performance plus significatif en ajustant votre programme pour optimiser le cache data . Rechercher sur le web Data Driven Design . Il ya beaucoup d'excellents articles sur ce sujet.

étant donné la nature scientifique du programme, les nombres à virgule flottante sont utilisés partout. Un goulot d'étranglement significatif dans mon code était la conversion de points flottants en entiers: le compilateur émettait du code pour sauver le mode d'arrondi actuel, le changeait, effectuait la conversion, puis restaurait l'ancien mode d'arrondi - - - même si rien dans le programme n'a jamais changé le mode d'arrondi! Désactiver ce comportement a considérablement accéléré mon code. Y a-t-il des gotchas similaires à point flottant que je devrais connaître?

Pour plus de précision, conservez tout comme un double . Ajuster pour arrondir seulement quand nécessaire et peut-être avant l'affichage. Cela tombe sous la règle d'optimisation, utiliser moins de code, éliminer code étranger ou deadwood .

voir également la section ci-dessus concernant la réservation d'espace dans les conteneurs avant leur utilisation.

certains processeurs peuvent charger et stocker des nombres à virgule flottante plus rapidement ou aussi vite que des entiers. Cela nécessiterait la collecte des données de profil avant de les optimiser. Cependant, si vous savez qu'il y a une résolution minimale, vous pouvez utiliser des entiers et changer votre base à cette résolution minimale . Par exemple, lorsqu'il s'agit de monnaie américaine, des entiers peuvent être utilisés pour représenter 1/100 ou 1/1000 d'un dollar.

une conséquence du fait que C++ soit compilé et lié séparément est que le compilateur n'est pas capable de faire ce qui semble être des optimisations très simples, comme move. les appels de méthode comme strlen () hors des conditions de terminaison de boucle. Y a-t-il une optimisation comme celle-ci que je devrais surveiller parce qu'elle ne peut pas être faite par le compilateur et doit être faite à la main?

Ce une hypothèse erronée. Les compilateurs peuvent optimiser en fonction de la signature de la fonction, surtout si les paramètres utilisent correctement const . J'aime toujours aider le compilateur en déplaçant des trucs constants en dehors de la boucle. Pour un upper valeur limite, telle qu'une longueur de chaîne, assignez-la à une variable const avant la boucle. Le modificateur const aidera l'Optimiseur.

il y a toujours le count-down optimisation en boucles. Pour de nombreux processeurs, un saut sur registre égal zéro est plus efficace que comparer et saut si moins que .

On de l'autre côté, y a-t-il des techniques que je devrais éviter parce qu'elles sont susceptibles d'interférer avec la capacité du compilateur d'optimiser automatiquement le code?

J'éviterais les"micro-optimisations". Si vous avez des doutes, imprimez le code d'assemblage généré par le compilateur (pour la zone que vous interrogez) dans le cadre d'optimisation le plus élevé. Essayez de réécrire le code pour exprimer le code d'assemblage du compilateur. Optimiser ce code, si vous le pouvez. Rien de plus nécessite des instructions spécifiques à la plate-forme.

Optimisation Des Idées & Concepts

1. Les ordinateurs préfèrent exécuter des instructions séquentielles.

La ramification les perturbe. Certains processeurs modernes ont suffisamment de cache d'instruction pour contenir du code pour les petites boucles. En cas de doute, ne provoquez pas de branches.

2. Supprimer Les Exigences

Moins de code, plus de performance.

3. Optimiser les conceptions avant le code Souvent, il est possible d'obtenir plus de rendement en modifiant la conception plutôt qu'en modifiant la mise en œuvre de la conception. Moins de design favorise moins de code, génère plus de performance.

4. Envisager l'organisation des données Optimiser les données.

Organiser les champs fréquemment utilisés en substructures . Définir des tailles de données pour s'adapter à une ligne de cache de données 1519330920". Supprimer les données constantes des structures de données.

Utilisez const dans la mesure du possible.

5. Envisager le changement de page Les systèmes d'exploitation échangeront votre programme ou tâche pour une autre. Souvent dans un "fichier d'échange" sur le disque dur. Décomposer le code en morceaux qui contiennent du code fortement exécuté et du code moins exécuté aider les OS. De plus, coagulez le code très utilisé en unités plus serrées. L'idée est de réduire l'échange de code à partir du disque dur (comme aller chercher de "loin" des fonctions). Si le code doit être échangé, il doit être comme une unité.

6. Envisager des optimisations d'entrées/sorties (Y compris les entrées/sorties de fichier).

La plupart des e / s préfèrent moins de gros blocs de données que de petits. Les disques durs aiment tourner. Plus grands paquets de données ont moins de frais généraux que les petits paquets.

Formater les données dans un tampon puis écrire le tampon.

7. Éliminer la concurrence

Débarrassez-vous de tous les programmes et tâches qui sont en concurrence avec votre application pour le(s) processeur (s). Des tâches telles que le balayage de virus et la lecture de musique. Même les pilotes D'E/S veulent un morceau de l'action (c'est pourquoi vous voulez réduire le nombre ou les transactions d'e / s).

ceux-ci devraient vous tenir occupé pendant un certain temps. :- )

13
répondu Thomas Matthews 2010-05-28 22:04:09
  1. L'utilisation de pools de mémoire tampon peut être d'un grand avantage de performance par rapport à l'allocation dynamique. Surtout s'ils réduisent ou préviennent la fragmentation de tas sur de longues durées d'exécution.

  2. soyez conscient de l'emplacement des données. Si vous avez un mélange significatif de données locales et globales, vous pourriez surcharger le mécanisme de cache. Essayez de garder les ensembles de données à proximité pour utiliser au maximum la validité de la ligne de cache.

  3. même si les compilateurs font un travail merveilleux avec les boucles, je les scrute toujours lors de l'accordage de performance. Vous pouvez repérer les défauts d'architecture qui donnent des ordres de grandeur où le compilateur ne peut couper que des pourcentages.

  4. si une seule file d'attente prioritaire prend beaucoup de temps dans son fonctionnement, il peut être avantageux de créer une batterie de files d'attente représentant des seaux de priorité. Ce serait la complexité étant échangée pour la vitesse dans ce cas.

  5. je remarque que vous n'avez pas mentionné l'utilisation des instructions de type SSE. Ils pourraient être applicables à votre type de calcul?

bonne chance.

8
répondu Amardeep AC9MF 2010-05-28 21:19:28

Ici est un beau papier sur le sujet.

5
répondu Doug Currie 2010-05-28 21:20:16

à propos des conteneurs STL.

la plupart des gens ici affirment que STL offre l'une des implémentations les plus rapides possibles des algorithmes de conteneur. Et je dis le contraire: pour les scénarios les plus réels les conteneurs STL pris comme-is donnent vraiment une performance catastrophique .

les Gens argumenter sur le complexité des algorithmes de la STL. Ici STL est bon: O (1) pour list / queue , vecteur (amorti), et o(log(N)) Pour map . Mais ce n'est pas le véritable goulot d'étranglement des performances pour une application typique! Pour de nombreuses applications le véritable goulot d'étranglement est le opérations tas ( malloc / free , new / delete , etc.).

une opération typique sur le list ne coûte que quelques cycles CPU. Sur un map - quelques dizaines, peuvent être plus (cela dépend de l'état de cache et du log(N) de cours.) Et les opérations typiques de tas coûtent de hunders à des milliers (!!!) de cycles de PROCESSEUR. Pour les applications multithread, par exemple, ils nécessitent également une synchronisation (opérations entrelacées). De plus, sur certains os (comme Windows XP), les fonctions tas sont entièrement implémentées en mode noyau.

de sorte que la performance réelle des conteneurs STL dans un scénario typique est dominée par la quantité d'opérations de tas qu'ils effectuent. Et ici, ils sont désastreuses. Pas parce qu'ils sont mal mis en œuvre, mais à cause de leur conception . C'est, c'est la question de la conception.

en revanche il y a d'autres conteneurs qui sont conçus différemment. Une fois que j'ai conçu et écrit de tels conteneurs pour mes propres besoins:

http://www.codeproject.com/KB/recipes/Containers.aspx

et il s'est avéré pour moi d'être supérieur de la point de vue des performances, et pas seulement.

mais récemment j'ai découvert que je ne suis pas le seul à y avoir pensé. boost::intrusive est la bibliothèque de conteneurs qui est mis en œuvre de la manière similaire à ce que j'ai fait alors.

je vous suggère de l'essayer (si vous ne l'avez pas déjà)

3
répondu valdo 2010-05-30 08:52:01

Est-il un avantage pour le remplacement des conteneurs STL/algorithmes avec des roulés à la main?

généralement, pas à moins que vous travaillez avec une mauvaise mise en œuvre. Je ne remplacerais pas un conteneur STL ou un algorithme juste parce que vous pensez que vous pouvez écrire du code plus serré. Je le ferais seulement si la version STL est plus générale que nécessaire pour votre problème. Si vous pouvez écrire une version plus simple qui fait juste ce que vous avez besoin, alors il pourrait y avoir un peu de vitesse pour y gagner.

une exception que j'ai vue est de remplacer une chaîne de caractères copy-on-write std::par une autre qui ne nécessite pas de synchronisation de thread.

Pour std:: vecteurs dont les tailles nécessaires sont inconnues mais dont la limite supérieure est relativement petite, est-il rentable de les remplacer par des matrices statiques?

improbable. Mais si vous utilisez beaucoup de temps à allouer à une certaine taille, il peut-être rentable pour ajouter une réserve (appeler).

performance compromis de retour de gros temporaire des structures de données en valeur vs. retour par le pointeur de vs le résultat le passage par référence.

quand je travaille avec des conteneurs, je passe des itérateurs pour les entrées et un itérateur de sortie, ce qui est encore assez général.

Comment cache-aware ne compilateurs ont tendance à être? Par exemple, vaut-il vous cherchez à réorganiser les boucles emboîtées?

pas très. Oui. Je trouve que les prédictions de branches manquées et les modèles d'accès à la mémoire hostile à la mémoire cache sont les deux plus grands tueurs de performance (une fois que vous avez obtenu des algorithmes raisonnables). Beaucoup de vieux codes utilisent des tests" early out " pour réduire les calculs. Mais sur les processeurs modernes, c'est souvent plus cher que de faire le calcul et d'ignorer le résultat.

"151950920 Un" important goulot d'étranglement dans mon code utilisé à des conversions de virgule flottante entiers

Yup. J'ai découvert récemment le même problème.

une conséquence du fait que C++ soit compilé et lié séparément est que le compilateur n'est pas capable de faire ce qui semble être des optimisations très simples, telles que des appels de méthode de déplacement comme strlen() hors des conditions de terminaison de boucle.

certains compilateurs peuvent traiter avec cette. Visual C++ a une option "link-time code generation" qui réinvite efficacement le compilateur pour une optimisation plus poussée. Et, dans le cas de fonctions comme strlen , de nombreux compilateurs reconnaître que comme une fonction intrinsèque.

y a-t-il une optimisation comme celle-ci que je devrais surveiller parce qu'elle ne peut pas être faite par le compilateur et doit être faite à la main? D'un autre côté, y a-t-il des techniques que je devrais éviter parce qu'elles sont susceptible d'interférer avec la capacité du compilateur d'optimiser automatiquement le code?

lorsque vous optimisez à ce niveau bas, il y a peu de règles empiriques fiables. Les compilateurs varient. Mesurez votre solution actuelle et décidez si elle est trop lente. Si c'est le cas, présentez une hypothèse (p. ex., "que se passe-t-il si je remplace les énoncés if internes par un tableau de recherche?"). Cela peut aider ("élimine les décrochages dus à des prédictions de branches ratées") ou cela peut faire mal ("recherche le motif d'accès nuit à la cohérence du cache"). Expérimenter et mesurer progressivement.

je vais souvent cloner la mise en œuvre simple et utiliser un #ifdef HAND_OPTIMIZED / #else / #endif basculer entre la version de référence et la version modifiée. C'est utile pour la maintenance et la validation ultérieures du code. Je confie chaque expérience réussie pour changer le contrôle, et de garder un journal (tableur) avec le nombre de changelist, les temps d'exécution, et l'explication pour chaque étape dans optimisation. Comme j'en apprends plus sur le comportement du code, le log rend facile de revenir en arrière et de se ramifier dans une autre direction.

vous avez besoin d'un framework pour exécuter des tests de chronométrage reproductibles et pour comparer les résultats avec la version de référence afin de vous assurer que vous n'introduisez pas de bogues par inadvertance.

2
répondu Adrian McCarthy 2010-05-28 22:39:55

si je travaillais là-dessus, je m'attendrais à un stade final où des choses comme la localisation de cache et les opérations vectorielles pourraient entrer en jeu.

cependant, avant d'arriver au stade final, je m'attendrais à trouver une série de problèmes de différentes tailles ayant moins à faire avec l'optimisation du niveau de compilateur, et plus à faire avec des choses étranges en cours qui ne pourrait jamais être deviné, mais une fois trouvé, sont simples à réparer. Généralement, ils tournent autour de la conception de classe excessive et la structure de données question.

voici un exemple de ce genre de processus.

j'ai constaté que les classes de conteneurs généralisées avec des itérateurs, qui en principe le compilateur peut optimiser jusqu'aux cycles minimaux, souvent ne sont pas ainsi optimisés pour une raison obscure. J'ai aussi entendu d'autres affaires sur donc où cela arrive.

D'autres ont dit, avant que vous ne fassiez quoi que ce soit d'autre, profil. Je suis d'accord avec cette approche sauf que je pense il ya une meilleure façon, et c'est indiqué dans le lien. Chaque fois que je me demande si une chose spécifique, comme STL, pourrait être un problème, je juste pourrait être juste - mais - je suis deviner . L'idée gagnante fondamentale dans l'accord de performance est trouver , ne devinez pas. Il est facile de savoir avec certitude ce qui prend le temps, alors ne devinez pas.

2
répondu Mike Dunlavey 2017-05-23 11:46:09

voici quelques trucs que j'ai utilisés:

  • gabarits pour spécialiser les limites de boucles les plus intimes (les rend vraiment rapides)
  • utiliser __restrict__ mots clés pour les problèmes d'alias
  • réserver les vecteurs à l'avance pour les valeurs par défaut.
  • éviter l'utilisation de la carte (il peut être vraiment lent)
  • vectoriel ajoute/ insère peut être considérablement lent. Si c'est le cas, les premières opérations peuvent le rendre plus rapide
  • N-octets de mémoire d'alignement (Intel a pragma alignée http://www.intel.com/software/products/compilers/docs/clin/main_cls/cref_cls/common/cppref_pragma_vector.htm )
  • essaie de garder la mémoire dans les caches L1/L2.
  • compilé avec NDEBUG
  • profil en utilisant l'oprofile, utilisez l'opannotate pour rechercher des lignes spécifiques (le ciel stl est clairement visible alors)

voici des exemples de données de profil (pour que vous sachiez où chercher les problèmes)

 * Output annotated source file with samples
 * Output all files
 *
 * CPU: Core 2, speed 1995 MHz (estimated)
--
 * Total samples for file : "/home/andrey/gamess/source/blas.f"
 *
 * 1020586 14.0896
--
 * Total samples for file : "/home/andrey/libqc/rysq/src/fock.cpp"
 *
 * 962558 13.2885
--
 * Total samples for file : "/usr/include/boost/numeric/ublas/detail/matrix_assign.hpp"
 *
 * 748150 10.3285

--
 * Total samples for file : "/usr/include/boost/numeric/ublas/functional.hpp"
 *
 * 639714  8.8315
--
 * Total samples for file : "/home/andrey/gamess/source/eigen.f"
 *
 * 429129  5.9243
--
 * Total samples for file : "/usr/include/c++/4.3/bits/stl_algobase.h"
 *
 * 411725  5.6840
--

exemple de code de mon projet

template<int ni, int nj, int nk, int nl>
inline void eval(const Data::density_type &D, const Data::fock_type &F,
                 const double *__restrict Q, double scale) {

    const double * __restrict Dij = D[0];
    ...
    double * __restrict Fij = F[0];
    ...

    for (int l = 0, kl = 0, ijkl = 0; l < nl; ++l) {
        for (int k = 0; k < nk; ++k, ++kl) {
            for (int j = 0, ij = 0; j < nj; ++j, ++jk, ++jl) {
                for (int i = 0; i < ni; ++i, ++ij, ++ik, ++il, ++ijkl) {
2
répondu Anycorn 2010-05-29 05:15:08

Et je pense que le principal indicateur de quelqu'un pourrais vous donner est: mesure , mesure , mesure . Ça et améliorer vos algorithmes.

La façon dont vous utilisez certaines fonctionnalités de langage, la version de compilateur, la mise en œuvre std lib, la plateforme, la machine-tout jouer leur rôle dans la performance et vous n'avez pas mentionné beaucoup de ceux et aucun de nous n'a jamais eu votre configuration exacte.

concernant le remplacement de std::vector : utilisez un remplacement Direct (par exemple, celui-ci ) et essayez-le.

1
répondu sbi 2010-05-28 21:30:32

Comment cache-aware ne compilateurs ont tendance à être? Par exemple, vaut-il la peine d'examiner la réorganisation des boucles emboîtées?

Je ne peux pas parler pour tous les compilateurs, mais mon expérience avec GCC montre qu'il ne va pas fortement optimiser le code en ce qui concerne le cache. Je m'attends à ce que cela soit vrai pour la plupart les compilateurs modernes. Optimisation telles que la réorganisation des boucles imbriquées peut certainement affecter les performances. Si vous croyez que vous avez des modèles d'accès à la mémoire cela pourrait conduire à de nombreuses erreurs de cache, il sera dans votre intérêt d'enquêter à ce sujet.

1
répondu Doug 2010-05-29 19:35:55

Est-il un avantage pour le remplacement de la STL conteneurs / algorithmes avec roulage à la main ? En particulier, mon programme comprend une très grande file d'attente de priorités (actuellement une std:: priority_queue) dont la manipulation prend beaucoup de temps total. Est-ce quelque chose d'intéressant la recherche, ou est le TSL mise en œuvre déjà probable le plus rapide possible?

le LTS est généralement le cas général le plus rapide. Si vous avez une très spécifiques cas, vous pourriez voir un speed-up avec un roulé à la main. Par exemple, std::sort (normalement quicksort) est le tri général le plus rapide, mais si vous savez à l'avance que vos éléments sont virtuellement déjà commandés, alors tri d'insertion pourrait être un meilleur choix.

sur le même modèle, Pour std::vecteurs dont les tailles nécessaires sont inconnues mais avoir une limite supérieure raisonnablement petite, est-il rentable de les remplacer par de manière statique les tableaux alloués?

cela dépend de l'endroit où vous allez faire la répartition statique. Une chose que j'ai essayé le long de cette ligne était de static allouer une grande quantité de mémoire sur la pile, puis réutiliser plus tard. Des résultats? La mémoire de tas était beaucoup plus rapide. Juste parce qu'un élément est sur la pile ne le rend pas plus rapide à accéder - la vitesse de la mémoire de pile dépend également de choses comme le cache. Un tableau global alloué statiquement ne peut pas être plus rapide que le tas. Je suppose que vous avez déjà essayé des techniques comme réserver la limite supérieure. Si vous avez beaucoup de vecteurs qui ont la même limite supérieure, pensez à améliorer cache en ayant un vecteur de structures, qui contiennent les données des membres.

j'ai trouvé cette mémoire dynamique l'allocation est souvent un grave goulot d'étranglement, et que l'élimination peut conduire à des accélérations significatives. En tant que conséquence je suis intéressant dans le compromis de rendement du retour grandes structures de données temporaires par valeur vs. retour par pointeur vs. en passant le résultat par référence. Être il y a un moyen de déterminer de façon fiable que le compilateur utilise ou non RVO pour une méthode donnée (en supposant que l'appelant n'a pas besoin de modifier le résultat, bien sûr)?

personnellement, je passe normalement le résultat par référence dans ce scénario. Il permet beaucoup plus de re-utiliser. Passer de grandes structures de données par valeur et espérer que le compilateur utilise RVO n'est pas une bonne idée quand vous peut juste utiliser manuellement RVO vous-même.

Comment cache-aware ne compilateurs ont tendance à l'être? Par exemple, est-il la peine de chercher pour réorganiser les boucles imbriquées?

j'ai trouvé qu'ils n'étaient pas particulièrement conscients du cache. Le problème est que le compilateur ne comprend pas votre programme et ne peut pas prédire la grande majorité de son état, surtout si vous dépendez fortement de tas. Si vous avez un profiler qui est livré avec votre compilateur, pour exemple L'optimisation guidée de profil de Visual Studio, puis cela peut produire d'excellentes vitesses.

étant donné la nature scientifique de la programme, les nombres à virgule flottante sont utilisé partout. Une importante goulot d'étranglement dans mon code les conversions de virgule flottante entiers: le compilateur émettrait du code pour sauvegarder le mode d'arrondissement courant, modifier, effectuer la conversion, ensuite restaurer l'ancien mode d'arrondi --- même si rien dans programme jamais changé le mode d'arrondi! Désactiver ce comportement de manière significative accéléré mon code. Il y a aucune similaire gotchas à virgule flottante devrais être au courant?

il y a différents modèles à virgule flottante-Visual Studio donne un réglage de compilateur fp:fast. En ce qui concerne les effets exacts d'une telle action, Je ne peux pas en être certain. Cependant, vous pouvez essayer de modifier la précision en virgule flottante ou d'autres paramètres de votre compilateur et vérifier le résultat.

une conséquence de la compilation de C++ et lié séparément est que le compilateur est incapable de faire ce qui serait semblent être des optimisations très simples, par exemple déplacer les appels de méthode comme strlen() de la cessation conditions de boucle. Il n'existe aucun optimisation comme celui-ci que j' ils devraient faire attention car ils ne peuvent pas être fait par le compilateur et doit être fait à la main?

Je n'ai jamais rencontré un tel scénario. Cependant, si vous êtes vraiment préoccupé par une telle chose, alors l'option reste de le faire manuellement. Une des choses que vous pourriez essayer est d'appeler une fonction sur une référence const, suggérant au compilateur que la valeur ne changera pas.

L'une des autres choses que je veux souligner est l'utilisation d'extensions non-standard au compilateur, par exemple fourni par Visual Studio est __supposer. http://msdn.microsoft.com/en-us/library/1b3fsfxw (VS.80).aspx

il y a aussi multithread, et je m'attends à ce que vous preniez cette voie. Vous pouvez essayer quelques options spécifiques, comme une autre Réponse suggérée SSE.

Edit: je me suis rendu compte qu'un grand nombre des suggestions que j'ai posté directement Visual Studio référencé. C'est vrai, mais, GCC fournit presque certainement des alternatives à la majorité d'entre eux. J'ai juste une expérience personnelle avec VS most.

0
répondu Puppy 2010-05-28 21:41:20

l'implémentation de la file D'attente prioritaire STL est assez bien optimisée pour ce qu'elle fait, mais certains types de tas ont des propriétés spéciales qui peuvent améliorer vos performances sur certains algorithmes. Les tas de Fibonacci en sont un exemple. En outre, si vous stockez des objets avec une petite clé et une grande quantité de données satellite, vous obtiendrez une amélioration majeure dans la performance de cache si vous stockez ces données séparément, même si cela signifie stocker un pointeur supplémentaire par objet.

As pour les tableaux, j'ai trouvé std::vector pour même légèrement sur-Effectuer les tableaux de constante de temps de compilation. Cela dit, ses optimisations sont Générales, et une connaissance spécifique des modèles d'accès de votre algorithme peut vous permettre d'optimiser davantage la localisation de cache, l'alignement, la coloration, etc. Si vous constatez que votre performance chute de manière significative au-delà d'un certain seuil en raison des effets de cache, les tableaux optimisés à la main peuvent déplacer ce seuil de taille de problème par un facteur de deux dans certains cas, mais il est peu probable de faire une énorme différence pour les petites boucles internes qui s'insèrent facilement dans le cache, ou les grands ensembles de travail qui dépassent la taille de n'importe quel cache CPU. Travailler d'abord sur la file d'attente prioritaire.

la plus grande partie des frais généraux de l'attribution dynamique de la mémoire est constante par rapport à la taille de l'objet attribué. Attribuer un grand objet et le retourner par un pointeur ne va pas faire autant de mal que de le copier. Le seuil pour la copie par rapport à l'allocation dynamique varie très entre les systèmes, mais il devrait être assez cohérent au sein d'une génération de puces.

Les compilateurs

sont assez conscients du cache lorsque le réglage spécifique au cpu est activé, mais ils ne connaissent pas la taille du cache. Si vous optimisez la taille du cache, vous pouvez le détecter ou demander à l'utilisateur de le spécifier à l'exécution, car cela variera même entre les processeurs de la même génération.

pour ce qui est de la virgule flottante, vous devez absolument utiliser le SSE. Ce ne nécessite pas nécessairement l'apprentissage SSE vous-même, car il existe de nombreuses bibliothèques de code SSE hautement optimisé qui font toutes sortes d'importantes opérations informatiques scientifiques. Si vous compilez du code 64 bits, le compilateur peut émettre du code SSE automatiquement, puisque SSE2 fait partie du jeu d'instructions x86_64. La SSE vous sauvera aussi une partie de la charge de x87 floating point, puisqu'elle ne convertit pas de va-et-vient en valeurs de 80 bits en interne. Ces conversions peuvent également être une source de précision problèmes, puisque vous pouvez obtenir des résultats différents du même ensemble d'opérations en fonction de la façon dont ils sont compilés, il est donc bon de se débarrasser d'eux.

0
répondu Chris 2010-05-28 22:15:36

si vous travaillez sur de grandes matrices par exemple, envisagez de carreler vos boucles pour améliorer la localité. Cela conduit souvent à des améliorations spectaculaires. Vous pouvez utiliser VTune/PTU pour surveiller les erreurs du cache L2.

0
répondu Kamchatka 2010-05-29 19:39:00

une conséquence du fait que C++ soit compilé et lié séparément est que le compilateur n'est pas capable de faire ce qui semble être des optimisations très simples, telles que des appels de méthode de déplacement comme strlen() hors des conditions de terminaison de boucle. Y a-t-il une optimisation comme celle-ci que je devrais surveiller parce qu'elle ne peut pas être faite par le compilateur et doit être faite à la main?

Sur certains compilateurs c'est incorrect. Le compilateur est parfait connaissance de tous les codes dans toutes les unités de traduction (y compris les bibliothèques statiques) et peut optimiser le code de la même façon qu'il le ferait s'il était dans une seule unité de traduction. Quelques-uns de ceux qui soutiennent cette caractéristique viennent à mon esprit:

  • Microsoft Visual C++ compilers
  • Compilateur Intel C++
  • LLVC-GCC
  • GCC (je pense, pas sûr)
0
répondu CMircea 2010-05-30 09:04:12

je suis surpris que personne n'ait mentionné ces deux-là:

  • Link time optimization clang et g++ à partir de 4.5 sur les optimisations de temps de liaison de soutien. J'ai entendu dire que g++ cas, l'heuristique est encore assez inmature mais il devrait s'améliorer rapidement la main et l'architecture.

    Les avantages de

    vont des optimisations procédurales inter au niveau du fichier objet, y compris des choses très recherchées comme inling de les appels virtuels (devirtualization)

  • Project inlining cela peut sembler à certains comme une approche très rudimentaire, mais c'est cette très grossièreté qui le rend si puissant: cela revient à déverser tous vos en-têtes et .rpc fichiers en un seul, vraiment grand .cpp fichier et compiler cela; fondamentalement, il vous donnera les mêmes avantages de l'optimisation du temps de lien dans votre voyage de retour à 1999. Bien sûr, si votre projet est vraiment grand, vous aurez encore besoin d'une machine 2010; cette chose va manger votre RAM comme il n'y a pas de demain. Cependant, même dans ce cas, vous pouvez le séparer en plus d'un pas-si-putain-énorme .fichier cpp

0
répondu lurscher 2011-07-14 16:09:47

si vous faites des mathématiques lourdes à virgule flottante, vous devriez envisager d'utiliser SSE pour vectoriser vos calculs si cela correspond bien à votre problème.

Google SSE intrinsics pour plus d'informations à ce sujet.

-1
répondu Laserallan 2010-05-28 21:19:12

voici quelque chose qui a fonctionné pour moi une fois. Je ne peux pas dire qu'il va travailler pour vous. J'avais un code sur les lignes de

switch(num) {
   case 1: result = f1(param); break;
   case 2: result = f2(param); break;
   //...
}

puis j'ai eu un sérieux coup de pouce de performance quand je l'ai changé en

// init:
funcs[N] = {f1, f2 /*...*/};
// later in the code:
result = (funcs[num])(param);

peut-être que quelqu'un ici peut expliquer la raison pour laquelle cette dernière version est meilleure. Je suppose qu'il a quelque chose à voir avec le fait qu'il n'y a pas des branchements conditionnels.

-1
répondu Tomer Vromen 2010-05-28 23:21:32

mon projet actuel est un serveur multimédia, avec un traitement de threads multiples (langage C++). C'est une application de temps Critique, une fois que les fonctions de faible performance pourraient causer de mauvais résultats sur le flux de médias comme la perte de synchronisation, une latence élevée, d'énormes retards et ainsi de suite.

la stratégie que j'utilise habituellement pour accorder la meilleure performance possible est de minimiser la quantité d'appels système opérationnels lourds qui allouent ou gèrent des ressources comme la mémoire, les fichiers, les sockets et ainsi de suite.

j'ai d'abord écrit mes propres classes STL, network et file manage.

toutes mes classes de conteneurs ("MySTL") gèrent leurs propres blocs de mémoire pour éviter les appels alloc (new) / free (delete) multiples. Les objets libérés sont recherchés sur un pool de blocs de mémoire pour être réutilisés en cas de besoin. De cette façon, j'améliore mes performances et protège mon code contre la fragmentation de la mémoire.

les parties du code qui ont besoin d'accéder à des ressources de système de performance inférieure (comme fichiers, bases de données, script, écriture réseau) j'utilise des threads séparés pour eux. Mais pas un thread pour chaque unité (comme pas un thread pour chaque socket), si c'est le cas, le système opérationnel perdrait des performances tout en gérant un nombre élevé de threads. Ainsi, vous pouvez grouper des objets de la même classe pour être traités sur un thread séparé si possible.

par exemple, si vous devez écrire des données sur une socket réseau, mais que le tampon d'écriture de socket est plein, je sauvegarde les données sur un tampon sendqueue (qui partage la mémoire avec toutes les sockets ensemble) pour être envoyé sur un fil séparé dès que les sockets deviennent de nouveau writable. De cette façon, vos threads principaux ne devraient jamais arrêter le traitement sur un état bloqué en attendant que le système opérationnel libère une ressource spécifique. Tous les tampons libérés sont sauvegardés et réutilisés au besoin.

après tout un outil de profil serait le bienvenu pour chercher des bouteilles de programme et montre quels algorithmes devraient être améliorés.

je suis réussi à utiliser cette stratégie Une fois que j'ai des serveurs tournant comme 500+ jours sur une machine linux sans redémarrage, avec des milliers d'utilisateurs se connectant tous les jours.

[02: 01] -alpha.ip.tv-temps de disponibilité: 525jours 12hrs 43mins 7secs

-1
répondu Jorg B Jorge 2010-05-29 05:07:11