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.

[Luc Hermitte]

1- Comme jo_link_noir: Ca n'a vraiment aucun sens de mesurer sans optims
2- Et après optim, il faut mesurer, beaucoup, beaucoup, mais vraiment beaucoup de fois, sortir des stats : médianes, quartiles, ignorer les outliers et comparer ensuite.

Et même là, on peut avoir des surprises avec une fonction plus rapide que l'autre alors que... le code ASM généré est strictement identique. Oui, oui. c'est possible. Plein de facteurs peuvent entrer en jeu à commencer par l'alignement des fonctions, des données...

+1 aussi pour les frameworks de microbenchmarking pour comparer les perfs ici: nanobench, ou quickbench qui est plus connu.

Mais quitte à vouloir optimiser, je testerai d'autres implémentations: https://en.wikipedia.org/wiki/Greatest_common_divisor plus il faudrait comparer à std::gcd

[serge17]

Merci Luc Hermitte

Comme tu l'as remarqué, ces fonctions calculent le gcd() par la méthode d'Euclide.
Autant que je sache, std::gcd() n'est pas très performant et est limité aux entiers courants (il ne supporte pas uint128_t par exemple).

Ma question anodine (en fait une mauvaise question) m'a permis, grâce à vous, d'apprendre des choses sur des sujets dont j'ignorais jusqu'à l'existence.

Merci encore à vous tous.

[Luc Hermitte]

Comme tu l'as remarqué, ces fonctions calculent le gcd() par la méthode d'Euclide.
Autant que je sache, std::gcd() n'est pas très performant et est limité aux entiers courants (il ne supporte pas uint128_t par exemple).

Les perfs de std::gcd seront propres à chaque implémentation. J'avoue que je ne les connais pas, mais il serait logique de comparer tes implémentations à celle standard (avec ton compilo et sa lib standard) -- et en optimisé bien évidemment.

Pour les entiers 128 bits... il y a divers problèmes à divers endroits, mais si ça ne passe pas pour std::gcd, rajouter la spécialisation manquante à std::common_type devrait suffire je pense.

[Guesset]

Bonjour,

w n'apporte aucun gain et consomme un registre de plus.

En effet u et v ne sont modifiées et utilisées que dans la boucle (par exemple : pas d'appel de fonctions avec l'une ou l'autre de ces variables). Alors, le compilateur évitera de faire de réelles affectations en laissant ces valeurs en registres et en opérant, si nécessaire, une affectation en sortie de boucle.

Si le compilateur est futé, il peut même éviter de refaire le test u != v (sauf à la première itération) car les opérations u -= v et v -= u positionnent déjà correctement le ZF (zero flag) correspondant au test d'in-égalité.

En ce qui concerne l'algorithme, l'utilisation de div/mod serait plus rapide malgré la lenteur relative de la division. Beaucoup moins d'itérations et pas de test interne, car si u > v, r = mod(u,v) et u = v et v = r : u reste > v.
Ajout : c'est certainement cet algorithme qui est utilisé dans la bibliothèque. Il suppose l'existence d'une division qui n'existe matériellement que jusqu'à 64 bits. Après il faut passer avec les bibliothèques en multi-précision, mais c'est une autre histoire.

Salutations

[serge17]

Bonjour Guesset

w n'apporte aucun gain et consomme un registre de plus.

Oui, j'ai fini par m'en rendre compte !

Ces exemples avaient pour seul but de poser la question au sujet du 'w'. Le gcd() est à la fois fort simple dans sa définition et fort complexe dans ses implémentations (et je ne parle même pas des polynômes) : multi-précision, hardware, etc. Il n'y qu'à regarder les divers articles sur le sujet (et sujets connexes) pour s'en rendre compte.
En ce qui me concerne, c'est juste pour une utilisation perso sur des entiers limités à 128 bits (je ne prétends pas apporter ma pierre à l'édifice !) ; le reste, c'est de la curiosité.

En ce qui concerne l'algorithme, l'utilisation de div/mod serait plus rapide malgré la lenteur relative de la division. Beaucoup moins d'itérations et pas de test interne, car si u > v, r = mod(u,v) et u = v et v = r : u reste > v.

On peut éviter les affectations dues à l'échange des variables 'u' et 'v' : si u > v, u = u mod v puis v = v mod u et on boucle. Il faudra de toute façon faire un test de sortie si le diviseur est nul. Même ainsi, dans la cadre restreint qui est le mien, cet algorithme est plus lent que le gcd binaire.

[Luc Hermitte]

Par curiosité, j'ai regardé les implémentations de libstdc++ et de libc++.

- Les deux dégagent les zeros de queue (divisent par les 2^n maximaux)
- libstdc++ fait un swap à chaque itération pour que a<b.
- libc++ calcule a - b, puis teste si a > b pour utiliser la différence que l'on vient de calculer, et l'ignore sinon. C'est surprenant, mais j'imagine que c'est lié aux expérimentations qui sont citées https://lemire.me/blog/2013/12/26/fa...common-divisor

[Guesset]

Bonjour serge17,

...On peut éviter les affectations dues à l'échange des variables 'u' et 'v' : si u > v, u = u mod v puis v = v mod u et on boucle. Il faudra de toute façon faire un test de sortie si le diviseur est nul. Même ainsi, dans la cadre restreint qui est le mien, cet algorithme est plus lent que le gcd binaire.

Les tests internes à la boucle disparaissent, il ne reste que le test de sortie (c'est le minimum vital ).

J'écrirais un truc du genre (non vérifié) :

Code :

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

1
2
3
4
5
6
7
8
int64_t pgcd(int64_t u, int64_t v) {          // on veillera à ce que les arguments soient > 0
   if(u < v) { u ^= v;  v ^= u;  u ^= v; }    // on remet dans l'ordre si nécessaire
   do {
      int64_t  w = u;
      u = v;
   }  while(v = w % v);                       // ce n'est pas très joli, mais équivalent à (v = t % v) != 0
   return u;
}

Dans la mesure où l'autre algorithme calcule le modulo pas à pas, le seul cas où il est meilleur semble être pour u / v = 1 (une itération pour l'un et l'autre, mais la division est plus longue).

Salut

[Luc Hermitte]

L'obfuscation avec le xor ne sert à rien. https://godbolt.org/z/fj71Erro8

Par contre, le truc dégueulasse dans le while n'est pas légal en C++.

[Guesset]

Bonjour Luc Hermitte,

L'obfuscation avec le xor ne sert à rien. https://godbolt.org/z/fj71Erro8

Par contre, le truc dégueulasse dans le while n'est pas légal en C++.

Ce n'est pas une obfuscation. Ce code donne un résultat, au pire égal à l'appel d'une bibliothèque en O3, meilleur dans les autres cas.

Je me suis effectivement laissé emporter, à tort, par une écriture type C légitime alors. Dont acte.

Salut

[Luc Hermitte]

Le compilateur reconnait le pattern. Il voit que l'on veut faire un swap et le remplace par le code qu'il aurait mis pour un swap.
C'est en cela que c'est de l'obfuscation: cela rend le code plus compliqué à maintenir pour 0 gain en termes de perfs sur les compilos contemporains (xor & swap donnent le même ASM depuis gcc7)

De la même manière que les vieilles optims comme:
- une multiplication par 33 sera remplacée par un shift et une addition -- OK, pas MSVC pour celui là on dirait bien
- un modulo fait avec une soustraction du dividende par le quotient multiplié par diviseur remplacé par l'asm généré pour le modulo et vice versa.

Au fil des versions des compilateurs le nombre bit twiddling hacks toujours pertinents diminue.

PS: désolé pour le dégueulasse, je m'étais suis laissé "embarqué" par le commentaire "pas très joli"

[Guesset]

Bonjour Luc Hermitte,

...De la même manière que les vieilles optims comme:
- une multiplication par 33 sera remplacée par un shift et une addition -- OK, pas MSVC pour celui là on dirait bien
- un modulo fait avec une soustraction du dividende par le quotient multiplié par diviseur remplacé par l'asm généré pour le modulo et vice versa.
Au fil des versions des compilateurs le nombre bit twiddling hacks toujours pertinents diminue...

Comme tu le fais remarquer tous les compilateurs n'ont pas le même comportement. Je préfère leur présenter un code qui, même si le compilateur ne l'optimise pas correctement, sera efficace. C'est un choix. Par ailleurs, quand cela pose un éventuel problème de lisibilité, je mets systématiquement un commentaire explicatif.

L'astuce du modulo (qui n'était intéressante que si la division était préalablement utilisée) est moins bonne que l'utilisation de DivMod (c'est la division et son reste aka modulo). Mais tant que les compilateurs ne le traitaient pas correctement, écrire une fonction DivMod en assembleur ne faisait pratiquement rien gagner ( <1% ) à cause de l'appel de fonction.

Au fil des années, les compilateurs s'améliorent, mais sont toujours en décalage vis-à-vis des évolutions de CPU (les langages y sont pour beaucoup, par exemple, en couvrant assez mal les données et opérations SIMD). Ça ne me dérange pas d'avoir alors recours à l'assembleur qui pose lui aussi des problèmes de lisibilité, surtout si le code est agencé (dé-séquentialisé) pour favoriser les traitements en désordre.

Salut

[Luc Hermitte]

Salut,

Sur l'exemple précis du swap, il faut remonter à gcc7, sorti en 2019. Pareil sept 2019 pour MSVC 16.3. Je pense que l'on peut basculer.

Pour le modulo, à nouveau ce que je cherche à montrer c'est que les compilateurs vont générer exactement le même asm si on utilise `%` ou si on calcule `a - (a/b) * b` depuis du C++.

Et donc il est inutile de recourir à des bidouilles non limpides quand il existe une façon de faire claire -- lorsque les compilos génèrent les mêmes ASM dans les deux cas.


Si maintenant tu sais que le compilo fait le mauvais choix dans tous les cas (avec l’hypothèse que le compilo fait le même choix d'ASM quel que soit le code C++ d'origine) et que c'est critique, why not de l'asm pour une archi donnée. Cependant, je préfère utiliser des libs portables et de plus haut niveau pour le SIMD plutôt que de recourir à de l'ASM directement, ou même à des intrinsics.