Differenze di ottimizzazione GCC in funzioni ricorsive usando le variabili globali

Question

L'altro giorno mi sono imbattuto in uno strano problema utilizzando GCC e il flag di ottimizzazione '-Ofast'. Compilando il seguente programma usando 'gcc -Ostile -o fib1 fib1.c'.

#include <stdio.h> 

int f1(int n) { 
    if (n < 2) { 
     return n; 
    } 
    int a, b; 
    a = f1(n - 1); 
    b = f1(n - 2); 
    return a + b; 
} 

int main(){ 
    printf("%d", f1(40)); 
} 

Quando si misura il tempo di esecuzione, il risultato è:

peter@host ~ $ time ./fib1 
102334155 
real 0m0.511s 
user 0m0.510s 
sys  0m0.000s 

Ora introduciamo una variabile globale nel nostro programma e compilare di nuovo usando 'gcc -o -Ofast fib2 fib2.c'.

#include <stdio.h> 

int global; 

int f1(int n) { 
    if (n < 2) { 
     return n; 
    } 
    int a, b; 
    a = f1(n - 1); 
    b = f1(n - 2); 

    global = 0; 

    return a + b; 
} 

int main(){ 
    printf("%d", f1(40)); 
} 

Ora il tempo di esecuzione è:

peter@host ~ $ time ./fib2 
102334155 
real 0m0.265s 
user 0m0.265s 
sys  0m0.000s 

La nuova variabile globale non fa qualcosa di significativo. Tuttavia, la differenza nei tempi di esecuzione è considerevole.

Oltre alla domanda (1) quale sia la ragione per tale comportamento, sarebbe anche bello se (2) l'ultima prestazione potesse essere raggiunta senza introdurre variabili prive di significato. Eventuali suggerimenti?

Grazie Peter

Answer 1

Sulla mia macchina (gcc (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010) ho questo:
time ./fib1 0,36s user 0,00s system 98% cpu 0,364 total
time ./fib2 0,20s user 0,00s system 98% cpu 0,208 total

Da man gcc:

-Ofast
Ignorare la conformità agli standard rigorosi . -Fast consente tutte le ottimizzazioni -O3. Consente inoltre ottimizzazioni che non sono valide per tutti i programmi conformi agli standard. Attiva -ffast-math e il Fortran-specifico -fno-protect-parens e -fstack-array.

Non così sicuro opzione, proviamo -O2:
time ./fib1 0,38s user 0,00s system 99% cpu 0,377 total
time ./fib2 0,47s user 0,00s system 99% cpu 0,470 total

credo, che alcune delle ottimizzazioni aggressive non sono stati applicati a fib1, ma sono stati applicati a fib2. Quando ho cambiato -Ofast per -O2 - alcune ottimizzazioni non sono state applicate a fib2, ma sono state applicate a fib1.

Proviamo -O0:
time ./fib1 0,81s user 0,00s system 99% cpu 0,812 total
time ./fib2 0,81s user 0,00s system 99% cpu 0,814 total

Sono uguali senza ottimizzazioni.
Quindi introdurre la variabile globale in funzione ricorsiva può rompere alcune ottimizzazioni da un lato e migliorare altre ottimizzazioni dall'altro.

Answer 2

Credo che abbiate ottenuto un'ottimizzazione gcc (mis-?) Molto intelligente e molto strana. Questo è il massimo che ho avuto nella ricerca di questo.

ho modificato il codice per avere un #ifdef G intorno al globale:

$ cc -O3 -o foo foo.c && time ./foo 
102334155 

real 0m0.634s 
user 0m0.631s 
sys  0m0.001s 
$ cc -O3 -DG -o foo foo.c && time ./foo 
102334155 

real 0m0.365s 
user 0m0.362s 
sys  0m0.001s 

Così ho la stessa differenza di prestazioni strano.

In caso di dubbio, leggere l'assemblatore generato.

$ cc -S -O3 -o foo.s -S foo.c 
$ cc -S -DG -O3 -o foog.s -S foo.c 

Qui diventa davvero bizzarro. Normalmente posso seguire facilmente il codice generato da gcc. Il codice generato qui è semplicemente incomprensibile. Quale dovrebbe essere la ricorsione e l'aggiunta piuttosto semplice che dovrebbe rientrare nelle istruzioni 15-20, gcc ha esteso a diverse centinaia di istruzioni con una raffica di turni, aggiunte, sottrazioni, confronti, rami e una grande matrice in pila. Sembra che abbia provato a convertire parzialmente una o entrambe le ricorsioni in un'iterazione e quindi a srotolare quel ciclo. Una cosa che mi ha colpito, però, la funzione non globale avuto solo una chiamata ricorsiva a se stesso (la seconda è la chiamata da principale):

$ grep 'call.*f1' foo.s | wc 
     2  4  18 

Mentre il Global One si doveva:

$ grep 'call.*f1' foog.s | wc 
    33  66  297 

La mia colta (l'ho già visto molte volte) indovina? Gcc ha cercato di essere intelligente e nel suo fervore la funzione che in teoria dovrebbe essere più semplice per ottimizzare il codice peggiore generato mentre la scrittura sulla variabile globale lo ha reso sufficientemente confuso da non poter ottimizzare così tanto da portare a un codice migliore. Questo accade sempre, molte ottimizzazioni che gli usi di gcc (e anche di altri compilatori, non li escludiamo) sono molto specifici per determinati benchmark che usano e potrebbero non generare codice in esecuzione più veloce in molti altri casi. In effetti, dall'esperienza uso sempre -O2 a meno che non abbia valutato con molta attenzione le cose per vedere che -O3 ha senso. Molto spesso no.

Se si vuole veramente per la ricerca questo ulteriore, mi consiglia di leggere la documentazione gcc su quali ottimizzazioni vengono abilitati con -O3 al contrario di -O2 (-O2 non la fanno), quindi provare uno per uno fino a trovare che uno causa questo comportamento e quell'ottimizzazione dovrebbe essere un buon suggerimento per quello che sta succedendo. Stavo per farlo, ma ho finito il tempo (devo fare shopping natalizio dell'ultimo minuto).

Answer 3

Questo deriva dai limiti in linea che si attivano in precedenza nella seconda versione. Perché la versione con la variabile globale fa di più. Ciò suggerisce fortemente che l'inlining peggiora le prestazioni durante il run-time in questo particolare esempio.

Compilare entrambe le versioni con -Ofast -fno-inline e la differenza di tempo è scomparsa. In effetti, la versione senza la variabile globale viene eseguita più velocemente.

In alternativa, contrassegnare la funzione con __attribute__((noinline)).