Pourquoi GCC n'optimise-t-il pas a*a*a*a*a*a*a en (a*a*a)*(a*a*a) ?

Question

Je fais de l'optimisation numérique sur une application scientifique. Une chose que j'ai remarquée est que GCC optimise l'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 la bibliothèque pow ce qui ralentit considérablement les performances. (En revanche, Compilateur Intel C++ , exécutable icc éliminera l'appel à la bibliothèque pour pow(a,6) .)

Ce qui m'intrigue, c'est que lorsque j'ai remplacé pow(a,6) con a*a*a*a*a*a en utilisant GCC 4.5.1 et les options " -O3 -lm -funroll-loops -msse4 ", il utilise 5 mulsd des 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) il 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 ?

Answer 1

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

Par conséquent, la plupart des compilateurs sont très prudents lorsqu'il s'agit de réorganiser des calculs en virgule flottante, sauf s'ils sont sûrs que la réponse restera la même ou si vous leur dites que vous ne vous souciez pas de la précision numérique. Par exemple : le site -fassociative-math option de gcc qui permet à gcc de réassocier les opérations en virgule flottante, ou encore la fonction -ffast-math qui permet des compromis encore plus agressifs entre la précision et la vitesse.

Answer 2

Lambdageek souligne à juste titre qu'étant donné que l'associativité n'est pas valable pour les nombres à virgule flottante, l'"optimisation" de l'option a*a*a*a*a*a a (a*a*a)*(a*a*a) peut modifier la valeur. C'est pourquoi il est interdit par C99 (sauf si l'utilisateur l'autorise spécifiquement, via un drapeau de compilation ou un pragma). En général, l'hypothèse est que le programmeur a écrit ce qu'il a fait pour une raison, et le compilateur devrait respecter cela. Si vous voulez (a*a*a)*(a*a*a) écrivez cela.

Mais cela peut être pénible à écrire ; pourquoi le compilateur ne peut-il pas simplement faire [ce que vous considérez comme] la bonne chose quand vous utilisez pow(a,6) ? Parce que ce serait le mauvais à faire. Sur une plate-forme avec une bonne bibliothèque de mathématiques, pow(a,6) est significativement plus précis que l'un ou l'autre a*a*a*a*a*a o (a*a*a)*(a*a*a) . Juste pour fournir quelques données, j'ai fait une petite expérience sur mon Mac Pro, en mesurant la pire erreur dans l'évaluation de a^6 pour tous les nombres flottants de 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

Utilisation de pow au lieu d'un arbre de multiplication réduit la limite d'erreur d'une facteur 4 . Les compilateurs ne devraient pas (et ne le font généralement pas) faire des "optimisations" qui augmentent le taux d'erreur, à moins que l'utilisateur n'y soit autorisé par l'utilisateur (par exemple, par l'intermédiaire de -ffast-math ).

Notez que GCC fournit __builtin_powi(x,n) comme alternative à pow( ) qui devrait générer un arbre de multiplication en ligne. Utilisez cette méthode si vous voulez sacrifier la précision aux performances, mais que vous ne voulez pas activer fast-math.

Answer 3

Un autre cas similaire : la plupart des compilateurs n'optimisent pas a + b + c + d a (a + b) + (c + d) (il s'agit d'une optimisation puisque la deuxième expression peut être mieux pipelinée) et l'évaluer comme indiqué (c'est-à-dire comme (((a + b) + c) + d) ). Cela aussi est dû à des cas particuliers :

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

Ces sorties 1.000000e-05 0.000000e+00

Answer 4

Fortran (conçu pour le calcul scientifique) possède un opérateur de puissance intégré et, pour autant que je sache, les compilateurs Fortran optimisent généralement l'élévation à la puissance des entiers d'une manière similaire à celle que vous décrivez. Malheureusement, le C/C++ ne dispose pas d'opérateur de puissance, mais seulement de la fonction de bibliothèque pow() . Cela n'empêche pas des compilateurs intelligents de traiter pow spécialement et le calculer de manière plus rapide pour des cas particuliers, mais il semble qu'ils le fassent moins souvent ...

Il y a quelques années, j'ai essayé de rendre plus pratique le calcul des puissances d'entiers de manière optimale, et j'ai trouvé ce qui suit. C'est du C++, pas du C cependant, et cela dépend toujours de l'intelligence du compilateur quant à l'optimisation/inline des choses. Quoi qu'il en soit, j'espère que vous le trouverez 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);
}

_{<strong>Clarification pour les curieux : </strong>cela ne permet pas de trouver la manière optimale de calculer les puissances, mais puisque <a href="http://en.wikipedia.org/wiki/Addition-chain_exponentiation">trouver la solution optimale est un problème NP-complet </a>et cela ne vaut la peine d'être fait que pour les petites puissances de toute façon (contrairement à l'utilisation des <code>pow</code> ), il n'y a aucune raison de s'attarder sur les détails.}

Ensuite, il suffit de l'utiliser comme power<6>(a) .

Cela permet de taper facilement les pouvoirs (pas besoin d'épeler 6 a avec des parenthèses), et vous permet d'avoir ce type d'optimisation sans -ffast-math au cas où vous auriez quelque chose qui dépende de la précision, comme sommation compensée (un exemple où l'ordre des opérations est essentiel).

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

J'espère que cela pourra vous être utile.

EDITAR:

Voici ce que j'obtiens de mon compilateur :

Para a*a*a*a*a*a ,

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

Para (a*a*a)*(a*a*a) ,

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

Para power<6>(a) ,

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

Answer 5

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 s'en rendent pas compte et croient également que * dans a*a représente la multiplication de nombres de précision arbitraire sans qu'il y ait d'erreurs liées à ces nombres. La raison pour laquelle certaines personnes ne s'en rendent pas compte est peut-être liée aux calculs mathématiques qu'elles ont effectués à l'école primaire : elles ne travaillent qu'avec des nombres idéaux sans erreur et croient qu'il est normal d'ignorer simplement "e" lors d'une multiplication. Ils ne voient pas le "e" implicite dans "float a=1.2", "a*a*a" et autres codes C similaires.

Si la majorité des programmeurs reconnaissaient (et étaient capables d'exécuter) l'idée que l'expression C a*a*a*a*a*a*a ne fonctionne pas réellement avec des nombres idéaux, le compilateur GCC serait alors LIBRE d'optimiser "a*a*a*a*a*a" en disant "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 donc GCC ne fera que ce à quoi le code source ressemble - parce que c'est ce que GCC voit avec son "œil nu".

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