Ubuntu-fr

LuxB2000

Programmation EFFICACE C++

Bonjour,
je suis en train de développer une application (de traitement d'images) dans le langage C++. L'application fonctionne correctement (les résultats sont bons) mais elle reste assez lente.
J'ai déjà passé pas mal de temps à effectuer des modifications par ci par là, par exemple :
- remplacer tous les itérateurs par des jeux sur les pointeurs,
- effectuer des lissages (pour ceux qui connaissent) efficaces,
-...

Je voudrai savoir si vous aviez sous la main une référence (site, livre, article, ...) qui me donnerait des tuyaux pour implémenter de manière efficace. Je sais programmer en C++ mais je dois reconnaître que mes connaissances dans l'optimisation d'algorithmes sont assez vagues (pour ne pas dire balbutiantes).
Il faut savoir que je dois programmer dans une librairie imposée et que celle-ci se base essentiellement sur la programmation par template.

Un grand merci pour vos conseils.

Link31

Re : Programmation EFFICACE C++

- remplacer tous les itérateurs par des jeux sur les pointeurs,

Ça commence très mal.

Sache que les itérateurs sont dans l'immense majorité des cas aussi rapides, voire plus rapides (selon le conteneur utilisé) que des pointeurs. Et dans tous les cas, ils sont plus sûrs, ce qui n'a pas de prix, même face à de l'optimisation.

Les compilateurs C++ actuels sont extrêmement perfectionnés et sont généralement capables de convertir du code C++/STL(/Boost...) en code assembleur aussi rapide que du code C écrit entièrement à la main. Certaines fonctions de la STL ou des itérateurs sont ramenées à une seule ligne d'assembleur aux plus hauts niveaux d'optimisation.

Pour du traitement d'image (matrices, vecteurs...) à travers des fonctions templates, je te conseillerais d'utiliser les expression templates. En gros, ça revient à passer à tes fonctions une opération mathématique plutôt qu'une valeur, le véritable calcul étant effectué en une seule fois à la fin de l'algorithme, là où le compilateur peut optimiser au maximum tes calculs. Ça revient presque à simplifier une opération mathématique à la main pour chacun des cas où c'est possible.

À lire :
http://loulou.developpez.com/tutoriels/cpp/metaprog/#L3.3
http://en.wikibooks.org/wiki/More_C++_Idioms/Expression-template

Bon, ça c'est déjà assez complexe comme optimisation. J'espère que tu as déjà vérifié les trucs de base, à savoir :
- sortir les invariants de tes boucles (bien que le compilateur soit parfois capable de le faire tout seul)
- éviter les allocations dynamiques (new) dans les sections les plus critiques de ton code (les boucles, entre autres)
- utiliser les options d'optimisation maximale du compilateur, et le profilage de code au besoin. Voire changer de compilateur pour voir si ça peut améliorer les choses.

xamaco

Re : Programmation EFFICACE C++

Pas grand chose à rajouter à Link31.
En termes de performances, avec C++ couplé avec STL, je ne pense pas que tu puisses faire beaucoup mieux. Il doit y avoir une 'couille' dans un de tes algorithmes. Un profiler devrait te dire où ton programme perd bêtement son temps.
Sans vouloir te brusquer, pour t'aider, il faudrait que tu en dise un peu plus...

LuxB2000

Re : Programmation EFFICACE C++

Bonjour,
tout d'abord un grand merci pour les réponse (je vais regarder les références dès que possible).

Sans vouloir remettre tes connaissances en doute, j'ai demandé à l'algo de calculer son temps d'exécution (à l'aide de commandes clock() ) et je confirme que parcourir une matrice à l'aide de pointeurs est plus rapide que de passer par un itérateur.

Pour les invariant ect j'avais déjà fait attention quand j'ai écris le code (pas complètement une nouille non plus )  Par contre qu'entends-tu par

utiliser les options d'optimisation maximale du compilateur, et le profilage de code au besoin

Un grand merci pour les infos en tout cas.

Dernière modification par LuxB2000 (Le 28/10/2008, à 10:41)

Luc Hermitte

Re : Programmation EFFICACE C++

Matrice, itérateur ? C'est rare de disposer d'itérateurs efficaces sur des matrices ?
Il ne doit guère y avoir adobe/boost.GIL qui sache le faire pour des images.

LuxB2000

Re : Programmation EFFICACE C++

@Luc : Oui entendons-nous lorsque je parle de matrice. Le fait est que je travaille dans la librairie ITK (car il y a déjà bcp de choses implémentée là dedans). Une image n'est peu-être pas stockée sous forme de matrice, elle peut-être également stockée dans un tableau 1D mais permettre à l'utilisateur de donner des coordonnées type [L,C]. Très honnêtement je n'ai pas été regarder.

nicolas66

Re : Programmation EFFICACE C++

je suis en train de développer une application (de traitement d'images) dans le langage C++. L'application fonctionne correctement (les résultats sont bons) mais elle reste assez lente.

La meilleure optimisation reste à baisser la complexité des algorithmes qu'on utilise.

---

"The computer was born to solve problems that did not exist before." (B. Gates)

LuxB2000

Re : Programmation EFFICACE C++

@nicolas66 : j'en suis bien conscient mais l'algorithme n'est pas de moi. Je fais de mon mieux pour faire un truc efficace mais je ne suis pas responsable de la complexité de l'algorithme (en supposant une implémentation parfaite).

nicolas66

Re : Programmation EFFICACE C++

* As-tu cherché dans la littérature un papier qui présenterait un algorithme de complexité inférieure ?
* As-tu cherché à paralléliser certaines parties du code ?

Dernière modification par nicolas66 (Le 28/10/2008, à 14:14)

---

"The computer was born to solve problems that did not exist before." (B. Gates)

LuxB2000

Re : Programmation EFFICACE C++

@nicolas66 : non je n'ai pas cherché pour la bonne et "simple" raison que l'algo est fixé et que (à ma connaissance) c'est le seul pour effectuer ce que je veux faire. Certaines parties du code sont déjà mises sous threads tandis que d'autres ont été optimisées (convolution par des noyaux efficaces, etc.). Je suis plutôt à la recherche de trucs genre
- meta-programmation (merci à Link31, mais malheureusement je n'ai pas l'impression que cela fonctionnera à grande échelle)
- SSE et MMX (voir par exemple http://www.cortstratton.org/articles/OptimizingForSSE.php )
- ... (tout ce qui est bon à prendre).
Il faut savoir que je travaille sur des images volumétriques (full 3D) et que dans ce cas on approche les heures de calculs. Ce qui n'est bien sûr pas admissible. Je cherche des "astuces" pour optimiser chaque partie indépendamment de l'algo en lui même.

nicolas66

Re : Programmation EFFICACE C++

non je n'ai pas cherché pour la bonne et "simple" raison que l'algo est fixé et que (à ma connaissance) c'est le seul pour effectuer ce que je veux faire.

Hum par curiosité, quel est l'algo en question ?

Il faut savoir que je travaille sur des images volumétriques (full 3D) et que dans ce cas on approche les heures de calculs. Ce qui n'est bien sûr pas admissible.

Je bosse aussi sur des images volumétriques et les temps de calculs sont effectivement souvent très longs. Cependant, je doute fort que les optimisations citées ici feront baisser les temps de calcul de manière significative ... L'utilisation d'instructions MMX peut être une piste intéressante. Sinon est-ce que les calculs sont lancés sur des clusters ?

Dernière modification par nicolas66 (Le 28/10/2008, à 16:34)

---

"The computer was born to solve problems that did not exist before." (B. Gates)

Link31

Re : Programmation EFFICACE C++

Sans vouloir remettre tes connaissances en doute, j'ai demandé à l'algo de calculer son temps d'exécution (à l'aide de commandes clock() ) et je confirme que parcourir une matrice à l'aide de pointeurs est plus rapide que de passer par un itérateur.

Par contre qu'entends-tu par

utiliser les options d'optimisation maximale du compilateur, et le profilage de code au besoin

Un grand merci pour les infos en tout cas.

Justement, c'est un des paramètres les plus importants.

Pour g++ par exemple, si tu compiles avec -O0 (le niveau d'optimisation par défaut), le compilateur se comporte de façon stupide, en traduisant chaque ligne de code qu'il rencontre par son équivalent assembleur, sans inliner aucune fonction (ou très peu)... C'est très utile pour le débogage, cela dit.

Par contre, si tu actives l'option -O3, g++ va analyser en profondeur ton code, et éliminer les invariants que tu n'aurais pas repérés, dérouler les boucles à la taille qui convient au pipeline de ton processeur... Et, en particulier, inliner les itérateurs. Ce qui revient quasiment à utiliser des pointeurs dans certains cas.

Mais il faut que les itérateurs de ta bibliothèque soient bien écrits. Le compilateur peut faire beaucoup pour l'optimisation, mais il faut souvent lui présenter le code d'une certaine façon pour qu'il y arrive.

En ce qui concerne le profilage de code : le principe est de lancer ton programme une première fois, compilé avec l'option de profilage, avec des données "standard" en entrée, et de le laisser tourner quelque temps. Il tournera probablement plus lentement que d'habitude, mais tu obtiendras en sortie un fichier décrivant le pourcentage d'utilisation de chaque partie du code. Le compilateur peut ensuite utiliser ces informations pour optimiser ses décisions quant aux probabilités de chaque embranchement (instructions if).

Tu peux normalement indiquer toi-même au compilateur quelles sont les probabilités de certains embranchements, comme le font beaucoup les développeurs du noyau Linux (macros likely() et unlikely()), mais il a été montré que les développeurs prennent souvent de mauvaises décision à ce sujet.

Enfin, si ton programme utilise beaucoup de calculs en virgule flottante, mais que tu n'as pas besoin d'un respect à 100% de la norme IEEE 754, tu devrais essayer l'option -ffast-math de g++, qui lui permet de bien plus vastes optimisations, au prix parfois d'une perte de précision dans les résultats.

La page de référence reste évidemment : man gcc.

Tu peux aussi essayer le compilateur Intel, qui est connu pour ses excellentes optimisations sur les processeurs de cette marque (il est bridé par défaut s'il tourne sur un AMD, mais on peut le débloquer).

Tom_L

Re : Programmation EFFICACE C++

Salut,

Tu peux aussi essayer le compilateur Intel, qui est connu pour ses excellentes optimisations sur les processeurs de cette marque (il est bridé par défaut s'il tourne sur un AMD, mais on peut le débloquer).

Je suis loin d'être un pro en optimisation de code, mais je me permet d'apporter mon témoignage...
Je développe des codes CFD en c++ et le passage de g++ à icc (compilo Intel) m'a permis de gagner pas mal en temps d'execution :

- à même niveaux d'optimisation (-O3) mon code tournait 10~15% plus vite
- en utilisant les option de vectorisation/parallelisation automatiques (-parallel) on gagne encore un dizaine de %
- en utilisant les librairies optimisées Intel (MKL, IPP), les outils d'analyse (Vtune, Thread checker) et en modifiant quelques routines critiques pour que le compilo puisse faire son boulot correctement et on gagne encore une dizaine de %...

Au final, mon code prenait quelque chose comme 60% du temps initial... Des chiffres à prendre avec des pincettes, cela ne donnera peut-être pas grand chose dans ton cas, je ne sais pas.... A noter que la machine est dôtée d'un processeur intel... je n'ai aucune idée de ce que ça peut donner sur un AMD...

Tout ces outils sont gratuit sur Linux (mais non libres bien sûr...), ça vaut peut-être le coup d'essayer...

---

~~~~~~
Thomas.

LuxB2000

Re : Programmation EFFICACE C++

Bien bien, je vais regarder tout ça. Je vous tiens au courant.
Un grand merci en tout cas !