Dlaczego GCC nie optymalizuje * a * a * a * a * a do (a * a * a) * (a * a * a)?

2120

Robię optymalizację numeryczną w aplikacji naukowej. Zauważyłem tylko, że GCC zoptymalizuje wywołanie pow(a,2), kompilując je a*a, ale wywołanie pow(a,6)nie jest zoptymalizowane i faktycznie wywoła funkcję biblioteki pow, co znacznie spowalnia działanie. (Natomiast kompilator Intel C ++ , wykonywalny icc, wyeliminuje wywołanie biblioteki pow(a,6)).

Jestem ciekaw co o to, że kiedy otrzymuje pow(a,6)z a*a*a*a*a*aużyciem GCC 4.5.1 i opcje „ -O3 -lm -funroll-loops -msse4”, używa 5 mulsdwskazówek:

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

podczas gdy jeśli napiszę (a*a*a)*(a*a*a), będzie produkować

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

co zmniejsza liczbę instrukcji mnożenia do 3. iccma podobne zachowanie.

Dlaczego kompilatory nie rozpoznają tej sztuczki optymalizacji?

xis
źródło
13
Co oznacza „rozpoznawanie pow (a, 6)”?
Varun Madiath
659
Um ... wiesz, że a a a a a a (a a a) * (a a * a) nie są takie same z liczbami zmiennoprzecinkowymi, prawda? Będziesz musiał użyć -funsafe-matematyki lub -ffast-matematyki lub czegoś takiego.
Damon
106
Sugeruję przeczytanie „Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej” Davida Goldberga: download.oracle.com/docs/cd/E19957-01/806-3568/…, po którym uzyskasz pełniejsze zrozumienie smoła, do której właśnie wszedłeś!
Phil Armstrong,
189
Zupełnie rozsądne pytanie. 20 lat temu zadałem to samo ogólne pytanie, a poprzez zmiażdżenie tego pojedynczego wąskiego gardła skróciłem czas wykonania symulacji Monte Carlo z 21 godzin do 7 godzin. Kod w wewnętrznej pętli został w tym czasie wykonany 13 trylionów razy, ale dostał symulację do okna na noc. (patrz odpowiedź poniżej)
23
Może też wrzucić (a*a)*(a*a)*(a*a)do miksu. Taka sama liczba mnożeń, ale prawdopodobnie dokładniejsza.
Rok Kralj

Odpowiedzi:

2738

Ponieważ matematyka zmiennoprzecinkowa nie jest asocjacyjna . Sposób grupowania operandów w mnożeniu zmiennoprzecinkowym ma wpływ na dokładność liczbową odpowiedzi.

W rezultacie większość kompilatorów jest bardzo konserwatywnych w kwestii zmiany kolejności obliczeń zmiennoprzecinkowych, chyba że mogą być pewni, że odpowiedź pozostanie taka sama lub jeśli nie powiesz im, że nie zależy ci na dokładności liczbowej. Na przykład: opcja gcc gcc, który pozwala na ponowne skojarzenie operacji zmiennoprzecinkowych, a nawet opcja, która pozwala jeszcze bardziej agresywny kompromisów dokładności wobec prędkości.-fassociative-math-ffast-math

Lambdageek
źródło
10
Tak. W przypadku -ffast-matematyki dokonuje takiej optymalizacji. Dobry pomysł! Ale ponieważ nasz kod dotyczy większej dokładności niż prędkości, lepiej nie przekazywać go.
x jest
19
IIRC C99 pozwala kompilatorowi na takie „niebezpieczne” optymalizacje FP, ale GCC (na czymkolwiek innym niż x87) podejmuje rozsądną próbę podążania za IEEE 754 - to nie jest „błąd graniczny”; jest tylko jedna poprawna odpowiedź .
tc.
14
Szczegóły implementacji pownie są ani tu, ani tam; ta odpowiedź nawet nie ma odniesienia pow.
Stephen Canon
14
@nedR: Domyślnie ICC zezwala na ponowne powiązanie. Jeśli chcesz uzyskać zachowanie zgodne ze standardami, musisz ustawić za -fp-model precisepomocą ICC. clangi gccdomyślnie przywiązanie do ścisłej zgodności.
Stephen Canon
49
@ xis, to nie jest tak naprawdę -fassociative-mathniedokładne; to tylko to a*a*a*a*a*ai (a*a*a)*(a*a*a)są różne. Tu nie chodzi o dokładność; chodzi o zgodność ze standardami i ściśle powtarzalne wyniki, np. takie same wyniki na dowolnym kompilatorze. Liczby zmiennoprzecinkowe nie są już dokładne. Kompilacja rzadko jest nieodpowiednia -fassociative-math.
Paul Draper
652

Lambdageek słusznie zauważa, że ponieważ asocjatywność nie trzymać dla liczb zmiennoprzecinkowych, „Optymalizacja” oda*a*a*a*a*ado(a*a*a)*(a*a*a)może zmienić wartość. Dlatego jest niedozwolony przez C99 (chyba że użytkownik wyraźnie na to zezwolił, poprzez flagę kompilatora lub pragma). Ogólnie zakłada się, że programista napisał to, co zrobiła bez powodu, i kompilator powinien to uszanować. Jeśli chcesz(a*a*a)*(a*a*a), napisz to.

Może to jednak być trudny do napisania; dlaczego kompilator nie może po prostu zrobić tego, co uważasz za właściwe pow(a,6)? Ponieważ byłoby to niewłaściwe . Na platformie z dobrą biblioteką matematyczną pow(a,6)jest znacznie bardziej dokładny niż jeden a*a*a*a*a*alub (a*a*a)*(a*a*a). Aby dostarczyć trochę danych, przeprowadziłem mały eksperyment na moim Macu Pro, mierząc najgorszy błąd w ocenie ^ 6 dla wszystkich liczb zmiennoprzecinkowych pojedynczej precyzji między [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

Użycie powzamiast drzewa mnożenia zmniejsza błąd związany czterokrotnie . Kompilatory nie powinny (i generalnie nie robią) „optymalizacji”, które zwiększają błąd, chyba że użytkownik na to zezwoli (np. Via -ffast-math).

Zauważ, że GCC stanowi __builtin_powi(x,n)alternatywę dla pow( ), która powinna wygenerować wbudowane drzewo mnożenia. Użyj tego, jeśli chcesz obniżyć dokładność pod względem wydajności, ale nie chcesz włączać szybkiej matematyki.

Stephen Canon
źródło
29
Zauważ też, że Visual C ++ zapewnia „ulepszoną” wersję pow (). Dzwoniąc _set_SSE2_enable(<flag>)z flag=1, użyje SSE2, jeśli to możliwe. To zmniejsza nieco dokładność, ale poprawia prędkość (w niektórych przypadkach). MSDN: _set_SSE2_enable () i pow ()
TkTech
18
@TkTech: Każda zmniejszona dokładność wynika z implementacji Microsoftu, a nie z wielkości używanych rejestrów. Możliwe jest dostarczenie poprawnie zaokrąglonego pow rejestru przy użyciu tylko 32-bitowych rejestrów, jeśli program piszący biblioteki jest tak zmotywowany. Istnieją powimplementacje oparte na SSE, które są więcej dokładne niż większość wdrożeń opartych na x87, a istnieją również implementacje że kompromis jakiegoś dokładności prędkości.
Stephen Canon
9
@TkTech: Oczywiście, chciałem tylko wyjaśnić, że zmniejszenie dokładności wynika z wyborów dokonanych przez autorów bibliotek, a nie jest nierozerwalnie związane z używaniem SSE.
Stephen Canon
7
Interesuje mnie to, co wykorzystałeś jako „złoty standard” tutaj do obliczania błędów względnych - normalnie spodziewałbym się, że tak będzie a*a*a*a*a*a, ale najwyraźniej tak nie jest! :)
j_random_hacker
8
@j_random_hacker: odkąd został porównywaniu wyników pojedynczej precyzji, podwójnej precyzji wystarczy do standardu złota - błąd z punktu A obliczony w podwójne * jest znacznie mniejszy niż błąd któregoś z obliczeń pojedynczej precyzji.
Stephen Canon
168

Inny podobny przypadek: większość kompilatory nie będzie optymalizować a + b + c + ddo (a + b) + (c + d)(jest to optymalizacja ponieważ drugi wyrażenie może być lepiej potokowym) i ocenia je jako dane (tj (((a + b) + c) + d)). Jest to również spowodowane przypadkami narożnymi:

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

To wychodzi 1.000000e-05 0.000000e+00

sanjoyd
źródło
10
To nie jest dokładnie to samo. Zmiana kolejności mnożenia / dzielenia (z wyłączeniem dzielenia przez 0) jest bezpieczniejsza niż zmiana kolejności sumowania / odejmowania. Moim skromnym zdaniem kompilator powinien spróbować skojarzyć mults./divs. ponieważ w ten sposób zmniejsza się łączna liczba operacji, a oprócz zwiększenia wydajności jest także zwiększenie precyzji.
CoffeDeveloper
4
@DarioOO: Nie jest bezpieczniej. Mnożenie i dzielenie są takie same jak dodawanie i odejmowanie wykładnika potęgi, a zmiana kolejności może łatwo spowodować, że tymczasowe wartości przekroczą możliwy zakres wykładnika potęgi. (Niezupełnie to samo, ponieważ wykładnik nie cierpi na utratę precyzji ... ale reprezentacja jest nadal dość ograniczona, a zmiana kolejności może prowadzić do niereprezentatywnych wartości)
Ben Voigt
8
Myślę, że brakuje ci rachunku różniczkowego. Mnożenie i dzielenie 2 liczb wprowadza tę samą ilość błędów. Podczas gdy odejmowanie / dodawanie 2 liczb może wprowadzać większy błąd, szczególnie gdy 2 liczby są różne o rząd wielkości, dlatego bezpieczniej jest ponownie rozmieścić mul / podzielić niż sub / dodać, ponieważ wprowadza niewielką zmianę w błędzie końcowym.
CoffeDeveloper
8
@DarioOO: ryzyko jest inne w przypadku mul / div: zmiana kolejności albo powoduje nieznaczną zmianę wyniku końcowego, albo wykładnik przepełnia się w pewnym momencie (w którym wcześniej by tego nie zrobił), a wynik jest zupełnie inny (potencjalnie + inf lub 0).
Peter Cordes
@GameDeveloper Narzucenie przyrostu precyzji w nieprzewidywalny sposób jest niezwykle problematyczne.
ciekawy
80

Fortran (zaprojektowany do obliczeń naukowych) ma wbudowany operator mocy i, o ile wiem, kompilatory Fortran zwykle optymalizują podnoszenie do mocy całkowitych w podobny sposób, jak to opisujesz. C / C ++ niestety nie ma operatora mocy, tylko funkcję biblioteki pow(). Nie uniemożliwia to inteligentnym kompilatorom powspecjalnego traktowania i obliczania go szybciej w szczególnych przypadkach, ale wygląda na to, że robią to rzadziej ...

Kilka lat temu próbowałem uczynić wygodniejszym obliczanie mocy całkowitych w optymalny sposób i wymyśliłem następujące. Jest to C ++, a nie C, i nadal zależy od tego, czy kompilator jest dość inteligentny w zakresie optymalizacji / wstawiania rzeczy. W każdym razie, mam nadzieję, że okaże się przydatny w praktyce:

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

Wyjaśnienie dla ciekawskich: nie znajduje to optymalnego sposobu obliczania mocy, ale ponieważ znalezienie optymalnego rozwiązania jest problemem NP-zupełnym i warto to robić tylko dla małych mocy (w przeciwieństwie do używania pow), nie ma powodu do zamieszania ze szczegółami.

Następnie użyj go jako power<6>(a).

Ułatwia to wpisywanie mocy (nie trzeba przeliterować 6 as za pomocą parens) i pozwala na tego rodzaju optymalizację bez -ffast-mathprzypadku, gdy masz coś zależnego od precyzji, np. Sumowanie skompensowane (przykład, w którym niezbędna jest kolejność operacji) .

Prawdopodobnie możesz również zapomnieć, że jest to C ++ i po prostu użyć go w programie C (jeśli kompiluje się z kompilatorem C ++).

Mam nadzieję, że to może być przydatne.

EDYTOWAĆ:

Oto, co otrzymuję od mojego kompilatora:

dla a*a*a*a*a*a,

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

dla (a*a*a)*(a*a*a),

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

dla power<6>(a),

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
Szabolcs
źródło
36
Znalezienie optymalnego drzewa mocy może być trudne, ale ponieważ jest interesujące tylko dla małych mocy, oczywistą odpowiedzią jest wstępne obliczenie go raz (Knuth zapewnia tabelę do 100) i użycie tej tabeli (to jest to, co gcc robi wewnętrznie dla powi) .
Marc Glisse,
7
W nowoczesnych procesorach prędkość jest ograniczona opóźnieniem. Na przykład wynik mnożenia może być dostępny po pięciu cyklach. W takiej sytuacji znalezienie najszybszego sposobu na wytworzenie mocy może być trudniejsze.
gnasher729
3
Możesz także spróbować znaleźć drzewo mocy, które daje najniższą górną granicę względnego błędu zaokrąglenia lub najniższy średni względny błąd zaokrąglenia.
gnasher729
1
Boost ma również na to wsparcie, np. Boost :: math :: pow <6> (n); Myślę, że nawet próbuje zmniejszyć liczbę mnożenia poprzez wyodrębnienie wspólnych czynników.
gast128
Zauważ, że ostatni jest równoważny (a ** 2) ** 3
minmaxavg
62

GCC jest rzeczywiście zoptymalizować a*a*a*a*a*ado (a*a*a)*(a*a*a)kiedy jest liczbą całkowitą. Próbowałem z tym poleceniem:

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

Istnieje wiele flag gcc, ale nic szczególnego. Oni mają na myśli: Czytaj ze standardowego; użyj poziomu optymalizacji O2; wypisuje listę języka asemblera zamiast pliku binarnego; lista powinna używać składni języka asemblera Intel; wejście jest w języku C (zwykle język wywodzi się z rozszerzenia pliku wejściowego, ale nie ma rozszerzenia pliku podczas odczytu ze standardowego wejścia); i napisz na standardowe wyjście.

Oto ważna część wyników. Zanotowałem to z kilkoma komentarzami wskazującymi, co się dzieje w języku asemblera:

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

Korzystam z systemu GCC na Linux Mint 16 Petra, pochodnej Ubuntu. Oto wersja gcc:

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

Jak zauważyli inni plakaty, ta opcja nie jest możliwa w liczbach zmiennoprzecinkowych, ponieważ arytmetyka zmiennoprzecinkowa nie jest asocjacyjna.

pikomancer
źródło
12
Jest to legalne w przypadku mnożenia liczb całkowitych, ponieważ przepełnienie uzupełnienia do dwóch jest zachowaniem niezdefiniowanym. Jeśli nastąpi przepełnienie, nastąpi to gdzieś, niezależnie od operacji zmiany kolejności. Tak więc wyrażenia bez przepełnienia oceniają to samo, wyrażenia przepełnienia są niezdefiniowanym zachowaniem, więc kompilator może zmienić punkt, w którym nastąpi przepełnienie. gcc też to robi unsigned int.
Peter Cordes
51

Ponieważ 32-bitowa liczba zmiennoprzecinkowa - taka jak 1.024 - nie jest równa 1.024. W komputerze 1.024 to przedział: od (1.024-e) do (1.024 + e), gdzie „e” oznacza błąd. Niektórzy ludzie nie zdają sobie z tego sprawy i wierzą również, że * w * a oznacza pomnożenie liczb o dowolnej dokładności bez żadnych błędów związanych z tymi liczbami. Powodem, dla którego niektórzy nie zdają sobie z tego sprawy, są być może obliczenia matematyczne, które wykonywali w szkołach podstawowych: praca tylko z idealnymi liczbami bez błędów i przekonanie, że po prostu pomiń „e” podczas mnożenia. Nie widzą „e” domyślnie w „float a = 1.2”, „a * a * a” i podobnych kodach C.

Gdyby większość programistów rozpoznała (i była w stanie wykonać) koncepcję, że wyrażenie C a * a * a * a * a * a tak naprawdę nie działa z liczbami idealnymi, kompilator GCC byłby WOLNY w celu optymalizacji „a * a” * a * a * a * a „powiedzieć” t = (a * a); t * t * t ”, co wymaga mniejszej liczby mnożenia. Niestety kompilator GCC nie wie, czy programista piszący kod uważa, że ​​„a” jest liczbą z błędem, czy bez. I tak GCC zrobi tylko to, jak wygląda kod źródłowy - ponieważ tak widzi GCC „gołym okiem”.

... kiedy już wiesz, jakim jesteś programistą , możesz użyć przełącznika „-ffast-matematyki”, aby powiedzieć GCC, że „Hej, GCC, wiem, co robię!”. Umożliwi to GCC konwersję * a * a * a * a * a na inny fragment tekstu - wygląda inaczej niż * a * a * a * a * a - ale nadal oblicza liczbę w przedziale błędu a * a * a * a * a * a. Jest to w porządku, ponieważ już wiesz, że pracujesz w interwałach, a nie w liczbach idealnych.


źródło
52
Liczby zmiennoprzecinkowe są dokładne. Po prostu niekoniecznie są dokładnie takie, jak się spodziewałeś. Co więcej, technika z epsilon sama w sobie jest przybliżeniem tego, jak radzić sobie w rzeczywistości, ponieważ prawdziwy oczekiwany błąd jest związany ze skalą mantysy, tj. Zwykle masz do około 1 LSB na zewnątrz, ale to może wzrosnąć z każda operacja wykonywana, jeśli nie jesteś ostrożny, więc skonsultuj się z analitykiem numerycznym, zanim wykonasz cokolwiek innego niż trywialne z użyciem zmiennoprzecinkowego. Użyj odpowiedniej biblioteki, jeśli to możliwe.
Donal Fellows
3
@DonalFellows: Standard IEEE wymaga, aby obliczenia zmiennoprzecinkowe dawały wynik, który najbardziej dokładnie odpowiada temu, jaki byłby wynik, gdyby operandy źródłowe były dokładnymi wartościami, ale to nie znaczy, że faktycznie reprezentują dokładne wartości. W wielu przypadkach bardziej pomocne jest uznanie 0,1f za (1 677 722 +/- 0,5) / 16 777 216, które powinno być wyświetlane z liczbą cyfr dziesiętnych implikowanych przez tę niepewność, niż uznanie jej za dokładną liczbę (1 677 722 +/- 0,5) / 16,777,216 (które powinny być wyświetlane z dokładnością do 24 cyfr dziesiętnych).
supercat
23
@supercat: IEEE-754 jest całkiem jasne, że na punkcie danych zmiennoprzecinkowych zrobić stanowią dokładne wartości; punkty 3.2–3.4 są odpowiednimi sekcjami. Możesz oczywiście wybrać ich interpretację w inny sposób, tak jak możesz interpretować int x = 3jako oznaczające, że x3 +/- 0,5.
Stephen Canon
7
@ superupat: Całkowicie się zgadzam, ale to nie znaczy, że Distancenie jest dokładnie równa wartości liczbowej; oznacza to, że wartość liczbowa jest jedynie przybliżeniem pewnej modelowanej wielkości fizycznej.
Stephen Canon
10
W przypadku analizy numerycznej twój mózg będzie ci wdzięczny, jeśli interpretujesz liczby zmiennoprzecinkowe nie jako przedziały, ale jako dokładne wartości (które nie są dokładnie tymi, których chciałeś). Na przykład, jeśli x jest gdzieś około 4,5 z błędem mniejszym niż 0,1, a obliczasz (x + 1) - x, interpretacja „interwału” pozostawia ci interwał od 0,8 do 1,2, podczas gdy interpretacja „dokładnej wartości” mówi wynikiem będzie 1 z błędem co najwyżej 2 ^ (- 50) w podwójnej precyzji.
gnasher729
34

Żaden plakat nie wspomniał jeszcze o skracaniu wyrażeń zmiennoprzecinkowych (norma ISO C, 6.5p8 i 7.12.2). Jeśli FP_CONTRACTpragma jest ustawiona na ON, kompilator może traktować wyrażenie takie jak a*a*a*a*a*apojedyncza operacja, tak jakby zostało ocenione dokładnie za pomocą pojedynczego zaokrąglenia. Na przykład kompilator może zastąpić go wewnętrzną funkcją zasilania, która jest zarówno szybsza, jak i dokładniejsza. Jest to szczególnie interesujące, ponieważ zachowanie jest częściowo kontrolowane przez programistę bezpośrednio w kodzie źródłowym, podczas gdy opcje kompilatora dostarczone przez użytkownika końcowego mogą czasami być używane nieprawidłowo.

Domyślny stan FP_CONTRACTpragmy jest zdefiniowany w implementacji, dzięki czemu kompilator może domyślnie wykonywać takie optymalizacje. W związku z tym kod przenośny, który musi ściśle przestrzegać reguł IEEE 754, powinien wyraźnie to ustawić OFF.

Jeśli kompilator nie obsługuje tej pragmy, musi być konserwatywny, unikając takiej optymalizacji, na wypadek, gdyby programista zdecydował się ją ustawić OFF.

GCC nie obsługuje tej pragmy, ale przy domyślnych opcjach zakłada, że ​​tak jest ON; tak więc dla celów ze sprzętową FMA, jeśli chce się zapobiec transformacji a*b+cdo fma (a, b, c), należy zapewnić opcję, taką jak -ffp-contract=off(jawnie ustawić pragmę OFF) lub -std=c99(poinformować GCC, aby dostosowała się do niektórych Wersja standardowa C, tutaj C99, dlatego należy postępować zgodnie z powyższym akapitem). W przeszłości ta ostatnia opcja nie uniemożliwiała transformacji, co oznacza, że ​​GCC nie było zgodne w tym punkcie: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845

vinc17
źródło
3
Wieloletnie popularne pytania czasem pokazują ich wiek. Na to pytanie zadano i udzielono odpowiedzi w 2011 r., Kiedy GCC można usprawiedliwić za nieprzestrzeganie dokładnie ówczesnego standardu C99. Oczywiście teraz jest 2014, więc GCC… hm.
Pascal Cuoq
Czy zamiast tego nie powinieneś odpowiadać na stosunkowo nowe pytania zmiennoprzecinkowe bez zaakceptowanej odpowiedzi? kaszel stackoverflow.com/questions/23703408 kaszel
Pascal Cuoq
Uważam to za ... niepokojące, że gcc nie implementuje pragmów zmiennoprzecinkowych C99.
David Monniaux,
1
@DavidMonniaux pragmy są z definicji opcjonalne do wdrożenia.
Tim Seguine,
2
@TimSeguine Ale jeśli pragma nie jest zaimplementowana, jej domyślna wartość musi być najbardziej restrykcyjna dla implementacji. Myślę, że o tym myślał David. W przypadku GCC jest to teraz naprawione dla FP_CONTRACT, jeśli ktoś korzysta z trybu ISO C : nadal nie realizuje pragmy, ale w trybie ISO C zakłada, że ​​pragma jest wyłączona.
vinc17
28

Jak zauważył Lambdageek, mnożenie zmiennoprzecinkowe nie jest asocjacyjne i można uzyskać mniejszą dokładność, ale także, gdy można uzyskać lepszą dokładność, można argumentować przeciwko optymalizacji, ponieważ chcesz deterministycznej aplikacji. Na przykład w grze klient / serwer do symulacji, w której każdy klient musi symulować ten sam świat, w którym obliczenia zmiennoprzecinkowe są deterministyczne.

Bjorn
źródło
3
@greggo Nie, to wciąż jest deterministyczne. Żadna przypadkowość nie jest dodawana w żadnym znaczeniu tego słowa.
Alice,
9
@Alice Wydaje się dość jasne, że Bjorn używa tutaj „deterministycznego” w sensie kodu dającego ten sam wynik na różnych platformach i różnych wersjach kompilatora itp. (Zewnętrzne zmienne, które mogą być poza kontrolą programisty) - w przeciwieństwie do braku faktycznej losowości liczbowej w czasie wykonywania. Jeśli wskazujesz, że to nie jest właściwe użycie tego słowa, nie będę się z tym kłócił.
greggo
5
@greggo Z wyjątkiem nawet twojej interpretacji tego, co mówi, nadal jest źle; to jest cały punkt IEEE 754, aby zapewnić identyczne cechy większości (jeśli nie wszystkich) operacji na różnych platformach. Teraz nie wspomniał o wersjach platform ani kompilatorach, co byłoby słusznym problemem, jeśli chcesz, aby każda operacja na każdym zdalnym serwerze / kliencie była identyczna ... ale nie jest to oczywiste z jego wypowiedzi. Lepszym słowem może być „niezawodnie podobny” lub coś w tym rodzaju.
Alice,
8
@ Alicja, marnujesz czas wszystkich, w tym swój własny, argumentując semantykę. Jego znaczenie było jasne.
Lanaru,
11
@Lanaru Cały punkt standardów to semantyka; jego znaczenie było zdecydowanie niejasne.
Alice,
28

Funkcje biblioteki, takie jak „pow”, są zwykle starannie tworzone, aby uzyskać minimalny możliwy błąd (w ogólnym przypadku). Zwykle osiąga się to w przybliżeniu funkcji z splajnami (zgodnie z komentarzem Pascala wydaje się, że najczęstszą implementacją jest algorytm Remeza )

zasadniczo następująca operacja:

pow(x,y);

ma nieodłączny błąd o wielkości w przybliżeniu tej samej wielkości co błąd w dowolnym pojedynczym pomnożeniu lub dzieleniu .

Podczas następujących operacji:

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

ma nieodłączny błąd większy niż 5-krotność błędu pojedynczego pomnożenia lub podziału (ponieważ łączysz 5 pomnożenia).

Kompilator powinien bardzo uważać na optymalizację:

  1. jeśli optymalizacja pow(a,6)do a*a*a*a*a*atego może poprawić wydajność, ale drastycznie zmniejszyć dokładność dla liczb zmiennoprzecinkowych.
  2. jeśli optymalizacja a*a*a*a*a*a dopow(a,6) niego może faktycznie zmniejszyć dokładność, ponieważ „a” było jakąś specjalną wartością, która pozwala na pomnożenie bez błędu (potęga 2 lub niewielka liczba całkowita)
  3. jeśli optymalizacja pow(a,6)do (a*a*a)*(a*a*a)lub (a*a)*(a*a)*(a*a)nadal może wystąpić utrata dokładności w porównaniu do powfunkcji.

Ogólnie wiesz, że dla dowolnych wartości zmiennoprzecinkowych „pow” ma lepszą dokładność niż jakakolwiek funkcja, którą ostatecznie możesz napisać, ale w niektórych szczególnych przypadkach wielokrotne mnożenie może mieć lepszą dokładność i wydajność, to programista wybiera to, co jest bardziej odpowiednie, ostatecznie komentując kod, aby nikt inny nie „zoptymalizował” tego kodu.

Jedyną rzeczą, która ma sens (osobista opinia i najwyraźniej wybór w GCC bez konkretnej optymalizacji lub flagi kompilatora) do optymalizacji, to zastąpienie „pow (a, 2)” przez „a * a”. To byłaby jedyna rozsądna rzecz, którą powinien zrobić dostawca kompilatora.

CoffeDeveloper
źródło
7
zwolennicy powinni zdać sobie sprawę, że ta odpowiedź jest w porządku. Potrafię zacytować dziesiątki źródeł i dokumentacji na poparcie mojej odpowiedzi i prawdopodobnie jestem bardziej zaangażowany w precyzję zmiennoprzecinkową niż jakikolwiek downvoter. W StackOverflow jest całkowicie rozsądne dodawanie brakujących informacji, których nie obejmują inne odpowiedzi, więc bądź uprzejmy i wyjaśnij swoje powody.
CoffeDeveloper
1
Wydaje mi się, że odpowiedź Stephena Canona obejmuje to, co masz do powiedzenia. Wydaje się, że nalegasz, aby biblioteki libms były implementowane za pomocą splajnów: częściej używają redukcji argumentów (w zależności od implementowanej funkcji) oraz pojedynczego wielomianu, którego współczynniki zostały uzyskane przez mniej lub bardziej wyrafinowane warianty algorytmu Remeza. Gładkość w punktach połączenia nie jest uważana za cel, do którego warto dążyć w przypadku funkcji libm (jeśli kończą się one dostatecznie dokładnie, i tak są automatycznie dość gładkie niezależnie od tego, na ile części podzielono domenę).
Pascal Cuoq,
Druga połowa twojej odpowiedzi całkowicie nie zgadza się z twierdzeniem, że kompilatory powinny tworzyć kod, który implementuje to, co mówi kod źródłowy, kropka. Używasz również słowa „precyzja”, gdy masz na myśli „dokładność”.
Pascal Cuoq,
Dziękuję za twój wkład, nieco poprawiłem odpowiedź, coś nowego jest wciąż obecne w ostatnich 2 liniach ^^
CoffeDeveloper
27

W ogóle nie spodziewałbym się, że ta sprawa zostanie zoptymalizowana. Często zdarza się, że wyrażenie zawiera podwyrażenia, które można zgrupować w celu usunięcia całych operacji. Spodziewałbym się, że autorzy kompilatorów zainwestują swój czas w obszary, w których bardziej prawdopodobne jest zauważalne ulepszenie, niż omawianie rzadko spotykanego przypadku.

Byłem zaskoczony, gdy dowiedziałem się z innych odpowiedzi, że to wyrażenie można rzeczywiście zoptymalizować za pomocą odpowiednich przełączników kompilatora. Albo optymalizacja jest trywialna, albo jest skrajnym przypadkiem znacznie powszechniejszej optymalizacji, lub autorzy kompilatora byli bardzo dokładni.

Nie ma nic złego w udzielaniu wskazówek kompilatorowi, tak jak tutaj zrobiłeś. Jest to normalna i oczekiwana część procesu mikrooptymalizacji polegająca na zmianie kolejności instrukcji i wyrażeń w celu sprawdzenia, jakie różnice przyniosą.

Chociaż kompilator może być uzasadniony, biorąc pod uwagę dwa wyrażenia w celu dostarczenia niespójnych wyników (bez odpowiednich przełączników), nie musisz być związany tym ograniczeniem. Różnica będzie niewiarygodnie mała - do tego stopnia, że ​​jeśli różnica jest dla Ciebie ważna, nie powinieneś używać standardowej arytmetyki zmiennoprzecinkowej.

Mark Ransom
źródło
17
Jak zauważył inny komentator, jest to nieprawdziwe do tego stopnia, że ​​jest absurdalne; różnica może wynosić nawet od połowy do 10% kosztów, a jeśli będzie działać w ciasnej pętli, przełoży się to na wiele instrukcji zmarnowanych, aby uzyskać niewielką dodatkową dokładność. Mówienie, że nie powinieneś używać standardowego FP, kiedy robisz monte carlo, jest jakby mówieniem, że zawsze powinieneś używać samolotu, aby dostać się przez kraj; ignoruje wiele efektów zewnętrznych. Wreszcie NIE jest to rzadka optymalizacja; analiza martwego kodu i redukcja / korekta kodu są bardzo powszechne.
Alice
21

Istnieje już kilka dobrych odpowiedzi na to pytanie, ale ze względu na kompletność chciałem zauważyć, że odpowiednią sekcją normy C jest 5.1.2.2.3 / 15 (która jest taka sama jak sekcja 1.9 / 9 w C ++ 11). W tej sekcji stwierdzono, że operatory można przegrupować tylko wtedy, gdy naprawdę są asocjacyjne lub przemienne.

Rastaban
źródło
12

gcc faktycznie może przeprowadzić tę optymalizację, nawet dla liczb zmiennoprzecinkowych. Na przykład,

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

staje się

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

z -O -funsafe-math-optimizations. Ta zmiana kolejności narusza IEEE-754, więc wymaga flagi.

Podpisane liczby całkowite, jak zauważył Peter Cordes w komentarzu, mogą przeprowadzić tę optymalizację bez, -funsafe-math-optimizationsponieważ zachowuje się dokładnie wtedy, gdy nie ma przepełnienia, a jeśli występuje przepełnienie, zachowanie jest niezdefiniowane. Więc dostajesz

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

z właśnie -O. W przypadku liczb całkowitych bez znaku jest to jeszcze łatwiejsze, ponieważ działają one na modach o wartości 2, dzięki czemu można je dowolnie zmieniać nawet w przypadku przepełnienia.

Charles
źródło
1
Godbolt link z double, int i unsigned. gcc i clang optymalizują wszystkie trzy w ten sam sposób (z -ffast-math)
Peter Cordes
@PeterCordes Thanks!
Charles