Comment mesurer la complexité en pratique de votre grand projet logiciel?

11

À l'université, lors de nos cours d'algorithmes, nous apprenons à calculer avec précision la complexité de divers algorithmes simples utilisés dans la pratique, tels que les tables de hachage ou le tri rapide.

Mais maintenant, dans un grand projet logiciel, lorsque nous voulons le rendre plus rapide, tout ce que nous faisons est de regarder des pièces individuelles - quelques boucles imbriquées là-bas qui peuvent être remplacées par une table de hachage plus rapide, une recherche lente ici qui peut être accélérée par une technique plus sophistiquée, mais nous ne calculons jamais la complexité de l'ensemble de notre pipeline.

Y'a-t'il un quelconque moyen d'y arriver? Ou, dans la pratique, les gens s'appuient-ils uniquement sur "localement" en utilisant un algorithme rapide, pour rendre l'ensemble de l'application plus rapide, au lieu de considérer globalement l'application dans son ensemble?

(Parce qu'il me semble non trivial de montrer que si vous accumulez un grand nombre d'algorithmes connus pour être très rapides par eux-mêmes, vous vous retrouvez également avec une application rapide dans son ensemble.)

Je pose cette question, car je suis chargé d'accélérer un grand projet que quelqu'un d'autre a écrit, où de nombreux algorithmes interagissent et travaillent sur des données d'entrée, il n'est donc pas clair pour moi comment l'impact de la création d'un seul algorithme plus rapidement sur toute l'application.

user7088941
la source
1) Cela nécessite une approche de test, pour trouver les points à améliorer. Tests de référence, tests de durabilité, tests dynamiques (en surveillant les mesures de mémoire / CPU de chaque composant). 2) Après avoir trouvé les points à améliorer, vous trouverez la cause première de ces points. 3) Trouvez une solution pour résoudre la cause profonde, en maintenant l'exactitude.
suréchange
vous avez besoin de quelques outils pour ces tests mentionnés au point 1
suréchange
1
L'analyse Big O ne vous dit pas comment un algorithme fonctionnera. Il vous indique comment les performances évolueront à mesure que les naugmentations.
John Wu

Réponses:

5

Les grands projets logiciels se composent de nombreux composants différents, et tous ne sont généralement pas un goulot d'étranglement. Bien au contraire: pour presque tous les programmes que j'ai vus dans ma vie où les faibles performances étaient un problème, le principe de Pareto s'appliquait: plus de 80% des gains de performances peuvent être obtenus en optimisant moins de 20% du code (en réalité, je pense que les chiffres étaient souvent plus de 95% à 5%).

Donc, commencer à regarder des pièces individuelles est souvent la meilleure approche. C'est pourquoi le profilage (comme expliqué dans la réponse de David Arno ) est très bien, car il vous aide à identifier les 5% mentionnés du code où l'optimisation vous donnera le "plus grand rapport qualité / prix". L'optimisation de «l'ensemble de l'application» comporte un certain risque de sur-ingénierie, et si vous optimisez ces 95% même par un facteur de 10, cela n'aurait souvent aucun effet mesurable. Notez également que le profilage vous en dit beaucoup plus que toute estimation de complexité d'algorithme hypothétique, car un algorithme simple qui nécessite O (N ^ 3) étapes peut toujours être plus rapide qu'un algorithme complexe qui nécessite O (N log (N)) tant que N est assez petit.

Une fois que le profilage a révélé les points chauds, on peut les optimiser. Bien sûr, un "point chaud" peut être plus grand qu'une simple ou deux lignes de code, parfois il faut remplacer un composant entier pour le rendre plus rapide, mais ce sera généralement toujours une petite partie de la base de code dans un programme plus grand .

Les techniques d'optimisation typiques incluent

  • améliorer l'utilisation des algorithmes et des structures de données

  • réglage fin de l'ancien

  • micro-optimisations à certains points chauds réels

  • recodage des sections critiques à l'aide du code d'assemblage ou de CUDA

Notez que ces techniques fonctionnent à différents niveaux d'abstraction, certaines d'entre elles visualisant un composant plus "dans son ensemble" que d'autres. Cela dépend donc de ce que vous entendez par «tout ce que nous faisons est d'examiner des pièces individuelles» - si vous n'aviez que des micro-optimisations en tête, je ne suis pas d'accord pour dire que «nous» ne travaillons que sur cela. Mais si vous entendez appliquer ces optimisations à grande échelle sur des pièces ou des composants isolés, "nous" travaillons probablement sur les bonnes pièces, et vous devriez remettre en question vos attentes.

Doc Brown
la source
13

La manière standard, éprouvée est de profiler le code . Vous effectuez une analyse dynamique du système en cours d'exécution pour mesurer les horaires, l'utilisation de la mémoire, etc. Analysez ensuite les résultats pour trouver les goulots d'étranglement des performances.

Ces goulots d'étranglement sont ensuite réécrits expérimentalement et le résultat est à nouveau profilé pour déterminer qu'une augmentation de la vitesse, une réduction de l'utilisation de la mémoire, etc. ont été obtenues. Ce processus est ensuite répété jusqu'à ce qu'un gain de performance acceptable soit atteint.

David Arno
la source
1
Cela résout le problème de performances, c'est pourquoi nous le faisons, mais ne répond pas à la question d'origine. Je pense que dans le pire des cas, la complexité du temps ou de l'espace serait mieux déterminée à l'aide d'un outil d'analyse de programme statique, qui peut être manquant. Les tests de performances sont parfaits pour des scénarios spécifiques, mais ils ne vous en disent pas beaucoup sur les pires situations possibles.
Frank Hileman
3
@FrankHileman Je pense que le point ici est que la performance est une préoccupation pratique et ne peut être mesurée qu'en pratique. Vous n'utilisez pas les mathématiques pour trouver le goulot d'étranglement de votre logiciel, même si vous pouvez le résoudre une fois trouvé en utilisant les mathématiques (algorithmes).
Wildcard
Sur une note connexe, dans la présentation de diaporamas à l'ancienne (diapositives en verre), il y avait toute une technologie prétendue pour calculer minutieusement la densité moyenne d'une diapositive de lanterne pour déterminer la luminosité de la lumière à utiliser. Complètement inutile: si l'image ne s'affiche pas bien, vous obtenez une lumière plus vive!
Wildcard
@Wildcard Bien que les performances ne puissent être mesurées qu'au moment de l'exécution, elles peuvent être prédites statiquement. Un mauvais choix d'une structure de données peut sembler correct, en termes de performances, dans les tests de performances, mais échoue lamentablement dans les cas limites qui pourraient être prédits dans une analyse statique. C'est la même raison pour laquelle nous examinons les analyses de complexité du pire des cas pour les structures de données en général.
Frank Hileman
@Wildcard: vous avez raison, mais Frank a également très raison de dire que ce message ne répond pas à la question.
Doc Brown
3

Bien que les autres réponses soient correctes et fournissent des indications, je pense qu’elles manquent une étape. Dans un système complexe comme celui avec lequel vous travaillez actuellement, la compréhension des différents composants qui composent le système est essentielle pour comprendre pourquoi quelque chose est lent.

Ma première étape serait de mettre la main sur un schéma d'architecture détaillé ou d'en créer un moi-même. Déterminez les étapes suivies par les composants du logiciel et la durée de chaque étape.

Découvrez également comment les composants interagissent les uns avec les autres. Cela peut faire toute la différence.

Par exemple, j'ai vu du code en C # où l'interface entre deux composants passait un IEnumerable construit par le premier composant, qui était ensuite énuméré par le deuxième composant. En C #, cela nécessite un changement de contexte, qui peut être coûteux dans certaines circonstances. Le résoudre n'a aucun impact sur l'algorithme. Un simple .ToList () assurez-vous que le résultat est collecté avant que la prochaine étape ne résout ce problème.

Une autre chose à considérer est l'impact sur le système sur lequel vous exécutez le code. Les interactions matérielles peuvent évidemment être un facteur dans les systèmes complexes. Recherchez Disk IO, Large Memory allocations et Network IO. Parfois, ces problèmes peuvent être résolus plus efficacement en modifiant le système ou même en remplaçant le matériel.

Jonathan van de Veen
la source