Domanda Perché GCC non ottimizza un * a * a * a * a * a a (a * a * a) * (a * a * a)?


Sto facendo un'ottimizzazione numerica su un'applicazione scientifica. Una cosa che ho notato è che GCC ottimizzerà la chiamata pow(a,2) compilandolo in a*a, ma la chiamata pow(a,6) non è ottimizzato e in realtà chiamerà la funzione di libreria pow, che rallenta notevolmente le prestazioni. (In contrasto, Compilatore Intel C ++, eseguibile icc, eliminerà la richiesta di libreria pow(a,6).)

Quello di cui sono curioso è che quando ho sostituito pow(a,6) con a*a*a*a*a*a usando GCC 4.5.1 e opzioni "-O3 -lm -funroll-loops -msse4", utilizza 5 mulsd Istruzioni:

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

mentre se scrivo (a*a*a)*(a*a*a), produrrà

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

che riduce il numero di istruzioni moltiplicate a 3. icc ha un comportamento simile

Perché i compilatori non riconoscono questo trucco di ottimizzazione?


1965
2018-06-21 18:49


origine


risposte:


Perché Floating Point Math non è associativo. Il modo in cui si raggruppano gli operandi in moltiplicazione in virgola mobile ha un effetto sull'accuratezza numerica della risposta.

Di conseguenza, molti compilatori sono molto prudenti nel riordinare i calcoli in virgola mobile a meno che non siano sicuri che la risposta rimarrà la stessa, oa meno che non dite loro che non vi importa dell'accuratezza numerica. Per esempio: il -fassociative-math opzione di gcc che consente a gcc di riassociare le operazioni in virgola mobile o persino il -ffast-math opzione che consente compromessi ancora più aggressivi di precisione contro la velocità.


2565
2018-06-22 15:32



Lambdageek indica correttamente che l'associatività non è valida per i numeri in virgola mobile, l '"ottimizzazione" di a*a*a*a*a*a a (a*a*a)*(a*a*a) può cambiare il valore. Questo è il motivo per cui non è consentito da C99 (a meno che non sia espressamente consentito dall'utente, tramite flag di compilazione o pragma). Generalmente, il presupposto è che il programmatore abbia scritto quello che ha fatto per una ragione, e il compilatore dovrebbe rispettarlo. Se vuoi (a*a*a)*(a*a*a), scrivilo.

Questo può essere un dolore scrivere, però; perché non è possibile che il compilatore esegua [ciò che consideri essere] la cosa giusta quando lo usi pow(a,6)? Perché sarebbe il sbagliato cose da fare. Su una piattaforma con una buona biblioteca matematica, pow(a,6) è significativamente più preciso di entrambi a*a*a*a*a*a o (a*a*a)*(a*a*a). Solo per fornire alcuni dati, ho eseguito un piccolo esperimento sul mio Mac Pro, misurando il peggiore errore nella valutazione di ^ 6 per tutti i numeri a virgola mobile a precisione singola tra [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

utilizzando pow invece di un albero di moltiplicazione riduce l'errore associato a a fattore di 4. I compilatori non dovrebbero (e generalmente non lo fanno) fare "ottimizzazioni" che aumentano l'errore a meno che la licenza non sia concessa all'utente (ad es. -ffast-math).

Nota che GCC fornisce __builtin_powi(x,n) in alternativa a pow( ), che dovrebbe generare un albero di moltiplicazione in linea. Usalo se vuoi scambiare la precisione con le prestazioni, ma non vuoi abilitare la matematica veloce.


613
2018-06-22 22:39



Un altro caso simile: la maggior parte dei compilatori non ottimizzerà a + b + c + d a (a + b) + (c + d) (questa è un'ottimizzazione poiché la seconda espressione può essere meglio sottoposta a pipeline) e valutarla come data (ad es (((a + b) + c) + d)). Anche questo è dovuto a casi angolari:

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

Questo produce 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Fortran (progettato per il calcolo scientifico) ha un operatore di potenza integrato e, per quanto ne so, i compilatori di Fortran generalmente ottimizzeranno l'aumento dei poteri interi in modo simile a quello che descrivete. C / C ++ sfortunatamente non ha un power operator, solo la funzione di libreria pow(). Ciò non impedisce ai compilatori intelligenti di trattare pow specialmente e calcolandolo in modo più rapido per casi speciali, ma sembra che lo facciano meno comunemente ...

Alcuni anni fa stavo cercando di rendere più conveniente il calcolo dei poteri interi in modo ottimale, e ho scoperto quanto segue. È C ++, non C, e dipende comunque dal fatto che il compilatore sia piuttosto intelligente su come ottimizzare / integrare le cose. Comunque, spero che tu possa trovare utile nella pratica:

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

Chiarimento per i curiosi: questo non trova il modo ottimale per calcolare i poteri, ma da allora trovare la soluzione ottimale è un problema NP-completo e questo vale comunque solo per le piccole potenze (al contrario dell'uso pow), non c'è motivo di lamentarsi dei dettagli.

Quindi usalo come power<6>(a).

Questo rende facile digitare i poteri (non è necessario precisare 6 as con parens), e ti permette di avere questo tipo di ottimizzazione senza -ffast-math nel caso in cui tu abbia qualcosa che dipende dalla precisione come sommatoria compensata (un esempio in cui l'ordine delle operazioni è essenziale).

Probabilmente si può anche dimenticare che questo è C ++ e basta usarlo nel programma C (se si compila con un compilatore C ++).

Spero che questo possa essere utile.

MODIFICARE:

Questo è ciò che ottengo dal mio compilatore:

Per a*a*a*a*a*a,

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

Per (a*a*a)*(a*a*a),

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

Per power<6>(a),

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

74
2018-06-23 10:07



Perché un numero a virgola mobile a 32 bit, come 1.024, non è 1.024. In un computer, 1.024 è un intervallo: da (1.024-e) a (1.024 + e), dove "e" rappresenta un errore. Alcune persone non si rendono conto di questo e credono anche che * in a * a sta per moltiplicazione di numeri arbitrari di precisione senza che vi siano errori associati a quei numeri. Il motivo per cui alcune persone non riescono a rendersi conto di ciò sono forse i calcoli matematici che hanno esercitato nelle scuole elementari: lavorare solo con numeri ideali senza errori, e credere che sia giusto ignorare semplicemente "e" mentre si esegue la moltiplicazione. Non vedono la "e" implicita in "float a = 1.2", "a * a * a" e codici C simili.

Se la maggioranza dei programmatori riconosce (ed è in grado di eseguire) l'idea che l'espressione C a * a * a * a * a * a non sta effettivamente lavorando con numeri ideali, il compilatore GCC sarebbe quindi GRATUITO per ottimizzare "a * a * a * a * a * a "in dire" t = (a * a); t * t * t "che richiede un numero minore di moltiplicazioni. Ma sfortunatamente, il compilatore GCC non sa se il programmatore che scrive il codice pensa che "a" sia un numero con o senza un errore. E così GCC farà solo quello che sembra il codice sorgente - perché è ciò che GCC vede con il suo "occhio nudo".

... una volta che sai che tipo di programmatore tu sei, puoi usare l'opzione "-ffast-math" per dire a GCC che "Ehi, GCC, so cosa sto facendo!". Ciò consentirà a GCC di convertire un * a * a * a * a * a in un altro pezzo di testo - sembra diverso da un * a * a * a * a * a - ma calcola ancora un numero nell'intervallo di errore di a * a * a * a * a * a. Questo è OK, dal momento che sai già che stai lavorando con intervalli, non numeri ideali.


49
2018-03-29 06:51



GCC in realtà ottimizza un * a * a * a * a * a a (a * a * a) * (a * a * a) quando a è un numero intero. Ho provato con questo comando:

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

Ci sono molte bandiere gcc ma niente di speciale. Significa: leggi da stdin; utilizzare il livello di ottimizzazione O2; elenco linguistico assembly di output anziché binario; la lista dovrebbe usare la sintassi del linguaggio assembly assembly; l'input è in linguaggio C (di solito la lingua è dedotta dall'estensione del file di input, ma non c'è estensione del file durante la lettura da stdin); e scrivere su stdout.

Ecco la parte importante dell'output. L'ho annotato con alcuni commenti che indicano cosa sta succedendo nel linguaggio assembly:

    ; 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

Sto usando il sistema GCC su Linux Mint 16 Petra, un derivato di Ubuntu. Ecco la versione di gcc:

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

Come hanno notato altri poster, questa opzione non è possibile in virgola mobile, perché l'aritmetica in virgola mobile non è in realtà associativa.


49
2018-06-27 21:03



Nessun poster ha menzionato la contrazione delle espressioni fluttuanti ancora (ISO C standard, 6.5p8 e 7.12.2). Se la FP_CONTRACT il pragma è impostato su ON, il compilatore può considerare un'espressione come a*a*a*a*a*a come singola operazione, come se fosse valutata esattamente con un singolo arrotondamento. Ad esempio, un compilatore può sostituirlo con una funzione di alimentazione interna che è sia più veloce che più accurata. Ciò è particolarmente interessante in quanto il comportamento è parzialmente controllato dal programmatore direttamente nel codice sorgente, mentre le opzioni del compilatore fornite dall'utente finale possono talvolta essere utilizzate in modo errato.

Lo stato predefinito di FP_CONTRACT pragma è definito dall'implementazione, così che un compilatore è autorizzato a fare tali ottimizzazioni per impostazione predefinita. Quindi il codice portatile che deve seguire rigorosamente le regole IEEE 754 dovrebbe impostarlo esplicitamente OFF.

Se un compilatore non supporta questo pragma, deve essere prudente evitando tali ottimizzazioni, nel caso in cui lo sviluppatore abbia scelto di impostarlo su OFF.

GCC non supporta questo pragma, ma con le opzioni di default, presume che sia ON; quindi per obiettivi con un FMA hardware, se si vuole impedire la trasformazione a*b+c a fma (a, b, c), è necessario fornire un'opzione come -ffp-contract=off (per impostare esplicitamente il pragma su OFF) o -std=c99 (per dire a GCC di conformarsi ad una versione standard C, qui C99, quindi seguire il paragrafo precedente). In passato, quest'ultima opzione non impediva la trasformazione, il che significa che GCC non si è conformato su questo punto: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44