Question Stratégies d'optimisation des performances de dernier recours [fermé]


Il y a déjà beaucoup de questions de performance sur ce site, mais il me semble que presque toutes sont très spécifiques au problème et assez étroites. Et presque tous répètent le conseil pour éviter une optimisation prématurée.

Assumons:

  • le code fonctionne déjà correctement
  • les algorithmes choisis sont déjà optimaux pour les circonstances du problème
  • le code a été mesuré, et les routines incriminées ont été isolées
  • toutes les tentatives d'optimisation seront également mesurées pour s'assurer qu'elles ne font pas qu'empirer les choses

Ce que je cherche ici, ce sont des stratégies et des astuces pour se faufiler jusqu'aux derniers pourcentages dans un algorithme critique quand il n'y a plus rien à faire mais tout ce qu'il faut.

Idéalement, essayez de rendre les réponses agnostiques, et indiquez les éventuels inconvénients des stratégies suggérées, le cas échéant.

J'ajouterai une réponse avec mes propres suggestions initiales, et j'attendrai avec impatience tout ce dont la communauté Stack Overflow pourra penser.


561
2018-05-29 14:38


origine


Réponses:


OK, vous définissez le problème à l'endroit où il semble qu'il n'y a pas beaucoup de place pour l'amélioration. C'est plutôt rare, d'après mon expérience. J'ai essayé d'expliquer cela dans un article de Dr. Dobbs en novembre 1993, en partant d'un programme non trivial conventionnellement bien conçu sans gaspillage évident et en passant par une série d'optimisations jusqu'à ce que son temps de travail soit réduit de 48 secondes à 1,1 seconde, et la taille du code source a été réduite d'un facteur 4. Mon outil de diagnostic était-ce. La séquence des changements était la suivante:

  • Le premier problème rencontré était l'utilisation de clusters de listes (maintenant appelés "itérateurs" et "classes de conteneurs") représentant plus de la moitié du temps. Ceux-ci ont été remplacés par du code assez simple, ce qui a réduit le temps à 20 secondes.

  • Maintenant, le plus grand preneur de temps est plus de construction de liste. En pourcentage, ce n'était pas si grand auparavant, mais maintenant c'est parce que le plus gros problème a été supprimé. Je trouve un moyen de l'accélérer, et le temps passe à 17 sec.

  • Maintenant, il est plus difficile de trouver des coupables évidents, mais il y en a quelques-uns plus petits que je peux faire quelque chose, et le temps tombe à 13 sec.

Maintenant, j'ai l'impression d'avoir frappé un mur. Les échantillons me disent exactement ce qu'il fait, mais je n'arrive pas à trouver quelque chose que je puisse améliorer. Ensuite, je réfléchis sur la conception de base du programme, sur sa structure axée sur les transactions, et je demande si toute la recherche de liste qu'il fait est réellement mandatée par les exigences du problème.

Ensuite, je suis tombé sur un re-design, où le code du programme est généré (via des macros préprocesseur) à partir d'un petit ensemble de sources, et dans lequel le programme ne comprend pas toujours des choses prévisibles. En d'autres termes, n'interprétez pas la séquence des choses à faire, ne la «compilez» pas.

  • Cette refonte est effectuée, en réduisant le code source d'un facteur 4, et le temps est réduit à 10 secondes.

Maintenant, parce que cela devient si rapide, il est difficile d'échantillonner, donc je lui donne 10 fois plus de travail, mais les temps suivants sont basés sur la charge de travail d'origine.

  • Plus de diagnostic révèle qu'il passe du temps dans la gestion des files d'attente. Cela réduit le temps à 7 secondes.

  • Maintenant, un grand temps est l'impression diagnostique que je faisais. Rincer cela - 4 secondes.

  • Maintenant, les plus grands preneurs de temps sont les appels à malloc et gratuit. Recycler les objets - 2,6 secondes.

  • Continuant à échantillonner, je trouve toujours des opérations qui ne sont pas strictement nécessaires - 1,1 secondes.

Facteur d'accélération total: 43,6

Maintenant, il n'y a pas deux programmes identiques, mais dans un logiciel non-jouet, j'ai toujours vu une progression comme celle-ci. D'abord, vous obtenez les choses faciles, puis le plus difficile, jusqu'à ce que vous arriviez à un point de rendements décroissants. Ensuite, la perspicacité que vous gagnez peut conduire à une nouvelle conception, en commençant une nouvelle série d'accélérations, jusqu'à ce que vous touchiez de nouveau des rendements décroissants. Maintenant, c'est le point où il peut être logique de se demander si ++i ou i++ ou for(;;) ou while(1) sont plus rapides: les types de questions que je vois si souvent sur SO.

P.S. On peut se demander pourquoi je n'ai pas utilisé de profileur. La réponse est que presque chacun de ces "problèmes" était un site d'appel de fonction, qui empilait des échantillons. Les profileurs, même aujourd'hui, arrivent à peine à l'idée que les instructions et les instructions d'appel sont plus importantes à trouver, et plus faciles à résoudre, que des fonctions entières. En fait, j'ai construit un profileur pour faire cela, mais pour une réelle intimité avec le code, il n'y a pas de substitut pour y mettre les doigts. Ce n'est pas un problème que le nombre d'échantillons est faible, car aucun des problèmes rencontrés sont si minuscules qu'ils sont facilement manqués.

AJOUTÉ: jerryjvl a demandé des exemples. Voici le premier problème. Il se compose d'un petit nombre de lignes de code séparées, prenant ensemble plus de la moitié du temps:

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

Ils utilisaient le cluster de liste ILST (similaire à une classe de liste). Ils sont implémentés de la manière habituelle, avec une "dissimulation d'information" signifiant que les utilisateurs de la classe n'étaient pas censés se préoccuper de la façon dont ils étaient implémentés. Quand ces lignes ont été écrites (sur environ 800 lignes de code), on n'a pas pensé à l'idée que celles-ci pourraient être un «goulot d'étranglement» (je déteste ce mot). Ils sont simplement la façon recommandée de faire les choses. C'est facile à dire avec le recul que cela aurait dû être évité, mais d'après mon expérience tout les problèmes de performance sont comme ça. En général, il est bon d'essayer d'éviter de créer des problèmes de performances. Il est même préférable de trouver et de réparer ceux qui sont créés, même s'ils "auraient dû être évités" (en rétrospective). J'espère que cela donne un peu de saveur.

Voici le deuxième problème, en deux lignes distinctes:

 /* ADD TASK TO TASK LIST */ 
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

Ce sont des listes de construction en ajoutant des éléments à leurs fins. (Le correctif consistait à collecter les éléments dans les tableaux et à générer les listes en une seule fois.) Ce qui est intéressant, c'est que ces instructions ne coûtent que (c'est-à-dire étaient sur la pile) 3/48 du temps d'origine. fait un gros problème au début. Cependant, après avoir enlevé le premier problème, ils coûtent 3/20 du temps et étaient donc maintenant un "poisson plus gros". En général, c'est comme ça que ça se passe.

Je pourrais ajouter que ce projet a été distillé à partir d'un vrai projet que j'ai aidé. Dans ce projet, les problèmes de performance étaient beaucoup plus dramatiques (tout comme les accélérations), comme l'appel d'une routine d'accès à la base de données dans une boucle interne pour voir si une tâche était terminée.

RÉFÉRENCE AJOUTÉE: Le code source, original et redessiné, peut être trouvé dans www.ddj.com, pour 1993, dans le fichier 9311.zip, les fichiers slug.asc et slug.zip.

EDIT 2011/11/26: Il y a maintenant un projet sourceforge contenant le code source dans Visual C ++ et une description de la façon dont il a été accordé. Il ne traverse que la première moitié du scénario décrit ci-dessus, et il ne suit pas exactement la même séquence, mais obtient toujours une accélération de 2-3 ordres de grandeur.


402
2018-05-29 14:32



Suggestions:

  • Pré-calculer plutôt que recalculer: toutes les boucles ou appels répétés qui contiennent des calculs ayant une plage d'entrées relativement limitée, pensez à créer une recherche (tableau ou dictionnaire) contenant le résultat de ce calcul pour toutes les valeurs de la plage valide d'entrées. Ensuite, utilisez une recherche simple dans l'algorithme à la place.
    Bas-côtés: si peu de valeurs pré-calculées sont réellement utilisées, cela peut empirer les choses, la recherche peut aussi prendre beaucoup de mémoire.
  • Ne pas utiliser les méthodes de bibliothèque: la plupart des bibliothèques doivent être écrites pour fonctionner correctement dans un large éventail de scénarios, et effectuer des vérifications nuls sur les paramètres, etc. En ré-implémentant une méthode, vous pouvez être en mesure d'éliminer une grande partie de la logique qui ne s'applique pas circonstance vous l'utilisez.
    Bas-côtés: écrire du code supplémentaire signifie plus de surface pour les bogues.
  • Utiliser les méthodes de bibliothèque: pour me contredire, les bibliothèques de langues sont écrites par des gens qui sont beaucoup plus intelligents que vous ou moi; les chances sont qu'ils l'ont fait mieux et plus vite. Ne l'implémentez pas vous-même à moins que vous ne puissiez le rendre plus rapide (c'est-à-dire: mesurez toujours!)
  • Tricher: dans certains cas, bien qu'un calcul exact puisse exister pour votre problème, vous n'avez pas besoin de 'exact', parfois une approximation peut être 'assez bonne' et beaucoup plus rapide dans le deal. Demandez-vous, est-ce vraiment important si la réponse est de 1%? 5%? même 10%?
    Bas-côtés: Eh bien ... la réponse ne sera pas exacte.

178
2018-05-29 14:42



Lorsque vous ne pouvez plus améliorer la performance, voyez si vous pouvez améliorer perçu la performance à la place.

Vous ne serez peut-être pas en mesure de rendre votre algorithme fooCalc plus rapide, mais il existe souvent des moyens de rendre votre application plus réactive à l'utilisateur.

Quelques exemples:

  • anticiper ce que l'utilisateur va demander et commencer à travailler sur ce avant cette date
  • afficher les résultats en ils viennent, au lieu de tout à la fois à la fin
  • Précis progrès

Ceux-ci ne rendront pas votre programme plus rapide, mais cela pourrait rendre vos utilisateurs plus heureux avec la vitesse que vous avez.


157
2018-05-29 14:32



Je passe la plus grande partie de ma vie dans cet endroit. Les larges traits sont pour exécuter votre profileur et l'obtenir pour enregistrer:

  • Cache rate. Le cache de données est la source n ° 1 de stalles dans la plupart des programmes. Améliorez le taux de succès du cache en réorganisant les structures de données offensantes pour avoir une meilleure localisation. regrouper les structures et les types numériques pour éliminer les octets gaspillés (et donc les récupérations de cache gaspillées); prélève des données dans la mesure du possible pour réduire les décrochages.
  • Load-hit-magasins. Les hypothèses du compilateur sur l'aliasing du pointeur et les cas où les données sont déplacées entre des ensembles de registres déconnectés via la mémoire peuvent provoquer un certain comportement pathologique qui provoque l'effacement de l'ensemble du pipeline du processeur lors d'une opération de chargement. Trouvez les endroits où les chars, les vecteurs et les ints sont moulés les uns aux autres et éliminez-les. Utilisation __restrict libéralement pour promettre le compilateur sur l'aliasing.
  • Opérations microcodées. La plupart des processeurs ont des opérations qui ne peuvent pas être pipelinées, mais exécutent à la place un petit sous-programme stocké dans la ROM. Les exemples sur le PowerPC sont multiplier, diviser et shift-by-variable-amount. Le problème est que tout le pipeline s'arrête de fonctionner pendant l'exécution de cette opération. Essayez d'éliminer l'utilisation de ces opérations ou au moins de les décomposer dans leurs opérations pipelined constituantes afin que vous puissiez bénéficier de l'envoi superscalaire sur tout ce que fait le reste de votre programme.
  • Mésaventures de la branche. Ceux-ci vident aussi le pipeline. Trouvez des cas où le processeur passe beaucoup de temps à remplir le canal après une branche, et utilisez l'indicateur de branche si disponible pour l'obtenir correctement plus souvent. Ou mieux encore, remplacer les branches par des mouvements conditionnels dans la mesure du possible, notamment après les opérations en virgule flottante parce que leur tuyau est généralement plus profond et en lisant les drapeaux de condition après que fcmp peut provoquer un décrochage.
  • Opérations séquentielles à virgule flottante. Faites ces SIMD.

Et une chose de plus que j'aime faire:

  • Définissez votre compilateur pour afficher les listes d'assemblage et regardez ce qu'il émet pour les fonctions de hotspot dans votre code. Toutes ces optimisations intelligentes qu'un "bon compilateur devrait pouvoir faire pour vous automatiquement"? Les chances sont que votre compilateur ne les fasse pas. J'ai vu GCC émettre vraiment du code WTF.

131



Jetez plus de matériel à elle!


76



Plus de suggestions:

  • Éviter les E / S: Toute E / S (disque, réseau, ports, etc.) est va toujours être beaucoup plus lent que tout code qui est effectuer des calculs, alors se débarrasser de toute E / S que vous faites pas strictement besoin.

  • Déplacer les E / S à l'avant: Chargez toutes les données que vous allez besoin d'un calcul à l'avance, de sorte que vous ne le faites pas avoir des attentes d'E / S répétées dans le noyau d'un algorithme (et peut-être par conséquent le disque répété cherche, quand charger toutes les données dans un coup peut éviter de chercher).

  • Retarder les E / S: Ne pas écrire vos résultats avant le le calcul est terminé, stockez-les dans une structure de données et puis vider dans une seule fois à la fin quand le dur travail est fait.

  • E / S fileté: Pour ceux qui osent assez, combiner 'I / O à l'avant »ou« Retarder les E / S »avec le calcul réel par déplacer le chargement dans un fil parallèle, de sorte que tout en vous chargez plus de données que vous pouvez travailler sur un calcul sur les données que vous avez déjà, ou pendant que vous calculez le prochain lot de données que vous pouvez écrire simultanément les résultats du dernier lot.


56



Étant donné que de nombreux problèmes de performances impliquent des problèmes de base de données, je vais vous donner quelques éléments spécifiques à prendre en compte lors de l'optimisation des requêtes et des procédures stockées.

Évitez les curseurs dans la plupart des bases de données. Évitez de faire une boucle aussi bien. La plupart du temps, l'accès aux données doit être basé sur un ensemble, et non sur un enregistrement. Cela inclut de ne pas réutiliser une seule procédure stockée d'enregistrement lorsque vous souhaitez insérer 1 000 000 enregistrements à la fois.

N'utilisez jamais select *, ne renvoyez que les champs dont vous avez réellement besoin. Cela est particulièrement vrai s'il y a des jointures car les champs de jointure seront répétés et causeront une charge inutile sur le serveur et le réseau.

Évitez l'utilisation de sous-requêtes corrélées. Utilisez les jointures (y compris les jointures aux tables dérivées si possible) (je sais que cela est vrai pour Microsoft SQL Server, mais testez le conseil lorsque vous utilisez un backend différent).

Index, index, index. Et obtenez ces statistiques mises à jour si applicable à votre base de données.

Faire la requête sargable. Ce qui signifie éviter les choses qui rendent impossible l'utilisation des index tels que l'utilisation d'un caractère générique dans le premier caractère d'une clause like ou d'une fonction dans la jointure ou comme partie gauche d'une instruction where.

Utilisez les types de données corrects. Il est plus rapide de faire des calculs de date sur un champ de date que d'essayer de convertir un type de données de type chaîne en un type de données de date, puis de faire le calcul.

Ne jamais mettre une boucle de toute sorte dans une gâchette!

La plupart des bases de données ont un moyen de vérifier comment l'exécution de la requête sera effectuée. Dans Microsoft SQL Server, cela s'appelle un plan d'exécution. Vérifiez les premiers à voir où se trouvent les zones à problèmes.

Réfléchissez à la fréquence d'exécution de la requête et au temps nécessaire à l'exécution pour déterminer ce qui doit être optimisé. Parfois, vous pouvez obtenir plus de performance à partir d'un léger tweak à une requête qui s'exécute des millions de fois par jour que vous pouvez effacer le temps d'une requête long_running qui ne s'exécute qu'une fois par mois.

Utilisez une sorte d'outil de profilage pour savoir ce qui est réellement envoyé vers et depuis la base de données. Je me souviens d'une fois dans le passé où nous ne pouvions pas comprendre pourquoi la page était si lente à charger lorsque la procédure stockée était rapide et nous découvrions que la page Web demandait la requête plusieurs fois au lieu d'une fois.

Le profileur vous aidera également à trouver qui bloque qui. Certaines requêtes qui s'exécutent rapidement lorsqu'elles s'exécutent seules peuvent devenir très lentes en raison des verrous d'autres requêtes.


46



Le facteur limitant le plus important aujourd'hui est le mémoire limitée. Les multicœurs ne font qu'aggraver la situation, car la bande passante est partagée entre les cœurs. En outre, la zone de puce limitée consacrée à l'implémentation de caches est également divisée entre les cœurs et les threads, ce qui aggrave encore ce problème. Enfin, la signalisation inter-chip nécessaire pour garder cohérentes les différentes caches augmente également avec un nombre accru de cœurs. Cela ajoute également une pénalité.

Ce sont les effets que vous devez gérer. Parfois, grâce à la gestion micro de votre code, mais parfois à travers un examen attentif et refactoring.

Beaucoup de commentaires mentionnent déjà le code amical de cache. Il y a au moins deux saveurs distinctes de ceci:

  • Évitez les latences de récupération de mémoire.
  • Abaissez la pression du bus mémoire (bande passante).

Le premier problème consiste spécifiquement à rendre vos modèles d'accès aux données plus réguliers, ce qui permet au pré-sélectionneur de travailler efficacement. Évitez l'allocation dynamique de mémoire qui répartit vos objets de données en mémoire. Utilisez des conteneurs linéaires plutôt que des listes liées, des hachages et des arbres.

Le deuxième problème concerne l'amélioration de la réutilisation des données. Modifiez vos algorithmes pour qu'ils fonctionnent sur des sous-ensembles de vos données qui tiennent dans le cache disponible, et réutilisez-les autant que possible pendant qu'ils sont encore dans le cache.

L'emballage plus serré des données et l'utilisation de toutes les données dans les lignes de cache des boucles chaudes permettent d'éviter ces autres effets utile les données dans le cache.


29



  • Quel matériel utilisez-vous? Pouvez-vous utiliser des optimisations spécifiques à la plate-forme (comme la vectorisation)?
  • Pouvez-vous obtenir un meilleur compilateur? Par exemple. passer de GCC à Intel?
  • Pouvez-vous faire fonctionner votre algorithme en parallèle?
  • Pouvez-vous réduire les échecs de cache en réorganisant les données?
  • Pouvez-vous désactiver les assertions?
  • Micro-optimiser pour votre compilateur et votre plate-forme. Dans le style de, "à un si / autre, mettez d'abord la déclaration la plus commune"

25



  • Routines en ligne (éliminer l'appel / retour et le poussage de paramètre)
  • Essayez d'éliminer les tests / commutateurs avec des recherches de table (si elles sont plus rapides)
  • Dérouler les boucles (périphérique de Duff) au point où elles se placent dans le cache de l'UC
  • Localiser l'accès à la mémoire pour ne pas faire exploser votre cache
  • Localiser les calculs connexes si l'optimiseur ne le fait pas déjà
  • Éliminer les invariants de boucle si l'optimiseur ne le fait pas déjà

15