Discussion :

[jblecanard]

Pour moi, le coût de la généricité (ie avoir un langage compilé qui fonctionne sur toutes les plateformes en passant par une machine virtuelle) a forcement un coût en terme de performance. Mais je me trompe peut être.

Attention, la JVM actuelle contient un Just In Time compiler (qui répond au doux nom de Hotspot). Ce qui signifie que certaines parties du byte code java sont compilées en langage machine lors de certaines boucles, pour gagner du temps. Or dans notre cas, notre ami fait du java "C++" style, et le JIT s'en donne, on peut s'en douter, à coeur joie.

Il n'en reste pas moins que Visual Studio défonce java. J'ai hâte de prendre le temps d'essayer avec gcc comme il faut.

[Klaim]

Je ne vais pas pouvoir tester ici mais j'ai quelques suggestions :

1. std::cout est très lent (mais aussi très "safe"), remplacer par printf voir (puisqu'il est question de performance, autant utiliser un outil performant quitte a perdre and type-safty)
2. Si ça n'explose pas la stack, remplacer toutes les tableaux alloués par new par des tableaux sur la stack. Ca evitera de perdre un temps considérable sur le delete (et oui ça fait perdre un temps fou). Même si il n'y en a qu'un, si on peut avoir tout dans la stack ça seraa naturellement plus rapide.


Si tu peux juste tenter ça je pense que ça réglera déjà pas mal de souci.

Il y a un autre point plus important : GetTickCount() est-il un bon outil de mesure? Si je me souviens bien, non, mais faut vérifier. Il me semble que cette fonction ne suffit pas à nue mesure correcte de perfs.

[gbdivers]

Il y a un autre point plus important : GetTickCount() est-il un bon outil de mesure? Si je me souviens bien, non, mais faut vérifier. Il me semble que cette fonction ne suffit pas à nue mesure correcte de perfs.

De toute façon, cette fonction n'existe pas sous linux. J'ai fait les tests avec boost::timer et boost::progress_timer. Par contre, je ne sais pas s'il y a mieux.

1. std::cout est très lent (mais aussi très "safe"), remplacer par printf voir (puisqu'il est question de performance, autant utiliser un outil performant quitte a perdre and type-safty)
2. Si ça n'explose pas la stack, remplacer toutes les tableaux alloués par new par des tableaux sur la stack. Ca evitera de perdre un temps considérable sur le delete (et oui ça fait perdre un temps fou). Même si il n'y en a qu'un, si on peut avoir tout dans la stack ça seraa naturellement plus rapide.

Le timer commence au début de la boucle principale (donc apès l'initialisation des variables) et termine avant l'affichage (donc sans prendre en compte std::cout). J'avais pensé effectivement à ce problème (c'est bien connu que les streams sont peu performants en c++)

J'ai également testé avec différents types de conteneur (tableaux dynamique et statique, std::vector, std::valarray). Par contre, je ne sais pas comment vérifier que la stack n'est pas saturé (je connais le problème et je connais à peu près ses effets mais ici, il n'y pas de perte de performances importante avec la stack donc je suppose que c'est bon)

Attention, la JVM actuelle contient un Just In Time compiler (qui répond au doux nom de Hotspot). Ce qui signifie que certaines parties du byte code java sont compilées en langage machine lors de certaines boucles, pour gagner du temps. Or dans notre cas, notre ami fait du java "C++" style, et le JIT s'en donne, on peut s'en douter, à coeur joie.

Ok, je ne savais pas. Avec cette info, on peut effectivement s'attendre à avoir une différence de performance moindre

[LittleWhite]

Des micros optimisation forcement inutile:

j+1 est calcule trois fois par tour de loop. Voir si on ne peut pas faire en sorte de le garder dans une variable (un registre ?)
La variable nbEchange n'est pas utile (programme dans le monde reel, n'aurait pas eu cela)
Le swap, peut peut etre etre optimise (mais je suis loin d'en etre sur)
Je ne sais plus, mais peut etre qu'en jouant sur les pointeur de tableaux a la place des indices ont irait plus vite.

n-2 est calcule pour chaque tour de loop. On pourrait donc le garder dans une variable (registre ?)

Voila ce que je vois ... bien sur ... tout cela est surement tres peut important sur la vitesse ... mais ce ne sont que les seules choses que je suis capable de voir.
Il faudrait voir tout cela sous un profiler ... mais comme le code n'a rien de choquant (c'est celui de la wikipedia en fait) ... bah je ne connais pas les optimisations.

Juste au cas ou, faire le GetTickCount (WinAPI) juste avant la boucle. et non avant quelques allocations. (Le compilateur garde surement l'ordre du code ...).
Habituellement, j'utilise http://www.manpagez.com/man/2/gettimeofday/

Voila ce que moi je peux dire, j'espere que d'autres apporteront leurs pierres, car c'est un sujet ou je suis un pur debutant :s

[Emmanuel Deloget]

Des micros optimisation forcement inutile:

j+1 est calcule trois fois par tour de loop. Voir si on ne peut pas faire en sorte de le garder dans une variable (un registre ?)

Le compilateur optimise ça, et ne le calcule qu'une fois.

La variable nbEchange n'est pas utile (programme dans le monde reel, n'aurait pas eu cela)

En mode release, puisque la variable n'est pas lue, le compilateur ne fait qu'un seul calcul et une seule affectation à la fin de la boucle.

Le swap, peut peut etre etre optimise (mais je suis loin d'en etre sur)

Pas vraiment, dans ce cas.

Je ne sais plus, mais peut etre qu'en jouant sur les pointeur de tableaux a la place des indices ont irait plus vite.

Pas sur que ça ait un impact non plus. Le compilateur l'optimise peut-être déjà.

n-2 est calcule pour chaque tour de loop. On pourrait donc le garder dans une variable (registre ?)

Le code fait très peu de choses, donc il y a peu de chance de l'optimiser sans passer par une modification algorithmique (telle que celle donnée dans Wikipedia)

C'est marrant de voir la progression d'un tri à bulle quand même :

[LittleWhite]

C'est bien ce que je disais / pensais ... mes optimisations sont loin d'etre utile et habituellement je fais confiance a mon compilateur

[hors sujet]
Sinon, entierement d'accord que les animations mises sur la wikipedia sont jolies a voir (sachant que j'ai passe 5 minutes a la regarder) (Je conseille de regarder les autres tris et le jeu de la vie de Conway.)
[/hors sujet]

[gbdivers]

Des micros optimisation forcement inutile:

j+1 est calcule trois fois par tour de loop. Voir si on ne peut pas faire en sorte de le garder dans une variable (un registre ?)
La variable nbEchange n'est pas utile (programme dans le monde reel, n'aurait pas eu cela)
Le swap, peut peut etre etre optimise (mais je suis loin d'en etre sur)
Je ne sais plus, mais peut etre qu'en jouant sur les pointeur de tableaux a la place des indices ont irait plus vite.

n-2 est calcule pour chaque tour de loop. On pourrait donc le garder dans une variable (registre ?)

Déjà testé aussi pas de gain
EDIT : message rédigé pendant les 2 messages suivants.

[Arzar]

Mon interrogation est plus générale : comment optimiser au maximum le code (oui, je sais, c'est de la micro optimisation).
[...]

Au final, ce qui m'embête le plus, c'est que je suis juste capable d'apporter 2-3 améliorations au code (c'est déjà pas si mal, je gagne 0,5 s par rapport au code initial) mais rien de vraiment fulgurant.
Ce que j'aimerai savoir, c'est si vous deviez apporter des améliorations du code du TriBulle donné, que feriez vous ? Ou alors, ne code n'est pas améliorable et les différences viendront uniquement de la qualité du code généré par le compilateur ?

Bon j'ai craqué.
Je me suis amusé à essayer de micro-optimiser le code du produit croisé (dans le zip : CrossProd -> CppDev). N'étant pas du tout un expert en analyse numérique, j'essaye pas mal de truc que j'ai pu lire à droite à gauche par essais et erreurs, sans forcement bien comprendre le pourquoi du gain.

Voici les résultats, obtenu avec Visual Studio 2010 :

Ci-dessous le code original :

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
 
#include <cstdlib>
#include <iostream>
#include <windows.h>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int n = 10000;
    int p = 200;
 
    double **x = new double*[n];
    for (int i = 0; i < n; i++){
     x[i] = new double[p];
     for (int j = 0; j < p ; j++)
        x[i][j] = (i*j) % 2;
    }
 
    double **mat = new double*[p];
    for (int j = 0; j < p; j++)
    {
       mat[j] = new double[p];
    }
 
    cout << "debut des calculs..." << endl;
 
    long t = GetTickCount();
    int j1, j2;
    int nbOp = 0;
 
    for (j1 = 0; j1 < p ; j1++)
        for (j2 = 0; j2 < p ; j2++)
         for (int i = 0; i < n ; i++)
         {
             mat[j1][j2] = mat[j1][j2] + x[i][j1]* x[i][j2];
             nbOp = nbOp + 1;
         }
 
    t = GetTickCount() - t;
 
    cout << "... fin des calculs" << endl;
    cout << "Temps de calcul = " << t << " ms." << endl;
    cout << "Nombre operations = " << nbOp << endl;
 
    return 0;
}

Resultat sur trois runs :4181 ms. 4353 ms. 4166 ms.
Moyenne = 4233ms +- 103ms

1.
Comme le dit l'auteur du blog, on peut obtenir un très gros grain en réorganisant les boucles for pour éviter de toucher en permanence des zones éloignés en mémoire. Le but étant de ne faire dans la même passe que des modifications sur les lignes des matrices, qui sont contiguës en mémoire.

Code :

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

1
2
3
4
5
6
7
for (int i = 0; i < n ; i++)
   for (j1 = 0; j1 < p ; j1++)
      for (j2 = 0; j2 < p ; j2++)
      {
         mat[j1][j2] = mat[j1][j2] + x[i][j1]* x[i][j2];
         nbOp = nbOp + 1;
      }

resultat sur 15 run : 1092 ms. 1498 ms.1077 ms.1326 ms. 1092 ms. 1076 ms. 1076 ms. 1077 ms. 1092 ms. 1076 ms. 1217 ms. 1061 ms. 1077 ms. 1076 ms. 1107 ms.
Moyenne = 1134ms +- 122ms

2.
Le code est faux !!
L'auteur a oublié d'initialiser le tableau de sortie "mat" à zéro, donc la matrice ne contient que des valeurs absurdes.

Code :

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

1
2
3
4
5
6
7
 
double **mat = new double*[p];
for (int j = 0; j < p; j++)
{
   mat[j] = new double[p];
   std::fill(mat[j], mat[j] + p, 0.0);
}

Et là surprise !!
Résultat : 578 ms.609 ms.577 ms.609 ms.764 ms.733 ms.593 ms.577 ms.577 ms.905 ms.639 ms. 577 ms. 578 ms.577 ms.578 ms.
Moyenne : 631ms +- 95ms
Je ne comprends pas vraiment pourquoi exactement, mais j'ai pu reproduire ce comportement systématiquement. Peut être que le processeur se débrouille beaucoup mieux sur des valeurs finalement assez petite (proche de zéro) que sur les valeurs absurdes que contient la matrice si on ne l'initialise pas ??

3.
Si on regarde de plus près la double-boucle :

Code :

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

1
2
3
4
5
6
7
8
9
 
for (j1 = 0; j1 < p ; j1++)
{
   for (j2 = 0; j2 < p ; j2++)
   {
      mat[j1][j2] = mat[j1][j2] +  x[i][j1] * x[i][j2];
      nbOp = nbOp + 1;
   }
}

On remarque que la valeur x[i][j1] est constante. A priori le compilateur devrait le voir, mais au cas où, autant sortir x[i][j1] de la boucle :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for (j1 = 0; j1 < p ; j1++)
{
   double xij1 = x[i][j1];
   for (j2 = 0; j2 < p ; j2++)
   {
      mat[j1][j2] = mat[j1][j2] +  xij1  * x[i][j2];
      nbOp = nbOp + 1;
   }
}

Résultat : 421 ms.421 ms.422 ms.421 ms.437 ms.436 ms.421 ms.421 ms.437 ms.422 ms.421 ms.421 ms.421 ms.421 ms.437 ms.
Moyenne : 425ms +- 7.3ms

Wow ! C'était vachement plus utile que je ne le pensais ! On a gagné environ 200 ms. En passant la fluctuations des mesures (l'écart-type) a lui aussi brusquement chuté, je ne comprends pas bien pourquoi.
4.

Je n'ai jamais bien compris pourquoi exactement, mais j'ai souvent lu que pour exploiter des effets de cache, il est préférable de parcourir des matrices par bloc.
C'est à dire remplacer :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for (j1 = 0; j1 < p ; j1++)
{
   double xij1 = x[i][j1];
   for (j2 = 0; j2 < p ; j2++)
   {
      mat[j1][j2] = mat[j1][j2] +  xij1  * x[i][j2];
      nbOp = nbOp + 1;
   }
}

par

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
for (j1 = 0; j1 < p ; j1++)
{
   double xij1 = x[i][j1];
   for (j2 = 0; j2 < (p / 16) ; j2 += 16) // 200 est divisible par 16...
   {
      for( int k = 0 ; k < 16 ; k++)
      {
         mat[j1][j2+k] = mat[j1][j2+k] + xij1 * x[i][j2+k];
      }
      nbOp += 16;
   }
}

Résultats : 47 ms.47 ms.47 ms.47 ms.63 ms.63 ms.47 ms.47 ms.47 ms.62 ms.62 ms.46 ms.46 ms.62 ms.62 ms.
Moyenne : 53ms +- 7.9ms
WAOU
Bon, j'ai du tuner à la main la taille des sous-blocs pour arriver à 16, la valeur optimal ici, mais ça en valait la peine.

Et voilà ! Partir de 4233ms pour arriver à 53ms, soit un gain x80, c'est quand même pas négligable. Je suis d'ailleurs persuadé qu'un expert en analyse numérique pourrait encore gagner au moins autant. Car, bon, quand même, 53ms pour une pauvre multiplication de matrice 10000x200 j'imagine qu'on est encore très très loin des temps qu'on doit pouvoir atteindre sur des supercalculateurs hyper-optimisés.

[gbdivers]

Très joli

Je me suis concentré principalement sur TriBulle, qui se prête beaucoup moins aux optimisations.

Le 2ème point est effectivement étrange. Si quelqu'un a une explication, je suis preneur.
Tu as un lien/tutoriel/n'importe quoi sur ton 4ème point ?

Il faudrait maintenant voir si ces mêmes optimisations portées sur java donneraient des gains aussi importants.

Merci d'avoir pris le temps de faire cette analyse

[jblecanard]

Le code est faux !!
L'auteur a oublié d'initialiser le tableau de sortie "mat" à zéro, donc la matrice ne contient que des valeurs absurdes.

Et là surprise !!
Résultat : 578 ms.609 ms.577 ms.609 ms.764 ms.733 ms.593 ms.577 ms.577 ms.905 ms.639 ms. 577 ms. 578 ms.577 ms.578 ms.
Moyenne : 631ms +- 95ms

Super bien vu, car java, lui, initialise bien à zéro. Ca prouve comme il est extrêmement difficile de faire des comparaisons "propres" entre langages.

Néanmoins, les autres optimisations valent le coup d'être testées sur java pour voir ce que ça donne avec le JIT.

[Arzar]

Fuuuuuuuuuuuuuuuuuu..
Je me suis gouré dans le code qui fait le parcours par bloc...

Code :

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

1
2
3
4
5
6
7
8
9
 
for (j2 = 0; j2 < /* erreur */ (p / 16) ; j2 += 16) // 200 est divisible par 16...
{
   for( int k = 0 ; k < 16 ; k++)
   {
      mat[j1][j2+k] = mat[j1][j2+k] + xij1 * x[i][j2+k];
   }
   nbOp += 16;
}

Forcement qu'on gagne du temps en ne faisant qu'1/16 du boulot.
Je ne peux pas tester maintenant, mais le code devrait plutôt ressembler à :

Code :

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

1
2
3
4
5
6
7
8
9
 
for (j2 = 0; j2 < p ; j2 += 16)
{
   for( int k = 0 ; k < 16 ; k++)
   {
      mat[j1][j2+k] = mat[j1][j2+k] + xij1 * x[i][j2+k];
   }
   nbOp += 16;
}

Bon ben le dernier code correct est celui du point 3. (425ms... )

[gbdivers]

Petite remarque sur le point 4 :
en sortant l'incrémentation du compteur nbOp de la boucle, tu remplaces 400000000 incrémentations ("nbOp = nbOp + 1;" qui est optimisé je pense en "++nbOp;") par 25000000 additions ("nbOp = nbOp + 16;")
Tu ne mesures peut être donc pas que la mise en cache de la boucle la plus interne (mais c'est une optimisation quand même)

[Jean-Marc.Bourguet]

Je ne comprends pas vraiment pourquoi exactement, mais j'ai pu reproduire ce comportement systématiquement.

Traitement de subormaux et NaN deferre a du micro-code ou meme des interruptions?

Le traitement par bloc n'a un interet que si on fait plusieurs passes sur le bloc...

[jblecanard]

Le traitement par bloc n'a un interet que si on fait plusieurs passes sur le bloc...

Ha bon, l'accès à un début de bloc ne met il pas en cache la suite du bloc, par "prédiction" ?

[Jean-Marc.Bourguet]

Ha bon, l'accès à un début de bloc ne met il pas en cache la suite du bloc, par "prédiction" ?

Quelle difference vois-tu dans les acces entre:

Code :

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

1
2
3
4
5
6
7
8
for (j2 = 0; j2 < p ; j2 += 16)
{
   for( int k = 0 ; k < 16 ; k++)
   {
      mat[j1][j2+k] = mat[j1][j2+k] + xij1 * x[i][j2+k];
   }
   nbOp += 16;
}

et

Code :

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

1
2
3
4
5
6
 
for (j2 = 0; j2 < p ; j2++)
{
      mat[j1][j2] = mat[j1][j2] + xij1 * x[i][j2];
   nbOp++;
}

le gestionnaire de cache voyant la meme chose doit faire la meme chose.

[Emmanuel Deloget]

Le 2ème point est effectivement étrange. Si quelqu'un a une explication, je suis preneur.

Travail sur des nombres flottants non initialisés == le coprocesseur arithmétique génère plein d'exceptions, qui sont généralement cachées à l'exécution (mais qu'on peut activer via un appel à une fonction dont je ne me rappelle plus le nom), parce qu'ils y a des nombres dénormalisés, des NaN, des infinis, etc.

Edit: retrouvé les fonctions :

man 2 feenableexcept avec la glibc
_controlfp avec Visual C++.

[jblecanard]

Effectivement, quand bien même ma supposition est vraie, il n'y aurait pas besoin de découper la boucle. Au temps pour moi.

[gbdivers]

Traitement de subormaux et NaN deferre a du micro-code ou meme des interruptions?

Quand je parlais d'expert je me sens tout petit... on parle encore c++ ?


J'ai testé la mise en cache pour le trie par bulle (en corrigeant l'erreur) : on diminue le temps de traitement de 30% (sans cache : 1.987 s ; avec cache : 1.363 s pour n = 256*128; soit un gain de 624 ms)

Le traitement par bloc n'a un interet que si on fait plusieurs passes sur le bloc...

Mais a priori, on a quand même un gain important.
Une autre explication que la mise en cache ?

Travail sur des nombres flottants non initialisés == le coprocesseur arithmétique génère plein d'exceptions, qui sont généralement cachées à l'exécution (mais qu'on peut activer via un appel à une fonction dont je ne me rappelle plus le nom), parce qu'ils y a des nombres dénormalisés, des NaN, des infinis, etc.

Merci, j'en apprend beaucoup en ce moment

PS : le code du trie que j'ai utilisé pour testé la mise en cache :

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
while (echange == true)
{
    echange = false;
    for (j = 0; j <= n-2; j+=16)
    {        
        for( int k = 0 ; k < 16 && (j +k <= n-2); k++)
        {
            if (vec[j+k] > vec[j+k+1])
            {
                tmp = vec[j+k];
                vec[j+k] = vec[j+k+1];
                vec[j+k+1] = tmp;
                echange = true;
            }
            ++nbOp;
        }
    }
}

et le code d'origine, pour rappel :

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
while (echange == true)
{
    echange = false;
    for (j = 0; j <= n - 2; j++)
    {      
        if (vec[j] > vec[j + 1])
        {
            tmp = vec[j];
            vec[j] = vec[j + 1];
            vec[j + 1] = tmp;
            echange = true;                
        }
        ++nbOp;
    }
}

PS : merci

Edit: retrouvé les fonctions :

man 2 feenableexcept avec la glibc
_controlfp avec Visual C++.

[Mat.M]

Les résultats mettent à mal le C++ (et surtout g++).

Vous en pensez quoi ? L'implémentation des versions C++ est à revoir (je n'ai pas regardé le code en profondeur mais ça ressemble beaucoup à du C)

je trouve que ces tests ne sont pas significatifs.
Un projet informatique ce n'est pas que des tests sur des calculs de tri ou des suites de Finobacci ; un projet informatique c'est aussi tout une interface graphique avec des boutons et des fenêtres.

C'est certain que si tu fais des tests de performances entre du code Java et C++ avec un programme "nu" Java sera performant.

Il y a un autre point plus important : GetTickCount() est-il un bon outil de mesure? Si je me souviens bien, non, mais faut vérifier. Il me semble que cette fonction ne suffit pas à nue mesure correcte de perfs.

effectivement GetTickCount() n'est pas assez précis ; il faut utiliser QueryPerformanceCounter compteur très précis

http://msdn.microsoft.com/en-us/libr...=vs.85%29.aspx

[gbdivers]

Mon stagiaire m'a parlé d'un document What Every Programmer Should Know About Memory datant de 2007 (aucun rapport avec le document "What Every Programmer Should Know About Floating-Point Arithmetic" de Goldberg, juste un clin d'oeil je suppose)
Quelqu'un connait ? C'est une bonne introduction aux problématiques évoquées ici ?

EDIT : finalement, je retire le