safe - Pourquoi GCC n'optimise-t-il pas un*a*a*a*a*a à(a*a*a)*(a*a*a)?




o3 gcc optimization (8)

Je suis en train d’optimiser numériquement une application scientifique. Une chose que j’ai remarquée est que GCC optimisera le pow(a,2) appel pow(a,2) en le compilant en a*a , mais l’appel pow(a,6) n’est pas optimisé et appellera en fait la fonction de bibliothèque pow , ce qui ralentit considérablement la performance. (En revanche, Intel C ++ Compiler , exécutable icc , éliminera l’appel de bibliothèque pour pow(a,6) .)

Ce que je suis curieux de savoir, c’est que lorsque je remplace pow(a,6) par a*a*a*a*a*a aide de GCC 4.5.1 et des options " -O3 -lm -funroll-loops -msse4 ", il utilise 5 instructions mulsd :

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

alors que si j'écris (a*a*a)*(a*a*a) , cela produira

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

ce qui réduit le nombre d'instructions de multiplication à 3. icc a un comportement similaire.

Pourquoi les compilateurs ne reconnaissent-ils pas cette astuce d'optimisation?

https://code.i-harness.com


Aucune affiche n'a encore mentionné la contraction des expressions flottantes (norme ISO C, 6.5p8 et 7.12.2). Si le pragma FP_CONTRACT est défini sur ON , le compilateur est autorisé à considérer une expression telle que a*a*a*a*a*a comme une opération unique, comme si elle était évaluée exactement avec un arrondi unique. Par exemple, un compilateur peut le remplacer par une fonction d'alimentation interne à la fois plus rapide et plus précise. Ceci est particulièrement intéressant car le comportement est partiellement contrôlé par le programmeur directement dans le code source, alors que les options du compilateur fournies par l'utilisateur final peuvent parfois être utilisées de manière incorrecte.

L'état par défaut du pragma FP_CONTRACT est défini par l'implémentation, de sorte qu'un compilateur est autorisé à effectuer ces optimisations par défaut. Par conséquent, le code portable devant respecter scrupuleusement les règles IEEE 754 doit le définir explicitement sur OFF .

Si un compilateur ne supporte pas ce pragma, il doit être prudent en évitant une telle optimisation, au cas où le développeur aurait choisi de le OFF .

GCC ne supporte pas ce pragma, mais avec les options par défaut, il suppose qu'il est ON ; ainsi pour les cibles avec un FMA matériel, si on veut empêcher la transformation a*b+c en fma (a, b, c), il faut fournir une option telle que -ffp-contract=off (pour définir explicitement le pragma to OFF ) ou -std=c99 (pour indiquer à GCC de se conformer à une version standard de C, ici C99, suivez donc le paragraphe ci-dessus). Dans le passé, cette dernière option n’empêchait pas la transformation, ce qui signifie que GCC n’était pas en conformité sur ce point: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


Car un nombre à virgule flottante 32 bits, tel que 1.024, n'est pas 1.024. Dans un ordinateur, 1.024 est un intervalle: de (1.024-e) à (1.024 + e), où "e" représente une erreur. Certaines personnes ne s'en rendent pas compte et croient également que * dans a * a signifie multiplication de nombres de précision arbitraire sans erreurs associées à ces nombres. Certaines personnes échouent à comprendre que c’est peut-être les calculs mathématiques qu’ils ont effectués à l’école élémentaire: ne travailler qu'avec des nombres idéaux sans erreurs, et croire qu’il est acceptable d’ignorer simplement "e" lors de la multiplication. Ils ne voient pas le "e" implicite dans "float a = 1.2", "a * a * a" et les codes C similaires.

Si la majorité des programmeurs reconnaissent (et sont capables d'exécuter) l'idée que l'expression C a * a * a * a * a * a ne fonctionne pas avec des nombres idéaux, le compilateur GCC serait alors GRATUIT pour optimiser "a * a * a * a * a * a "en dire" t = (a * a); t * t * t "qui nécessite un plus petit nombre de multiplications. Mais malheureusement, le compilateur GCC ne sait pas si le programmeur qui écrit le code pense que "a" est un nombre avec ou sans erreur. Ainsi, GCC ne fera que reproduire le code source, car c’est ce que GCC voit de son "œil nu".

... une fois que vous savez quel genre de programmeur vous êtes, vous pouvez utiliser le commutateur "-ffast-math" pour dire à GCC que "Hey, GCC, je sais ce que je fais!". Cela permettra à GCC de convertir un * a * a * a * a * a * a en un morceau de texte différent - il est différent de a * a * a * a * a * a - mais calcule tout de même un nombre compris dans l'intervalle d'erreur de a * a * a * a * a * a. C'est bon, car vous savez déjà que vous travaillez avec des intervalles et non des nombres idéaux.


Fortran (conçu pour l'informatique scientifique) a un opérateur de puissance intégré et, autant que je sache, les compilateurs Fortran optimisent généralement l'augmentation des puissances de nombres entiers de la même manière que ce que vous décrivez. C / C ++, malheureusement, n’a pas d’opérateur électrique, seulement la fonction de bibliothèque pow() . Cela n'empêche pas les compilateurs intelligents de traiter spécialement le pow et de le calculer plus rapidement dans des cas particuliers, mais il semble qu'ils le fassent moins fréquemment ...

Il y a quelques années, j'essayais de rendre plus pratique le calcul optimal des puissances entières. C'est du C ++, pas du C cependant, et cela dépend toujours du compilateur qui est assez intelligent pour optimiser les choses / en ligne. Quoi qu'il en soit, j'espère que vous pourrez le trouver utile dans la pratique:

template<unsigned N> struct power_impl;

template<unsigned N> struct power_impl {
    template<typename T>
    static T calc(const T &x) {
        if (N%2 == 0)
            return power_impl<N/2>::calc(x*x);
        else if (N%3 == 0)
            return power_impl<N/3>::calc(x*x*x);
        return power_impl<N-1>::calc(x)*x;
    }
};

template<> struct power_impl<0> {
    template<typename T>
    static T calc(const T &) { return 1; }
};

template<unsigned N, typename T>
inline T power(const T &x) {
    return power_impl<N>::calc(x);
}

Précision pour les curieux: cela ne trouve pas le moyen optimal de calculer les puissances, mais comme trouver la solution optimale est un problème NP-complet et que cela ne vaut que pour les petites puissances (par opposition à l’utilisation de pow ), il n’ya aucune raison de le faire. faire du bruit avec les détails.

Ensuite, utilisez-le simplement comme power<6>(a) .

Cela facilite la -ffast-math pouvoirs (pas besoin d’écrire 6 a s avec des parens), et vous permet d’avoir ce type d’optimisation sans -ffast-math si vous avez quelque chose qui dépend de la précision, telle que la sommation compensée (un exemple où l’ordre des opérations est indispensable).

Vous pouvez aussi probablement oublier qu'il s'agit de C ++ et l'utiliser simplement dans le programme C (s'il compile avec un compilateur C ++).

J'espère que cela peut être utile.

MODIFIER:

Voici ce que je tire de mon compilateur:

Pour a*a*a*a*a*a ,

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0

Pour (a*a*a)*(a*a*a) ,

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm0, %xmm0

Pour le power<6>(a) ,

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1

GCC optimise effectivement un * a * a * a * a * a à (a * a * a) * (a * a * a) quand a est un entier. J'ai essayé avec cette commande:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

Il y a beaucoup de drapeaux gcc mais rien d'extraordinaire. Ils veulent dire: Read from stdin; utiliser le niveau d'optimisation de l'O2; liste de langage d'assemblage de sortie au lieu d'un binaire; la liste doit utiliser la syntaxe du langage d'assemblage Intel; l'entrée est en langage C (généralement la langue est déduite de l'extension du fichier d'entrée, mais il n'y a pas d'extension de fichier lors de la lecture de stdin); et écrivez sur stdout.

Voici la partie importante de la sortie. Je l'ai annoté avec quelques commentaires indiquant ce qui se passe dans le langage d'assemblage:

    ; x is in edi to begin with.  eax will be used as a temporary register.
    mov    eax, edi     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

J'utilise le système GCC sous Linux Mint 16 Petra, un dérivé d'Ubuntu. Voici la version gcc:

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Comme d'autres auteurs l'ont noté, cette option n'est pas possible en virgule flottante, car l'arithmétique en virgule flottante n'est en réalité pas associative.


Je n'aurais pas prévu que ce cas soit optimisé du tout. Il est rare qu’une expression contienne des sous-expressions pouvant être regroupées pour supprimer des opérations entières. Je m'attendrais à ce que les rédacteurs de compilateurs investissent leur temps dans des domaines susceptibles de déboucher sur des améliorations notables, plutôt que de couvrir un cas marginal rarement rencontré.

J'ai été surpris d'apprendre par les autres réponses que cette expression pouvait effectivement être optimisée avec les commutateurs de compilation appropriés. Soit l’optimisation est triviale, soit il s’agit d’une optimisation beaucoup plus courante, soit les rédacteurs du compilateur ont été extrêmement minutieux.

Il n'y a rien de mal à fournir des astuces au compilateur, comme vous l'avez fait ici. Il est normal et prévisible que le processus de micro-optimisation consiste à réorganiser les instructions afin de déterminer les différences qu’elles apporteront.

Bien que le compilateur puisse justifier que les deux expressions produisent des résultats incohérents (sans les commutateurs appropriés), vous n'êtes pas obligé d'être lié par cette restriction. La différence sera incroyablement minime - à tel point que si la différence vous importe, vous ne devriez pas utiliser d'arithmétique en virgule flottante standard.


Les fonctions de bibliothèque telles que "pow" sont généralement soigneusement conçues pour générer le minimum d'erreur possible (en cas générique). Ceci est généralement réalisé en approximant des fonctions avec des splines (selon le commentaire de Pascal, l'implémentation la plus courante semble utiliser l' algorithme de Remez )

fondamentalement l'opération suivante:

pow(x,y);

a une erreur inhérente d'approximativement la même ampleur que l'erreur de toute multiplication ou division .

Alors que l'opération suivante:

float a=someValue;
float b=a*a*a*a*a*a;

a une erreur inhérente qui est supérieure à 5 fois celle d'une multiplication ou d'une division unique (parce que vous combinez 5 multiplications).

Le compilateur devrait être très attentif au type d'optimisation qu'il effectue:

  1. si l'optimisation de pow(a,6) en a*a*a*a*a*a peut améliorer les performances, mais réduire considérablement la précision des nombres à virgule flottante.
  2. en optimisant a*a*a*a*a*a à pow(a,6) la précision peut en être réduite car "a" était une valeur spéciale qui permet une multiplication sans erreur (une puissance de 2 ou un petit nombre entier)
  3. si l'optimisation de pow(a,6) à (a*a*a)*(a*a*a) ou (a*a)*(a*a)*(a*a) peut encore entraîner une perte de précision par rapport à la fonction de pow .

En général, vous savez que pour des valeurs à virgule flottante arbitraires, "pow" a une meilleure précision que toute fonction que vous pourriez éventuellement écrire, mais dans certains cas particuliers, plusieurs multiplications peuvent avoir une précision et des performances meilleures, il appartient au développeur de choisir celle qui convient le mieux, éventuellement commenter le code de sorte que personne ne «optimise» ce code.

La seule chose qui ait du sens (opinion personnelle, et apparemment un choix dans GCC sans optimisation particulière ou indicateur du compilateur) à optimiser devrait être de remplacer "pow (a, 2)" par "a * a". Ce serait la seule chose saine qu'un vendeur de compilateur devrait faire.


Un autre cas similaire: la plupart des compilateurs n’optimiseront pas a + b + c + d en (a + b) + (c + d) (c’est une optimisation puisque la seconde expression peut être mieux canalisée) et l’évaluera comme donnée (ie comme (((a + b) + c) + d) ). C'est aussi à cause des cas de coin:

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

Cette sortie 1.000000e-05 0.000000e+00


gcc peut réellement faire cette optimisation, même pour les nombres à virgule flottante. Par exemple,

double foo(double a) {
  return a*a*a*a*a*a;
}

devient

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

avec -O -funsafe-math-optimizations . Cette réorganisation enfreint IEEE-754, cependant, elle nécessite le drapeau.

Comme Peter Cordes l'a souligné dans un commentaire, les entiers signés peuvent effectuer cette optimisation sans -funsafe-math-optimizationsque cela soit valable, car il existe exactement quand il n'y a pas de dépassement de capacité et en cas de dépassement de capacité, vous obtenez un comportement non défini. Donc vous obtenez

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

avec juste -O. Pour les entiers non signés, c'est encore plus facile, car ils travaillent avec une puissance de 2 et peuvent donc être réorganisés librement, même en cas de dépassement de capacité.





fast-math