Vraag Waarom optimaliseert GCC een * a * a * a * a * a tot (a * a * a) * (a * a * a) niet?


Ik ben bezig met numerieke optimalisatie van een wetenschappelijke toepassing. Een ding dat me opviel, is dat GCC de oproep zal optimaliseren pow(a,2) door het te compileren a*a, maar de oproep pow(a,6) is niet geoptimaliseerd en zal eigenlijk de bibliotheekfunctie oproepen pow, wat de prestaties enorm vertraagt. (In tegenstelling tot, Intel C ++ Compiler, uitvoerbaar icc, zal de bibliotheekoproep elimineren pow(a,6).)

Waar ik nieuwsgierig naar ben is dat toen ik het verving pow(a,6) met a*a*a*a*a*a GCC 4.5.1 en opties gebruiken "-O3 -lm -funroll-loops -msse4", het gebruikt 5 mulsd instructies:

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

terwijl ik schrijf (a*a*a)*(a*a*a), het zal produceren

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

wat het aantal vermenigvuldigingsinstructies reduceert tot 3. icc heeft vergelijkbaar gedrag.

Waarom herkennen compilers deze optimalisatietruc niet?


1965
2018-06-21 18:49


oorsprong


antwoorden:


Omdat Floating Point Math is niet Associatief. De manier waarop u de operanden in zwevende puntvermenigvuldiging groepeert, heeft invloed op de numerieke nauwkeurigheid van het antwoord.

Dientengevolge zijn de meeste compilers heel conservatief over het opnieuw ordenen van drijvende-kommaberekeningen, tenzij ze er zeker van kunnen zijn dat het antwoord hetzelfde blijft, of tenzij je hen vertelt dat je niet om numerieke nauwkeurigheid geeft. Bijvoorbeeld: de -fassociative-math keuze van gcc waarmee gcc floating point-bewerkingen opnieuw kan toewijzen, of zelfs de -ffast-math optie die nog agressievere afwegingen van nauwkeurigheid tegen snelheid mogelijk maakt.


2565
2018-06-22 15:32



Lambdageek wijst er terecht op dat associativiteit niet geldt voor drijvende-kommagetallen, de "optimalisatie" van a*a*a*a*a*a naar (a*a*a)*(a*a*a) kan de waarde veranderen. Dit is waarom het niet is toegestaan ​​door C99 (tenzij specifiek toegestaan ​​door de gebruiker, via compilervlag of pragma). Over het algemeen is de veronderstelling dat de programmeur schreef wat ze deed met een reden, en de compiler zou dat moeten respecteren. Als je wil (a*a*a)*(a*a*a), schrijf dat.

Dat kan echter lastig zijn om te schrijven; waarom kan de compiler niet gewoon [wat jij als correct beschouwt] het juiste doen als je het gebruikt pow(a,6)? Omdat het de. Zou zijn fout ding om te doen. Op een platform met een goede wiskundebibliotheek, pow(a,6) is aanzienlijk nauwkeuriger dan beide a*a*a*a*a*a of (a*a*a)*(a*a*a). Om wat gegevens aan te leveren, heb ik een klein experiment op mijn Mac Pro uitgevoerd, waarbij de slechtste fout werd gemeten bij de evaluatie van een ^ 6 voor alle drijvende getallen met enkele precisie tussen [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

Gebruik makend van pow in plaats van een vermenigvuldigingsboom vermindert de fout gebonden door a factor van 4. Compilers mogen (en maken in het algemeen) geen "optimalisaties" uit die de fouten vergroten, tenzij ze daarvoor toestemming hebben gekregen van de gebruiker (bijvoorbeeld via -ffast-math).

Merk op dat GCC biedt __builtin_powi(x,n) als een alternatief voor pow( ), die een inline-vermenigvuldigingsboom zou moeten genereren. Gebruik dat als je nauwkeurigheid wilt inruilen voor prestaties, maar geen snelle wiskunde wilt inschakelen.


613
2018-06-22 22:39



Een ander soortgelijk geval: de meeste compilers zullen niet optimaliseren a + b + c + d naar (a + b) + (c + d) (dit is een optimalisatie aangezien de tweede expressie beter kan worden gepijplijnd) en het als gegeven (d.w.z. (((a + b) + c) + d)). Dit is ook vanwege hoekgevallen:

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

Dit levert op 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Fortran (ontworpen voor wetenschappelijk computergebruik) heeft een ingebouwde krachtbron en voor zover ik weet zullen Fortran-samenstellers gewoonlijk het verhogen van de integer-krachten op dezelfde manier optimaliseren als wat u beschrijft. C / C ++ hebben helaas geen stroomvoorziening, alleen de bibliotheekfunctie pow(). Dit voorkomt niet dat slimme compilers kunnen worden behandeld pow speciaal en bereken het op een snellere manier voor speciale gevallen, maar het lijkt erop dat ze het minder vaak doen ...

Een paar jaar geleden probeerde ik het handiger te maken om integer bevoegdheden op een optimale manier te berekenen, en kwam met het volgende. Het is echter C ++, niet C, en het hangt er nog steeds van af of de compiler enigszins slim is over het optimaliseren / inline dingen. Hoe dan ook, ik hoop dat je het in de praktijk misschien handig vindt:

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);
}

Verduidelijking voor nieuwsgierigen: dit vindt niet de optimale manier om vermogens te berekenen, maar sindsdien het vinden van de optimale oplossing is een NP-compleet probleem en dit is sowieso alleen de moeite waard om te doen voor kleine vermogens (in tegenstelling tot gebruiken pow), er is geen reden om gedoe met de details.

Gebruik het dan gewoon als power<6>(a).

Dit maakt het gemakkelijk om krachten te typen (het is niet nodig om 6 te spellen) as met parens), en laat je dit soort optimalisatie zonder hebben -ffast-math voor het geval dat u iets afhankelijk van de precisie zoals gecompenseerde sommatie (een voorbeeld waarbij de volgorde van bewerkingen essentieel is).

Je kunt waarschijnlijk ook vergeten dat dit C ++ is en gebruik het alleen in het C-programma (als het compileert met een C ++ -compiler).

Ik hoop dat dit nuttig kan zijn.

BEWERK:

Dit is wat ik krijg van mijn compiler:

Voor a*a*a*a*a*a,

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

Voor (a*a*a)*(a*a*a),

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

Voor power<6>(a),

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

74
2018-06-23 10:07



Omdat een 32-bits drijvende-kommagetal - zoals 1.024 - niet 1.024 is. Op een computer is 1.024 een interval: van (1.024-e) tot (1.024 + e), waarbij "e" een fout vertegenwoordigt. Sommige mensen realiseren zich dit niet en geloven ook dat * in a * a staat voor vermenigvuldiging van willekeurige precisienummers zonder dat er fouten aan die getallen zijn gekoppeld. De reden waarom sommige mensen dit niet realiseren is misschien wel de wiskundige berekening die ze op basisscholen uitvoerden: alleen werken met ideale getallen zonder toegevoegde fouten, en geloven dat het OK is om "e" simpelweg te negeren tijdens het uitvoeren van vermenigvuldiging. Ze zien de "e" niet impliciet in "float a = 1.2", "a * a * a" en vergelijkbare C-codes.

Als de meerderheid van de programmeurs het idee erkent (en kan uitvoeren) dat C-expressie a * a * a * a * a * a niet echt met ideale getallen werkt, is de GCC-compiler dan GRATIS om te optimaliseren "a * a * a * a * a * a "zeggen" t = (a * a); t * t * t "waarvoor een kleiner aantal vermenigvuldigingen vereist is. Maar helaas weet de GCC-compiler niet of de programmeur die de code schrijft denkt dat "a" een getal is met of zonder een fout. En dus doet GCC alleen hoe de broncode eruit ziet - want dat is wat GCC met zijn "blote oog" ziet.

... als je eenmaal weet wat voor soort programmeur u zijn, je kunt de "-fas-math" -knop gebruiken om GCC te vertellen dat "Hé, GCC, ik weet wat ik aan het doen ben!". Hierdoor kan GCC een * a * a * a * a * a omzetten in een ander stuk tekst - het ziet er anders uit dan een * a * a * a * a * a - maar wordt nog steeds een getal berekend binnen het foutinterval van a * a * a * a * a * a. Dit is OK, omdat je al weet dat je met intervallen werkt, geen ideale cijfers.


49
2018-03-29 06:51



GCC optimaliseert in feite a * a * a * a * a * a tot (a * a * a) * (a * a * a) wanneer a een geheel getal is. Ik heb geprobeerd met dit commando:

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

Er zijn veel gcc-vlaggen maar niets bijzonders. Ze bedoelen: lezen van stdin; gebruik O2-optimalisatieniveau; output assembly language listing in plaats van een binary; de lijst moet de syntaxis van Intel assembly language gebruiken; de invoer is in C-taal (meestal wordt de taal afgeleid van de extensie van het invoerbestand, maar er is geen bestandsextensie bij het lezen van stdin); en schrijf naar stdout.

Dit is het belangrijkste deel van de uitvoer. Ik heb het geannoteerd met enkele opmerkingen die aangeven wat er in de assembleertaal aan de hand is:

    ; 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

Ik gebruik systeem GCC op Linux Mint 16 Petra, een Ubuntu-derivaat. Hier is de gcc-versie:

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

Zoals andere posters hebben opgemerkt, is deze optie niet mogelijk in drijvende komma, omdat drijvende-komma-aritmetiek eigenlijk niet associatief is.


49
2018-06-27 21:03



Er zijn nog geen posters die de samentrekking van zwevende expressies hebben genoemd (ISO C-standaard, 6.5p8 en 7.12.2). Als het FP_CONTRACT pragma is ingesteld op ON, de compiler mag een uitdrukking zoals beschouwen a*a*a*a*a*a als een enkele bewerking, alsof deze exact met een enkele afronding werd geëvalueerd. Een compiler kan deze bijvoorbeeld vervangen door een interne stroomfunctie die zowel sneller als nauwkeuriger is. Dit is met name interessant omdat het gedrag gedeeltelijk door de programmeur rechtstreeks in de broncode wordt geregeld, terwijl de door de eindgebruiker aangeboden compileeropties soms soms verkeerd worden gebruikt.

De standaardstatus van de FP_CONTRACT pragma is door de implementatie gedefinieerd, zodat een compiler standaard dergelijke optimalisaties mag uitvoeren. Dus draagbare code die strikt de IEEE 754 regels moet volgen, moet dit expliciet instellen OFF.

Als een compiler dit pragma niet ondersteunt, moet deze conservatief zijn door een dergelijke optimalisatie te vermijden, in het geval de ontwikkelaar ervoor heeft gekozen deze OFF.

GCC ondersteunt dit pragma niet, maar met de standaardopties gaat dit ervan uit ON; dus voor doelen met een hardware FMA, als men de transformatie wil voorkomen a*b+c tot fma (a, b, c) moet een optie zoals -ffp-contract=off (om het pragma expliciet in te stellen OFF) of -std=c99 (om GCC te vertellen dat het voldoet aan een C-standaardversie, hier C99, volg dus de bovenstaande paragraaf). In het verleden was de laatste optie niet om de transformatie te voorkomen, wat betekent dat GCC op dit punt niet conformeerde: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44



Zoals Lambdageek opmerkte dat float-vermenigvuldiging niet associatief is en je minder nauwkeurigheid kunt krijgen, maar ook wanneer je een betere nauwkeurigheid krijgt, kun je argumenteren tegen optimalisatie, omdat je een deterministische toepassing wilt. Bijvoorbeeld in een game-simulatieclient / server, waarbij elke client dezelfde wereld moet simuleren, dan wilt u dat drijvende-kommaberekeningen deterministisch zijn.


26
2018-06-21 18:52