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


Ich mache eine numerische Optimierung für eine wissenschaftliche Anwendung. Eine Sache, die mir aufgefallen ist, ist, dass GCC den Anruf optimieren wird pow(a,2) indem man es in kompiliert a*a, aber der Anruf pow(a,6) ist nicht optimiert und wird die Bibliotheksfunktion tatsächlich aufrufen pow, was die Leistung stark verlangsamt. (Im Gegensatz, Intel C ++ - Compilerausführbar icc, wird den Bibliotheksaufruf für eliminieren pow(a,6).)

Worüber ich neugierig bin ist, dass ich ersetzt habe pow(a,6) mit a*a*a*a*a*a mit GCC 4.5.1 und Optionen "-O3 -lm -funroll-loops -msse4", es verwendet 5 mulsd Anleitung:

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

was die Anzahl der Multiplikationsanweisungen auf 3 reduziert. icc hat ähnliches Verhalten.

Warum erkennen Compiler diesen Optimierungstrick nicht?


1965
2018-06-21 18:49


Ursprung


Antworten:


weil Fließkomma Math ist nicht assoziativ. Die Art, wie Sie die Operanden in der Gleitkomma-Multiplikation gruppieren, wirkt sich auf die numerische Genauigkeit der Antwort aus.

Daher sind die meisten Compiler sehr konservativ, wenn es darum geht, Fließkomma-Berechnungen neu zu ordnen, es sei denn, sie können sicher sein, dass die Antwort gleich bleibt, oder wenn Sie ihnen sagen, dass Ihnen die numerische Genauigkeit egal ist. Beispielsweise: das -fassociative-math Möglichkeit von gcc, die es gcc erlaubt, Fließkommaoperationen neu zu assoziieren, oder sogar die -ffast-math Option, die einen noch aggressiveren Kompromiss zwischen Genauigkeit und Geschwindigkeit ermöglicht.


2565
2018-06-22 15:32



Lambdageek weist richtig darauf hin, dass, da die Assoziativität nicht für Fließkommazahlen gilt, die "Optimierung" von a*a*a*a*a*a zu (a*a*a)*(a*a*a) kann den Wert ändern. Aus diesem Grund ist es von C99 nicht erlaubt (es sei denn, der Benutzer hat dies ausdrücklich erlaubt, über Compiler-Flag oder Pragma). Im Allgemeinen ist die Annahme, dass der Programmierer aus einem bestimmten Grund geschrieben hat, was sie getan hat, und der Compiler sollte das respektieren. wenn du willst (a*a*a)*(a*a*a), schreibe das.

Das kann allerdings schmerzhaft sein. Warum kann der Compiler nicht einfach das tun, was Sie für richtig halten? pow(a,6)? Weil es das sein würde falsch etwas zu tun. Auf einer Plattform mit einer guten Mathematikbibliothek, pow(a,6) ist wesentlich genauer als beide a*a*a*a*a*a oder (a*a*a)*(a*a*a). Um nur einige Daten zu liefern, führte ich ein kleines Experiment auf meinem Mac Pro durch, bei dem der schlechteste Fehler bei der Auswertung eines ^ 6 für alle Gleitkommazahlen 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

Verwenden pow anstelle eines Multiplikationsbaums reduziert sich der durch a Faktor 4. Compiler sollten (und machen im Allgemeinen) keine "Optimierungen" vornehmen, die den Fehler erhöhen, wenn sie nicht vom Benutzer lizenziert werden (z. B. über -ffast-math).

Beachten Sie, dass GCC bietet __builtin_powi(x,n) als Alternative zu pow( ), die einen Inline-Multiplikationsbaum erzeugen sollte. Verwenden Sie das, wenn Sie die Genauigkeit für die Leistung abwägen möchten, aber nicht schnell rechnen wollen.


613
2018-06-22 22:39



Ein weiterer ähnlicher Fall: Die meisten Compiler werden nicht optimiert a + b + c + d zu (a + b) + (c + d) (Dies ist eine Optimierung, da der zweite Ausdruck besser pipelined sein kann) und wertet es als gegeben aus (d. h. als (((a + b) + c) + d)). Dies ist auch wegen 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


152
2018-06-23 11:44



Fortran (entworfen für wissenschaftliches Rechnen) hat einen eingebauten Energieoperator, und soweit ich weiß, optimieren Fortran-Compiler im Allgemeinen das Erhöhen auf ganzzahlige Potenzen in ähnlicher Weise wie Sie es beschreiben. C / C ++ hat leider keinen Power Operator, nur die Bibliotheksfunktion pow(). Dies hindert Smart Compiler nicht daran, zu behandeln pow besonders und es für spezielle Fälle schneller zu berechnen, aber es scheint, dass sie es weniger häufig tun ...

Vor einigen Jahren habe ich versucht, es einfacher zu machen, ganzzahlige Potenzen auf optimale Weise zu berechnen, und kam auf das Folgende. Es ist C ++, aber nicht C, und es hängt immer noch davon ab, dass der Compiler ein wenig schlau ist, wie man Dinge optimiert. Hoffentlich finden Sie 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);
}

Aufklärung für Neugierige: Dies ist nicht der optimale Weg, um Kräfte zu berechnen, aber seit Das Finden der optimalen Lösung ist ein NP-vollständiges Problem und das lohnt sich sowieso nur für kleine Kräfte (im Gegensatz zur Verwendung von pow), gibt es keinen Grund, sich mit dem Detail zu beschäftigen.

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

Dies macht es einfach, Mächte einzugeben (keine Notwendigkeit, buchstabieren 6 as mit Parens), und lässt Sie diese Art der Optimierung ohne -ffast-math für den Fall, dass Sie etwas Präzision abhängig wie kompensierte Summe (ein Beispiel, bei dem die Reihenfolge der Operationen wesentlich ist).

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

Hoffe, das kann nützlich sein.

BEARBEITEN:

Das bekomme ich von meinem Compiler:

Zum a*a*a*a*a*a,

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

Zum (a*a*a)*(a*a*a),

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

Zum power<6>(a),

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

74
2018-06-23 10:07



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. Manche Menschen erkennen das nicht und glauben auch, dass * in a * a für die Multiplikation von Zahlen mit beliebiger Genauigkeit steht, ohne dass diese Zahlen mit Fehlern behaftet sind. Der Grund, warum manche Menschen dies nicht erkennen, sind vielleicht die mathematischen Berechnungen, die sie in der Grundschule durchführten: nur mit idealen Zahlen ohne Fehler arbeiten und glauben, dass es in Ordnung ist, "e" während der Multiplikation einfach zu ignorieren. Sie sehen nicht das "e" implizit in "float a = 1.2", "a * a * a" und ähnlichen C-Codes.

Sollte die Mehrheit der Programmierer die Idee, dass C-Ausdruck a * a * a * a * a * a nicht wirklich mit idealen Zahlen arbeitet, erkennen (und ausführen können), wäre der GCC-Compiler dann FREI, um "a * a" zu optimieren * a * a * a * a "in sagen" t = (a * a); t * t * t ", die eine geringere Anzahl von Multiplikationen erfordert. Aber leider weiß der GCC-Compiler nicht, ob der Programmierer, der den Code schreibt, denkt, dass "a" eine Zahl mit oder ohne Fehler ist. Und so wird GCC nur tun, wie der Quellcode aussieht - denn das sieht GCC mit bloßem Auge.

... sobald du weißt, was für ein Programmierer Sie Sie können den Schalter "-ffast-math" verwenden, um GCC mitzuteilen, dass "Hey, GCC, ich weiß, was ich tue!". Dies ermöglicht es GCC, ein * a * a * a * a * a in ein anderes Stück Text umzuwandeln - es sieht anders aus als ein * a * a * a * a * a - berechnet aber immer noch eine Zahl innerhalb des Fehlerintervalls von a * a * a * a * a * a. Das ist in Ordnung, da Sie bereits wissen, dass Sie mit Intervallen arbeiten, nicht mit idealen Zahlen.


49
2018-03-29 06:51



GCC optimiert tatsächlich a * a * a * a * a * a bis (a * a * a) * (a * a * a), wenn a eine ganze Zahl ist. Ich habe es mit folgendem 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 Flags, aber nichts Besonderes. Sie meinen: Read from stdin; Verwenden Sie O2-Optimierungsstufe; Ausgabe-Assembler-Sprachliste anstelle einer Binärdatei; Die Auflistung sollte die Intel-Assembler-Syntax verwenden. Die Eingabe erfolgt in der Sprache C (normalerweise wird die Sprache aus der Eingabedateierweiterung abgeleitet, aber beim Lesen von stdin gibt es keine Dateierweiterung); und schreibe auf stdout.

Hier ist der wichtige Teil der Ausgabe. Ich habe es mit einigen Kommentaren kommentiert, die darauf hinweisen, 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     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

Ich benutze System GCC auf Linux Mint 16 Petra, ein 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 Fließkomma nicht möglich, da Fließkommaarithmetik eigentlich nicht assoziativ ist.


49
2018-06-27 21:03



Kein Poster hat die Kontraktion von Fließkommaausdrücken erwähnt (ISO C Standard, 6.5p8 und 7.12.2). Wenn die FP_CONTRACT Pragma ist eingestellt auf ONkann der Compiler einen Ausdruck wie z a*a*a*a*a*a als einzelne Operation, als ob sie genau mit einer einzigen Rundung ausgewertet würde. Zum Beispiel kann ein Compiler es durch eine interne Leistungsfunktion 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 die vom Endbenutzer bereitgestellten Compileroptionen manchmal falsch verwendet werden.

Der Standardstatus von FP_CONTRACT Pragma ist implementierungsdefiniert, so dass ein Compiler standardmäßig solche Optimierungen durchführen kann. Daher sollte portabler Code, der den IEEE-754-Regeln strikt folgen muss, explizit darauf eingestellt 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 geht es davon aus ON; also für Ziele mit einer Hardware-FMA, wenn man die Transformation verhindern will a*b+c zu fma (a, b, c) muss man eine Option wie z -ffp-contract=off (Um das Pragma explizit zu setzen OFF) oder -std=c99 (Um GCC zu sagen, dass es einer C-Standardversion entspricht, hier C99, folge dem obigen Absatz). In der Vergangenheit verhinderte die letztgenannte Option nicht die Umwandlung, was bedeutet, dass der GCC in diesem Punkt nicht konform war: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44



Wie Lambdageek darauf hingewiesen hat, ist die Float-Multiplikation nicht assoziativ und Sie können weniger Genauigkeit erhalten, aber wenn Sie eine bessere Genauigkeit erhalten, können Sie auch gegen die Optimierung argumentieren, weil Sie eine deterministische Anwendung wollen. Zum Beispiel im Spielesimulations-Client / Server, wo jeder Client die gleiche Welt simulieren muss, in der Fließkommaberechnungen deterministisch sein sollen.


26
2018-06-21 18:52