Warum optimiert GCC nicht a * a * a * a * a * a bis (a * a * a) * (a * a * a)?

2120

Ich mache eine numerische Optimierung für eine wissenschaftliche Anwendung. Eine Sache, die mir aufgefallen ist, ist, dass GCC den Aufruf pow(a,2)durch Kompilieren optimiert a*a, aber der Aufruf pow(a,6)nicht optimiert ist und tatsächlich die Bibliotheksfunktion aufruft pow, was die Leistung erheblich verlangsamt. (Im Gegensatz dazu eliminiert der ausführbare Intel C ++ - Compilericc den Bibliotheksaufruf für pow(a,6).)

Was ich bin gespannt ist , dass , wenn ich ersetzt pow(a,6)mit a*a*a*a*a*aVerwendung von GCC 4.5.1 und Optionen „ -O3 -lm -funroll-loops -msse4“ es 5 verwendet mulsdAnweisungen:

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

während, wenn ich schreibe (a*a*a)*(a*a*a), wird es produzieren

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

Dies reduziert die Anzahl der Multiplikationsbefehle auf 3. icchat ein ähnliches Verhalten.

Warum erkennen Compiler diesen Optimierungstrick nicht?

xis
quelle
13
Was bedeutet "Pow (a, 6) erkennen"?
Varun Madiath
659
Ähm ... Sie wissen, dass a a a a a und (a a a) * (a a * a) bei Gleitkommazahlen nicht dasselbe sind, nicht wahr? Sie müssen -funsafe-math oder -ffast-math oder etwas dafür verwenden.
Damon
106
Ich schlage vor, Sie lesen "Was jeder Informatiker über Gleitkomma-Arithmetik wissen sollte" von David Goldberg: download.oracle.com/docs/cd/E19957-01/806-3568/…. Danach haben Sie ein umfassenderes Verständnis von die Teergrube, in die du gerade gegangen bist!
Phil Armstrong
189
Eine durchaus vernünftige Frage. Vor 20 Jahren stellte ich dieselbe allgemeine Frage und reduzierte durch die Beseitigung dieses einzelnen Engpasses die Ausführungszeit einer Monte-Carlo-Simulation von 21 Stunden auf 7 Stunden. Der Code in der inneren Schleife wurde dabei 13 Billionen Mal ausgeführt, brachte die Simulation jedoch in ein Nachtfenster. (siehe Antwort unten)
23
Vielleicht auch (a*a)*(a*a)*(a*a)in die Mischung werfen . Gleiche Anzahl von Multiplikationen, aber wahrscheinlich genauer.
Rok Kralj

Antworten:

2738

Weil Gleitkomma-Mathematik nicht assoziativ ist . Die Art und Weise, wie Sie die Operanden in Gleitkomma-Multiplikation gruppieren, wirkt sich auf die numerische Genauigkeit der Antwort aus.

Infolgedessen sind die meisten Compiler sehr konservativ bei der Neuordnung von Gleitkommaberechnungen, es sei denn, sie können sicher sein, dass die Antwort gleich bleibt, oder Sie sagen ihnen, dass Ihnen die numerische Genauigkeit egal ist. Zum Beispiel: die -fassociative-mathOption von gcc, mit der gcc Gleitkommaoperationen neu zuordnen kann, oder sogar die -ffast-mathOption, die noch aggressivere Kompromisse zwischen Genauigkeit und Geschwindigkeit ermöglicht.

Lambdageek
quelle
10
Ja. Mit -ffast-math wird eine solche Optimierung durchgeführt. Gute Idee! Da unser Code jedoch mehr Genauigkeit als Geschwindigkeit betrifft, ist es möglicherweise besser, ihn nicht weiterzugeben.
xis
19
Mit IIRC C99 kann der Compiler solche "unsicheren" FP-Optimierungen durchführen, aber GCC (auf etwas anderem als dem x87) unternimmt einen vernünftigen Versuch, IEEE 754 zu folgen - es sind keine "Fehlergrenzen". Es gibt nur eine richtige Antwort .
tc.
14
Die Implementierungsdetails von powsind weder hier noch dort; Diese Antwort bezieht sich nicht einmal pow.
Stephen Canon
14
@nedR: ICC erlaubt standardmäßig die erneute Zuordnung. Wenn Sie ein standardkonformes Verhalten erhalten möchten, müssen Sie -fp-model preciseICC festlegen . clangund gccstandardmäßig strikte Konformität für die Neuzuordnung.
Stephen Canon
49
@xis, es ist nicht wirklich so, dass -fassociative-mathes ungenau wäre; es ist nur das a*a*a*a*a*aund (a*a*a)*(a*a*a)sind anders. Es geht nicht um Genauigkeit; Es geht um Standardkonformität und streng wiederholbare Ergebnisse, z. B. dieselben Ergebnisse auf jedem Compiler. Gleitkommazahlen sind bereits nicht genau. Es ist selten unangemessen, mit zu kompilieren -fassociative-math.
Paul Draper
652

Lambdageek weist zutreffend darauf hin, dass die "Optimierung" vona*a*a*a*a*ato(a*a*a)*(a*a*a)den Wert ändern kann, da die Assoziativität für Gleitkommazahlen nicht gilt. Aus diesem Grund wird es von C99 nicht zugelassen (sofern vom Benutzer nicht ausdrücklich über das Compiler-Flag oder das Pragma zugelassen). Im Allgemeinen wird davon ausgegangen, dass die Programmiererin aus einem bestimmten Grund geschrieben hat, was sie getan hat, und der Compiler sollte dies respektieren. Wenn du willst(a*a*a)*(a*a*a), schreibe das.

Das kann jedoch ein Schmerz sein zu schreiben; Warum kann der Compiler nicht einfach das Richtige tun, wenn Sie es verwenden pow(a,6)? Weil es das Falsche wäre . Auf einer Plattform mit einer guten Mathematikbibliothek pow(a,6)ist deutlich genauer als entweder a*a*a*a*a*aoder (a*a*a)*(a*a*a). Um einige Daten bereitzustellen, habe ich auf meinem Mac Pro ein kleines Experiment durchgeführt, bei dem der schlimmste Fehler bei der Auswertung von ^ 6 für alle schwebenden Zahlen mit einfacher Genauigkeit zwischen [1,2] gemessen wurde:

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

Die Verwendung powanstelle eines Multiplikationsbaums reduziert den um einen Faktor 4 begrenzten Fehler . Compiler sollten keine (und im Allgemeinen keine) "Optimierungen" vornehmen, die den Fehler erhöhen, es sei denn, der Benutzer hat eine Lizenz dafür (z -ffast-math. B. über ).

Beachten Sie, dass GCC __builtin_powi(x,n)eine Alternative zu bietet pow( ), die einen Inline-Multiplikationsbaum generieren sollte. Verwenden Sie diese Option, wenn Sie die Genauigkeit gegen die Leistung austauschen möchten, aber keine schnelle Mathematik aktivieren möchten.

Stephen Canon
quelle
29
Beachten Sie auch, dass Visual C ++ eine erweiterte Version von pow () bietet. Durch den Aufruf _set_SSE2_enable(<flag>)mit flag=1, wird es SSE2 wenn möglich nutzen. Dies verringert die Genauigkeit ein wenig, verbessert jedoch die Geschwindigkeit (in einigen Fällen). MSDN: _set_SSE2_enable () und pow ()
TkTech
18
@TkTech: Eine verringerte Genauigkeit ist auf die Implementierung von Microsoft zurückzuführen, nicht auf die Größe der verwendeten Register. Es ist möglich, eine korrekt gerundete pow Verwendung mit nur 32-Bit-Registern zu liefern , wenn der Bibliotheksschreiber so motiviert ist. Es gibt SSE-basierte powImplementierungen , die sind mehr genauer als die meisten x87-basierten Implementierungen, und es gibt auch Implementierungen , dass der Handel aus einer gewissen Genauigkeit für die Geschwindigkeit.
Stephen Canon
9
@TkTech: Natürlich wollte ich nur klarstellen, dass die Verringerung der Genauigkeit auf die von den Bibliotheksautoren getroffenen Entscheidungen zurückzuführen ist, die für die Verwendung von SSE nicht wesentlich sind.
Stephen Canon
7
Ich bin interessiert zu wissen, was Sie hier als "Goldstandard" für die Berechnung relativer Fehler verwendet haben - ich hätte normalerweise damit gerechnet a*a*a*a*a*a, aber das ist anscheinend nicht der Fall! :)
j_random_hacker
8
@j_random_hacker: da ich mit einfacher Genauigkeit Ergebnisse doppelter Genauigkeit genügt für einen Goldstandard wurde Vergleich - den Fehler von einem a a a a a in Doppel berechnete * erheblich kleiner ist als der Fehler von einem der mit einfacher Genauigkeit Berechnungen.
Stephen Canon
168

Ein weiterer ähnlicher Fall: Die meisten Compiler optimieren nicht a + b + c + dauf (a + b) + (c + d)(dies ist eine Optimierung, da der zweite Ausdruck besser per Pipeline übertragen werden kann) und bewerten ihn als gegeben (dh als (((a + b) + c) + d)). Auch dies liegt an Eckfällen:

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

Dies gibt aus 1.000000e-05 0.000000e+00

sanjoyd
quelle
10
Das ist nicht genau das gleiche. Die Änderung der Reihenfolge der Multiplikationen / Divisionen (ohne Division durch 0) ist sicherer als die Änderung der Reihenfolge der Summe / Subtraktion. Meiner bescheidenen Meinung nach sollte der Compiler versuchen, mults./divs zuzuordnen. weil dadurch die Gesamtzahl der Operationen reduziert wird und neben dem Leistungsgewinn auch ein Präzisionsgewinn erzielt wird.
CoffeDeveloper
4
@DarioOO: Es ist nicht sicherer. Multiplizieren und Dividieren sind dasselbe wie Addieren und Subtrahieren des Exponenten, und das Ändern der Reihenfolge kann leicht dazu führen, dass Provisorien den möglichen Bereich des Exponenten überschreiten. (Nicht genau das gleiche, weil der Exponent keinen Genauigkeitsverlust erleidet ... aber die Darstellung ist immer noch recht begrenzt und eine Neuordnung kann zu nicht darstellbaren Werten führen)
Ben Voigt
8
Ich denke, Ihnen fehlt ein Kalkülhintergrund. Das Multiplizieren und Teilen von 2 Zahlen führt zu der gleichen Fehlermenge. Während das Subtrahieren / Addieren von 2 Zahlen einen größeren Fehler verursachen kann, insbesondere wenn die 2 Zahlen in der Größenordnung unterschiedlich sind, ist es sicherer, Mul / Dividieren neu anzuordnen als Sub / Addieren, da es eine geringfügige Änderung des endgültigen Fehlers einführt.
CoffeDeveloper
8
@DarioOO: Das Risiko ist bei mul / div unterschiedlich: Eine Neuordnung führt entweder zu einer vernachlässigbaren Änderung des Endergebnisses, oder der Exponent läuft irgendwann über (wo es vorher nicht gewesen wäre) und das Ergebnis ist massiv unterschiedlich (möglicherweise + inf oder 0).
Peter Cordes
@GameDeveloper Es ist äußerst problematisch, auf unvorhersehbare Weise einen Präzisionsgewinn zu erzielen.
Neugieriger
80

Fortran (entwickelt für wissenschaftliches Rechnen) verfügt über einen eingebauten Energieoperator. Soweit ich weiß, optimieren Fortran-Compiler das Erhöhen auf ganzzahlige Kräfte auf ähnliche Weise wie von Ihnen beschrieben. C / C ++ hat leider keinen Power Operator, nur die Bibliotheksfunktion pow(). Dies hindert intelligente Compiler nicht daran, sie powspeziell zu behandeln und für spezielle Fälle schneller zu berechnen, aber es scheint, dass sie dies weniger häufig tun ...

Vor einigen Jahren habe ich versucht, es einfacher zu machen, ganzzahlige Potenzen optimal zu berechnen, und habe Folgendes gefunden. Es ist C ++, nicht C, und hängt immer noch davon ab, dass der Compiler etwas klug ist, wie man Dinge optimiert / inline macht. Wie auch immer, ich hoffe, Sie finden es in der Praxis nützlich:

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

Klarstellung für Neugierige: Dies ist kein optimaler Weg, um Kräfte zu berechnen, aber da das Finden der optimalen Lösung ein NP-vollständiges Problem ist und dies ohnehin nur für kleine Kräfte sinnvoll ist (im Gegensatz zur Verwendung pow), gibt es keinen Grund zur Aufregung mit dem Detail.

Dann benutze es einfach als power<6>(a).

Dies erleichtert das Eingeben von Potenzen (es ist nicht erforderlich, 6 aSekunden mit Parens zu buchstabieren ) und ermöglicht Ihnen diese Art der Optimierung, ohne dass -ffast-mathSie etwas Präzisionsabhängiges wie eine kompensierte Summierung haben (ein Beispiel, bei dem die Reihenfolge der Operationen wesentlich ist). .

Sie können wahrscheinlich auch vergessen, dass dies C ++ ist, und es einfach im C-Programm verwenden (wenn es mit einem C ++ - Compiler kompiliert wird).

Hoffe das kann nützlich sein.

BEARBEITEN:

Folgendes bekomme ich von meinem Compiler:

Für a*a*a*a*a*a,

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

Für (a*a*a)*(a*a*a),

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

Für power<6>(a),

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
Szabolcs
quelle
36
Es mag schwierig sein, den optimalen Potenzbaum zu finden, aber da er nur für kleine Potenzen interessant ist, besteht die offensichtliche Antwort darin, ihn einmal vorab zu berechnen (Knuth stellt eine Tabelle mit bis zu 100 bereit) und diese fest codierte Tabelle zu verwenden (das macht gcc intern für powi). .
Marc Glisse
7
Bei modernen Prozessoren ist die Geschwindigkeit durch die Latenz begrenzt. Beispielsweise kann das Ergebnis einer Multiplikation nach fünf Zyklen verfügbar sein. In dieser Situation ist es möglicherweise schwieriger, den schnellsten Weg zu finden, um Energie zu erzeugen.
Gnasher729
3
Sie können auch versuchen, den Potenzbaum zu finden, der die niedrigste Obergrenze für den relativen Rundungsfehler oder den niedrigsten durchschnittlichen relativen Rundungsfehler angibt.
Gnasher729
1
Boost unterstützt dies auch, z. B. boost :: math :: pow <6> (n); Ich denke, es wird sogar versucht, die Anzahl der Multiplikationen zu reduzieren, indem gemeinsame Faktoren extrahiert werden.
Gast128
Beachten Sie, dass der letzte entspricht (a ** 2) ** 3
minmaxavg
62

GCC optimiert tatsächlich a*a*a*a*a*a, (a*a*a)*(a*a*a)wenn a eine Ganzzahl ist. Ich habe es mit diesem Befehl versucht:

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

Es gibt viele gcc-Flaggen, aber nichts Besonderes. Sie bedeuten: Lesen Sie von stdin; O2-Optimierungsstufe verwenden; Auflistung der Assembler-Sprache anstelle einer Binärdatei; Die Auflistung sollte die Syntax der Assemblersprache von Intel verwenden. Die Eingabe erfolgt in C-Sprache (normalerweise wird die Sprache aus der Dateierweiterung der Eingabe abgeleitet, beim Lesen aus stdin gibt es jedoch keine Dateierweiterung). und schreibe an stdout.

Hier ist der wichtige Teil der Ausgabe. Ich habe es mit einigen Kommentaren kommentiert, die angeben, was in der Assemblersprache vor sich geht:

; 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

Ich verwende das System GCC unter Linux Mint 16 Petra, einem Ubuntu-Derivat. Hier ist die gcc-Version:

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

Wie andere Poster angemerkt haben, ist diese Option im Gleitkomma nicht möglich, da Gleitkomma-Arithmetik nicht assoziativ ist.

Picomancer
quelle
12
Dies ist für die Ganzzahlmultiplikation zulässig, da der Zweierkomplementüberlauf ein undefiniertes Verhalten ist. Wenn es zu einem Überlauf kommt, geschieht dies irgendwo, unabhängig von der Neuordnung. Ausdrücke ohne Überlauf werden also gleich ausgewertet. Ausdrücke mit Überlauf sind undefiniertes Verhalten, sodass der Compiler den Punkt ändern kann, an dem ein Überlauf auftritt. gcc macht das auch mit unsigned int.
Peter Cordes
51

Weil eine 32-Bit-Gleitkommazahl wie 1.024 nicht 1.024 ist. In einem Computer ist 1.024 ein Intervall: von (1.024-e) bis (1.024 + e), wobei "e" einen Fehler darstellt. Einige Leute erkennen dies nicht und glauben auch, dass * in a * a für die Multiplikation von Zahlen mit beliebiger Genauigkeit steht, ohne dass mit diesen Zahlen Fehler verbunden sind. Der Grund, warum manche Menschen dies nicht erkennen, sind möglicherweise die mathematischen Berechnungen, die sie in Grundschulen durchgeführt haben: Sie arbeiten nur mit idealen Zahlen ohne Fehler und glauben, dass es in Ordnung ist, "e" einfach zu ignorieren, während Sie die Multiplikation durchführen. Sie sehen das "e" nicht implizit in "float a = 1.2", "a * a * a" und ähnlichen C-Codes.

Sollte die Mehrheit der Programmierer die Idee erkennen (und ausführen können), dass der C-Ausdruck a * a * a * a * a * a nicht mit idealen Zahlen funktioniert, kann der GCC-Compiler "a * a" KOSTENLOS optimieren * a * a * a * a "in say" t = (a * a); t * t * t ", was eine geringere Anzahl von Multiplikationen erfordert. Leider weiß der GCC-Compiler nicht, ob der Programmierer, der den Code schreibt, der Meinung ist, dass "a" eine Zahl mit oder ohne Fehler ist. Und so wird GCC nur das tun, wie der Quellcode aussieht - denn das sieht GCC mit seinem "bloßen Auge".

... Sobald Sie wissen, was für ein Programmierer Sie sind, können Sie den Schalter "-ffast-math" verwenden, um GCC mitzuteilen, dass "Hey, GCC, ich weiß, was ich tue!". Auf diese Weise kann GCC a * a * a * a * a * a in einen anderen Text konvertieren - es sieht anders aus als a * a * a * a * a * a -, berechnet jedoch eine Zahl innerhalb des Fehlerintervalls von a * a * a * a * a * a. Dies ist in Ordnung, da Sie bereits wissen, dass Sie mit Intervallen arbeiten, nicht mit idealen Zahlen.


quelle
52
Gleitkommazahlen sind genau. Sie sind einfach nicht unbedingt genau das, was Sie erwartet haben. Darüber hinaus ist die Technik mit Epsilon selbst eine Annäherung an die Vorgehensweise in der Realität, da der tatsächlich erwartete Fehler relativ zur Skala der Mantisse ist, dh Sie sind normalerweise bis zu 1 LSB out, aber das kann mit zunehmen Jede Operation, die ausgeführt wird, wenn Sie nicht vorsichtig sind, konsultieren Sie einen numerischen Analysten, bevor Sie etwas nicht Triviales mit Gleitkomma ausführen. Verwenden Sie eine geeignete Bibliothek, wenn Sie können.
Donal Fellows
3
@DonalFellows: Der IEEE - Standard erfordert , dass Gleitkommarechnungen das Ergebnis ergeben, die genau dem entspricht , was das Ergebnis sein würde , wenn die Quellenoperanden exakte Werte waren, aber das bedeutet nicht , dass sie tatsächlich darstellen genaue Werte. In vielen Fällen ist es hilfreicher, 0,1f als (1.677.722 +/- 0,5) / 16.777.216 zu betrachten, das mit der durch diese Unsicherheit implizierten Anzahl von Dezimalstellen angezeigt werden sollte, als es als exakte Menge (1.677.722 +/-) zu betrachten. 0,5) / 16,777,216 (sollte mit 24 Dezimalstellen angezeigt werden).
Supercat
23
@supercat: IEEE-754 ist ziemlich klar auf den Punkt , dass Floating-Point - Daten tun genaue Werte darstellen; Die Abschnitte 3.2 - 3.4 sind die relevanten Abschnitte. Sie können sie natürlich auch anders interpretieren, genauso wie Sie sie int x = 3als x3 +/- 0,5 interpretieren können .
Stephen Canon
7
@supercat: Ich stimme vollkommen zu, aber das bedeutet nicht, dass Distancedas nicht genau seinem numerischen Wert entspricht. Dies bedeutet, dass der numerische Wert nur eine Annäherung an eine physikalische Größe ist, die modelliert wird.
Stephen Canon
10
Für die numerische Analyse wird sich Ihr Gehirn bei Ihnen bedanken, wenn Sie Gleitkommazahlen nicht als Intervalle, sondern als exakte Werte interpretieren (die zufällig nicht genau die Werte sind, die Sie wollten). Wenn beispielsweise x irgendwo in der Runde 4,5 mit einem Fehler von weniger als 0,1 liegt und Sie (x + 1) - x berechnen, erhalten Sie bei der Interpretation "Intervall" ein Intervall von 0,8 bis 1,2, während die Interpretation "exakter Wert" dies angibt Sie erhalten 1 mit einem Fehler von höchstens 2 ^ (- 50) in doppelter Genauigkeit.
Gnasher729
34

Noch keine Poster haben die Kontraktion schwebender Ausdrücke erwähnt (ISO C-Standard, 6.5p8 und 7.12.2). Wenn das FP_CONTRACTPragma auf gesetzt ist, ONkann der Compiler einen Ausdruck wie a*a*a*a*a*aeine einzelne Operation betrachten, als würde er genau mit einer einzelnen Rundung ausgewertet. Zum Beispiel kann ein Compiler es durch eine interne Power-Funktion ersetzen, die sowohl schneller als auch genauer ist. Dies ist besonders interessant, da das Verhalten teilweise vom Programmierer direkt im Quellcode gesteuert wird, während vom Endbenutzer bereitgestellte Compileroptionen manchmal falsch verwendet werden.

Der Standardstatus des FP_CONTRACTPragmas ist implementierungsdefiniert, sodass ein Compiler standardmäßig solche Optimierungen vornehmen kann. Daher sollte portabler Code, der die IEEE 754-Regeln genau befolgen muss, explizit festgelegt werden OFF.

Wenn ein Compiler dieses Pragma nicht unterstützt, muss es konservativ sein, indem eine solche Optimierung vermieden wird, falls der Entwickler dies festgelegt hat OFF.

GCC unterstützt dieses Pragma nicht, aber mit den Standardoptionen wird davon ausgegangen, dass dies der Fall ist ON. Wenn Sie also für Ziele mit einer Hardware-FMA die Umwandlung a*b+cin fma (a, b, c) verhindern möchten, müssen Sie eine Option bereitstellen, z. B. -ffp-contract=off(um das Pragma explizit festzulegen OFF) oder -std=c99(um GCC anzuweisen, sich an einige anzupassen C Standardversion, hier C99, folgen Sie daher dem obigen Absatz). In der Vergangenheit hat die letztere Option die Transformation nicht verhindert, was bedeutet, dass GCC in diesem Punkt nicht konform war: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845

vinc17
quelle
3
Langlebige populäre Fragen zeigen manchmal ihr Alter. Diese Frage wurde 2011 gestellt und beantwortet, als GCC dafür entschuldigt werden konnte, dass er den damals aktuellen C99-Standard nicht genau eingehalten hatte. Natürlich ist es jetzt 2014, also GCC… ähm.
Pascal Cuoq
Sollten Sie nicht vergleichsweise aktuelle Gleitkomma-Fragen ohne eine akzeptierte Antwort beantworten? Husten stackoverflow.com/questions/23703408 Husten
Pascal Cuoq
Ich finde es ... beunruhigend, dass gcc keine C99-Gleitkomma-Pragmas implementiert.
David Monniaux
1
@ DavidMonniaux-Pragmas sind per Definition optional zu implementieren.
Tim Seguine
2
@TimSeguine Wenn ein Pragma jedoch nicht implementiert ist, muss sein Standardwert für die Implementierung am restriktivsten sein. Ich denke, daran hat David gedacht. Mit GCC ist dies jetzt für FP_CONTRACT behoben, wenn ein ISO C-Modus verwendet wird : Es implementiert das Pragma immer noch nicht, aber in einem ISO C-Modus wird jetzt davon ausgegangen, dass das Pragma deaktiviert ist.
vinc17
28

Wie Lambdageek hervorhob, ist die Float-Multiplikation nicht assoziativ und Sie können weniger Genauigkeit erzielen. Wenn Sie jedoch eine bessere Genauigkeit erzielen, können Sie gegen eine Optimierung argumentieren, da Sie eine deterministische Anwendung wünschen. Zum Beispiel in einem Spielsimulations-Client / Server, bei dem jeder Client dieselbe Welt simulieren muss, in der Gleitkommaberechnungen deterministisch sein sollen.

Björn
quelle
3
@greggo Nein, dann ist es immer noch deterministisch. Es wird keine Zufälligkeit im wahrsten Sinne des Wortes hinzugefügt.
Alice
9
@ Alice Es scheint ziemlich klar zu sein, dass Björn hier 'deterministisch' im Sinne des Codes verwendet, der auf verschiedenen Plattformen und verschiedenen Compilerversionen usw. das gleiche Ergebnis liefert (externe Variablen, die möglicherweise außerhalb der Kontrolle des Programmierers liegen) - im Gegensatz zum Mangel der tatsächlichen numerischen Zufälligkeit zur Laufzeit. Wenn Sie darauf hinweisen, dass dies keine richtige Verwendung des Wortes ist, werde ich damit nicht streiten.
Greggo
5
@greggo Außer selbst in deiner Interpretation dessen, was er sagt, ist es immer noch falsch; Das ist der ganze Sinn von IEEE 754, identische Eigenschaften für die meisten (wenn nicht alle) Operationen plattformübergreifend bereitzustellen. Jetzt erwähnte er keine Plattformen oder Compilerversionen, was ein berechtigtes Anliegen wäre, wenn Sie möchten, dass jeder einzelne Vorgang auf jedem Remote-Server / Client identisch ist ... aber dies ist aus seiner Aussage nicht ersichtlich. Ein besseres Wort könnte "zuverlässig ähnlich" oder so sein.
Alice
8
@ Alice, du verschwendest die Zeit aller, einschließlich deiner eigenen, indem du über Semantik diskutierst. Seine Bedeutung war klar.
Lanaru
11
@ Lanaru Der gesamte Punkt der Standards ist Semantik; seine Bedeutung war entschieden nicht klar.
Alice
28

Bibliotheksfunktionen wie "pow" werden normalerweise sorgfältig ausgearbeitet, um den minimal möglichen Fehler zu erzielen (im allgemeinen Fall). Dies wird normalerweise erreicht, indem Funktionen mit Splines angenähert werden (laut Pascals Kommentar scheint die häufigste Implementierung die Verwendung des Remez-Algorithmus zu sein ).

Grundsätzlich die folgende Operation:

pow(x,y);

hat einen inhärenten Fehler von ungefähr der gleichen Größe wie der Fehler bei einer einzelnen Multiplikation oder Division .

Während der folgenden Operation:

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

hat einen inhärenten Fehler, der mehr als das Fünffache des Fehlers einer einzelnen Multiplikation oder Division beträgt (weil Sie 5 Multiplikationen kombinieren).

Der Compiler sollte sehr vorsichtig mit der Art der Optimierung sein, die er durchführt:

  1. wenn die Optimierung pow(a,6)auf a*a*a*a*a*asie kann die Leistung verbessern, aber drastisch reduziert die Genauigkeit für Gleitkommazahlen.
  2. wenn die Optimierung a*a*a*a*a*a auf pow(a,6)es tatsächlich die Genauigkeit verringern kann , weil „a“ war etwas spezieller Wert, die Multiplikation ohne Fehler (eine Potenz von 2 oder einer kleinen ganzen Zahl ist ) ermöglicht
  3. Wenn die Optimierung pow(a,6)auf (a*a*a)*(a*a*a)oder (a*a)*(a*a)*(a*a)es immer noch zu einem Genauigkeitsverlust im Vergleich zur powFunktion kommen kann.

Im Allgemeinen wissen Sie, dass für beliebige Gleitkommawerte "pow" eine bessere Genauigkeit aufweist als jede Funktion, die Sie eventuell schreiben könnten. In einigen speziellen Fällen können jedoch mehrere Multiplikationen eine bessere Genauigkeit und Leistung aufweisen. Es ist Sache des Entwicklers, die geeignetere zu wählen. schließlich den Code kommentieren, so dass niemand sonst diesen Code "optimieren" würde.

Das einzige, was Sinn macht (persönliche Meinung und anscheinend eine Wahl in GCC ohne eine bestimmte Optimierung oder ein bestimmtes Compiler-Flag), um zu optimieren, sollte sein, "pow (a, 2)" durch "a * a" zu ersetzen. Das wäre das einzig Vernünftige, was ein Compiler-Anbieter tun sollte.

Kaffeeentwickler
quelle
7
Downvoter sollten erkennen, dass diese Antwort vollkommen in Ordnung ist. Ich kann Dutzende von Quellen und Dokumentationen zitieren, um meine Antwort zu unterstützen, und ich beschäftige mich wahrscheinlich mehr mit Gleitkommapräzision als jeder Downvoter. In StackOverflow ist es durchaus sinnvoll, fehlende Informationen hinzuzufügen, die in anderen Antworten nicht behandelt werden. Seien Sie also höflich und erläutern Sie Ihre Gründe.
CoffeDeveloper
1
Es scheint mir, dass Stephen Canons Antwort das abdeckt, was Sie zu sagen haben. Sie scheinen darauf zu bestehen, dass Libms mit Splines implementiert werden: Sie verwenden in der Regel eine Argumentreduktion (abhängig von der implementierten Funktion) plus ein einzelnes Polynom, dessen Koeffizienten durch mehr oder weniger ausgefeilte Varianten des Remez-Algorithmus erhalten wurden. Die Glätte an Verbindungspunkten wird nicht als Ziel angesehen, das es wert ist, für libm-Funktionen verfolgt zu werden (wenn sie genau genug sind, sind sie ohnehin automatisch ziemlich glatt, unabhängig davon, in wie viele Teile die Domäne aufgeteilt wurde).
Pascal Cuoq
In der zweiten Hälfte Ihrer Antwort wird der Punkt, an dem Compiler Code erzeugen sollen, der das implementiert, was der Quellcode sagt, Punkt, völlig verfehlt. Sie verwenden auch das Wort "Präzision", wenn Sie "Genauigkeit" meinen.
Pascal Cuoq
Vielen Dank für Ihre Eingabe, ich habe die Antwort leicht korrigiert, etwas Neues ist noch in den letzten 2 Zeilen vorhanden ^^
CoffeDeveloper
27

Ich hätte nicht erwartet, dass dieser Fall überhaupt optimiert wird. Es kann nicht sehr oft vorkommen, dass ein Ausdruck Unterausdrücke enthält, die neu gruppiert werden können, um ganze Operationen zu entfernen. Ich würde erwarten, dass Compiler-Autoren ihre Zeit in Bereiche investieren, die eher zu spürbaren Verbesserungen führen, als einen selten anzutreffenden Randfall abzudecken.

Ich war überrascht, aus den anderen Antworten zu erfahren, dass dieser Ausdruck tatsächlich mit den richtigen Compiler-Schaltern optimiert werden kann. Entweder ist die Optimierung trivial, oder es handelt sich um einen Randfall einer viel häufigeren Optimierung, oder die Compiler-Autoren waren äußerst gründlich.

Es ist nichts Falsches daran, dem Compiler Hinweise zu geben, wie Sie es hier getan haben. Es ist ein normaler und erwarteter Teil des Mikrooptimierungsprozesses, Anweisungen und Ausdrücke neu anzuordnen, um festzustellen, welche Unterschiede sie mit sich bringen.

Während der Compiler berechtigt sein kann, die beiden Ausdrücke zu berücksichtigen, um inkonsistente Ergebnisse zu liefern (ohne die richtigen Schalter), müssen Sie nicht an diese Einschränkung gebunden sein. Der Unterschied wird unglaublich klein sein - so sehr, dass Sie, wenn der Unterschied für Sie wichtig ist, überhaupt keine Standard-Gleitkomma-Arithmetik verwenden sollten.

Mark Ransom
quelle
17
Wie von einem anderen Kommentator bemerkt, ist dies so unwahr, dass es absurd ist; Der Unterschied kann bis zur Hälfte bis zu 10% der Kosten betragen. Wenn er in einer engen Schleife ausgeführt wird, werden viele Anweisungen verschwendet, um eine möglicherweise unbedeutende zusätzliche Präzision zu erzielen. Zu sagen, dass Sie kein Standard-FP verwenden sollten, wenn Sie ein Monte Carlo machen, ist so etwas wie zu sagen, dass Sie immer ein Flugzeug verwenden sollten, um quer durch das Land zu gelangen. es ignoriert viele externe Effekte. Schließlich ist dies KEINE ungewöhnliche Optimierung. Dead Code-Analyse und Code-Reduktion / Refactor sind sehr verbreitet.
Alice
21

Es gibt bereits einige gute Antworten auf diese Frage, aber der Vollständigkeit halber wollte ich darauf hinweisen, dass der anwendbare Abschnitt der C-Norm 5.1.2.2.3 / 15 ist (der gleiche wie Abschnitt 1.9 / 9 in der C ++ 11 Standard). In diesem Abschnitt wird angegeben, dass Operatoren nur dann neu gruppiert werden können, wenn sie wirklich assoziativ oder kommutativ sind.

Rastaban
quelle
12

gcc kann diese Optimierung sogar für Gleitkommazahlen durchführen. Zum Beispiel,

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

wird

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

mit -O -funsafe-math-optimizations. Diese Neuordnung verstößt jedoch gegen IEEE-754, sodass das Flag erforderlich ist.

Vorzeichenbehaftete Ganzzahlen können, wie Peter Cordes in einem Kommentar hervorhob, diese Optimierung ohne durchführen, -funsafe-math-optimizationsda sie genau dann gelten, wenn kein Überlauf vorliegt und wenn ein Überlauf vorliegt, erhalten Sie ein undefiniertes Verhalten. Also verstehst du

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

mit nur -O. Für vorzeichenlose Ganzzahlen ist es sogar noch einfacher, da sie Mod-Potenzen von 2 haben und daher auch bei Überlauf frei neu angeordnet werden können.

Charles
quelle
1
Godbolt Link mit double, int und unsigned. gcc und clang optimieren beide alle gleich (mit -ffast-math)
Peter Cordes
@ PeterCordes Danke!
Charles