gcc è equivalente asm volatile all'impostazione predefinita di gfortran per le ricorsioni?

Question

Stavo solo giocando con le funzioni ricorsive in C++ e Fortran e mi sono reso conto che una semplice funzione ricorsiva in Fortran è quasi due volte più veloce della sua equivalente funzione C++. Ora, prima di entrare in questo, so che ci sono domande simili qui, in particolare:

1. Why does adding assembly comments cause such radical change in generated code?
2. Working of asmvolatile (“” : : : “memory”)
3. Equivalent to asm volatile in gfortran

Tuttavia, io sono un po 'più specifico e perplesso come il Il compilatore Fortran sembra fare ciò che è possibile ottenere con asm volatile in gcc. Per darvi qualche contesto prendiamo in considerazione il seguente ricorsiva Fibonacci number implementazione:

codice Fortran:

module test 
implicit none 
private 
public fib 

contains 

! Fibonacci function 
integer recursive function fib(n) result(r) 
    integer, intent(in) :: n 
    if (n < 2) then 
     r = n 
    else 
     r = fib(n-1) + fib(n-2) 
    end if 
end function ! end of Fibonacci function 
end module 

program fibonacci 
use test, only: fib 
implicit none 
integer :: r,i 
integer :: n = 1e09 
real(8) :: start, finish, cum_time 

cum_time=0 
do i= 1,n 
    call cpu_time(start) 
    r = fib(20) 
    call cpu_time(finish) 
    cum_time = cum_time + (finish - start) 
    if (cum_time >0.5) exit 
enddo 

print*,i,'runs, average elapsed time is', cum_time/i/1e-06, 'us' 
end program 

compilato con:

gfortran -O3 -march=native 

codice C++:

#include <iostream> 
#include <chrono> 
using namespace std; 

// Fib function 
int fib(const int n) 
{ 
    int r; 
    if (n < 2) 
     r = n; 
    else 
     r = fib(n-1) + fib(n-2); 
    return r; 
} // end of fib 

template<typename T, typename ... Args> 
double timeit(T (*func)(Args...), Args...args) 
{ 
    double counter = 1.0; 
    double mean_time = 0.0; 
    for (auto iter=0; iter<1e09; ++iter){ 
     std::chrono::time_point<std::chrono::system_clock> start, end; 
     start = std::chrono::system_clock::now(); 

     func(args...); 

     end = std::chrono::system_clock::now(); 
     std::chrono::duration<double> elapsed_seconds = end-start; 

     mean_time += elapsed_seconds.count(); 
     counter++; 

     if (mean_time > 0.5){ 
      mean_time /= counter; 
      std::cout << static_cast<long int>(counter) 
      << " runs, average elapsed time is " 
      << mean_time/1.0e-06 << " \xC2\xB5s" << std::endl; 
      break; 
     } 
    } 
    return mean_time; 
} 

int main(){ 
    timeit(fib,20); 
    return 0; 
} 

compilato con:

g++ -O3 -march=native 

Timing:

Fortran: 24991 runs, average elapsed time is 20.087 us 
C++ : 12355 runs, average elapsed time is 40.471 µs 

Così gfortran è due volte più veloce rispetto ai non gcc. Guardando il codice assembly, ottengo

Assembly (Fortran):

.L28: 
    cmpl $1, %r13d 
    jle .L29 
    leal -8(%rbx), %eax 
    movl %ecx, 12(%rsp) 
    movl %eax, 48(%rsp) 
    leaq 48(%rsp), %rdi 
    leal -9(%rbx), %eax 
    movl %eax, 16(%rsp) 
    call __bench_MOD_fib 
    leaq 16(%rsp), %rdi 
    movl %eax, %r13d 
    call __bench_MOD_fib 
    movl 12(%rsp), %ecx 
    addl %eax, %r13d 

Assembly (C++):

.L28: 
    movl 72(%rsp), %edx 
    cmpl $1, %edx 
    movl %edx, %eax 
    jle .L33 
    subl $3, %eax 
    movl $0, 52(%rsp) 
    movl %eax, %esi 
    movl %eax, 96(%rsp) 
    movl 92(%rsp), %eax 
    shrl %eax 
    movl %eax, 128(%rsp) 
    addl %eax, %eax 
    subl %eax, %esi 
    movl %edx, %eax 
    subl $1, %eax 
    movl %esi, 124(%rsp) 
    movl %eax, 76(%rsp) 

codici Sia montaggio sono costituiti da blocchi quasi simili/etichette ripetute più e più volte. Come si può vedere, l'assembly Fortran effettua due chiamate alla funzione fib mentre nell'assembly C++, è stato probabilmente srotolato tutte le chiamate ricorsive che probabilmente richiedono più stack push/pop e salti di coda.

Ora, se ho appena messo una linea commento assembly nel codice C++ in questo modo

Modificato il codice C++:

// Fib function 
int fib(const int n) 
{ 
    int r; 
    if (n < 2) 
     r = n; 
    else 
     r = fib(n-1) + fib(n-2); 
    asm(""); 
    return r; 
} // end of fib 

Il codice assembly generato, modifiche

Assembly (C++ modificato):

.L7: 
    cmpl $1, %edx 
    jle .L17 
    leal -4(%rbx), %r13d 
    leal -5(%rbx), %edx 
    cmpl $1, %r13d 
    jle .L19 
    leal -5(%rbx), %r14d 
    cmpl $1, %r14d 
    jle .L55 
    leal -6(%rbx), %r13d 
    movl %r13d, %edi 
    call _Z3fibi 
    leal -7(%rbx), %edi 
    movl %eax, %r15d 
    call _Z3fibi 
    movl %r13d, %edi 
    addl %eax, %r15d 

Ora è possibile visualizzare due chiamate alla funzione fib. li Timing mi dà

Timing:

Fortran: 24991 runs, average elapsed time is 20.087 us 
C++ : 25757 runs, average elapsed time is 19.412 µs 

so l'effetto di asm senza uscita e asm volatile è quella di sopprimere ottimizzazioni del compilatore aggressivi ma in questo caso, gcc pensato che fosse troppo intelligente, ma ha finito per generare un codice meno efficiente in primo luogo.

Quindi la domanda è:

• Perché può gcc non vedere questo "ottimizzazione", quando gfortan chiaramente può?
• La riga di assemblaggio in linea deve essere prima dell'istruzione di reso. Mettilo altrove e non avrà alcun effetto. Perché?
• Questo compilatore di comportamento è specifico? Ad esempio, puoi imitare lo stesso comportamento con clang/MSVC?
• Esistono modi più sicuri per velocizzare le ricorsioni in C o C++ (senza fare affidamento sull'assembly inline o sulla codifica in stile iterativo)? Modelli Variadic forse?

UPDATE:

• Il risultato mostrato sopra sono tutte con gcc 4.8.4. Ho anche provato a compilarlo con gcc 4.9.2 e gcc 5.2 e ottengo risultati identici.
• Il problema può anche essere replicato (fisso?) Se invece di inserire asm dichiaro l'argomento di input come volatile, ovvero (volatile int n) anziché (const int n), sebbene ciò comporterà un rallentamento dei tempi di esecuzione sulla mia macchina.
• Come indicato da Michael Karcher, possiamo invece passare il flag -fno-optimize-sibling-calls per risolvere questo problema. Poiché questo flag è attivato al livello -O2 e oltre, anche la compilazione con -O1 risolve questo problema.
• Ho eseguito lo stesso esempio con clang 3.5.1 con -O3 -march=native e sebbene la situazione non sia identica, clang sembra anche generare un codice più veloce con asm.

Clang Timing:

clang++ w/o asm : 8846 runs, average elapsed time is 56.4555 µs 
clang++ with asm : 10427 runs, average elapsed time is 47.8991 µs 

Answer 1

Vedere le grassetto verso la fine di questa risposta su come ottenere un programma veloce generato da gcc. Leggi la risposta per le risposte alle quattro domande.

La prima domanda presuppone che gfortran sia in grado di visualizzare una possibilità di ottimizzazione che è impossibile visualizzare gcc. In realtà, è vero il contrario. gcc ha identificato qualcosa che considerava una possibilità di ottimizzazione, mentre gfortran lo ha perso. Ahimè, gcc era sbagliato e l'ottimizzazione applicata risulta essere una perdita di velocità del 100% sul sistema (paragonabile alla mia).

Per rispondere alla seconda domanda: l'istruzione asm ha impedito una trasformazione interna che ha reso gcc la possibilità di ottimizzazione errata. Senza la dichiarazione asm, il codice ottenuto (validamente) trasformato:

int fib(const int n) 
{ 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
} 

L'istruzione return contenente la chiamata ricorsiva innesca il "fratello chiama ottimizzazione" che pessimizes codice. Includere l'istruzione asm impedisce di spostare l'istruzione di ritorno su di essa.

Attualmente, ho solo gcc a portata di mano, quindi non posso provare il comportamento di altri compilatori per rispondere alla terza domanda tramite prove, ma questo sembra decisamente dipendente dal compilatore. Ti sei imbattuto in una stranezza (o bug, comunque lo chiami tu) di gcc che genera codice errato mentre cerchi di ottimizzarlo. Gli ottimizzatori di diversi compilatori sono molto diversi, quindi è abbastanza probabile che qualche altro compilatore non ottimizzi male il tuo codice come fa gcc. D'altra parte, le trasformazioni del codice per l'ottimizzazione sono un argomento ben studiato e molti compilatori stanno implementando approcci simili all'ottimizzazione, quindi è possibile che un altro compilatore passi nella stessa trappola come gcc.

Per rispondere all'ultima domanda: non si tratta di un problema di C/C++ rispetto a Fortan, ma di un problema relativo a gcc che compromette questo programma di esempio (e probabilmente programmi di produzione simili). Quindi non v'è alcun modo per make ricorsione più velocemente in C++, ma c'è un modo per accelerare questo esempio in gcc, disabilitando l'ottimizzazione problematico: -fno-optimize-sibling-calls, che risultati (sul mio sistema, in un singolo test eseguito) in un codice ancora più veloce rispetto all'inserimento dell'istruzione asm.