Discussion :

[serge17]

Bonjour

La fonction suivante

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
 
uint64_t  f1(int64_t a, int64_t p)
{
   int64_t u = p, v = a, r = 0, s = 1;
   while(u != v){  
      if(u > v){
         u -= v;
        // code1
      }else{
         v -= u;
         // code2
      }
   }
   return s;
}

effectue une soustraction et 2 tests de comparaison, chacun ayant un de temps d'execution équivalent à celui d'une soustraction (rectifiez moi si je me trompe).
J'ai donc pensé à la modifier de la façon suivante

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
 
uint64_t  f2(int64_t a, int64_t p)
{
   int64_t u = p, v = a, r = 0, s = 1, w;
   while( (w = u - v) != 0){  
      if(w > 0){
         u  = w;
        // code1
      }else{
         v = -w;
         // code2
      }
   }
   return s;
}

A la place de 3 "soustractions", cette nouvelle fonction effectue une soustraction avec affectation (dans w) et un test du bit de signe (les autres affectations sont les mêmes).

Je ne m'attendais pas à un gain énorme mais à ma grande surprise f2 est 20 à 25% plus lente que f1.

Avez vous une explication ?
Merci d'avance.

[Obsidian]

J'imagine que cela va beaucoup dépendre à la fois de la plateforme cible, du compilateur lui-même et surtout des options d'optimisation en vigueur. Il faudrait demander à ton compilateur de produire la sortie assembleur du programme compilé.

Cela dit, en dépit de la « lourdeur » syntaxique, la première boucle n'implique que deux comparaisons et une affectation (« l'une ou l'autre », en fonction du résultat du test), là où l'autre programme en implique deux. En matière de « pourcentage » des opérations effectuées par tour de boucle, ce n'est donc pas si étonnant.

Par ailleurs, tu travailles avec des int64_t. Cela représente tout de même huit octets à la fois. Ça passe sur une architecture 64 bits, mais cela a forcément une influence sur la ligne de cache. Et si tu compiles en 32 bits, chaque accès 64 bits pénalisera un peu les performances également.

Enfin, moins tu utilises de variables, plus le compilateur est à même d'optimiser les choses en utilisant des registres du processeur pour les conserver. Tu peux alors descendre sous un seuil où plus aucun accès mémoire n'est effectué, ce qui change alors énormément les choses. Cependant, dans le cas présent et avec seulement trois variables impliquées, ton processeur devrait être capable de le faire dans tous les cas, à condition qu'un minimum d'optimisations soit appliqué quand même.

[serge17]

Merci Obsidian

Je travaille sous Windows 10 avec Code::Blocks. Compilateur 64 bits TDM64. Aucune option d'optimisation.

La première boucle contient 2 comparaisons (u != v) et (u > v) ainsi qu'une soustraction avec affectation (u = u - v) vs (v = v - u) suivant le cas.
La deuxième boucle contient une soustraction avec affectation (w = u - v) un test à 0 (w != 0) un test de signe (w >0) et une affectation (u = w) vs (v = -w) suivant le cas.

Si on retire ce qui est en commun, càd une soustraction avec affectation, il reste
première boucle ; 2 comparaisons = 2 soustractions
deuxième boucle : un test à 0, un test de signe et une affectation.

La différence parait faible (dans quel sens ?). Ce qui m'interpelle c'est ce 20 à 25% : cela me semple énorme !

[Obsidian]

Si on retire ce qui est en commun, càd une soustraction avec affectation, il reste
première boucle ; 2 comparaisons = 2 soustractions

Attention, il s'agit de -= : il ne s'agit donc pas d'une soustraction seule, mais bien d'une soustraction suivie d'une affectation pour mettre à jour la lvalue, qui sert ici d'accumulateur.

(update : j'avais omis le début de la phrase, mea culpa).

deuxième boucle : un test à 0, un test de signe et une affectation. La différence parait faible (dans quel sens ?).
Ce qui m'interpelle c'est ce 20 à 25% : cela me semple énorme !

C'est peu s'il s'agit d'une opération ponctuelle noyée au milieu du reste d'un grand logiciel mais ici, ta boucle ne fait que ça.

En admettant par exemple que l'on expurge tous les tests et opérations pour ne conserver que les affectations, alors si tu passes de une à deux affectations au sein de ta boucle, tu doubles par définition la durée d'exécution de ton programme et tu observes 100 % d'augmentation.

Les options d'optimisation peuvent aussi avoir un effet considérable lorsque l'on audite un programme aussi simple : sans option d'optimisation, ton programme met à jour toutes les variables en mémoire à chaque tour de boucle (parce que la mémoire doit l'être et qu'il faut pouvoir éventuellement les lire indirectement avec un pointeur).

Avec un premier niveau d'optimisation, le compilateur comprend que comme ces variables sont locales à ta fonction, il n'y a pas besoin de les exposer à l'extérieur et il peut essayer de les conserver dans les registres du processeur. Plus aucun accès bus et même la ligne de cache n'est pas sollicitée. Tu fais déjà le grand écart entre les deux versions.

En activant toutes les options d'optimisation, le compilateur comprend qu'aucune information ne sort de ta fonction en dehors du « return » final, qui renvoie le contenu d'une variable qui ne varie jamais. Le compilateur peut alors abandonner la totalité du code le remplacer par un simple « return 1; » constant. C'est ce que fait GCC avec l'option -O3 par exemple… à condition qu'il puisse s'en rendre compte !

Or, le fait de « conditionner la condition » de if à l'affectation d'une variable complexifie l'expression au point que certaines choses vont devenir non déterministes pour le compilateur. En particulier, dans le premier cas, il est garanti que u et v restent toujours constantes en dehors du corps de la boucle. L'expression peut donc être simplifiée par le compilateur de la même façon que l'on simplifie des équations sur papier avant de les résoudre et il peut en tirer des conclusions. Dans le deuxième cas, l'expression entière (entre parenthèses) dépend également de w, qui est mise à jour au cours de l'évaluation. Dans le corps de la boucle, w interagit avec u et v. Il y a donc une relation bidirectionnelle entre ces deux acteurs et le compilateur ne peut plus considérer qu'il ne peut pas les mettre à jour. Avec cela, il y a aussi des histoires de points de séquence.

Voici comment GCC compile les deux versions avec l'optimisation maximum -O3 :

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
 _Z2f1ll:                            |  _Z2f2ll:
  .LFB3:                             |  .LFB3:  jmp     .L3
 
                                     |  .L4:    jle     .L7
                                     |  .L3:    mov     rax, rsi
                                     |          sub     rsi, rdi
                                     |          test    rsi, rsi
                                     |          jne     .L4
 
          mov     eax, 1             |          mov     eax, 1
          ret                        |          ret
 
                                     |  .L7:    sub     rdi, rax
                                     |          mov     rsi, rax
                                     |          jmp     .L3

Dans le premier cas, la sortie est immédiate avec eax = 1 (code de retour). Dans le second, rsi et rdi (registres source et destination) correspondent à u et v, et rax est utilisé pour maintenir w. On arrive à faire tenir les trois variables dans des registres, mais on est quand même obligé d'honorer la boucle et de la mener à terme. On obtient donc un gain virtuellement « infini » dans le premier cas. Dans cette situation, il est donc difficile de faire des mesures qui soient fiables et surtout qui aient un sens.

[serge17]

1)

En admettant par exemple que l'on expurge tous les tests et opérations pour ne conserver que les affectations

Cela handicape fortement la deuxième fonction puisque les tests ne sont pas équivalents en temps d'exécution.
Dans la boucle 1 se sont des comparaisons (ie des soustractions) alors que dans la boucle 2 ce sont des test à 0 ou de signe qui sont beaucoup plus rapides.
La question qui se pose est de savoir si cela compense ou non l'affectation supplémentaire.

2) l'optimisation permet sans doute d'utiliser les registres mais cela est valable pour les deux programmes. Je vais voir si cela change quelque chose.

3) c'est de ma faute : je voulais focaliser sur la différence entre ces deux fonctions mais les parties notées "code1" et "code2" modifient la variable 's' (qui est donc différente de 1 à la sortie).
Sans ces lignes de code, la boucle ne fait rien qui concerne 's' : l'optimisation du programme 1 ne fait donc rien, sinon renvoyer la valeur '1' de 's' ; mais cela n'a rien à voir avec les vrais programmes !

4) je vais simplifier et compléter tout ça pour que ces programmes puissent être compilés correctement.

PS : points de séquence ?

[jo_link_noir]

PS : points de séquence ?

C'est l'ordre dans lequel les instructions doivent être exécutées. Quand on active les optimisations (parce que ça n'a pas de sens de mesurer sans optimisation), le compilateur peut — et va — réordonner les instructions. Du moment que cela ne change pas le comportement final, il n'y a pas de limite. Bien sûr, comme certaines instructions dépendent d'autres instructions, tout ne peut pas être réordonné.

Le compilateur ne fait pas que réordonner, il change aussi les instructions, ce n'est pas du 1-1 de C++ vers asm. Compter bêtement les opérations effectuées depuis un code C++ n'a pas trop de sens. Le faire avec la sortie asm a aussi ses limites.

Pour voir l'asm, compiler-explorer est très pratique. Voici avec les codes au-dessus: https://godbolt.org/z/5TWdfsY1E (il peut tourner en local).
J'ai ajouté ++s dans la boucle histoire qu'elle ne fasse pas rien et 2 compilateurs avec et sans opti.

Pour des mesures, j'aime bien nanobench. Sinon il y a https://quick-bench.com/ qui utilise google-benchmark, mais le site est tellement lent à donner un résultat qu'il vaut mieux faire la mesure chez soit... J'ai régulièrement un timeout.

[Obsidian]

1) Cela handicape fortement la deuxième fonction puisque les tests ne sont pas équivalents en temps d'exécution.
Dans la boucle 1 se sont des comparaisons (ie des soustractions) alors que dans la boucle 2 ce sont des test à 0 ou de signe qui sont beaucoup plus rapides.

Non, ça ne devrait pas affecter les performances plus que cela. Comme tu le dis, en langage machine, une comparaison est une soustraction dont on examine le résultat sans le sauvegarder, et déterminer une égalité se fait justement en observant si ce résultat est nul. En reprenant une variable quelconque, il est possible de faire « TEST » (sur Intel, avec opérande) ou « TST » (sur Motorola, sans opérande) dessus pour repositionner les bits de flags, qui sont généralement positionnés automatiquement à la fin d'une opération.

Donc, ici l'optimisation consisterait à placer le test juste après la dernière opération pour pouvoir justement en économiser une, mais les tests eux-mêmes ne varieraient pas beaucoup en performances.

La question qui se pose est de savoir si cela compense ou non l'affectation supplémentaire.

Probablement pas et ce n'est pas le problème en réalité. Ce qui importe ici est de savoir ce que fait réellement ton compilateur, d'une part et de faire en sorte qu'il comprenne qu'en principe, w est invariant ou peut à tout le moins être optimisé. On a vu ci-dessus que gcc, par exemple, est confronté à une situation où il est dans l'impossibilité d'en faire l'hypothèse, même avec le niveau maximum d'optimisation.

2) l'optimisation permet sans doute d'utiliser les registres mais cela est valable pour les deux programmes. Je vais voir si cela change quelque chose.

Essaie surtout d'obtenir la sortie assembleur pour chacune de tes deux fonctions et partage-là avec nous ici.

Je lis que TDM64 est en fait un GCC déguisé. Il faut passer l'option « -S » dans « Compiler Settings » puis « Other Compiler Options ».

3) c'est de ma faute : je voulais focaliser sur la différence entre ces deux fonctions mais les parties notées "code1" et "code2" modifient la variable 's' (qui est donc différente de 1 à la sortie).
Sans ces lignes de code, la boucle ne fait rien qui concerne 's' : l'optimisation du programme 1 ne fait donc rien, sinon renvoyer la valeur '1' de 's' ; mais cela n'a rien à voir avec les vrais programmes !

Effectivement, si tu modifies « s » sans qu'on le voie dans les extraits présentés ici, cela va impacter encore plus les performances, surtout qu'il ne pourra pas en faire abstraction puisqu'il aura besoin de retrouver cette valeur en fin de fonction après tous les traitements, et même la faire remonter à la fonction appelante.

PS : points de séquence ?

Il s'agit d'une notion en C et C++ notoirement connue mais relativement peu souvent exposée lorsque l'on apprend ces langages. Voir ici et ici.

Contrairement à ce que l'on pourrait légitimement supposer de prime abord, lorsqu'un compilateur C ou C++ évalue une expression, il ne le fait pas nécessairement linéairement et de gauche à droite. Il va agréger toutes les informations dans le sens qui est le plus facile pour lui et en tenant compte de celle qu'il possède déjà.

Cela signifie que la mémoire n'est pas forcément mise à jour immédiatement après une opération et que les effets de bord que ces opérations peuvent avoir ne se produiront pas forcément dans l'ordre attendu non plus. On est seulement certain qu'ils auront été tous honorés dès qu'un point de séquence aura été atteint, ce qui se produira formellement dans les situations suivantes :

• À la fin d'une expression complète (qui ne fait pas partie d'une expression plus vaste) ;
• Juste avant l'appel à une fonction — mais après l'évaluation de chacun de ses paramètres, qui eux ne le sont pas forcément dans l'ordre où ils sont écrits ;
• Après le premier opérande de certains opérateurs « forts », soit :
  • , (opérateur virgule) ;
  • && et || (pseudo-ET et pseudo-OU. Ne concerne pas les opérateurs bit à bit & et |) ;
  • ?: (opérateur ternaire ou opérateur conditionnel). Dans ce dernier cas, seul le deuxième ou le troisième opérande est évalué ensuite (par définition).

Un exemple-type est celui où l'on utilise de façon ambiguë des opérateurs de pré et post-incrémentation ou décrémentation :

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
int main(void)
{
    using std::cout;
    using std::endl;
 
    int x = 1;
 
    cout << "1) x = " << x++ + ++x << endl;
    cout << "2) x = " << x         << endl;
 
    return 0;
}

En le compilant avec les avertissements, on obtient :

Code Shell :

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

1
2
3
4
5
6
7
8
9
10
$ g++ -O3 -pedantic -Wall --std=c++03 xxx.cpp -o xxx && ./xxx 

xxx.cpp: In function «*int main()*»:
xxx.cpp:10:27: attention: l'opération sur «*x*» est peut être non définie [-Wsequence-point]
   10 |     cout << "1) x = " << x++ + ++x << endl;
      |                          ~^~
xxx.cpp:10:27: attention: l'opération sur «*x*» est peut être non définie [-Wsequence-point]

1) x = 4
2) x = 3

Ici, le compilateur s'en sort en renvoyant le résultat attendu, mais nous avertit qu'il aurait très bien pu ne pas l'être.

Ce qui nous amène à ton exemple : je me suis demandé si une affectation « = », surtout au sein d'une condition « if() », impliquait un point de séquence. On aurait pu le supposer légitimement, mais ce n'est pas le cas à ce stade. Par contre, la norme impose un point de séquence après l'évaluation de la condition de contrôle de if( ) et de while( ) (entre autres). Donc, si cette condition implique une affectation à w comme dans l'exemple numéro 2, celle-ci doit être honorée à chaque tour de boucle.

(UPDATE : jo_link_noir a répondu entretemps…)

[serge17]

Merci Jo_link_noir, je vais regarder tout cela de plus près.

En simplifiant à l'extrême on obtient

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
 
uint64_t f1(int64_t u, int64_t v)
{
   while(u != v){
      if(u > v){
         u -= v;
      }else{
         v -= u;
      }
   }
   return(u);
}
 
uint64_t f2(int64_t u, int64_t v)
{
   int64_t w;
   while((w = u - v) != 0){
      if(w > 0){
         u = w;
      }else{
         v = -w;
      }
   }
   return(u);
}

Cette fois, toujours sans optimisation, f2 est 70% plus lente que f1.
Mais l'optimisation change tout. Pour une raison que j'ignore le compilateur optimise f1 beaucoup mieux que f2.
Si bien qu'avec l'option O3, f2 est (en moyenne) 40 fois plus lente que f1 !
Effectivement

ça n'a pas de sens de mesurer sans optimisation

!

update : merci aussi à toi Obsidian : j'ai lu ta réponse après avoir répondu à Jo_link_noir.