De la rapidité du code [Trucs & Astuces]

**Luc Hermitte** · 05/10/2005, 00h26

Pour les matrices et vecteurs, voir Blitz++, et dérivés comme boost.uBlas, qui profitent de la méta-progammation pour éliminer les temporaires, obtenir une sémantique de déplacement au niveau des retours, et autres calculs retardés.

Pré-incrémentation et compagnie n'avaient pas déjà été signalés ?

Sinon oui, il faut profiter des profileurs de code.

PS à délester: algorithme "vient" (façon de parler) de l'Arabe (cf Al!) et non du Grec.

**Coelacanthe** · 05/01/2006, 01h31

Ce sujet confirme que je suis tombé sur un site de fous furieux...

**Amokrane** · 05/01/2006, 12h30

Envoyé par Luc Hermitte

Pour les matrices et vecteurs, voir Blitz++, et dérivés comme boost.uBlas, qui profitent de la méta-progammation pour éliminer les temporaires, obtenir une sémantique de déplacement au niveau des retours, et autres calculs retardés.

Pré-incrémentation et compagnie n'avaient pas déjà été signalés ?

Sinon oui, il faut profiter des profileurs de code.

PS à délester: algorithme "vient" (façon de parler) de l'Arabe (cf Al!) et non du Grec.

juste un truc , Al khawarizmi est perse , pas arabe non ?

**Rafy** · 02/02/2006, 21h36

Hum j'avais dis ça car je venais de coder une class de vecteur et une class de matrice... Maintenant je vais soit utiliser un type de matrice et de vecteur déjà coder : (D3DXVECTOR3 et D3DXMATRIX) ou bien des insructions 3DNow!

**Charlemagne** · 06/05/2006, 01h55

La discussion est vieille, mais je voudrais y mettre mon grain de sel.

Supposons que je veuille optimiser la boucle suivante:

Code :

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

1
2
3
 
for (int i=0; i<n; ++i)
  z[i]=x[i]+y[i];

Beaucoup de propositions précédentes ne sont que superficielles.
Mais voici les 3 voies principales d'optimisations que je suggère.
Si vous croyez que les compilos les font automatiquement, vous vous trompez (malheureusement).

1) instructions parallèles SIMD (SSE1, SSE2 pour les Pentiums)
Pour les pentium cela permet un gain de:
-char: 16x
-short: 8x
-int, float: 4x
-double: 2x
Il faut faire néanmoins attention aux contraintes d'alignement mémoire et éventuellement prévoir de traiter les éléments restants de la boucle.

Code :

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

1
2
3
4
 
float *px=x, py=y, pz=z;
for (int i=0, imax=n-4; i<imax; px+=4, py+=4, pz+=4, i+=4)
  _mm_store_ps(pz,_mm_add_ps(_mm_load_ps(px),_mm_load_ps(ps)));

2) développer la boucle
Certes un Pentium prédit la plupart du temps correctement le saut conditionnel de la boucle 'for', évitant ainsi de briser le pipeline.
Mais développer la boucle permet un gain important de vitesse, surtout quand les index des tableaux sont constants (instructions plus rapides du Pentium).

Code :

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

1
2
3
4
5
6
7
8
 
for (int i=0, imax=n-16; i<imax; i+=16)
{
  float *px=&x[i], py=&y[i], pz=&z[i];
  pz[0]=px[0]+py[0];
  pz[1]=px[1]+py[1];
  ...
}

3) Garder autant que possible les variables dans les registres.
Ainsi si l'on désire calculer Z1=X+Y et Z2=X-Y, pourquoi ne pas faire qu'une seule boucle:

Code :

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

1
2
3
4
5
6
7
 
for (int i=0; i<n; ++i)
{
  float xi=x[i], yi=y[i];
  z1[i]=xi+yi;
  z2[i]=xi-yi;
}

Il n'est pas interdit de mélanger ces 3 techniques.

Dans un autre ordre d'idées:
-Le processeur prédit qu'un test 'if' est vérifié. Donc pour minimiser les pipeline brisés (destructeur pour la vitesse), placez le code le moins probable après 'else'.
-le mot clé 'restrict' peut supprimer l'aliasing. 'restrict' est dans le C99, mais pas encore officiellement dans le C++. Sinon votre compilateur a surement une option de compilation adéquate.

**Rafy** · 11/05/2006, 22h14

tu as écris += 4, je suppose que ça vient de la taille de l'int enfin tu suppose que sizeof(int) vaut toujours 4... Il faut faire gaffe avec ça....
C'est pas forcement vrai...
Ce qui est vrai c'est :

Code :

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

1
2
3
4
5
6
 
sizeof(char) == 1
et
sizeof(char) <= sizeof(int) <= sizeof(long)
de même
sizeof(float) <= sizeof(double) <= sizeof(long double)

rien n'empêche que les 3 soient égales

**Charlemagne** · 11/05/2006, 22h50

tu as écris += 4, je suppose que ça vient de la taille de l'int enfin tu suppose que sizeof(int) vaut toujours 4... Il faut faire gaffe avec ça....

T'as pas dû comprendre grand chose à mon exemple:
- J'ai pris des floats pour l'exemple, pas des ints
- Il y a bien 4 floats dans un registre SSE = 16 octets

**Luc Hermitte** · 12/05/2006, 00h25

Sa remarque au sujet des constantes magiques reste valide. (Certes dans ton cas, tu vises une archi bien précise, au détriment de la portabilité des perfs.)

**Rafy** · 12/05/2006, 09h56

Il faut éviter le plus possible de semer dans son code des nombres magiques....
Pour plusieurs raisons :
-> le coté utilitaire de la chose, dans ton cas si tu veux adapter ça avec un autre type alors tu es obligé de modifier ton code à plusieurs endroits. Tu peux mettre des nombres magiques mais alors fait une ou des variables globals constantes ou alors des variables d'une class static const
-> le coté parachutage, une valeur qui arrive comme ça d'on ne sait trop ou, j'ai lu dans un bouquin que pour chaque nombre magique qu'on introduit dans son code, il faut au moins une dizaine de lignes pour justifier la valeur et la commenter...
-> les seuls nombre magiques autorisés (c'est un bien grand mot) sont les nombres qui sont dans une formule.
exemple :

Code :

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

1
2
3
4
5
 
const float GetPerimeter(const float Radius)
{
    return 2 * Pi * Radius;    // En considérant que Pi est une variable globale constante
}

**Charlemagne** · 12/05/2006, 10h42

-> le coté utilitaire de la chose, dans ton cas si tu veux adapter ça avec un autre type alors tu es obligé de modifier ton code à plusieurs endroits. Tu peux mettre des nombres magiques mais alors fait une ou des variables globals constantes ou alors des variables d'une class static const

Mon exemple est en C.
Mon implémentation réelle des instructions SIMD est faite avec des surcharges, et reste quasi transparente dans mon programme.

-> le coté parachutage, une valeur qui arrive comme ça d'on ne sait trop ou, j'ai lu dans un bouquin que pour chaque nombre magique qu'on introduit dans son code, il faut au moins une dizaine de lignes pour justifier la valeur et la commenter...

De quel nombre magique tu parles? 4?
Renseigne toi sur SSE... C'est toi même qui dit utiliser 3dnow dans un poste précédent! C'est peut-être parce que 3dnow est plus général que SSE?

-> les seuls nombre magiques autorisés (c'est un bien grand mot) sont les nombres qui sont dans une formule.
exemple :
const float GetPerimeter(const float Radius)
{
return 2 * Pi * Radius; // En considérant que Pi est une variable globale constante
}

Tu veux bien optimiser ce code stp! Tu veux bien me dire en quoi la discussion sur une constante nous intéresse dans une discussion sur l'optimisation.
Dis moi, tu les as critiqué, tous ceux qui proposent plus haut dans cette discussion de programmer en assembleur?

Sa remarque au sujet des constantes magiques reste valide. (Certes dans ton cas, tu vises une archi bien précise, au détriment de la portabilité des perfs.)

Effectivement, j'ai bien dis que dans mon exemple j'utilise SSE, et donc bien entendu je vise l'architecture Intel.
On ne peut pas sérieusement dire qu'un code est optimisé si on passe à coté des SIMD (quand c'est possible).
Mais en s'y prenant bien, ce n'est pas pas au détriment de la portabilité du code (surcharge d'opérateurs...c'est ce que j'ai déjà fait).

Pour tous les as de l'optimisation
Je vous mets au défit.
Je propose que l'on teste nos implémentations respectives d'une multiplication de matrices...

**Rafy** · 13/05/2006, 14h58

Pour juger l'optimisation il vaut mieux faire de la gestion de mémoire, faire du travail sur des conteneurs. Un pur calcul entre 2 matrices ne sera pas très parlant !!!
une personne va mettre 10 ms et l'autre va mettre 11 ms bouh il a fait moins bien que moi.... Il est Null!!!
C'est naze de dire, et de penser ça...
L'optimisation doit avant tout porter sur ce qui est de plus lent dans un programme....
Optimiser un if c'est trop c**
C'est comme si dans un jeu on optimisait le chargement des niveaux au lieu d'optimiser l'affichage ou le rendu !!!!!
Le chargement qu'il dure 100 ms de plus car on a un algo qui pourrait être amélioré on s'en fout, par contre si à chaque boucle d'affichage on perd 100ms car l'algo est foireux alors, ça nous aura fait une belle jambe d'avoir optimisé le chargement du niveau, c'est sur qu'on chargera le niveau rapidement, mais si c'est pour avoir 3 fps, c'est complétement crétin.
Avant de dire je vais optimiser ma mutiplication de matrice il vaudrai mieux savoir si le travail pour générer les matrices, les utiliser par la suite est bien fait et ne peux plus être optimisé.
A propos des nombre magique tu pourras demander à n'importe qui sur le forum, c'est pas bon d'en semer dans son code.

De quel nombre magique tu parles? 4?
Renseigne toi sur SSE... C'est toi même qui dit utiliser 3dnow dans un poste précédent! C'est peut-être parce que 3dnow est plus général que SSE?

ben oui c'est ça un nombre magique !
Je ne vois pas le rapport entre le SSE ou les instruction 3DNow! et le chiffre 4.
tu as écris :

Code :
float *px=x, py=y, pz=z;for (int i=0, imax=n-4; i<imax; px+=4, py+=4, pz+=4, i+=4) _mm_store_ps(pz,_mm_add_ps(_mm_load_ps(px),_mm_load_ps(ps)));

Il y a bien des 4 non ? c'est de ces 4 la dont je parle, tu décales des pointeurs dans la mémoire, non ? et ton 4 c'est parceque sizeof(float) t'as donné sur ta machine 4, mais si tu vas sur une vieille machine tu trouvera peut-être autre chose que 4!!!
Et si ce 4 n'est pas sizeof(float) alors il va falloir que tu expliques car a mon avis je ne suis pas le seul à ne pas avoir tout compris.

Tu veux bien optimiser ce code stp! Tu veux bien me dire en quoi la discussion sur une constante nous intéresse dans une discussion sur l'optimisation.
Dis moi, tu les as critiqué, tous ceux qui proposent plus haut dans cette discussion de programmer en assembleur?

Optimiser quoi ? c'est un exemple pour te monter quel nombre magique, à mon gout, on a le droit d'utiliser....
Et pour ceux qui travail en assembleur il font ce qu'ils veulent, ils peuvent coder en assembleut si ils veulent moi je code en C++, et j'essaye de coder le mieux possible pour que le code généré soit le plus performant possible. Et pourquoi je les critiquerai, car il utilisent un autre langage du miens car une addition des deux entiers en assembleur est plus rapide qu'en C++, c'est n'importe quoi.

**Charlemagne** · 13/05/2006, 17h19

J'ai plus envie de discuter avec toi.
Je déteste être pris pour un débutant par un ... débutant.

La seule explication sensée à ta remarque plus haut sur sizeof(int)==4, est que tu crois que l'instruction p+=4 ajoute 4 octet à l'adresse.
Apprends que le "nombre magique 4" n'est pas sizeof(float) mais le nombre de floats calculés en parallèle dans un registre SSE soit 16/sizeof(float).

J'ai remarqué ton poste posant des questions sur les références, c'est la B.A.BA: apprends le C++ avant de faire tes remarques secondaires qui ne tiennent pas compte du sujet. Tu as appris quelque part que les sizeof(..) sont différents d'un système à l'autre, à la bonne heure...

J'ai illustré mes propositions d'exemples simples de quelques lignes, tu aurais préféré des pages complètes. Non il faut s'en tenir à l'idée.

Tu critiques mes précisions sur la rapidité des 'if', alors que tu proposes plus haut d'utiliser de préférence ++i que i++ !!

Tu dis qu'un programme prendrait 10ms alors qu'un autre 11ms: tu n'as aucune, mais alors aucune idée de l'optimisation.

La multiplication de matrices est un algo simple, fréquemment utilisé pour comparer les performances de librairies mathématiques. Il illustre parfaitement l'optimisation des boucles.
C'est trop compiqué pour toi?
Relève le défi ou ferme la.

C'est bon je me calme...

**Matthieu Brucher** · 13/05/2006, 17h41

Voilà, sujet clos...

**Charlemagne** · 13/05/2006, 18h05

Miles, pourquoi sujet clos?

**Laurent Gomila** · 13/05/2006, 18h13

Parce que cela a déjà trop dégénéré. Si vous voulez continuer cette discussion tendue, faites-le par MP, merci.

**Charlemagne** · 13/05/2006, 18h19

Je me calme.
Mais il faut bien que quelqu'un lui dise que l'instruction p+=4, n'ajoute pas 4 octets au pointeur mais 16=4*sizeof(float) octets. Sans quoi, effectivement, on comprend rien.

**Luc Hermitte** · 14/05/2006, 16h18

Le truc, c'est que le 4 vient de BUFFER_SIZE / sizeof(float). La constante magique est bien éliminable.

**Charlemagne** · 14/05/2006, 17h27

Et ton BUFFER_SIZE il vient d'où? J'y peux rien si les registres SSE ont une taille fixe de 16 octets.
Je veux bien faire toutes les constantes que vous voulez, mais cessez de ne parler que de cette constante alors que j'illustrais mon propos sur l'optimisation SSE par un exemple de 2 lignes.
Si mon exemple n'est pas approximativement 4 fois plus rapide que la simple boucle, qu'on me le dise, et le prouve.
De grâce, recentrons le sujet.

Personne ne veut commenter ma 2ème suggestion qui innove par rapport au développement de boucle proposé encore plus haut dans ce forum? Cette suggestion consiste à:
-développer la boucle
-ne recalculer le déplacement du poineteur qu'une seule fois par boucle
-d'utiliser des index constants.