Discussion :

[leilaleila]

Salut,,

S V P,, Avez vous des astuces qui me permettent d'optimiser le temps de calcul de mon programme écrit en c++,,

Merci par avance!!

[Ehonn]

Bonjour

Il nous faudrait plus de détail (code par exemple) pour te répondre. Voici quelques généralités
- faire des benchmarks
- flags de compilation (-O3 -DNDEBUG -march=native -ffast-math)
- réduire la complexité de l'algorithme
- éviter les calculs et les copies inutils
- parcourir la mémoire "dans le bon sens"
- parallélisation

[Davidbrcz]

Optimiser, ce n'est pas une question d'astuce : il faut être précis et méthodique.

Il faut d'abords commencer par profiler ton programme, voir ou le programme passe du temps et quels sont les bottlenecks.
Avec ces infos, on peut essayer d'adapter l'algorithme (source première de gain de performance [1]). Après, on peut éventuellement regarder le tête du code (copie a outrance, cache friendly or not)

Et si jamais ca suffit pas, on peut alors aller chercher dans le multi threading

Bref, sans plus de détail ni de contexte, difficile d’être plus précis.

------------------------------------------
1 : Ca peut etre un changement de complexite (n^2 en n*log n) par exemple, que des changements qui vont impacter les accès mémoires (cache miss, ...)

[MrPchoun]

Salut,

Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
http://frouin.me/optimisation-en-cpp/

Après.. Toutes les structures que tu utilises dans ton programme (vector, list, map) n'ont pas la même réactivité si je puis dire : penche toi sur la notion de complexité, et poses toi toujours la question de savoir si tu ne peux pas utiliser une autre structure.

Le plus simple, évidement, c'est de chronométrer un algorithme (perso j'utilise sf::Clock avec la bibliothèque SFML, mais il doit y avoir l'équivalent dans la bibli standard), et de voir quelles modifications peuvent être efficaces en terme de rapidité.

Cordialement,

[ternel]

J'avais eu un professeur qui résumait l'optimisation ainsi:

1. Choisir un compromis espace-temps
2. Établir un contexte favorable,
3. Réduire le volume total d'informations, après tout, "La plus rapide façon de calculer, c'est encore de ne pas calculer du tout",
4. Réduire la complexité de tous les grands calculs,
5. Si le programme reste trop lent, envisager des optimisations "magiques"

Ce qui signifie concrètement:
Mémoire ou temps
Un programme devra choisir entre utiliser moins de mémoire et moins de temps. Dans ton cas, c'est moins de temps.

Établir un contexte favorable
Ehonn en a parlé, il s'agit de choisir les flags de compilations orienté vers cette optimisation.

Réduire le volume total d'informations
Là, il s'agit de tenter de supprimer des calculs.
Je n'ai pas d'idée d'exemple à te donner, mais l'idée est que rien n'ira plus vite que de se passer d'un long calcul.

Réduire la complexité de tous les grands calculs
Ça demande de savoir quels sont les longs calculs, donc de profiler.
Cela dit, tu peux avoir une idée initiale: les calculs qui sont le but du programme.
Un programme de calcul matriciel va très certainement devoir optimiser la somme et le produit matriciel.

Une fois que tu le sais, renseigne toi sur la complexité espérable.
Par exemple un tri en N*log N, une recherche dans un espace trié en log N.

Vérifie aussi si tu passes plus de temps à lire et ordonner tes données ou à les consulter.
Ça te permettra de choisir entre une collection triée (comme un arbre, et donc une map) ou une collection plus rapide à parcourir, mais à trier une fois (vector)

Dans ce cadre de réduction de complexité, il faut choisir une unité de temps.
J'en vois trois: l'affectation, l'accès à une collection et l'accès disque

En général, c'est en nombre d'accès aux collections qu'il faut faire attention.

Quant à la magie, réserve la aux cas ultimes, et c'est vraiment au coup par coup, une fois que tu sais que le programme est algorithmiquement optimal.

[Ehonn]

Réduire le volume total d'informations
Là, il s'agit de tenter de supprimer des calculs.
Je n'ai pas d'idée d'exemple à te donner, mais l'idée est que rien n'ira plus vite que de se passer d'un long calcul.

Pour les calculs itératifs (convergence), on peut commencer en simple précision et finir en double précision.
Dans certains cas, on peut se contenter d'une solution approchée (algorithme génétique contre recherche exhaustive).

[Davidbrcz]

Salut,

Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
http://frouin.me/optimisation-en-cpp/

Après.. Toutes les structures que tu utilises dans ton programme (vector, list, map) n'ont pas la même réactivité si je puis dire : penche toi sur la notion de complexité, et poses toi toujours la question de savoir si tu ne peux pas utiliser une autre structure.

Le plus simple, évidement, c'est de chronométrer un algorithme (perso j'utilise sf::Clock avec la bibliothèque SFML, mais il doit y avoir l'équivalent dans la bibli standard), et de voir quelles modifications peuvent être efficaces en terme de rapidité.

Cordialement,

Le lien que tu donne est clairement le genre de chose a (globalement) NE PAS FAIRE, c'est a dire des micros optimisations dans tous les sens, qui vont dégrader fortement la lisibilité du code (et donc complexifier sa maintenance et/ou debug) alors que le compilateur fera mieux que toi dans 99% des cas Tant que la règle du As-if n'est pas brise, il peut faire ce qu'il veut avec ton programme (réarrangement des instructions, réutilisation de variable,...) et au final ce que tu aura écrit ne sera pas ce qui sera exécute.

[MrPchoun]

Le lien que tu donne est clairement le genre de chose a (globalement) NE PAS FAIRE, c'est a dire des micros optimisations dans tous les sens, qui vont dégrader fortement la lisibilité du code (et donc complexifier sa maintenance et/ou debug) alors que le compilateur fera mieux que toi dans 99% des cas Tant que la règle du As-if n'est pas brise, il peut faire ce qu'il veut avec ton programme (réarrangement des instructions, réutilisation de variable,...) et au final ce que tu aura écrit ne sera pas ce qui sera exécute.

Bonjour,

Effectivement, certaines optimisations proposées par l'article rendent le code carrément illisible, après si on les utilise juste pour une petite fonction, à mon sens, ce n'est pas bien grave. Il y a tout de même quelque éléments intéressants : éviter les tests dans les boucles, préférer les entiers aux réels, les multiplications (*0.5) aux divisions (/2), et dans une série de tests, placer le test le plus probable en tête..



Cordialement,

[Davidbrcz]

Bonjour,

Effectivement, certaines optimisations proposées par l'article rendent le code carrément illisible, après si on les utilise juste pour une petite fonction, à mon sens, ce n'est pas bien grave. Il y a tout de même quelque éléments intéressants : éviter les tests dans les boucles, préférer les entiers aux réels, les multiplications (*0.5) aux divisions (/2), et dans une série de tests, placer le test le plus probable en tête..



Cordialement,

Non. Dans le tas, ya du bon sens (oui, l'arithmétique entiere est plus rapide que celle flottants, c'est logique). Pour multiplication vs division, j'attends de voir l'ASM généré, car c'est typiquement le truc que le compilateur va faire comme un grand.

Pour placer le coup du test le plus probable, c'est vrai mais il faut connaitre comment marche un processeur pour comprendre le pourquoi.
Pour éviter de pourrir le pipeline d'instruction, le CPU va faire lors d'un test un pari sur quelle branche va être la bonne et charger les instructions correspondantes. Si jamais il se plante, il doit vider le pipeline et ca prend du temps. Si en plus c'est dans une boucle et quil se plante a chaque fois, tu plombes les perfs...

C'est pareil pour le cache ; le temps d’accès RAM est constant, donc autant en lire le plus possible (en choisissant via le principe de localité) et mettre le tout en cache. Donc si a l'instruction suivante, tu n'utilises pas ce qui mis en cache, tu prends un cache miss, le CPU doit alors vider le cache et retourner chercher ce qu'il faut en RAM. ca aussi ca plombe les perfs...

En général les gains se feront sur l'algorithme : En premier lieu en réduisant la complexité de l'algorithme, et ensuite travailler le code pour qu'il soit cache friendly. Mais ca ne se fait pas sans avoir lu un cours d’architecture, ce qui devrait être obligatoire dans tout cursus qui fait du big data/HPC.

[TropMDR]

préférer [...] les multiplications (*0.5) aux divisions (/2)

Euh, "lol"? Cet article est mauvais, et ta lecture de l'article est encore pire :-\

[Joel F]

Salut,

Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
http://frouin.me/optimisation-en-cpp/

j'aime bien ce billet, il contient plein de chose vrai ... en 1990 quand les compilos etaient juste merdiques .
90% du temps ce genre de micro-optimisation est inutile, le compilo en fait des meilleurs, cf http://www.fefe.de/source-code-optimization.pdf