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!!
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!!
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
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, ...)
"Never use brute force in fighting an exponential." (Andrei Alexandrescu)
Mes articles dont Conseils divers sur le C++
Une très bonne doc sur le C++ (en) Why linux is better (fr)
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,
"There should be no boundaries to human endeavor" - Hawking
Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei
J'avais eu un professeur qui résumait l'optimisation ainsi:
- Choisir un compromis espace-temps
- Établir un contexte favorable,
- 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",
- Réduire la complexité de tous les grands calculs,
- 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.
Mes principes de bases du codeur qui veut pouvoir dormir:Pour faire des graphes, essayez yEd.
- Une variable de moins est une source d'erreur en moins.
- Un pointeur de moins est une montagne d'erreurs en moins.
- Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
- jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
- La plus sotte des questions est celle qu'on ne pose pas.
le ter nel est le titre porté par un de mes personnages de jeu de rôle
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.
"Never use brute force in fighting an exponential." (Andrei Alexandrescu)
Mes articles dont Conseils divers sur le C++
Une très bonne doc sur le C++ (en) Why linux is better (fr)
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,
"There should be no boundaries to human endeavor" - Hawking
Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei
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.
"Never use brute force in fighting an exponential." (Andrei Alexandrescu)
Mes articles dont Conseils divers sur le C++
Une très bonne doc sur le C++ (en) Why linux is better (fr)
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
Euh, "lol"? Cet article est mauvais, et ta lecture de l'article est encore pire :-\Envoyé par MrPchoun;7829721} Il y a tout de même quelque éléments intéressants : [...
Même avec -ffast-math ou -Ofast ?
Je suis très satisfaite de vos réponses précise et concrète et vous remercie donc sincèrement. Merci Beaucoup!!
Juste pour préciser deux trois choses :
1) Oui cet article date de il y a fort fort longtemps, gcc 2, et concernait des notes que j'avais prise lors d'écriture de code sur des Symbian, Wince ou Brew avec très peu de mémoire et ARM !
2) Oui, il faudrait que je le reprenne, la lisibilité du code en prend un coup, et moi même n'est pas réussi très longtemps à m'y tenir, surtout en switchant de language.
3) Bien sure de nos jours les pré-processeur / compilo s'en sorte mieux, après cela peut permettre de comprendre.
4) J'ai quelques articles sur le timming et les optimis ASM (comme y'en a qui en parlent) : http://frouin.me/category/cpp/
5) Je n'ai pas la science infuse donc ... c'est surtout un support de discussion et de réflexion
Voila
Allons y, parlons de http://frouin.me/optimisation-en-cpp/.
Voyons voir. J'ai le code suivant:Dans les cas ou l’indice de boucle n’est pas utilisé dans la boucle, une boucle pré-décrémentale et bien plus efficace qu’une boucle post-incrémentale :
Peut-être optimise par:
Code : Sélectionner tout - Visualiser dans une fenêtre à part for(int i=0; i<Count; i++) DoSomething();
Cette boucle génère 2 instructions de moins et réorganise la boucle de façon linéaire.
Code : Sélectionner tout - Visualiser dans une fenêtre à part for(int i=Count+1; --i;) DoSomething();
Avec la version "rapide" et "lente" de la boucle. Le code genere par Clang en -O2:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 void SlowIter(int iter, void (*f)()) { for (int i = 0; i < iter; i++) { f(); } } void FastIter(int iter, void (*f)()) { for (int i = iter + 1; --i;) { f(); } }
Difference? Ligne 21 [inlinecode]jle LBB0_2[/inlinecode] vs. ligne 57 [inlinecode]je LBB1_2[/inlinecode]. Soit aucune.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 __Z8SlowIteriPFvvE: ## @_Z8SlowIteriPFvvE .cfi_startproc ## BB#0: pushq %rbp Ltmp3: .cfi_def_cfa_offset 16 Ltmp4: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp5: .cfi_def_cfa_register %rbp pushq %r14 pushq %rbx Ltmp6: .cfi_offset %rbx, -32 Ltmp7: .cfi_offset %r14, -24 movq %rsi, %r14 movl %edi, %ebx testl %ebx, %ebx jle LBB0_2 .align 4, 0x90 LBB0_1: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 callq *%r14 decl %ebx jne LBB0_1 LBB0_2: ## %._crit_edge popq %rbx popq %r14 popq %rbp ret .cfi_endproc .globl __Z8FastIteriPFvvE .align 4, 0x90 __Z8FastIteriPFvvE: ## @_Z8FastIteriPFvvE .cfi_startproc ## BB#0: pushq %rbp Ltmp11: .cfi_def_cfa_offset 16 Ltmp12: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp13: .cfi_def_cfa_register %rbp pushq %r14 pushq %rbx Ltmp14: .cfi_offset %rbx, -32 Ltmp15: .cfi_offset %r14, -24 movq %rsi, %r14 movl %edi, %ebx testl %ebx, %ebx je LBB1_2 .align 4, 0x90 LBB1_1: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 callq *%r14 decl %ebx jne LBB1_1 LBB1_2: ## %._crit_edge popq %rbx popq %r14 popq %rbp ret .cfi_endproc
Suivant
Testons. Code:Même dans certain cas ou l’indice est utilisé, il est plus efficace d’utiliser un autre index :
Peut être optimise par
Code : Sélectionner tout - Visualiser dans une fenêtre à part for(int i=0; i<Count; i++) Tableau[i]=GetNextValue() ;
Ou encore mieux
Code : Sélectionner tout - Visualiser dans une fenêtre à part for(int i=Count+1,j=0; --i; j++) Tableau[j]=GetNextValue();
Code : Sélectionner tout - Visualiser dans une fenêtre à part for(int i=Count+1,*ptr=Tableau; --i; ptr++) *ptr=GetNextValue();
Assembleur produit:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 void SlowLoop(int size, int array[], void (*f)(int)) { for (int i = 0; i < size; i++) { f(array[i]); } } void FastLoop(int size, int array[], void (*f)(int)) { for (int i = size + 1, *ptr = array; i--; ptr++) { f(*ptr); } }
Pour aider a lire, la boucle "lente":
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95 .section __TEXT,__text,regular,pure_instructions .globl __Z8SlowLoopiPiPFviE .align 4, 0x90 __Z8SlowLoopiPiPFviE: ## @_Z8SlowLoopiPiPFviE .cfi_startproc ## BB#0: pushq %rbp Ltmp3: .cfi_def_cfa_offset 16 Ltmp4: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp5: .cfi_def_cfa_register %rbp pushq %r15 pushq %r14 pushq %rbx pushq %rax Ltmp6: .cfi_offset %rbx, -40 Ltmp7: .cfi_offset %r14, -32 Ltmp8: .cfi_offset %r15, -24 movq %rdx, %r14 movq %rsi, %rbx movl %edi, %r15d testl %r15d, %r15d jle LBB0_2 .align 4, 0x90 LBB0_1: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 movl (%rbx), %edi callq *%r14 addq $4, %rbx decl %r15d jne LBB0_1 LBB0_2: ## %._crit_edge addq $8, %rsp popq %rbx popq %r14 popq %r15 popq %rbp ret .cfi_endproc .globl __Z8FastLoopiPiPFviE .align 4, 0x90 __Z8FastLoopiPiPFviE: ## @_Z8FastLoopiPiPFviE .cfi_startproc ## BB#0: pushq %rbp Ltmp12: .cfi_def_cfa_offset 16 Ltmp13: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp14: .cfi_def_cfa_register %rbp pushq %r15 pushq %r14 pushq %rbx pushq %rax Ltmp15: .cfi_offset %rbx, -40 Ltmp16: .cfi_offset %r14, -32 Ltmp17: .cfi_offset %r15, -24 movq %rdx, %r14 movq %rsi, %rbx movl %edi, %r15d cmpl $-1, %r15d je LBB1_3 ## BB#1: ## %.lr.ph.preheader notl %r15d .align 4, 0x90 LBB1_2: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 movl (%rbx), %edi callq *%r14 addq $4, %rbx incl %r15d jne LBB1_2 LBB1_3: ## %._crit_edge addq $8, %rsp popq %rbx popq %r14 popq %r15 popq %rbp ret .cfi_endproc .subsections_via_symbols
et la boucle "rapide":
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 LBB0_1: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 movl (%rbx), %edi callq *%r14 addq $4, %rbx decl %r15d jne LBB0_1
Difference? Aucune. Perte de lisibilite? Considerable.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 LBB1_2: ## %.lr.ph ## =>This Inner Loop Header: Depth=1 movl (%rbx), %edi callq *%r14 addq $4, %rbx incl %r15d jne LBB1_2
La suivante est bien marrante:
Testons:Par contre :
ne sera pas optimisé par le compilateur et restera une multiplication.
Code : Sélectionner tout - Visualiser dans une fenêtre à part int a=b*17;
Alors que :
est bien meilleur même si cela génère deux instructions au lieu d’une.
Code : Sélectionner tout - Visualiser dans une fenêtre à part int a=(b<<4)+b;
Code produit:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 int SlowMult(int i) { return i * 17; } int FastMult(int i) { return (i << 4) + i; }
Et oui, vous avez bien lu, le code est rigoureusement le meme, mais en plus, c'est une multiplication par 17 et non pas un shift/add! Les auteurs de compilos sont obligés d'écrire des "desoptimiseurs" pour retirer ce genre de code stupide... En fait les approches ont le meme temps d'execution, mais la version a coup de shift et + a plus d'instructions. Et qui dit plus d'instructions dit mauvaise utilisation du cache. Bref, la encore, une optim qui ne sert a rien.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 __Z8SlowMulti: ## @_Z8SlowMulti .cfi_startproc ## BB#0: pushq %rbp Ltmp2: .cfi_def_cfa_offset 16 Ltmp3: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp4: .cfi_def_cfa_register %rbp imull $17, %edi, %eax popq %rbp ret .cfi_endproc .globl __Z8FastMulti .align 4, 0x90 __Z8FastMulti: ## @_Z8FastMulti .cfi_startproc ## BB#0: pushq %rbp Ltmp7: .cfi_def_cfa_offset 16 Ltmp8: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp9: .cfi_def_cfa_register %rbp imull $17, %edi, %eax popq %rbp ret .cfi_endproc
La suggestion sur la "multiplication par l'inverse d'un flottant" oublie de preciser que le resultat n'est pas le meme. Et pour MrPchoun qui dit qu'il faut "preferer les multiplications (*0.5) aux divisions (/2)", j'ai fait le test, il n'y a aucune difference pour ces deux valeurs.
Continuons:
Testons.L’utilisation de variable temporaire dans des boucles permet de forcer le chargement en registre des valeurs. Ceci est particulièrement vrai pour les pointeurs et les références de tableau:
Deviendra :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 If (NeedCopy) { for(int i=1001;--i;) DataCopy[i]=myClass.Data[i] ; }
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 If (NeedCopy) { int *tmp=myClass.Data; for(int i=1001;--i;) DataCopy[i]=tmp[i]; }
Le code produit est un peu trop long pour etre copie, mais voila la boucle interne "rapide":
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 struct Foo { int size; int data[]; }; int SlowSum(const Foo& foo) { int result = 0; for (int i= 0; i < foo.size; i++) { result += foo.data[i]; } return result; } int FastSum(const Foo& foo) { int result = 0; const int* data = foo.data; for (int i= 0; i < foo.size; i++) { result += data[i]; } return result; }
Et la "lente"
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 LBB1_3: ## %vector.body ## =>This Inner Loop Header: Depth=1 movdqa %xmm1, %xmm2 movdqa %xmm0, %xmm3 movdqu 4(%rdi,%rsi,4), %xmm0 movdqu 20(%rdi,%rsi,4), %xmm1 paddd %xmm3, %xmm0 paddd %xmm2, %xmm1 addq $8, %rsi cmpq %rsi, %rax jne LBB1_3
C'est evidement rigoureusement le meme code, puisque le compilo a sorti de la boucle l'access au champ de la structure.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 LBB0_3: ## %vector.body ## =>This Inner Loop Header: Depth=1 movdqa %xmm1, %xmm2 movdqa %xmm0, %xmm3 movdqu 4(%rdi,%rsi,4), %xmm0 movdqu 20(%rdi,%rsi,4), %xmm1 paddd %xmm3, %xmm0 paddd %xmm2, %xmm1 addq $8, %rsi cmpq %rsi, %rax jne LBB0_3
En conclusion, cette page "d'optimisation" est pleine de suggestions qu'un compilateur fait tres bien tout seul, voir pire, que le compilo doit retirer! Et tout ca au prix d'un code source bien moins lisible.
Donc je confirme: ces conseils sont A NE SURTOUT PAS SUIVRE
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager