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


Je fais de l'optimisation numérique sur une application scientifique. Une chose que j'ai remarquée est que GCC optimisera l'appel pow(a,2) en le compilant en a*amais l'appel pow(a,6) n'est pas optimisé et appellera réellement la fonction de bibliothèque pow, ce qui ralentit considérablement la performance. (En revanche, Compilateur Intel C ++, exécutable icc, éliminera l'appel de la bibliothèque pour pow(a,6).)

Ce que je suis curieux, c'est que quand j'ai remplacé pow(a,6) avec a*a*a*a*a*a en utilisant GCC 4.5.1 et les options "-O3 -lm -funroll-loops -msse4", il utilise 5 mulsd instructions:

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), ça va produire

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?


1965
2018-06-21 18:49


origine


Réponses:


Car Les mathématiques à virgule flottante ne sont pas associatives. La façon dont vous regroupez les opérandes en multiplication à virgule flottante a un effet sur la précision numérique de la réponse.

En conséquence, la plupart des compilateurs sont très conservateurs sur les calculs de réorganisation à virgule flottante à moins qu'ils ne puissent être sûrs que la réponse restera la même, ou à moins que vous leur disiez que vous ne vous souciez pas de la précision numérique. Par exemple: la -fassociative-math option de gcc qui permet à gcc de réassocier les opérations en virgule flottante, ou même -ffast-math option qui permet des compromis encore plus agressifs de précision contre la vitesse.


2565
2018-06-22 15:32



Lambdageek souligne correctement que parce que l'associativité ne tient pas pour les nombres à virgule flottante, l '"optimisation" de 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 si spécifiquement autorisé par l'utilisateur, via un flag de compilation ou un pragma). En général, l'hypothèse est que le programmeur a écrit ce qu'elle a fait pour une raison, et le compilateur devrait respecter cela. Si tu veux (a*a*a)*(a*a*a), écris ça.

Cela peut être une douleur à écrire, cependant; pourquoi le compilateur ne peut-il pas faire ce que vous considérez être la bonne chose lorsque vous utilisez pow(a,6)? Parce que ce serait le faux chose à faire. Sur une plate-forme avec une bonne bibliothèque de maths, pow(a,6) est significativement plus précis que a*a*a*a*a*a ou (a*a*a)*(a*a*a). Juste pour fournir quelques données, j'ai couru une petite expérience sur mon Mac Pro, en mesurant la pire erreur en évaluant un ^ 6 pour tous les nombres flottants à simple précision 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

En utilisant pow au lieu d'un arbre de multiplication réduit l'erreur liée à un facteur de 4. Les compilateurs ne devraient pas (et ne font généralement pas) des "optimisations" qui augmentent l'erreur à moins que l'utilisateur ne l'autorise à le faire (p. -ffast-math).

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


613
2018-06-22 22:39



Un autre cas similaire: la plupart des compilateurs n'optimiseront pas a + b + c + d à (a + b) + (c + d) (ceci est une optimisation puisque la deuxième expression peut être améliorée) et l'évaluer comme donné (c'est-à-dire 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));

Cela produit 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Fortran (conçu pour le calcul scientifique) a un opérateur de puissance intégré, et pour autant que je sache, les compilateurs Fortran optimiseront généralement l'augmentation des puissances entières d'une manière similaire à ce que vous décrivez. C / C ++ n'a malheureusement pas d'opérateur de puissance, seule la fonction de bibliothèque pow(). Cela n'empêche pas les compilateurs intelligents de traiter pow spécialement et en le calculant plus rapidement pour des cas particuliers, mais il semble qu'ils le font moins souvent ...

Il y a quelques années, j'essayais de rendre plus pratique le calcul optimal des puissances entières et j'ai trouvé ce qui suit. C'est C ++, et non C, et cela dépend toujours du fait que le compilateur soit un peu plus intelligent sur la façon d'optimiser / inline les choses. Quoi qu'il en soit, j'espère que vous trouverez cela utile en 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);
}

Clarification pour les curieux: cela ne trouve pas le moyen optimal de calculer les pouvoirs, mais depuis trouver la solution optimale est un problème NP-complet et cela vaut la peine de le faire pour les petites puissances de toute façon (par opposition à l'aide de pow), il n'y a aucune raison d'embêter les détails.

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

Cela permet de taper facilement des puissances (pas besoin d'épeler 6 as avec parens), et vous permet d'avoir ce genre d'optimisation sans -ffast-math dans le cas où vous avez quelque chose de dépendant de la précision sommation compensée (un exemple où l'ordre des opérations est essentiel).

Vous pouvez probablement aussi oublier que c'est du C ++ et juste l'utiliser dans le programme C (s'il compile avec un compilateur C ++).

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

MODIFIER:

C'est ce que je reçois 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 power<6>(a),

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

74
2018-06-23 10:07



Parce qu'un nombre à virgule flottante de 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 réalisent pas cela et croient également que * dans un * a représente la multiplication de nombres de précision arbitraires sans qu'il y ait d'erreurs attachées à ces nombres. La raison pour laquelle certaines personnes ne réalisent pas cela est peut-être les calculs mathématiques qu'ils ont pratiqués dans les écoles primaires: travailler uniquement avec des nombres idéaux sans erreurs, et croire qu'il est acceptable de simplement ignorer "e" tout en effectuant 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 peuvent exécuter) l'idée que C expression a * a * a * a * a * a ne fonctionne pas réellement avec des nombres idéaux, le compilateur GCC serait alors LIBRE pour optimiser "a * a * a * a * a * a "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. Et GCC ne fera que ce à quoi ressemble le code source - parce que c'est ce que GCC voit à l'œil nu.

... une fois que vous savez quel genre de programmeur toi sont, vous pouvez utiliser le commutateur "-fast-math" pour dire à GCC que "Hey, GCC, je sais ce que je fais!". Cela permettra à GCC de convertir un * a * a * a * a * a en un texte différent - il a l'air différent d'un * a * a * a * a * a - mais calcule toujours un nombre dans l'intervalle d'erreur de a * a * a * a * a * a. C'est OK, puisque vous savez déjà que vous travaillez avec des intervalles, pas des nombres idéaux.


49
2018-03-29 06:51



GCC optimise réellement un * a * a * a * a * a à (a * a * a) * (a * a * a) quand a est un nombre 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 signifient: Lire à partir de stdin; utiliser le niveau d'optimisation O2; liste des langages d'assemblage en 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 à stdout.

Voici la partie importante de la sortie. Je l'ai annoté avec quelques commentaires indiquant ce qui se passe dans la langue de l'assemblée:

    ; 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 sur 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 affiches 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.


49
2018-06-27 21:03



Aucune affiche n'a encore mentionné la contraction des expressions flottantes (norme ISO C, 6.5p8 et 7.12.2). Si la FP_CONTRACT pragma est configuré pour ON, le compilateur est autorisé à considérer une expression telle que a*a*a*a*a*a en une seule opération, comme si elle était évaluée exactement avec un seul arrondi. Par exemple, un compilateur peut le remplacer par une fonction de puissance 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 incorrectement.

L'état par défaut de la FP_CONTRACT pragma est défini par l'implémentation, de sorte qu'un compilateur est autorisé à effectuer de telles optimisations par défaut. Ainsi, un code portable qui doit suivre strictement les règles IEEE 754 doit explicitement OFF.

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

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


27
2018-06-23 12:44



Comme Lambdageek a souligné que la multiplication flottante n'est pas associative et que vous pouvez obtenir moins de précision, mais aussi quand vous obtenez une meilleure précision, vous pouvez argumenter contre l'optimisation, parce que vous voulez une application déterministe. Par exemple, dans la simulation de jeu client / serveur, où chaque client doit simuler le même monde, vous voulez que les calculs à virgule flottante soient déterministes.


26
2018-06-21 18:52



Je ne m'attendais pas à ce que ce cas soit optimisé. Cela ne peut pas être très fréquent lorsqu'une expression contient des sous-expressions qui peuvent ê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 qui seraient plus susceptibles d'entraîner des améliorations notables, plutôt que de couvrir un cas limite rarement rencontré.

J'ai été surpris d'apprendre des autres réponses que cette expression pourrait en effet être optimisée avec les bons commutateurs de compilation. Soit l'optimisation est triviale, soit c'est un cas marginal d'une optimisation beaucoup plus courante, ou les rédacteurs du compilateur étaient extrêmement minutieux.

Il n'y a rien de mal à fournir des indices au compilateur comme vous l'avez fait ici. C'est une partie normale et attendue du processus de micro-optimisation de réorganiser les expressions et expressions pour voir quelles différences elles apporteront.

Alors que le compilateur peut être justifié en considérant les deux expressions pour fournir des résultats incohérents (sans les commutateurs appropriés), vous n'avez pas besoin d'être lié par cette restriction. La différence sera incroyablement minime - si bien que si la différence vous importe, vous ne devriez pas utiliser l'arithmétique flottante standard en premier lieu.


26
2018-01-03 16:40



Les fonctions de bibliothèque telles que "pow" sont généralement soigneusement conçues pour produire l'erreur minimale possible (dans le cas générique). Ceci est généralement réalisé en approximant les fonctions avec des splines (selon le commentaire de Pascal, la mise en œuvre la plus courante semble utiliser Algorithme de Remez)

fondamentalement l'opération suivante:

pow(x,y);

a une erreur inhérente d'environ la même ampleur que l'erreur dans une multiplication ou division unique.

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 à plus de 5 fois l'erreur d'une seule multiplication ou division (parce que vous combinez 5 multiplications).

Le compilateur devrait être très attentif au type d'optimisation qu'il est en train de faire:

  1. si l'optimisation pow(a,6) à a*a*a*a*a*a il mai améliorez les performances, mais réduisez drastiquement la précision des nombres à virgule flottante.
  2. si l'optimisation a*a*a*a*a*a  à pow(a,6) il peut en fait réduire la précision 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 pow(a,6) à (a*a*a)*(a*a*a) ou (a*a)*(a*a)*(a*a) il peut encore y avoir une perte de précision par rapport à pow fonction.

En général, vous savez que pour des valeurs flottantes arbitraires, "pow" a une meilleure précision que n'importe quelle fonction que vous pourriez éventuellement écrire, mais dans certains cas particuliers, plusieurs multiplications peuvent avoir une meilleure précision et performance, c'est au développeur de choisir ce qui convient le mieux. finalement commentant le code afin que personne d'autre "optimise" ce code.

La seule chose qui a du sens (opinion personnelle, et apparemment un choix dans GCC sans optimisation ou compilateur particulier) à optimiser devrait remplacer "pow (a, 2)" par "a * a". Ce serait la seule chose sensée qu'un vendeur de compilateur devrait faire.


22
2017-10-01 19:33



Il y a déjà quelques bonnes réponses à cette question, mais pour être complet, je voulais souligner que la section applicable de la norme C est 5.1.2.2.3 / 15 (qui est la même que la section 1.9 / 9 de la Norme C ++ 11). Cette section stipule que les opérateurs ne peuvent être regroupés que s'ils sont réellement associatifs ou commutatifs.


19
2018-06-16 18:44