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





6 Answers

Lambdageek souligne à juste titre que l’optimisation d’ a*a*a*a*a*a à (a*a*a)*(a*a*a) peut changer la valeur. C'est pourquoi il est interdit par C99 (sauf autorisation expresse de l'utilisateur, via un indicateur de compilation ou un pragma). En règle générale, l'hypothèse est que la programmeuse a écrit ce qu'elle a fait pour une raison et que le compilateur devrait respecter cela. Si vous voulez (a*a*a)*(a*a*a) , écrivez cela.

Cela peut être pénible à écrire, cependant; pourquoi le compilateur ne peut-il pas simplement faire [ce que vous considérez être] la bonne chose lorsque vous utilisez pow(a,6) ? Parce que ce serait la mauvaise chose à faire. Sur une plate-forme avec une bonne bibliothèque mathématique, pow(a,6) est nettement plus précis que soit a*a*a*a*a*a ou (a*a*a)*(a*a*a) . Juste pour fournir des données, j'ai effectué une petite expérience sur mon Mac Pro, mesurant la pire erreur lors de l'évaluation de ^ 6 pour tous les nombres flottants à simple précision compris entre [1,2):

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

L'utilisation de pow au lieu d'un arbre de multiplication réduit l'erreur liée d'un facteur 4 . Les compilateurs ne devraient pas (et ne font généralement pas) faire des "optimisations" qui augmentent l'erreur sauf si l'utilisateur le permet (par exemple via -ffast-math ).

Notez que GCC fournit __builtin_powi(x,n) comme alternative à pow( ) , ce qui devrait générer un arbre de multiplication en ligne. Utilisez-le si vous voulez échanger précision et performance, mais ne souhaitez pas activer le calcul rapide.

bug compilation flags

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?




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.




Comme Lambdageek l'a souligné, la multiplication flottante n'est pas associative et vous pouvez obtenir moins de précision, mais lorsque vous obtenez une meilleure précision, vous pouvez vous opposer à l'optimisation, car vous souhaitez une application déterministe. Par exemple, dans la simulation de jeu client / serveur, où chaque client doit simuler le même monde pour lequel les calculs en virgule flottante doivent être déterministes.




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.




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é.




Related