Discussion :

[gl]

Je comprends pas pourquoi << fonctionne pas pour les negatifs. Le compilateur est bien cencé savoir que le nombre est signé et remplacer par l'instruction assembleur corespondante :

Code :

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

1
2
3
4
5
int a;
unsigned int b;
 
a >>= 4;
b >>= 4;

devrait etre en toute logique remplacé par :

Code :

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

1
2
sar  a, 4
shr a, 4

On trouve même dans la doc assembleur

sar r/m, 1 : signed divided by 2
shr r/m, 1 : unsigned divide by 2

Si >> et << marche tres bien sur les nombres negatifs. Le but de ces instructions est de decaler les bits et non de faire une multiplication ou une division. Le fait que ca effectue sur des entiers non signe une multiplication ou une division est seulement une consequence de l'operation (du a la representation des entiers)

[Gandalf]

La premiere regle devrait etre de ne pas optimiser pour le plaisir mais par nessessitée.

commencer par faire un bench avant optimlisation, puis de profiler l'application pour trouver les quelques lignes de codes qui ont besoin d'etre optimisée...

Ensuite optimiser peut etre fait en tenant compte de la(des) plateforme(s)... c'est a dire en evaluant l'effet de chaque optimisation.

ex : les decalages de bits peuvent etre plus lent qu'une division par deux (cas du Pentium 4) le decalage de bit retrouvant une meilleur efficacité à partir de 4 (division par 16) environ

les inlines peuvent alourdir une fonction qui du coup depasser du cache instructions alors que sinon la fct en non-inline aurrait pu s'y trouver...

Les regles ne sont pas valables sur toutes les architectures, par contre le resultat en perte de lisibilité est souvent garanti...

Et pour le coup c'est la maintenance qui n'est pas optimisée...

[nyal]

La premiere regle devrait etre de ne pas optimiser pour le plaisir mais par nessessitée.

commencer par faire un bench avant optimlisation, puis de profiler l'application pour trouver les quelques lignes de codes qui ont besoin d'etre optimisée...

Ensuite optimiser peut etre fait en tenant compte de la(des) plateforme(s)... c'est a dire en evaluant l'effet de chaque optimisation.

ex : les decalages de bits peuvent etre plus lent qu'une division par deux (cas du Pentium 4) le decalage de bit retrouvant une meilleur efficacité à partir de 4 (division par 16) environ

les inlines peuvent alourdir une fonction qui du coup depasser du cache instructions alors que sinon la fct en non-inline aurrait pu s'y trouver...

Les regles ne sont pas valables sur toutes les architectures, par contre le resultat en perte de lisibilité est souvent garanti...

Et pour le coup c'est la maintenance qui n'est pas optimisée...

En résumé : Laisser faire le compilo. Il s'occupera trés bien bien. S'il faut commencer à connaitre tout les processeurs et optimiser pour chacun d'eux tu n'es pas sorti de l'auberge. Le compilo s'occupera de faire les optimisations selon le proc. Commencer à faire : heu atta il est de combien mon cache de niveau 1 et 2. ma pipeline gére combien d'instructions en méme temps. heu, j ai une pipeline specifique pour les nombres à virgules....

franchement on n'a fait des compilo, des langages évolué exprés pour éviter de se faire chier avec ce genre de choses. Simplement pour ce fixer un objectif : son programme et son algo.

[Blustuff]

M'ettonerai bien moi que le pentium 4 fasse les divisions par deux plus vite que un "shr eax, 1" !!! (qui est "pariable" donc qui peut prendre qu'un demi cycle)

Si >> et <<7 marche tres bien sur les nombres negatifs. Le but de ces instructions est de decaler les bits et non de faire une multiplication ou une division. Le fait que ca effectue sur des entiers non signe une multiplication ou une division est seulement une consequence de l'operation (du a la representation des entiers)

oui m'enfin ce que j'ai ecrit c'est que je vois pas pourquoi ca n'effectuerait pas une division par deux pour les nombres negatifs. (du au fait que les operations sur les decalage de bit marchent aussi bien en signé qu'en non signé et on tout les deux comme consequencecs la division par deux, que le nombre soit positif ou negatif. Seulement le C++ doit effectuer toujours une division signée que le noimbre soit signed ou unsigned)


Blustuff.

[Blustuff]

Va demander a ceux qui creent les moteurs 3D de quake 3 et dee unreal, si il n'utilise pas les optimisation du processeur. Si on parle d'optimisation, c'est parce que ca peut nous servir. (Moi je m'en sert pour l'ecriture d'un emulateur). Il n'y a pas tant de type dee processeur que ca, a partir du moment ou tu consifere que tu programmes pour un PC. Il y a (en assembleur) 4 types d'optimisations :

- remplaceer des instructions assembleur par des equivalent qui sont plus rapide (En général pour le 486)

- Optimisations pour le pentium 4 (Le trruc qui permet d'executer deux instructions en un cycle)

- Utilisation de la cache.

- Utilisation du mmx 3DNox, etc.

Les optimisations du C++ concernent quant a elle, la quasi-totalité des procecsseurs puisque ce sont des optimisations d'algorythme.


Blustuff.

[Blustuff]

Ca m'intriguait alors j'ai mis mon compilateur a l'épreuve (BC++ Builder 4). Et ca marche. on peut bien effectuer des divisions ou des multiplications par des puissances de 2 sur dees nombres negatifs. Essayez voir si ca marche sur votrre compilateur :

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
#include "iostream.h"
 
void main()
{
  unsigned int a = 100;
  signed int b = -100;
 
  cout << (a >> 1) << '\n';
 
  asm shr a, 1
  cout << a  << '\n';
 
  cout << (b >> 1)  << '\n';
 
  asm sar b, 1
  cout << b  << '\n';
}

qui donne la sortie (theoriquement) :

Code :

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

1
2
3
4
50
50
-50
-50

J'explique pour ceux que ca interesse. Lorsque le compilateur rencontre l'operateur << ou >> il "traduis" l'operation en une instructions assembleur choisie parmis "sar", "shr", "sal", "shl". Si c'est l'operateur >> l'instruction se finira par r (right) cad shr ou sar, si c'est << l'instruction sera shl ou sal. Si la variable a gauche de l'operateur << ou >> (cad l'operande sur laquelle on fait le décalage) est signed l'instrtuction correspondante sera sar ou sal, si l'operande est unsigned l'instruction assembleur sera shr ou shl.

Voici la différence entrte un decalage signé et un décalage non signé :

---------------------------------------------------------------------------------
--- Decalages vers la droite ---

* Decalage signé :

Ex :

Code :

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

1
2
signed int a = 24;
a >>= 2;

Representation binaire de 24 : 00011000
Après deux décalage à droite : xx000110

Pour connaitree la valeur des x, lors d'un decalage signé on regarde le bit de poid le plus fort. Ici c'est 0. Donc les x seront remplacé par des 0

Valeur finale de a : 00000110 (= 6 = 24 / 4)

Code :

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

1
2
signed int a = -24;
a >>= 2;

Representation binaire de 24 : 11101000
Après deux décalage à droite : xx111010

comme le bit de poid le plus fort est 1, les x sont remplacés par des 1

Valeur finale de a : 11111010 (= -6 = -24 / 4)


* Decalage non signé :

Ex :

Code :

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

1
2
unsigned int a = 24;
a >>= 2;

Representation binaire de 24 : 00011000
Après deux décalage à droite : xx000110

Dans le cas de nombres signés on remplace toujours les x par des 0.

Valeur finale de a : 00000110 (= 6 = 24 / 4)


--- Decalages vers la gauche ---

Code :

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

1
2
3
4
unsigned int a = 24
signed b = 24;
a <<= 2;
b <<= 2;

Representation binaire de 24 : 00011000
Après deux décalage à gauche : 011000xx

Pour le décalage a gauche, que l'operande soit signée ou non signée les x sopnt toujours remplacés par 0. (Ca n'aurait aucun sens si ct autrtement). C'est la raison pour laquelle sal et shl represente la même opération pour le processeur.

Valeur finale de a : 01100000 (= 96 = 24 * 4)

---------------------------------------------------------------------------------


Quoiqu'il arrive les décalages de bits sont toujours (theoriquement) des divisions ou des multiplications par des puissances de 2.


Blustuff.

[Musaran]

Toutes les variables constantes donnent exactement le même effet que les #define

Malheureusement non.
Une constante externe, par exemple, a une valeur inconnue du compilateur.
La preuve: elle ne peut pas servir de valeur case ou paramètre de patron en C++.

Je comprends pas pourquoi << fonctionne pas pour les negatifs.

Mais il marche ! La subtilité, c'est que >> arrondit vers le bas:

Code :

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

1
2
 3>>1 =  1,5 =  1
-3>>1 = -1.5 = -2

Ça n'est bien sûr pas une spécification du standard.

Et comme la division est définie comme entière, elle est censée arrondir vers 0, donc le compilateur ne remplace pas /2 par >>1 pour une valeur susceptible d'être négative.
CQFD.




Quand je pense 'optimisation'...

1) Il ne s'agit pas de faire le boulot du compilateur.
Simplement, au lieu d'être passif, on peut l'aider en se se débrouillant pour lui présenter les choses de façon favorable.
Encore faut-il avoir un vrai compilateur !

2) Le compilateur a une portée limitée.
Il y a des choses qui ne sont pas de son ressort, comme l'organisation intelligente des E/S, appels systèmes et accès mémoire.
C'est au développeur de connaître les coûts de ces opérations et de ne pas faire l'andouille.

3) Il n'y a pas que la vitesse propre a optimiser.
Il y a aussi la taille et la charge placée sur le système.

4) Une optimisation bien pensée sera portable, sûre, et automatique.


Si on pense à la réutilisation de code, ça ne fait pas de mal d'être vigilant dès le départ.
Une optimisation n'est pas forcément possible après-coup si c'est l'organisation qui est en cause.

On peut optimiser une fonction tout de qu'on veut, si à la base on aurait pu éviter son appel...

[Blustuff]

oui, mais c'est de la connerie ca les variables const externes :). Non, c'est vrai qu'en fait j'y avait pas pensé. Mais pour cec qui est des consts non externes mon compilateurs me les integre directement. Pour -3 >> 1 ca peut etre vrai, si on considère bien la definition ded la division euclidienne :

n = q*p + r avec q quotient, et r reste, 0 <= r < q

donc le resulta de la division euclidienne de -3 par 2 est -2 !!! (Cela dit ca n'a pas grand interet)


blustuff

[antony_esi]

Un petit conseil pour ceux qui utilise Borland C++:
Compiler en mode "ANSI" et hop en 2 temps trois mouvements le programme est près a etre executé !!!

[Musaran]

Il y a des conventions de passage d'argument aux fonctions.
C'est non-standard, mon compilateur dispose de:
fastcall qui utilise les registres (pour les arguments qui y tiennent).
stdcall qui utilise la pile.

fastcall devrait donc améliorer les performances.
Je pense même que cela évite à la fonction de devoir systématiquement sauvegarder et restaurer les registres, puisque l'appelant sait qu'ils vont être utilisés.

Mais est-ce le cas ?
Y a-t'il des cas défavorables ?


Dans un autre registre...
L'exemple des 'extern const' montre que la compilation en modules suivie de liaison entrave les optimisations globales, c-a-d à travers tout le code source utilisé par l'exécutable.
Comment peut-on aider le compilateur à faire des optimisations globales ?
Est-ce que mettre tout le code dans un unique fichier source peut aider ?
(on peut simuler cela en faisant un source qui #include une fois seulement de chaque autre source)

[LeGreg]

le compilateur de VC++ 7 fait des optimisations globales (entre les .o d'un projet). Je ne sais pas ce que ca recouvre.
Pour fastcall ca marche presque toujours faut juste faire attention aux callbacks, et evidemment a l'appel d'une fonction d'un .o ou d'un .lib depuis un projet qui n'utilise pas les memes conditions d'appels.

Pour le gros fichier source on fait comme ca chez nous. Mais c'est moins pour des problemes d'optimisations (les fonctions a inliner sont dans les headers et on n'a pas de extern const, que des classes et des objets)
que pour des problemes de temps de compilations.
Les differentes libs mettent un quart d'heure a compiler en mode "allsource" (un gros fichier avec les include par librairie ou dll).
Le comportement doit etre identique entre le projet compile allsource et celui compile normalement.

LeGreg

[ludovic.fernandez]

Et pour celui qui en veux, éditer l'assembleur à partir du C++, puis ré-arranger le fichier assembleur.

[LeGreg]

Question posee en entretien d'embauche:

Code :

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

1
2
3
4
5
int tab[MAX];
for (int i=0; i<MAX; i++)
{
   tab[i] = a * i * i + b * i + c + d;
}

1 - Lister les optimisations possibles pour rendre ce code plus rapide

2 - parmi les optimisations citées quelle est l'optimisation la plus susceptible d'etre effectuee par le compilateur et qu'il ne sert donc à rien d'effectuer à la main.

Evidemment l'interet est de voir si le candidat connait un tant soit peu les mécanismes d'optimisations des compilateurs et ne va donc pas passer son temps a optimiser du code inutilement.

LeGreg

[Blustuff]

moi pour répondre a cette question j'ai absolument besoin de savoir ce que sont a, b, c et d. De quel type ? des constantes ? ca va changer bcp de choses notement comment le compilateur va optimiser...

P.S. J'ai été très decu par l'optimisation que fesait mon compilateur de mon code.

[LeGreg]

ah bon tu en as besoin?

Pas besoin de se compliquer la tete
c'est juste un exemple a la con et
il n'y a pas de piege.

LeGreg

[Blustuff]

déja moi si MAX est inferieur à 10000 j'optimise pas, si c et d sont des constantes, le compilateur les remplace a l'execution par le resultat. Si a,b,c et d ne sont pas des int les optimisations vont etre différentes, suivant le type de chacune, pour eviter le maximum de conversions.

[LeGreg]

déja moi si MAX est inferieur à 10000 j'optimise pas, si c et d sont des constantes, le compilateur les remplace a l'execution par le resultat. Si a,b,c et d ne sont pas des int les optimisations vont etre différentes, suivant le type de chacune, pour eviter le maximum de conversions.

peu importe MAX, ce code peut etre execute beaucoup
de fois et on aimerait qu'il soit le plus rapide possible.

tab[i] est un int dans ce bout de code et on part du principe que
a b c et d sont des int aussi si ca t'arrange mais il y a des optimisations qui n'ont pas besoin de cette indication.

Si c et d sont des constantes (pourquoi as-tu besoin que ce soit
des constantes?) tu peux effectivement sortir le calcul du resultat de la boucle. Meme si tu prends le probleme de travers je t'accorde cette premiere optimisation.

Dans un premier temps tu te contentes de faire comme si le compilateur n'optimisait pas (c'est ce qu'on m'a demandé de faire).

LeGreg

[Blustuff]

oki, je me trompe peut etre mais j'ai fait quelques test. J'arrive a ca :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
  tab[0] = c + d;
  int x = b - a - c - d;
  a *= 2;
 
  for (int i = 1 ; i < MAX ; i++)
  {
     x -= a;
     tab[i] = tab[i-1] - x;
  }

La seule optimisation de mon compilateur est d'utiliser un pointeur sur &Tab[i] L'optimisation courante en caclulant par recursion pour supprimer les multiplication me fait gagner ~20% de vitese ce qui est un peu ridicule pour les calculs que ca demande. Un solution qui me semblait plus rapide était d'utiliser les pointeur comme on le fait de manière courante

Code :

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

1
2
 
for (int* p = tab, p < &tab[MAX] ; p++)

Le code asm corespondant est plus rapide quand on compte les cycles manuelement. Mais certaienemnt pour des raisons de pairing et d'autres trucs difficilement prévisibles et dépendant du compilateur c'est plus lent.

De toute facon 3 multiplication par ittération c'est même pas encore très lourd surtout que le compilateur s'arrange pour que les registres utilisés soient différents ce qui permet dee les faire en parrallèle.

En résumé si jamais on a un code comme ca, autant le laisser tel quel.


P.S.

si c et d sont des constantes, j'entends par là les deux cas suivants :

Code :

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

1
2
3
4
5
 
const int c = 3;
const int d = 4;
 
int e = c + d;

et

Code :

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

1
2
 
int e = 3 + 4;

dans ces deux cas le compilateur effectue le calcul lui même. Donc si ce sont des constantes on laisse tel quel, si ce ne sont pas des constantes on sort le calcul de la boucle.

[LeGreg]

Code :

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

1
2
3
4
5
6
7
8
9
10
 
  tab[0] = c + d;
  int x = b - a - c - d;
  a *= 2;
 
  for (int i = 1 ; i < MAX ; i++)
  {
     x -= a;
     tab[i] = tab[i-1] - x;
  }

A mon avis c'est tres complique et ca ne marche pas.
Surtout pourquoi autant de soustractions ?

De toute facon 3 multiplication par ittération c'est même pas encore très lourd surtout que le compilateur s'arrange pour que les registres utilisés soient différents ce qui permet dee les faire en parrallèle.

Le but ce n'est pas de discuter le cout individuel d'une operation
mais de reduire le cout global sur un grand nombre d'appels.

En résumé si jamais on a un code comme ca, autant le laisser tel quel.

Je n'ai pas la reponse a cette question. A mon avis c'est une question ouverte telle qu'on peut te la poser a un entretien. L'examinateur s'attend a ce que tu proposes un certain nombre d'optimisation et que tu voies que le code qui suit ne peut pas etre compile litteralement pour s'executer de facon optimale meme si dans 98% des cas on s'en fout. En fait ce n'est pas le but de la question de savoir si ca a un sens.

De toute facon, je ne pense pas que les programmeurs dans sa boite passent leur temps a se poser ce genre de questions, c'est juste un exo d'entretien..

dans ces deux cas le compilateur effectue le calcul lui même. Donc si ce sont des constantes on laisse tel quel, si ce ne sont pas des constantes on sort le calcul de la boucle.

Donc selon toi les chances pour qu'une telle optimisation ait lieu
est de 50% ?

En fait tu te rends bien compte que cette discussion est ridicule puisque
cette operation va disparaitre quoi qu'il arrive a cause d'une autre optimisation: du coup le fait de savoir de quel type c et d sont n'a plus grande importance.

LeGreg

[Blustuff]

c'est parce que en ecrivant

Ui = ai² + bi + c +d

on arrive à

Ui+1 = Ui + 2ai + a + b + c + d

ou

Ui-1 = Ui - 2ai + a - b + c + d

pour des raisons dont je ne me rappelle plus j'ai coisi la deuxième ce qui nous donne :

Ui = Ui-1 + 2ai - a + b - c - d

d'où toutes les soustractions.
x contient -a + b - c - d, mis sous la forme b - a - c - d par flemme de mathematicien, et incrementé de 2a a chaque fois (pour ne pas refaire la multiplication, je double a avant, il faudrait passer par une autre variable theoriquement). Donc la déja cj'ai fait une erreur, c'est += au lieu de -= et dans le calcul c'est + x et pas - x. Ca me fait penser qu'on pourrait encore essayer de supprimer un accès en mémoire en passanat par une variable intermediaire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
  tab[0] = c + d; 
  int x = b - a - c - d; 
  int y = a * 2;
  int Temp = tab[0]; 
 
  for (int i = 1 ; i < MAX ; i++) 
  { 
     x += y;
     Temp += x;
     tab[i] = Temp; 
  }

Mais la mon compilateur il en peux plus, puisque il déclare y dans la pile donc, un autre accès en mémoire, ce qui donne exactement la même chose, que la précedente. Pourtant moi je compte : 1)x 2)y, 3)i, 4)tab[i], 5)Temp, normalement 5 variables il y a largemnt de quoi les mettre en registre. Donc soit forcer les auto et les register, sois passer par l'asm. (moi j'y arrive pas avec mon compilo)

Le coup d'une multiplication est important, puisque si l'on veut optimiser il ne va pas falloir forcement supprimer les multiplications, mais reduire le nombr d'operations.

Le dernier code que j'ai optimisé j'ai plus que doublé ca rapidité. Même si j'en demande pas tant a chaque fois, pour 20 % c'était pas la peine de ce donner ce mal.

Cela dit, j'avais enormement de mal a prevoir quel code serait plus rapide que quel autre. Sans faire des tests, j'en aurais jamais eu le coeur net.