Dans quelle mesure les logiciels scientifiques doivent-ils être optimisés?

13

Pour les applications nécessitant des ressources informatiques importantes, des performances élevées peuvent être un facteur critique lorsqu'il s'agit de fournir des résultats scientifiques ou de réaliser des "percées" dans un délai raisonnable.

Combien de temps et d'efforts les développeurs de logiciels devraient-ils investir pour optimiser une application? Quels sont les principaux critères utilisés?

Allan P. Engsig-Karup
la source
Les programmes que les scientifiques écrivent durent souvent très longtemps (par exemple des simulations). Le temps du programmeur et celui de l'ordinateur peuvent être comparables. Ceci est très différent du travail de programmeur "habituel" d'aujourd'hui. Comme au début de l'informatique, il vaut souvent la peine d'investir des efforts (et du temps de programmeur) pour accélérer la simulation, la terminer plus rapidement et faire le travail plus rapidement.
Szabolcs

Réponses:

15

Dans la grande majorité des cas, des améliorations algorithmes fait une plus grande différence que l'amélioration de l'optimisation. Les algorithmes sont également plus portables que les optimisations de bas niveau. Mon conseil est de suivre les meilleures pratiques générales en ce qui concerne la disposition de la mémoire pour la réutilisation du cache, en évitant les copies ou les communications excessives, en traitant le système de fichiers de manière saine et en faisant en sorte que les noyaux à virgule flottante aient une granularité suffisante pour la vectorisation. Parfois, cela suffit pour atteindre une fraction suffisamment élevée de "pic" (pour cette opération).

Esquissez toujours un modèle de performance pour les opérations que vous jugez importantes (ou que vous découvrez importantes par profilage). Ensuite, vous pouvez utiliser le modèle de performances pour estimer ce qu'une implémentation hautement optimisée pourrait offrir. Si vous décidez que l'accélération en vaut la peine (par rapport aux autres choses que vous pourriez faire), faites l'optimisation.

Le défi le plus difficile est peut-être la conception d'interfaces et de structures de données de haut niveau et importantes (dans le sens où beaucoup de code dépendra de ces choix) afin que vous puissiez les optimiser ultérieurement sans avoir à changer l'API. Contrairement aux optimisations spécifiques et aux directives générales, je ne sais comment enseigner cela que par l'expérience. Travailler avec des logiciels open source sensibles aux performances aide. Comme pour toute décision d'API, il est important de comprendre l'espace du problème.

Jed Brown
la source
1
Tout récemment, j'ai obtenu un facteur de 10 000 (pour nos plus grands événements) une amélioration de la durée d'exécution d'une étape limite de notre analyse en remplaçant simplement un algorithme qui était O (n ^ 2) dans le temps et l'espace par un O (n log n ) à la fois. Remarquez que cela signifiait une autre dépendance et une complexité supplémentaire, mais parfois cela en vaut la peine ...
dmckee --- chaton ex-modérateur
1
Les facteurs d'accélération (qui sont relatifs à quelque chose) ne valent pas beaucoup une référence claire à ce que vous avez comparé. Si vous vous comparez à une mauvaise implémentation basée sur un algorithme inapproprié, puis que vous changez, il ne serait évidemment pas déraisonnable de vous attendre à des gains relatifs importants.
Allan P. Engsig-Karup,
1
@Allan: S'il y avait un facteur de 10 000 à obtenir d'un seul changement, il s'agissait évidemment d' une implémentation mal choisie. Le code précédent était blessé autant par l'espace inutile que par la complexité temporelle: les performances de mise en cache étaient épouvantables. Mais c'est le point n'est-ce pas?
dmckee --- chaton ex-modérateur
8

Comment définiriez-vous "optimiser"? Il existe un spectre complet allant du développement de meilleurs algorithmes ou modèles de calcul à l'utilisation d'un assembleur réglé à la main.

À mon avis et par expérience, le fruit bas se situe quelque part au milieu, par exemple en choisissant un algorithme qui convient le mieux à l'architecture informatique sous-jacente. L'algorithme ne doit pas nécessairement être nouveau et votre compréhension de l'architecture sous-jacente ne doit pas nécessairement être très spécifique, par exemple

  • Si vous savez que votre architecture prend en charge SIMD, restructurez le calcul de sorte que vos opérations puissent être écrites en termes de vecteurs courts,
  • Si vous savez que votre architecture est un ordinateur multicœur, essayez de décomposer votre tâche de calcul en sous-tâches individuelles qui n'interfèrent pas entre elles et exécutez-les en parallèle (pensez à un DAG de vos sous-tâches) ,
  • Si votre architecture sous-jacente a un GPU, pensez à des façons de reformuler votre calcul en tant que groupe de threads parcourant les données en étape de verrouillage,
  • etc...

Toutes les fonctionnalités ci-dessus, par exemple SIMD, parallélisme et GPU, sont accessibles sans trop de connaissances de bas niveau, mais n'offrent vraiment qu'un avantage dans les algorithmes qui peuvent facilement les exploiter.

Pedro
la source
4

Je suis d'accord avec toutes les réponses déjà avancées jusqu'à présent ... Je veux juste aborder un autre aspect négligé de l'optimisation du code: l'attente de qualité.

Le problème de l'optimisation du code se pose généralement lorsque l'utilisateur essaie de résoudre des problèmes de plus en plus importants et que le code est insuffisant pour répondre aux besoins / attentes de l'utilisateur. Le temps qu'il faut investir dans l'optimisation du code dépend de la demande pour répondre à cette attente. Il vaut certainement la peine d'investir beaucoup de temps s'il existe un besoin critique d'un avantage concurrentiel (par exemple, terminer et publier vos recherches sur un sujet brûlant avant d'autres).

Bien sûr, le temps à investir dépend de la vitesse à laquelle vous en avez besoin et de la portabilité du code. Souvent, ces deux besoins sont en conflit l'un avec l'autre et vous devez décider lequel est le plus important avant de commencer l'optimisation. Plus vous le souhaitez, plus vous devez vous fier à des modifications de conception de haut niveau du code (algorithme / structure de données). Plus vous voulez que le code s'exécute rapidement, il doit être réglé avec des optimisations de bas niveau spécifiques à une machine particulière (par exemple, optimisations de code / compilateur / runtime).

Paul
la source
4

Vous devrez faire l'analyse (des coûts) de tant de mois-hommes (et ceux-ci sont toujours mythiques :-)) pour gagner en vitesse d'exécution. Vous devrez déterminer combien de fois ce logiciel sera utilisé et par combien de personnes pour pouvoir estimer le gain.

La règle d'or, comme toujours, est la fameuse règle des 80/20. À un certain moment, cela n'ajoute tout simplement plus pour passer de plus en plus de temps à gagner quelques pourcentages (ou moins) de temps de fonctionnement. Mais vous devrez analyser.

Et je suis sincèrement d'accord avec les affiches ci-dessus: assurez-vous que votre API est bien pensée afin qu'elle n'ait pas besoin de beaucoup de changements et assurez-vous que le code est portable et maintenable (pensez à devoir ré-analyser un algorithme que vous avez écrit et très précis) optimisé il y a dix ans). Et assurez-vous d'utiliser de bonnes pratiques de programmation et des bibliothèques standard. Les chances sont raisonnables que quelqu'un ait déjà pensé à l'algorithme le plus efficace pour votre application.

Pour citer Donald Knuth: "l'optimisation prématurée est la racine de tout mal". Profilez donc votre code, mais pas trop tôt.

GertVdE
la source
Faites-vous référence à la règle du principe de Pareto (80/20)? Si oui, voulez-vous dire que nous devrions concentrer les efforts d'optimisation sur les 20% du code qui produisent 80% du ralentissement? Ou voulez-vous dire que si vous ne pouvez vous attendre qu'à 20% d'accélération, cela ne vaut tout simplement pas la peine d'être optimisé?
Paul
Non, je ne l'ai utilisé que comme une sorte de principe, pas exactement 80/20. À un moment donné, vous consacrerez tellement d'efforts à gagner seulement quelques pourcentages que cela n'en vaut plus la peine.
GertVdE
3

Quelques conseils supplémentaires:

  1. Avant de faire toute optimisation d'un programme de travail, assurez-vous que vous disposez d'un bon ensemble de cas de test qui aident à maintenir l'intégrité du code. Il est inutile d'obtenir des résultats erronés plus rapidement.
  2. Si votre optimisation rend le code moins lisible, conservez la version d'origine, au moins sous la forme d'un commentaire, mais mieux comme version alternative à sélectionner au moment de la compilation et de l'exécution. Vos besoins d'optimisation peuvent changer à mesure que vos problèmes et vos machines évoluent, et le code d'origine peut être un meilleur point de départ pour l'optimisation que vous ferez dans cinq ans.
  3. Si votre version optimisée s'avère avoir un impact minimal, mais rend le code moins lisible, moins universel ou moins stable, revenez à la version d'origine. Vous perdez plus que vous ne gagnez.
Khinsen
la source