Discussion :

[jfloviou]

Bonjour à tous, je suis nouveau sur ce forum et suis à la recherche de tous les trucs et astuces du plus bateau au plus compliqué pour un code plus efficace en vitesse de calcul: ex mieux vaut une boucle FOR ou l'usage du WHILE ? La pile est elle vraiment plus rapide que le tas?
l'usage de inline c'est mieux pour la vitesse?

et tous les autres...

Donc si vous connaissez des sites, ou des astuces, merci!

jaja

[loic.radio]

Bonjour,

Les astuces de bases les plus utiles :

- ne jamais utiliser de double ni de float si on peut faire autrement,
- utiliser les fonctions inline si possible,
- si tu as des calculs utilisant fréquement des sinus, cosinus.. calcul les une fois et mets les dans un tableau indexé ( ex au lieu de cos(12), calcul tout les cos jusqu'à 360 et mets-les dans un tableau double MonCos : cos(12) devient MonCos[12]).
- sauter dans les fichiers (utiliser ftell et fseek) au lieu de lire octet par octet.
- essayer d'avoir le moins de division et de multiplication possible.
- utiliser les décalages plutot que les multiplication ou division si multiple de 2 : ex : x<<2 au lieu de x=x*2
- etc, etc,etc

[exxos]

pour ce qui est des float, je crois que maintenant avec les new processeurs c aussi bien gere que des int. mais bon a voir ....

pour ce qui est des parcours des tab, il vaut mieux des pointeurs mobile:
de meme, il vaut mieux comparer qqch avec qqch du registre (ici le 0), voir meme 2 choses du registre entre eux:

ex:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int tab[50000];
for(int i(0);i<50000;i++){
//qqch a faire
}

remplacer par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int tab[50000];
int * ptr=tab;
register int i=50000;
while (i--){
//qqch a faire
}

[Musaran]

Je suis tombé sur ce vieux topic au hasard d'une recherche...
Et je le remonte sans honte !


Commentaires:
Ne pas remplacer une division (par une puissance de 2) par un décalage !
Le compilateur sait très bien le faire.
Et puis ça ne marche pas sur les nombres négatifs.

register est un voeu pieu... Là aussi, le compilateur sait très bien décider tout seul.

inline est pareil...
Attention à ne pas forcer, l'augmentation de taille du code pourrait annuler le gain des appels de fonctions évités.


Conseils:
Attention, tout ceci est à comprendre 'dans la mesure du raisonnable'.

-prendre un bon compilateur ! Lui faire confiance pour les optimisations de base.

-utiliser des librairies efficaces !

-simplifier les expressions.

-avoir une structure de programme efficace.

-mesurer les performances, se concentrer sur les 20% de codes consommant 80% du temps. Typiquement les boucles imbriquées.

-préférer les entiers aux flottants.

-préférer le type int, c'est quasiment par définition le plus rapidement manipulé par le processeur.

-spécifier const tout ce qui peut l'être. Si ça bouge pas, pas besoin d'aller y voir..

-éviter les opérations d'écriture.

-mettre des assert dans le code. En plus de capturer des bogues, certains compilateurs savent s'en servir comme indices d'optimisation.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
signed int i= ...;
assert(i>0);
...=i/4; //bien que signé, i est positif, et /4 est remplacé par >>2.

-éviter les appels systèmes. Ils engendrent un changement d'état du processeur qui consomme une centaine de cycles d'horloge...

-éviter les E/S, surtout les accès disques.

-gérer un tampon avec les E/S lentes. fopen au lieu de open par exemple.

-éviter les branchements, ils impliquent un "jump" au niveau processeur, ce qui nuit aux enchaînements de traitements.
Les boucles(for et (do)while) impliquent une condition à chaque itération. do...while fait un branchement de moins à la fin.
Une condition (if/else et ?:) implique un branchement. if sans else n'a de branchement que si faux.
Le branchement goto nuit à la compréhension qu'à le complilateur de votre code.
Si vous l'utilisez quand même, sachez que les accolades traversées engendrent des libérations/allocations/initialisations sur la pile, donc c'est plus qu'un simple "jump" processeur.

-mettre la moité la plus fréquente du if-else côté... je sais plus !

-dérouler les boucles. Euh... non! Le compilateur s'en charge.

-éviter les appels de fonctions. En plus du double saut aller-retour, il y a des sauvegardes de registres.

-manier les compteurs de max vers 0. Car les comparaisons avec 0 sont plus rapides.

-utiliser des pointeurs mobiles plutot que des indices.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
p++ ; //1 addition
*p  ; //1 déréférencement
 
i++ ; //1 incrémentation
t[i]; //*(t+i) 1 multiplication, 1 addition, 1 déréférencement

-ne pas copier inutilement les données. Traitements sur les chaînes par exemple...

-pré-calculer ce qui peut l'être.

-éviter les allocations dynamiques.

-ne pas confondre nombre de lignes de source et taille du code compilé.

-ne pas faire de choses inutiles. C'est évident...

-cherchez la localité de référence.
Ça veut dire faire des accès sur les mêmes données (ou adjacentes) à peu d'intervalle.
Pour bénéficier à plein des caches processeur, carte mère, mémoire, système, disque, ect...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int tab[X][Y];
for(y=0;y<Y;y++)
	for(x=0;x<X;x++)
		tab[x][y]; //mauvais, x varies le plus vite
for(x=0;x<X;x++)
	for(y=0;y<Y;y++)
		tab[x][y]; //bon, c'est la dernière dimension dont les cellules sont adjacentes en mémoire

-faire des accès linéaires. Car les caches pré-chargent les données adjacentes.


C'est tout pour cette fois, mais il y en aura sûrement d'autres...

[gl]

Penser dans les options de compilation a parametrer le compilateur en 'optimisation de temps d'execution'

[shef]

Et surtout bencher régulièrement son appli au fur et à mesure des potimisations, pour se rendre compte de leur effet (ou de la dégradation)

[fd]

...et generer le code assembleur pour l'optimiser eventuellement (je parle de l'optimiser en C/C++ et pas taper ds l'asm directement bien entendu)

[olivic]

Et faire des vrais algo. J'ai vu un prog avec un trie bulle pour trié un tableau avec à coté des décallage binaire partout.

Quand je vois des personnes qui créés des class existante (liste chainé par ex) je suis persuadé qu'elles sont moins efficace que la STL.

[Pazz]

> olivic : pas d'accord avec toi. Tu peux faire une liste bien chainée bien plus efficace que celle de la STL, par contre elle n'aura pas la même robustesse.

Avantages de la STL : efficacité connue mais pas forcément optimale (mais toujours correcte), et surtout utilisable dans toutes conditions, tous les cas ont été pensés.

Mais si c pour un cas particulier tu peux faire bien plus rapide.

[Musaran]

Choisir comme option d'appel par défaut des fonctions "fastcall".

Le standard est "stdcall" il me semble, c'est l'appelant de la fonction qui nettoie les arguments passés.

Ça doit bien faire... oh... 3 octets de perdus par appel de fonction, c'est intolérable !

[LeGreg]

- ne jamais utiliser de double ni de float si on peut faire autrement,

Vous pouvez utilisez les float tant que vous voulez surtout que le besoin s'en fait sentir avec l'informatique moderne.
Par contre, vous devriez limiter les conversions float -> int -> float.
Limitez l'utilisation du fmod a ce qui est necessaire.
Sinon les multiplications, additions, soustractions de float sont assez rapides sur les processeurs > pentium. ce ne sera pas le facteur limitant si tu es obligé de faire du code compliqué pour compenser l'absence du float.

- si tu as des calculs utilisant fréquement des sinus, cosinus.. calcul les une fois et mets les dans un tableau indexé ( ex au lieu de cos(12), calcul tout les cos jusqu'à 360 et mets-les dans un tableau double MonCos : cos(12) devient MonCos[12]).

Gain non garanti pour des raisons d'etranglement sur l'acces à la lookup table alors que les processeurs incluent une instruction de calcul du cosinus. A n'utiliser que pour des processeurs limités en virgule flottante (proc embarqués) et meme la ca peut etre parfois plus rapide et aussi efficace de faire le calcul par approximation.

- essayer d'avoir le moins de division et de multiplication possible.

Beaucoup plus vrai pour les divisions que pour les multiplications qui sont assez rapides. Notez que diviser par X revient a multiplier par 1/X mais c'est un truc de base, il paraitrait meme que des compilateurs l'optimisent (quand il s'agit de constantes).

Ne pas remplacer une division (par une puissance de 2) par un décalage !Le compilateur sait très bien le faire.
Et puis ça ne marche pas sur les nombres négatifs.

moi j'aime bien generer des puissances de deux par un 2^n = 1 << n;
Sinon la puissance de deux en binaire a une propriete interessante
on peut calculer son modulo par un & (2^n-1)
et on peut l'arrondir a la puissance de deux voulue par l'opération complementaire & ~(2^n-1).
Ca ne sert presque a rien. Enfin de toute facon ce genre d'optimisation vous le ferez après la touche finale si jamais ca a une importance quelconque.

inline est pareil...
Attention à ne pas forcer, l'augmentation de taille du code pourrait annuler le gain des appels de fonctions évités.

Si vous pensez qu'une methode peut-etre inline, pensez a la mettre
dans le fichier header de votre classe, sinon le compilo ne saura pas ou trouver le corps de la fonction pour l'inliner. (certains ont un fichier header qu'ils appellent machin.inl pour spécifier qu'il contient les définitions des fonctions inlinables)

-prendre un bon compilateur ! Lui faire confiance pour les optimisations de base.

C'est lesquels les mauvais compilateurs?
perso j'utilise MSVC++, c'est bien suffisant
pour ce que je fais.

-avoir une structure de programme efficace.

Oui avant de chercher a gagner des cycles sur une boucle
voir si l'algo qui prend une heure ne peut pas etre ramené
a un algo qui prend une minute par analyse du probleme.

-préférer les entiers aux flottants.

cf ma remarque ci dessus

-préférer le type int, c'est quasiment par définition le plus rapidement manipulé par le processeur.

Ca veut dire que bool ne peut pas etre manipulé rapidement par le proc?
L'important c'est tout de meme la proprete des types manipulés par le programme, le compilateur fait sa sauce derriere pour arranger ca au mieux.

-spécifier const tout ce qui peut l'être. Si ça bouge pas, pas besoin d'aller y voir..

Je ne crois pas que le compilateur optimisera tres souvent sur const.
Par contre un code peut-etre optimisé pour du const-specific
exemple: surcharge d'une methode const sur une string qui renvoie un char plutot qu'une reference vers un char.

-éviter les opérations d'écriture.

??

-ne pas faire de choses inutiles. C'est évident...

Ah tu veux dire, eviter de mettre des noop au milieu du code?

[snip] (je coupe)

Ca fait tout de meme beaucoup de regles dont certaines ont un interet qui est soit tres faible soit risquent d'etre mal interpretées.

LeGreg

[Pazz]

ne jamais utiliser de double ni de float si on peut faire autrement,

à noter que sur les Pentium IV, ALU et FPU peuvent fonctionner simultanément.

Donc si tu as besoin de faire 20% d'op sur des floats et 80% sur des entiers, tu lances une op sur float, 4 sur entiers, une sur float, 4 sur entiers etc.

Bon évidemment c plus facile à faire en asm qu'en C++ mais on voit quand même la différence.

Je ne sais pas si certains compilo réalisent cette optimisation pour l'instant spécifique à un CPU.

[haypo]

Je suis p'têtre HS, mais je veux quand même faire part de ma pensée : je me concentre sur la qualité du code, le rendre portable, bien optimiser les algorithmes. L'optimisation en elle-même : compilateur s'en charge :-)

En jouant avec les "petites" optimisations : décalages binaires, utiliser int plutôt que float, etc., on gagne des performances, c'est sûr, mais ça rend le code moins compréhensible et donc plus difficile à maintenir et déboguer ...

Un changement d'algorithme par contre permet des gains énorme de performances ! On passant d'une liste simplement chaînée à une liste doublement chaînée je passe d'un calcul de 3.5 secondes à 20 millisecondes !!! Simplement car effacer un élément dans une liste chaînée demande à connaître l'élément précédent, il faut donc parcourir la liste ... quand tu as 1 million d'élément, ça prend le temps qu'il faut :-)

Par contre j'ai un faible pour le mot clé "const".

On m'a d'ailleurs dit qu'il fallait plutôt utiliser "const int cst_x = 4;" que "#define cst_x (4)". Je doute. Mon problème est surtout de placer des "const type var=valeur;" dans un fichier .H ... "Impossible de précompiler l'entête car il contient du code" :-( Et si je mets un "extern" devant, et que je le déclare avec sa valeur dans le .CPP ... Ca marche pas, il me dit que la variable n'est pas définit ou je ne sais pas quoi :-/

@+ Haypo

[LeGreg]

Un changement d'algorithme par contre permet des gains énorme de performances ! On passant d'une liste simplement chaînée à une liste doublement chaînée je passe d'un calcul de 3.5 secondes à 20 millisecondes !!! Simplement car effacer un élément dans une liste chaînée demande à connaître l'élément précédent, il faut donc parcourir la liste ... quand tu as 1 million d'élément, ça prend le temps qu'il faut :-)

Oui le meilleur moyen de faire du code rapide
c'est de faire une analyse du probleme et d'en déduire
la structure de donnée la moins mauvaise à utiliser.

Donc conseil au programmeur débutant: n'apprend pas de quel coté du if il faut mettre le bloc le plus probable, cela te donnera une fausse idée que tu maitrises la machine. Par contre prend des cours d'algorithmique de base ou lis un bouquin (style introduction a l'algorithmique de Thomas Cormen).

On m'a d'ailleurs dit qu'il fallait plutôt utiliser "const int cst_x = 4;" que "#define cst_x (4)". Je doute. Mon problème est surtout de placer des "const type var=valeur;" dans un fichier .H ... "Impossible de précompiler l'entête car il contient du code" :-( Et si je mets un "extern" devant, et que je le déclare avec sa valeur dans le .CPP ... Ca marche pas, il me dit que la variable n'est pas définit ou je ne sais pas quoi :-/

Entre les const et les define c'est un peu la guerre.
Par contre ce qui est sur c'est qu'on peut toujours remplacer
une suite de define par un type enum. C'est une maniere de typer plus fortement un entier, et en plus une
variable de type enum apparaitra sous son nom propre dans
le debogueur, ce qui peut etre un gain de temps.

Pour ce qui est de la définition des constantes globales:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

extern const type mavar; // dans le .h

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

const type mavar = .. ; // dans le cpp

normalement ca marche.
Quel est ton code et quel est ton message d'erreur? (a la compilation ou lors de l'édition de liens?)

LeGreg

[Pazz]

bien d'accord avec vous, ce qui prime c avant tout la structure de donnée et l'algo, et seulement ensuite l'implémentation.

Mais c plus compliqué à expliquer dans le forum

[Musaran]

moi j'aime bien generer des puissances de deux par un 2^n = 1 << n;

Moi aussi. Mais cela implique:

Supposition 1) << et >> signifient déclage vers le poids fort/faible.
Les explications que je lis parlent juste de gauche/droite.
L'effet serait inversé avec le "boutisme" de bits opposé ?

Supposition 2) Les nombres sont représentés en système de base partant de 0, ou arabe, je ne sais pas trop comment on dit.
Il existe d'autres représentations, certes moins courantes: décimal codé binaire, fibonacci, biaisé...

Supposition 3) Les nombres sont représentés en base 2 (binaire).
En base n, ce serait multiplier/diviser par n.

Des suppositions légères, mais des suppositions quand même.

Nota: il est vrai que mon manuel dit que <<1 revient à *2.

C'est lesquels les mauvais compilateurs?

Je ne sais pas...
Mais le jour où j'ai besoin que mon exécutable soit effectivement performant, la première chose que je fais, c'est de me renseigner là-dessus.

-préférer le type int, c'est quasiment par définition le plus rapidement manipulé par le processeur.

Ca veut dire que bool ne peut pas etre manipulé rapidement par le proc?
L'important c'est tout de meme la proprete des types manipulés par le programme, le compilateur fait sa sauce derriere pour arranger ca au mieux.

Je veux dire:
Si le type n'est pas soumis à une contrainte particulière, comme initialisé par tel autre type, passé a une fonction, surpasser ou pas, avoir des décimales, être signé ou pas...
...alors, il faut prendre int.
Prendre un type plus petit en se disant "il prends moins de place en mémoire, j'y gagne" risque surtout de forcer le compilateur à générer du code supplémentaire, ou à utiliser des instructions processeur anciennes pour y accéder conformément au code écrit.

int est par définition de la taille que le processeur manipule le mieux (mais au moins 32 bits dans les dernières normes).
En interne, les types <int sont placés dans un espace d'un int, le compilateur sait ce qu'il fait.

Je ne crois pas que le compilateur optimisera tres souvent sur const.

Je crois l'inverse.
Je crois même qu'il traque ce qui est const sans l'avoir été déclaré.
Mais de toutes façon, il vaudrais mieux savoir que croire.

-éviter les opérations d'écriture.

??

J'ai été un peu bref, là...
Je veux dire qu'une écriture, que ce soit en mémoire ou sur disque ou autre, est typiquement plus longue qu'une lecture.
Ça peut être intéressant de travailler sur une valeur temporaire, et de n'écrire le résultat qu'une fois.

Ca fait tout de meme beaucoup de regles dont certaines ont un interet qui est soit tres faible soit risquent d'etre mal interpretées.

Oui...
Toutes les expliquer en détail serait trop long.
Mais je préfères les donner que de les taire.
Ceux qui sont intéressés doivent se documenter pour bien comprendre, c'est clair...

Une optimisation mal faite peut être pire que le code non-optimisé !

[Musaran]

En C, on ne peut pas partager les variables constantes par un header comme en C++.
Chaque source crée sa propre constante.

Et si on utilises extern, la constante n'est pas connue à la compilation, ce qui permet moins d'optimisations (le C++ est également concerné).

Par contre, on peut substituer des enums pour les entiers int:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

enum{Maconst=5};

[Musaran]

Plutôt que de faire malloc/free dans un bloc pour une broutille...
...utiliser alloca, la mémoire est allouée sur la pile et automatiquement libérée à la sortie de bloc.

Toutefois:
-ce n'est pas standard.
-la pile n'est faites que pour quelques mégas maximum.

[LeGreg]

<< et >> signifient déclage vers le poids fort/faible.
Les explications que je lis parlent justent de gauche/droite.
L'effet serait inversé avec le "boutisme" de bits opposé ?

Bien sur que non! on parle de representation binaire du nombre
et non pas de sa representation en memoire (ou sur disque).

Supposition 2) Les nombres sont représentés en système de base partant de 0, ou arabe, je ne sais pas trop comment on dit.
Il existe d'autres représentations, certes moins courantes: décimal codé binaire, fibonacci, biaisé...

les operateurs binaires operent sur les representations binaires
des nombres. Point.

Je crois l'inverse.
Je crois même qu'il traque ce qui est const sans l'avoir été déclaré.
Mais de toutes façon, il vaudrais mieux savoir que croire.

Non tu crois probablement la meme chose que moi . Mais optimiser ce qui est effectivement "const" dans une expression, n'est pas ce que j'appelle moi optimiser sur le mot-clé "const".
(exemple classique : fonction(objet&, const objet &)..)

un article qui etaie ce que j'essaie d'expliquer tant bien que mal
http://www.gotw.ca/gotw/081.htm

LeGreg

[gl]

Supposition 2) Les nombres sont représentés en système de base partant de 0, ou arabe, je ne sais pas trop comment on dit.
Il existe d'autres représentations, certes moins courantes: décimal codé binaire, fibonacci, biaisé...

les operateurs binaires operent sur les representations binaires
des nombres. Point.

Non, Musaran a raison, vous ne parlais pas de la meme chose, toi tu parle de la base, lui de la representation.
En effet un nombre peut etre coder classiquement, c'est a dire qu'il est converti dans la base, ainsi en 10 decimal s'ecrit 0000 1010 en binaire et la effectivement >> et << corresponde nt a des multiplicationdivision par puissance de 2.

Maintenant un nombre peut aussi etre representer en BCD (binaire code decimal), 10 en decimal devient alors 0001 0000 et du coup << et >> pour mulitplier/diviser par 2 ne fonction plus. Pourtant on travaille dans les deux cas avec des operateur binaires.

En resume le binaire, decimal, hexadecimal, ... ne sont que de bases et quelque soit la base, le comportement et la valeur d'un nombre ne varie pas.

La numerotation classique, le BCD, ... sont des representations qui influe sur les proprietes du nombre