Stratégies d’optimisation de performance de dernier recours

Question

Il y a beaucoup de questions de performances sur ce site déjà, mais il me semble que presque tous sont très spécifiques au problème et assez étroite. Et presque tout répéter les conseils pour éviter l'optimisation prématurée.

Supposons:

• le code est déjà fonctionne correctement
• les algorithmes choisis sont déjà optimale pour les circonstances du problème
• le code a été mesurée, et la délinquance routines ont été isolés
• toutes les tentatives pour optimiser seront également évalués pour s'assurer qu'ils ne pas aggraver les choses

Ce que je cherche ici est des stratégies et des astuces pour essorer jusqu'à la dernière quelques pour cent dans une critique de l'algorithme lorsqu'il n'y a rien d'autre à faire, mais tout ce qu'il faut.

Idéalement, essayez de faire des réponses de la langue agnostique, et indiquer les bas-côtés pour les stratégies proposées le cas échéant.

Je vais ajouter une réponse avec mes propres suggestions initiales, et espérons que ce soit d'autre que le Dépassement de Pile de la communauté peuvent penser.

Answer 1

OK, vous êtes à la définition du problème à l'endroit où il semble il n'y a pas beaucoup de place pour l'amélioration. C'est assez rare, dans mon expérience. J'ai essayé de l'expliquer dans un Dr Dobbs article en novembre 93, en partant d'une conventionnellement bien conçu non-trivial programme avec pas évident de déchets et en la prenant à travers une série d'optimisations jusqu'à ce que son horloge murale a été réduit de 48 secondes à 1,1 secondes, et le code source de la taille a été réduite par un facteur de 4. Mon outil de diagnostic a été cette. La séquence de changements:

• Le premier problème est l'utilisation de la liste des clusters (maintenant appelé "itérateurs" et "les classes conteneur") qui représente plus de la moitié du temps. Ceux qui ont été remplacés par de code assez simple, amenant le temps jusqu'à 20 secondes.

• Maintenant le plus grand temps-taker est plus de création de liste. En pourcentage, il n'était pas si grand, mais maintenant c'est parce que le plus gros problème a été supprimé. J'ai trouver un moyen de l'accélérer, et le temps de chute à 17 sec.

• Maintenant, il est plus difficile de trouver évident coupables, mais il y a un peu plus petits que je peux faire quelque chose, et le temps de chute à 13 sec.

Maintenant j'ai l'impression d'avoir frappé un mur. Les échantillons sont de me dire exactement ce qu'il fait, mais je n'arrive pas à trouver quelque chose que je peux améliorer. Puis je réfléchis sur la base de la conception du programme, sur une opération pilotée par la structure, et de se demander si toute la liste de recherche qu'il est en train de faire est réellement obligatoire par les exigences du problème.

Puis j'ai frappé à une re-conception, où le code du programme est réellement produite (via les macros du préprocesseur) à partir d'un petit ensemble de la source, et dans lequel le programme n'est pas constamment essayer de trouver des choses que le programmeur sait sont assez prévisibles. En d'autres termes, ne pas "interpréter" la séquence de choses à faire, "compiler".

• Cette refonte est fait, la réduction du code source par un facteur de 4, et le temps est réduit à 10 secondes.

Maintenant, parce que c'est trop rapide, il est difficile de l'échantillon, donc, je lui donne 10 fois plus de travail à faire, mais le suivant, basé sur l'original de la charge de travail.

• Plus le diagnostic révèle que c'est le temps passé dans la file d'attente-gestion. En doublure de ces réduit le temps de 7 secondes.

• Maintenant un grand temps-taker est le diagnostic de l'impression que j'avais fait. Couleur que - 4 secondes.

• Maintenant, le plus gros temps-preneurs sont les appels à malloc et free. Recycler objets - 2,6 secondes.

• En continuant d'exemple, je trouve encore des opérations qui ne sont pas strictement nécessaires - 1.1 secondes.

Total de l'accélération de facteur: 43.6

Maintenant pas de deux programmes sont identiques, mais dans la non-jouet de logiciel je l'ai toujours vu une progression de ce genre. Vous recevez d'abord les choses faciles, et puis le plus difficile, jusqu'à ce que vous arrivez à un point de rendements décroissants. Puis, les informations de gain peut ainsi conduire à une refonte, le démarrage d'un nouveau cycle de la vitesse, jusqu'à ce que vous atteint des rendements décroissants. Maintenant c'est le moment à partir duquel il pourrait être judicieux de s'interroger sur l' ++i ou i++ ou for(;;) ou while(1) sont plus rapides: les types de questions que je vois souvent sur.

P. S. Il peut être demandé pourquoi je ne l'ai pas utiliser un profiler. La réponse est que presque tous ces "problèmes" était un appel de fonction du site, qui mettent des échantillons pinpoint. Les profileurs, même aujourd'hui, sont à peine à se rallier à l'idée que les déclarations et les instructions d'appel sont plus importants pour les localiser, et plus faciles à résoudre, que l'ensemble des fonctions. J'en ai construit un profiler pour le faire, mais pour un vrai bas-et-sale intimité avec ce que fait le code, il n'y a pas de substitut pour l'obtention de vos doigts à droite. C'est pas une question que le nombre d'échantillons est faible, car aucun des problèmes trouvés sont si minuscules qu'ils sont faciles à manquer.

AJOUTÉ: jerryjvl demandées quelques exemples. Ici, c'est le premier problème. Il se compose d'un petit nombre de lignes de code, ensemble, à prendre 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)

Elles ont été à l'aide de la liste de cluster ILST (similaire à une liste de classe). Ils sont mis en œuvre dans la manière habituelle, avec "se cacher de l'information", qui signifie que les utilisateurs de la classe n'étaient pas censés avoir de soins de la façon dont ils ont été mises en œuvre. Lorsque ces lignes ont été écrites (sur environ 800 lignes de code) la pensée n'a pas été donnée à l'idée que ces pourrait être un "goulot d'étranglement" (je déteste ce mot). Ils sont tout simplement la méthode recommandée pour faire des choses. C'est facile à dire avec le recul, que ceux-ci devraient avoir été évité, mais dans mon expérience de tous 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 encore mieux de trouver et de corriger celles qui sont créées, même si elles "aurait pu être évité" (avec le recul). J'espère que donne un peu de la 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)

Il s'agit des listes en ajoutant des éléments à leurs extrémités. (La solution était de recueillir les éléments de tableaux, et de construire les listes de tous à la fois). La chose intéressante est que ces déclarations ne coût (c'est à dire ont été sur la pile d'appel) 3/48 de l'heure d'origine, de sorte qu'ils n'étaient pas en fait un gros problème au début. Cependant, après avoir enlevé le premier problème, ils coûtent 3/20 de l'époque et étaient donc maintenant un "gros poisson". En général, c'est comment il va.

Je pourrais ajouter que ce projet a été distillé à partir d'un projet réel, je l'ai aidé. Dans ce projet, les problèmes de performance ont été beaucoup plus dramatique (comme l'ont été les accélérations), comme l'appel d'une base de données-routine de l'accès à l'intérieur d'une boucle interne pour voir si une tâche a été terminée.

RÉFÉRENCE AJOUTÉE: Le code source, à la fois original et repensé, peut être trouvé dans www.ddj.compour 1993, dans le fichier 9311.zip, fichiers slug.asc et slug.zip .

EDIT 2011/11/26: Il y a maintenant un projet sur sourceforge contenant le code source en Visual C++ et d'un coup-par-coup de description de la façon dont il a été à l'écoute. Il ne va que jusqu'à 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 un 2-3 ordre de grandeur de l'accélération.

Answer 2

Suggestions:

• Pré-calculer, plutôt que de re-calculer: les boucles ou les appels répétés qui contiennent des calculs qui ont une aire de répartition relativement limitée des intrants, pensez à faire une recherche (tableau ou dictionnaire), qui contient le résultat de ce calcul pour toutes les valeurs dans la plage valide d'intrants. Utilisez ensuite une recherche simple à l'intérieur de l'algorithme de la place.
  Les bas-côtés: si quelques-uns de la pré-calculé les valeurs sont effectivement utilisés, ce qui peut rendre les choses pire, également la recherche peut prendre beaucoup de mémoire.
• Ne pas utiliser des méthodes de bibliothèques: la plupart des bibliothèques doivent être écrites à fonctionner correctement dans un large éventail de scénarios, et d'effectuer null contrôles sur les paramètres, etc. Par la re-mise en œuvre d'une méthode que vous pouvez être en mesure de sortir la bande a beaucoup de logique qui ne s'applique pas exactement à la circonstance que vous utilisez.
  Les bas-côtés: l'écriture de code supplémentaire signifie plus de surface pour les bugs.
• Utilisez des méthodes de bibliothèques: me contredire, les bibliothèques de langue sont écrits par des gens qui sont beaucoup plus intelligents que vous et moi; les chances sont qu'ils l'ont fait mieux et plus vite. Ne pas mettre en œuvre vous-même, sauf si vous pouvez le faire plus rapidement (c'est à dire: toujours mesurer!)
• Cheat: dans certains cas, bien qu'un calcul exact peut exister pour votre problème, vous ne pouvez pas besoin de 'exact', parfois, un rapprochement peut être "suffisamment bonne" et beaucoup plus vite dans l'affaire. Demandez-vous, est-il vraiment si la réponse est de 1%? 5%? même à 10%?
  Les bas-côtés: eh Bien... la réponse ne sera pas exacte.

Answer 3

Lorsque vous ne pouvez pas améliorer la performance plus - voir si vous pouvez améliorer la perception de la performance à la place.

Vous ne pouvez pas être en mesure de faire votre fooCalc algorithme plus rapide, mais souvent, il ya des façons de rendre votre application semble plus adaptée à l'utilisateur.

Quelques exemples:

• en anticipant ce que l'utilisateur va à la demande et de commencer à travailler sur ce avant
• l'affichage des résultats, comme ils viennent dans, au lieu de tout à la fois à la fin
• Précis de la barre de progression

Ces de ne pas rendre votre programme plus rapide, mais il peut rendre vos utilisateurs plus heureux avec la vitesse que vous avez.

Answer 4

Je passe la plupart de ma vie en ce lieu. Les grandes lignes sont à l'exécution de votre générateur de profils et d'obtenir l'enregistrement:

• Les défauts de Cache. Cache de données est la source #1 de stands dans la plupart des programmes. Améliorer cache taux de succès par la réorganisation de la délinquance des structures de données pour avoir une meilleure localité; pack structures et les types de vers le bas pour éliminer les gaspillages octets (et donc perdue cache extrait); prefetch de données dans la mesure du possible afin de réduire les stands.
• Charge-hit-magasins. Compilateur hypothèses sur pointeur aliasing, et les cas où les données sont transférées entre déconnecté jeux de registre via la mémoire, peut causer un certain comportement pathologique qui cause l'ensemble de la CPU pipeline pour effacer sur une charge de l'op. Trouver des endroits où les chars, les vecteurs, et ints sont jetés l'un de l'autre et de les éliminer. Utiliser __restrict - le généreusement de promettre le compilateur sur la création d'alias.
• Microcoded opérations. La plupart des transformateurs de certaines opérations qui ne peuvent pas être mises en pipeline, mais au lieu d'exécuter un minuscule sous-programme stocké dans la mémoire ROM. Des exemples sur le PowerPC sont des entiers multiplier, diviser, et shift-by-variable-montant. Le problème est que l'ensemble du pipeline s'arrête net alors que cette opération est en cours d'exécution. Essayez d'éliminer l'utilisation de ces opérations, ou au moins de les décomposer en leurs constituants pipeline ops de sorte que vous pouvez obtenir le bénéfice de diffusion superscalaire sur tout le reste de votre programme.
• Direction de la mispredicts. Ces trop vider le pipeline. Trouver des cas où le PROCESSEUR est de dépenser beaucoup de temps de remplissage de la canalisation après une branche, et l'utilisation de la branche allusion si disponible pour l'obtenir à prédire correctement le plus souvent. Ou mieux encore, remplacer les branches conditionnelles-se déplace dans la mesure du possible, surtout après les opérations à virgule flottante, parce que leur conduite est généralement plus profonde et la lecture de l'état des drapeaux après fcmp peut provoquer un décrochage.
• Séquentielle à virgule flottante de la fpo. Faire ces SIMD.

Et une chose que j'aime faire:

• Définissez votre compilateur à la sortie de l'assemblée des listes et regardez ce qu'il émet pour le hotspot des fonctions dans votre code. Tous ceux intelligent optimisations "un bon compilateur doit être en mesure de le faire automatiquement pour vous"? Les Chances sont de votre compilateur ne pas les faire. J'ai vu GCC émettent vraiment WTF code.

Answer 5

Jeter plus de matériel à elle !