Quelles sont les bonnes stratégies pour améliorer les performances en série de mon code?

66

Je travaille dans le domaine de la science informatique et, par conséquent, je passe une bonne partie de mon temps à essayer d’accroître le débit scientifique de nombreux codes, ainsi qu’à en comprendre l’efficacité.

Supposons que j’ai évalué le compromis performance / lisibilité / réutilisabilité / maintenabilité du logiciel sur lequel je travaille, et j’ai décidé qu’il était temps de passer à la performance. Supposons également que je sais que je n'ai pas un meilleur algorithme pour mon problème (en termes de flop / s et de bande passante mémoire). Vous pouvez également supposer que ma base de code est dans un langage de bas niveau tel que C, C ++ ou Fortran. Enfin, supposons qu'il n'y ait pas de parallélisme dans le code, ou que nous ne sommes intéressés que par la performance sur un seul noyau.

Quelles sont les choses les plus importantes à essayer en premier? Comment savoir combien de performances je peux obtenir?

Aron Ahmadia
la source

Réponses:

66

Tout d'abord, comme l' ont indiqué skillman et Dan , le profilage est essentiel. Personnellement , j'utilise VTune Amplificateur d'Intel sur Linux car il me donne une vue d' ensemble à grain très fin où le temps a été passé à faire quoi.

Si vous ne voulez pas modifier l'algorithme (c'est-à-dire s'il n'y a pas de changements majeurs rendant toutes vos optimisations obsolètes), alors je vous conseillerais de rechercher des détails d'implémentation courants qui peuvent faire toute la différence:

  • Lieu de mémoire : les données lues / utilisées ensemble sont-elles également stockées ensemble ou prenez-vous des morceaux ici et là?

  • Alignement de la mémoire : vos doubles sont-ils réellement alignés sur 4 octets? Comment avez-vous emballé votre structs? Pour être pédant, utilisez posix_memalignau lieu de malloc.

  • Efficacité du cache : Locality prend en charge la plupart des problèmes d’efficacité du cache, mais si vous avez souvent de petites structures de données que vous lisez / écrivez, il est utile qu’il s’agisse d’un multiple entier ou d’une fraction d’une ligne de cache (généralement de 64 octets). Cela aide également si vos données sont alignées sur la taille d'une ligne de cache. Cela peut réduire considérablement le nombre de lectures nécessaires pour charger une donnée.

  • Vectorisation : Non, n'allez pas de l'avant avec l'assembleur codé à la main. gccoffre des types de vecteurs qui sont traduits en SSE / AltiVec / quelles que soient les instructions automatiquement.

  • Parallélisme au niveau de l'instruction : le fils bâtard de la vectorisation. Si certains calculs souvent répétés ne vectorisent pas bien, vous pouvez essayer d’accumuler des valeurs d’entrée et de calculer plusieurs valeurs à la fois. C'est un peu comme une boucle qui se déroule. Ce que vous exploitez ici, c'est que votre CPU aura généralement plus d'une unité à virgule flottante par cœur.

  • Précision arithmétique : Avez-vous vraiment besoin d'arithmétique à double précision dans tout ce que vous faites? Par exemple, si vous calculez une correction dans une itération de Newton, vous n'avez généralement pas besoin de tous les chiffres que vous calculez. Pour une discussion plus approfondie, voir cet article.

Certaines de ces astuces sont utilisées dans daxpy_cvec ce fil. Cela dit, si vous utilisez Fortran (pas un langage de bas niveau dans mes livres), vous aurez très peu de contrôle sur la plupart de ces "astuces".

Si vous utilisez du matériel dédié, par exemple un cluster que vous utilisez pour toutes vos exécutions en production, vous pouvez également consulter les spécificités des processeurs utilisés. Non pas que vous deviez écrire directement dans assembleur des éléments pour cette architecture, mais cela pourrait vous inciter à rechercher d'autres optimisations que vous avez peut-être manquées. Connaître une fonctionnalité est une première étape nécessaire à l'écriture d'un code capable de l'exploiter.

Mise à jour

Cela fait un moment que j'ai écrit cela et je n'avais pas remarqué que c'était devenu une réponse si populaire. Pour cette raison, j'aimerais ajouter un point important:

  • Parlez à votre informaticien local : Ne serait-il pas intéressant qu’il existe une discipline qui se consacre exclusivement à rendre les algorithmes et / ou les calculs plus efficaces / élégants / parallèles, et nous pourrions tous leur demander conseil? Eh bien, bonne nouvelle, cette discipline existe: l’informatique. Il y a de fortes chances que votre institution dispose même d'un département entier. Parlez à ces gars.

Je suis sûr que pour un certain nombre de non-informaticiens, cela ramènera des souvenirs de discussions frustrantes avec ladite discipline qui n'ont conduit à rien, ou de souvenirs des anecdotes d'autres personnes à ce sujet. Ne vous découragez pas. La collaboration interdisciplinaire est une tâche délicate, qui demande un peu de travail, mais les avantages peuvent être énormes.

D'après mon expérience, en tant qu'informaticien (CS), l'astuce consiste à répondre correctement aux attentes et à la communication.

En termes d’ attente , un CS ne vous aidera que s’il / elle pense que votre problème est intéressant. Cela exclut pratiquement d’essayer d’optimiser / vectoriser / paralléliser un morceau de code que vous avez écrit, mais pas vraiment commenté, pour un problème qu’ils ne comprennent pas. Les CS sont généralement plus intéressés par le problème sous-jacent, par exemple les algorithmes utilisés pour le résoudre. Ne leur donnez pas votre solution , donnez-leur votre problème .

En outre, préparez-vous à ce que le CS dise " ce problème a déjà été résolu " et vous donne simplement une référence à un document. Un conseil: lisez ce document et, s'il s'applique vraiment à votre problème, implémentez l'algorithme proposé. Ce n'est pas un CS en train de faire un malin, c'est un CS qui vient de vous aider Ne soyez pas offensé, rappelez-vous: si le problème n’est pas intéressant du point de vue calcul, c’est-à-dire qu’il a déjà été résolu et que la solution qui s’avère optimale, ils ne fonctionneront pas, encore moins le coder pour vous.

Sur le plan de la communication , rappelez-vous que la plupart des CS ne sont pas des experts dans votre domaine et expliquez le problème en termes de ce que vous faites, par opposition à comment et pourquoi . Habituellement, nous ne nous soucions pas vraiment du pourquoi , et du comment , eh bien, de ce que nous faisons le mieux.

Par exemple, je travaille actuellement avec un groupe de cosmologistes informaticiens sur l'écriture d'une meilleure version de leur code de simulation, basée sur SPH et Multipoles . Il a fallu environ trois réunions pour arrêter de parler en termes de matière noire et de halos de galaxie (hein?) Et d’approfondir au cœur du calcul, c’est-à-dire qu’il faut trouver tous les voisins dans un rayon donné de chaque particule, en calculer quantité sur eux, puis repasser sur tous les voisins et appliquer cette quantité dans un autre calcul. Ensuite, déplacez les particules, ou au moins certaines d’entre elles, et recommencez. Vous voyez, bien que le premier puisse être incroyablement intéressant (c'est le cas!), C'est ce que j'ai besoin de comprendre pour commencer à penser aux algorithmes.

Mais je me démarque de l’essentiel: si vous souhaitez vraiment faire votre calcul rapidement et que vous n’êtes pas un informaticien, parlez-en à un.

Pedro
la source
4
En ce qui concerne les outils de profilage, je n’oublierais pas Valgrind .
GertVdE
1
Je suis d’accord avec toi Pedro, alors que le programme en cours d’optimisation ressemble à une voiture de course F1, déjà proche de l’optimum. Les programmes que je vois dans la pratique, qu'ils soient scientifiques ou non, ressemblent souvent davantage à Cadillac Coupe DeVilles. Pour obtenir de réelles performances, vous pouvez éliminer des tonnes de graisse. Après cela, le cycle-rasage commence à frapper sa foulée.
Mike Dunlavey
1
@ MikeDunlavey: Complètement d'accord. J'ai ajouté une mise à jour à ma réponse pour résoudre davantage de problèmes liés à l'algorithme.
Pedro
1
@MikeDunlavey, je suis un CS folk :)
Pedro
2
Je l'ai démontré lors d'une conférence à U Mass. Lowell. C'était une démonstration en direct, montrant toutes les étapes de l'accélération 730x. Je pense qu'un professeur a compris le point, sur une demi-douzaine.
Mike Dunlavey
38

Les logiciels scientifiques ne diffèrent pas beaucoup des autres logiciels en ce qui concerne la manière de savoir ce qui doit être réglé.

La méthode que j'utilise est la pause aléatoire . Voici quelques exemples d'accélérations qu'il a trouvées pour moi:

Si une grande partie du temps est passée dans des fonctions comme loget exp, je peux voir quels sont les arguments de ces fonctions, en fonction des points à partir desquels elles sont appelées. Souvent, ils sont appelés à plusieurs reprises avec le même argument. Si c'est le cas, la mémorisation produit un facteur d'accélération énorme.

Si j'utilise les fonctions BLAS ou LAPACK, il se peut que je trouve qu'une grande partie du temps est consacrée aux routines pour copier des tableaux, multiplier des matrices, transformer de choleski, etc.

  • La routine pour copier des tableaux n’est pas là pour la vitesse, mais pour la commodité. Vous trouverez peut-être un moyen moins pratique, mais plus rapide, de le faire.

  • Les routines pour multiplier ou inverser les matrices, ou effectuer des transformations choleski, ont tendance à avoir des arguments de caractères spécifiant des options, telles que 'U' ou 'L' pour le triangle supérieur ou inférieur. Encore une fois, ceux-ci sont là pour plus de commodité. Ce que j’ai trouvé, c’est que, comme mes matrices n’étaient pas très grosses, les routines passaient plus de la moitié de leur temps à appeler le sous-programme permettant de comparer des caractères uniquement pour déchiffrer les options. L’écriture de versions spéciales des routines mathématiques les plus coûteuses a entraîné une accélération considérable.

Si je peux m'étendre sur le dernier point: la routine de multiplication de matrice DGEMM appelle LSAME pour décoder ses arguments de caractères. En examinant le pourcentage de temps global (la seule statistique qui vaille la peine d'être regardé), les profileurs considérés comme "bons" pourraient montrer que DGEMM utilise un pourcentage du temps total, tel que 80%, et LSAME, utilisant un pourcentage du temps total, tel que 50%. En regardant l'ancien, vous seriez tenté de dire "il doit être fortement optimisé, donc je ne peux rien faire à ce sujet". En regardant ce dernier, vous seriez tenté de dire "Hein? Qu'est-ce que c'est? Qu'est-ce que c'est? Ce n'est qu'une routine minuscule. Ce profileur doit se tromper!"

Ce n'est pas faux, c'est juste ne pas vous dire ce que vous devez savoir. Ce que la pause aléatoire vous montre, c'est que DGEMM est sur 80% des échantillons de pile et que LSAME est sur 50%. (Vous n'avez pas besoin de beaucoup d'échantillons pour détecter cela. 10, c'est généralement beaucoup.) De plus, sur beaucoup de ces échantillons, DGEMM est en train d'appeler LSAME à partir de deux lignes de code différentes.

Alors maintenant, vous savez pourquoi les deux routines prennent autant de temps inclusif. Vous savez également où, dans votre code, ils sont appelés pour passer tout ce temps. C'est pourquoi j'utilise des pauses aléatoires et jette un regard noir sur les profileurs, peu importe leur qualité. Ils sont plus intéressés à obtenir des mesures qu'à vous dire ce qui se passe.

Il est facile de supposer que les routines de la bibliothèque mathématique ont été optimisées au nième degré, mais en réalité, elles ont été optimisées pour pouvoir être utilisées à des fins très diverses. Vous devez voir ce qui se passe réellement et non ce qui est facile à supposer.

ADDED: Donc pour répondre à vos deux dernières questions:

Quelles sont les choses les plus importantes à essayer en premier?

Prélevez 10 à 20 échantillons de pile et ne vous contentez pas de les résumer, comprenez ce que chacun vous dit. Faites ceci en premier, dernier et entre les deux. (Il n'y a pas "d'essayer", jeune Skywalker.)

Comment savoir combien de performances je peux obtenir?

Xβ(s+1,(n-s)+1)sn1/(1-X)n=dixs=5X
entrez la description de l'image ici
XX

Comme je vous l’ai déjà dit, vous pouvez répéter l’ensemble de la procédure jusqu’à ce que vous ne puissiez plus vous en passer, et le taux d’accélération composé peut être assez important.

(s+1)/(n+2)=3/22=13.6%.) La courbe inférieure du graphique suivant représente sa distribution:

entrez la description de l'image ici

Considérez si nous avons prélevé jusqu'à 40 échantillons (plus que ce que j'ai jamais eu à la fois) et que nous n’avons vu un problème que sur deux d’entre eux. Le coût estimé (mode) de ce problème est de 5%, comme indiqué sur la courbe la plus haute.

Qu'est-ce qu'un "faux positif"? Si vous résolvez un problème, vous réalisez un gain tellement inférieur à celui attendu, vous regrettez de l'avoir résolu. Les courbes montrent (si le problème est "petit") que, même si le gain pourrait être inférieur à la fraction d'échantillons le montrant, il sera en moyenne plus important.

Il existe un risque beaucoup plus grave - un "faux négatif". C'est quand il y a un problème, mais il n'est pas trouvé. (Cela contribue au "biais de confirmation", où l'absence de preuve tend à être traitée comme une preuve d'absence.)

Ce que vous obtenez avec un profileur (un bon) est que vous obtenez la mesure beaucoup plus précise (donc moins de chance de faux positifs), au détriment des informations beaucoup moins précises sur ce que le problème en fait est (donc moins de chance de trouver et d' obtenir tout gain). Cela limite l'accélération globale qui peut être obtenue.

J'encourage les utilisateurs de profileurs à signaler les facteurs d'accélération qu'ils obtiennent réellement dans la pratique.


Il y a un autre point à faire re. La question de Pedro sur les faux positifs.

Il a mentionné qu'il pourrait y avoir une difficulté à s'attaquer aux problèmes mineurs dans un code hautement optimisé. (Pour moi, un petit problème est celui qui représente 5% ou moins du temps total.)

Comme il est tout à fait possible de construire un programme totalement optimal à l'exception de 5%, ce point ne peut être traité que de manière empirique, comme dans cette réponse . Pour généraliser à partir de l'expérience empirique, voici ce qui se passe:

Un programme, tel qu’il est écrit, contient généralement plusieurs possibilités d’optimisation. (On peut les appeler "problèmes" mais ce sont souvent un code parfaitement correct, simplement susceptible d'une amélioration considérable.) ... que, une fois trouvés et corrigés, économisez 30%, 21%, etc. sur les 100 originaux.

entrez la description de l'image ici

Notez que le problème F coûte 5% du temps initial, il est donc "petit" et difficile à trouver sans 40 échantillons ou plus.

Cependant, les 10 premiers échantillons trouvent facilement le problème A. ** Une fois le problème résolu, le programme ne prend que 70 secondes, pour une accélération de 100/70 = 1,43x. Cela rend non seulement le programme plus rapide, mais il amplifie, par ce rapport, les pourcentages pris par les problèmes restants. Par exemple, le problème B prenait à l'origine 21, soit 21% du total, mais après suppression de A, B prend 21 sur 70, soit 30%, de sorte qu'il est plus facile de rechercher le processus complet répété.

Une fois le processus répété cinq fois, le temps d'exécution est maintenant de 16,8 secondes, le problème F étant de 30% et non de 5%. 10 échantillons le trouvent facilement.

Donc c'est le point. De manière empirique, les programmes contiennent une série de problèmes ayant une distribution de tailles, et tout problème trouvé et résolu facilite la recherche des problèmes restants. Pour ce faire, aucun des problèmes ne peut être ignoré car, s’ils le sont, ils prennent le temps, limitant l’accélération totale et n’amplifiant pas les problèmes restants. C'est pourquoi il est très important de trouver les problèmes qui se cachent .

Si les problèmes A à F sont trouvés et résolus, l'accélération est 100 / 11.8 = 8.5x. Si l’un d’eux manque, par exemple D, l’accélération n’est que de 100 / (11.8 + 10.3) = 4.5x. C'est le prix payé pour les faux négatifs.

Donc, quand le profileur dit "il ne semble pas y avoir de problème significatif ici" (c’est-à-dire un bon codeur, c’est un code pratiquement optimal), c’est peut-être vrai et peut-être que non. (Un faux négatif .) Vous ne savez pas avec certitude s'il y a plus de problèmes à résoudre, pour une accélération plus rapide, à moins que vous n'utilisiez une autre méthode de profilage et que vous en découvriez. D'après mon expérience, la méthode de profilage ne nécessite pas un grand nombre d'échantillons, résumés, mais un petit nombre d'échantillons, où chaque échantillon est suffisamment bien compris pour reconnaître toute possibilité d'optimisation.

2/0,3=6.671 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

Xβ(s+1,(n-s)+1)nsy1/(1-X)Xyy-1Distribution BetaPrime . Je l'ai simulé avec 2 millions d'échantillons, aboutissant à ce comportement:

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

(n+1)/(n-s)s=ny

Ceci est une représentation graphique de la distribution des facteurs d'accélération et de leurs moyennes pour 2 résultats positifs sur 5, 4, 3 et 2 échantillons. Par exemple, si 3 échantillons sont pris et que 2 d’entre eux sont des occurrences d’un problème et que ce problème peut être supprimé, le facteur d’accélération moyen serait de 4x. Si les 2 résultats sont vus dans seulement 2 échantillons, l'accélération moyenne est indéfinie - conceptuellement, car les programmes avec des boucles infinies existent avec une probabilité non nulle!

entrez la description de l'image ici

Mike Dunlavey
la source
1
Uhm ... N'obtenez-vous pas exactement ces informations sous forme de graphiques d'appel de profileur ou de résumés de type "bottom-up" fournis par VTune?
Pedro
2
@ Pedro: Si seulement. Dans un échantillon de pile (& variables connexes) est codé la raison complète pour laquelle un incrément de temps est utilisé. Vous ne pouvez pas vous en débarrasser sans savoir pourquoi. Certains problèmes peuvent être trouvés avec des informations limitées, mais pas tous . Si vous n’en obtenez que quelques-uns, mais pas tous, les problèmes qui ne vous sont pas imputés vous empêchent d’accélérer les choses. Vérifiez ici et ici .
Mike Dunlavey
On peut soutenir que vous comparez votre méthode à un mauvais profilage ... Vous pouvez également parcourir le profil de chaque routine, indépendamment de sa contribution au temps total d'exécution, et rechercher des améliorations, avec le même effet. Ce qui m'inquiète dans votre approche, c'est le nombre croissant de faux positifs que vous finirez par traquer au fur et à mesure que les "points chauds" de votre code deviennent de plus en plus petits.
Pedro
@ Pedro: Continuez simplement à prendre des échantillons jusqu'à ce que vous voyiez quelque chose que vous pouvez corriger sur plusieurs échantillons. La distr bêta dit combien elle peut économiser, si vous y tenez, mais si vous craignez une accélération moins rapide que cela ne le montre, sachez que vous éliminez le risque que cela puisse aussi être plus important (et que cela est asymétrique à droite). ). Le plus grand danger, avec les profileurs de synthèse, est les faux négatifs . Il peut y avoir un problème, mais vous êtes juste en espérant votre intuition renifler quand le profileur est d' être très non précisé où il pourrait être.
Mike Dunlavey
@Pedro: La seule faiblesse que je connaisse est le moment où, en regardant un instantané, vous ne pouvez pas comprendre pourquoi ce temps est dépensé, par exemple s'il traite simplement des événements asynchrones où le demandeur se cache, ou des protocoles asynchrones. Pour un code plus "normal", montrez-moi un "bon" profileur et je vous montrerai un problème avec lequel il a des problèmes ou qu'il ne peut tout simplement pas trouver (vous obligeant à vous rabaisser sur votre intelligence infaillible). Généralement, la manière de construire un tel problème est de s’assurer que l’objet visé ne peut pas être déchiffré localement. Et de tels problèmes abondent dans les logiciels.
Mike Dunlavey
23

Non seulement vous devez avoir une connaissance intime de votre compilateur , vous avez également une connaissance intime de votre architecture cible et de votre système d'exploitation .

Qu'est-ce qui peut affecter les performances?

Si vous souhaitez optimiser les performances, chaque fois que vous modifiez votre architecture cible, vous devrez peaufiner et réoptimiser votre code. Quelque chose qui était une optimisation avec un processeur peut devenir sous-optimal lors de la prochaine révision de ce même processeur.

Un excellent exemple de ceci serait le cache du processeur. Déplacez votre programme d'un processeur doté d'un petit cache rapide vers un processeur doté d'un cache légèrement plus lent et légèrement plus volumineux, et votre profilage pourrait changer considérablement.

Même si l'architecture cible ne change pas, les modifications de bas niveau apportées à un système d'exploitation peuvent également affecter les performances. Les correctifs d'atténuation Spectre et Meltdown ont eu un impact considérable sur certaines charges de travail. Ils pourraient donc forcer une réévaluation de vos optimisations.

Comment puis-je garder mon code optimisé?

Lorsque vous développez un code hautement optimisé, vous devez le garder modulaire et faciliter l’échange de différentes versions du même algorithme, éventuellement en sélectionnant même la version spécifique utilisée au moment de l’exécution, en fonction des ressources disponibles et de la taille / complexité du logiciel. données à traiter.

Modularité signifie également pouvoir utiliser la même suite de tests sur toutes vos versions optimisées et non optimisé, vous permettant de vérifier que tous ont le même comportement et le profil de chacun rapidement dans un like-for-like comparaison. Je vais un peu plus en détail dans ma réponse à Comment documenter et enseigner aux autres un code de calcul intensif «optimisé au-delà de la reconnaissance»? .

Lectures complémentaires

En outre, je vous recommanderais vivement de jeter un coup d'œil à l'excellent article de Ulrich Drepper intitulé Tout programmeur doit savoir sur la mémoire , dont le titre est un hommage à David Goldberg, qui est tout aussi fantastique que Tout informaticien sur l'arithmétique en virgule flottante .

N'oubliez pas que chaque optimisation a le potentiel de devenir une future anti-optimisation , elle doit donc être considérée comme une éventuelle odeur de code, à conserver au minimum. Ma réponse à La micro-optimisation est-elle importante lors du codage? fournit un exemple concret de cette expérience personnelle.

Mark Booth
la source
8

Je pense que vous formulez la question de manière trop étroite. À mon avis, une attitude utile consiste à croire que seules des modifications apportées aux structures de données et aux algorithmes peuvent générer des gains de performance significatifs sur des codes de plus de 100 lignes, et je crois que je n'ai pas encore trouvé de contre-exemple. cette revendication.

Wolfgang Bangerth
la source
3
Accord de principe, mais il ne faut pas sous-estimer l'interaction entre la performance d'un algorithme / structure de données et les détails du matériel sous-jacent. Par exemple, les arbres binaires équilibrés sont parfaits pour la recherche / stockage de données, mais en fonction de la latence de la mémoire globale, une table de hachage peut être meilleure.
Pedro
1
D'accord. Les algorithmes et la structure de données peuvent apporter des améliorations de O (10) à O (100). Toutefois, pour quelques problèmes délimités par le calcul (comme dans les calculs de dynamique moléculaire, l'astrophysique, le traitement d'images et de vidéos en temps réel, la finance), une boucle critique hautement optimisée peut signifier une exécution globale de l'application 3x à 10x plus rapide.
fcruz
J'ai vu des boucles imbriquées mal ordonnées dans des codes de "production" de taille importante. Autre que cela, je pense que vous avez raison.
dmckee
8

La toute première chose à faire est de profiler votre code. Vous voulez savoir quelles parties de votre programme vous ralentissent avant de commencer à optimiser, sinon vous pourriez finir par optimiser une partie de votre code qui ne prenait pas beaucoup de temps d'exécution de toute façon.

Linux

gprof est très bon, mais il ne vous dit que le temps pris par chaque fonction plutôt que par chaque ligne.

Apple OS X

Vous voudrez peut-être essayer Shark . Il est disponible sur le site de développement Apple sous Téléchargements> Outils de développement> CHUD 4.6.2, l'ancienne version ici . CHUD contient également d’autres outils de profilage tels que l’interface BigTop, l’outil de recherche PMC Index, le profileur Saturn et de nombreuses autres commandes. Shark viendra avec une version en ligne de commande.

Dan
la source
+1 profil? Oui, d’une certaine manière ... C’est bien mieux que de deviner, mais voici une liste de problèmes qui s’appliquent plus particulièrement à gprof et à de nombreux autres profileurs.
Mike Dunlavey
Shark est-il une ancienne commande sous OS X? Plus ici . Avec Mountain Lion, devrais-je utiliser des instruments?
hhh
@hhh: C'était un profileur graphique pour les macs, bien qu'il semble qu'il ne soit plus maintenu. Je n'ai pas programmé sur une machine Apple depuis que j'ai écrit cette réponse, je ne peux donc pas vous aider beaucoup.
Dan
1
Il est disponible sur le site Apple Developer sous Téléchargements> Outils de développement> CHUD 4.6.2. L'ancienne version ici contient toutes sortes d'éléments de profilage. Malheureusement, cette installation n'a pas abouti: "Contactez le fabricant", aucune idée du bogue. Shark a été retiré du Xcode apparemment après Lion, puis remis sur le site Apple Dev après avoir été un outil gratuit dans MacUpdate.
hhh
@hhh: Vous semblez plus qualifié que moi pour répondre à cette question. N'hésitez pas à modifier ma réponse pour la mettre à jour ou à écrire la vôtre.
Dan
7

En ce qui concerne les performances que vous pouvez obtenir, prenez les résultats du profilage de votre code et supposons que vous identifiiez un élément prenant "p" une fraction du temps. Si vous deviez améliorer les performances de cette pièce uniquement avec un facteur "s", votre accélération globale sera de 1 / ((1-p) + p / s). Par conséquent, vous pouvez augmenter votre vitesse au maximum d'un facteur 1 / (1-p). Espérons que vous avez des zones de haute p! C'est l'équivalent de la loi d' Amdahl pour l'optimisation en série.

skillman
la source
5

Optimiser votre code doit être fait avec soin. Supposons également que vous avez déjà débogué le code. Vous pouvez économiser beaucoup de temps si vous suivez certaines priorités, à savoir:

  1. Utilisez des bibliothèques hautement optimisées (ou professionnellement optimisées) dans la mesure du possible. Quelques exemples peuvent inclure FFTW, OpenBlas, Intel MKL, bibliothèques NAG, etc. Sauf si vous êtes très talentueux (comme le développeur de GotoBLAS), vous ne pouvez probablement pas battre les professionnels.

  2. Utilisez un profileur (plusieurs dans la liste ci-dessous ont déjà été nommés dans ce fil - Intel Tune, valgrind, gprof, gcov, etc.) pour déterminer quelles parties de votre code prennent le plus de temps. Inutile de perdre du temps à optimiser des portions de code rarement appelées.

  3. Dans les résultats du profileur, examinez la partie de votre code qui a pris le plus de temps. Déterminez la nature de votre algorithme: est-il lié au processeur ou à la mémoire? Chacune nécessite un ensemble différent de techniques d'optimisation. Si vous rencontrez de nombreuses erreurs de cache, la mémoire peut constituer le goulot d'étranglement: le processeur gaspille des cycles d'horloge en attendant que la mémoire soit disponible. Déterminez si la boucle est compatible avec le cache L1 / L2 / L3 de votre système. Si vous avez des instructions "if" dans votre boucle, vérifiez si le profileur dit quoi que ce soit à propos d'une mauvaise prédiction de branche? Quelle est la peine de mauvaise prédiction de branche de votre système? En passant, vous pouvez obtenir des données sur les erreurs de prédiction de branche à partir des manuels de référence d’optimisation Intel [1]. Notez que la pénalité d'erreur de prédiction de branche est spécifique au processeur, comme vous le verrez dans le manuel Intel.

  4. Enfin, résolvez les problèmes identifiés par le profileur. Un certain nombre de techniques ont déjà été discutées ici. Un certain nombre de ressources d'optimisation complètes, fiables et complètes sont également disponibles. Pour n'en nommer que deux, il existe Intel Optimization Reference Manual [1] et les cinq manuels d'optimisation d'Agner Fog [2]. Notez que si le compilateur le fait déjà, vous n'aurez peut-être pas besoin de faire certaines choses - par exemple, dérouler des boucles, aligner la mémoire, etc. Lisez attentivement la documentation de votre compilateur.

Références:

[1] Manuel de référence de l'optimisation des architectures Intel 64 et IA-32: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf.

[2] Agner Fog, "Ressources d'optimisation logicielle": http://www.agner.org/optimize/

  • "Optimiser les logiciels en C ++: Guide d'optimisation pour les plateformes Windows, Linux et Mac"
  • "Optimisation des sous-routines en langage assembleur: guide d'optimisation pour les plates-formes x86"
  • "La microarchitecture des processeurs Intel, AMD et VIA: un guide d'optimisation pour les programmeurs d'assemblage et les fabricants de compilateurs"
  • "Tableaux d'instructions: listes des latences des instructions, des débits et des pannes de micro-opérations pour les processeurs Intel, AMD et VIA"
  • "Conventions d'appel pour différents compilateurs C ++ et systèmes d'exploitation"
nathanielng
la source
3

Je ne suis pas un scientifique en informatique comme beaucoup d'autres ici (je peux donc me tromper :)), mais de nos jours, il est inutile de passer trop de temps à la performance en série tant que nous utilisons des bibliothèques standard. Il serait peut-être plus intéressant de consacrer plus de temps / d’efforts à rendre le code plus évolutif.

Quoi qu'il en soit, voici deux exemples (si vous ne les avez pas déjà lus) de l'amélioration des performances (pour les problèmes de FE non structurés).

Série : voir la deuxième moitié du résumé et du texte associé.

Parallèle : spécialement la phase d'initialisation, en secondes 4.2.

Stali
la source
3

C'est peut-être plus une méta-réponse qu'une réponse ...

Vous devez développer une familiarité intime avec votre compilateur. Vous pouvez l’acquérir plus efficacement en lisant le manuel et en expérimentant les options.

Une grande partie des bons conseils donnés par @Pedro peut être mise en œuvre en ajustant la compilation plutôt que le programme.

Marque de haute performance
la source
Je ne suis pas d'accord avec le dernier point. Savoir ce que votre compilateur peut faire est une chose, mais écrire votre code pour que votre compilateur puisse réellement faire quelque chose avec cela est un problème totalement différent. Aucun indicateur de compilateur ne permet de trier vos données, d’utiliser une précision plus faible au besoin ou de réécrire vos boucles les plus internes de sorte qu’elles ne comportent que peu ou pas de branches. Connaître votre compilateur est une bonne chose, mais cela ne fera que vous aider à écrire un meilleur code, cela ne le rendra pas meilleur en soi.
Pedro
1

Un moyen facile de profiler un programme (sous Linux) consiste à utiliser perfen statmode. La manière la plus simple est juste de l'exécuter comme

perf stat ./my_program args ...

et cela vous donnera un tas de statistiques de performances utiles:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

Parfois, il liste également les charges et les échecs de D-cache. Si vous constatez de nombreuses défaillances de cache, votre programme consomme beaucoup de mémoire et ne traite pas correctement les caches. De nos jours, les processeurs deviennent plus rapides que la bande passante de la mémoire et le problème vient toujours des accès à la mémoire.

Vous pouvez également essayer de déterminer le perf record ./my_program; perf reportmoyen le plus simple. Lisez les pages de manuel pour en savoir plus.

Mark Lakata
la source