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

À 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.

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.

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.

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.