Perché gcc genera un programma più veloce di clang in questo codice ricorsivo di Fibonacci?

Question

Questo è il codice che ho provato:

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

#define CHRONO_NOW     chrono::high_resolution_clock::now() 
#define CHRONO_DURATION(first,last) chrono::duration_cast<chrono::duration<double>>(last-first).count() 

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

int main() { 
    auto t0 = CHRONO_NOW; 
    cout << fib(45) << endl; 
    cout << CHRONO_DURATION(t0, CHRONO_NOW) << endl; 
    return 0; 
} 

Naturalmente, ci sono modi molto più veloce di calcolo dei numeri di Fibonacci, ma questo è un buon test po 'di stress che si concentra su chiamate di funzione ricorsive. Non c'è nient'altro al codice, se non l'uso del cronometro per misurare il tempo.

Prima ho eseguito il test un paio di volte in Xcode su OS X (quindi è clang), utilizzando l'ottimizzazione -O3. Ci sono voluti circa 9 secondi per correre.

Quindi, ho compilato lo stesso codice con gcc (g ++) su Ubuntu (usando di nuovo -O3), e quella versione impiegava solo circa 6,3 secondi per essere eseguita! Inoltre, stavo usando Ubuntu all'interno di VirtualBox sul mio Mac, il che poteva influenzare negativamente la performance, se non del tutto.

Così ci si va:

clangore su OS X -> ~ 9 secondi

gcc su Ubuntu in VirtualBox -> ~ 6.3 sec.

So che si tratta di compilatori completamente diversi, quindi fanno cose diverse, ma tutti i test che ho visto con gcc e clang hanno mostrato solo una differenza minore, e in alcuni casi la differenza era il contrario (clang essere più veloce).

Quindi c'è qualche spiegazione logica perché gcc batte il clang per miglia in questo particolare esempio?

Answer 1

Non direi che i battiti di gcc hanno suonato per miglia. A mio parere, la differenza di prestazioni (6,3 secondi contro 9 secondi) è piuttosto piccola. Sul mio sistema FreeBSD, clang richiede 26.12 secondi e gcc richiede 10.55 secondi.

Tuttavia, il modo per eseguire il debug di questo è utilizzare g ++ -S e clang ++ -S per ottenere l'output dell'assieme.

Ho provato questo sul mio sistema FreeBSD. I file di linguaggio assembly sono troppo lunghi per postare qui, ma sembra che gcc esegua più livelli di inlining nella funzione di calcolo dei fibonacci (ci sono stati 20 fib() chiamate in là!) Mentre clang chiama semplicemente fib (n-1) e fib (n-2) senza livelli di inlining.

A proposito, la mia versione gcc era 4.2.1 20070831 con patch [FreeBSD] e la versione clang era 3.1 (branches/release_31 156863) 20120523. Queste erano le versioni fornite con il sistema di base FreeBSD 9.1-RELEAESE. La CPU è AMD Turion II Neo N40L Processore Dual-Core (1497,54-MHz).

Answer 2

Non ho GCC disponibile, ma GCC 4.9.2 in gcc godbolt srotola veramente tante le chiamate di funzione, mentre Clang chiamata fib due volte ogni iterazione senza ottimizzazione chiamata anche coda come di seguito

fibonacci(int):       # @fibonacci(int) 
    push rbp 
    push rbx 
    push rax 
    mov ebx, edi 
    cmp ebx, 2 
    jge .LBB0_1 
    mov eax, ebx 
    jmp .LBB0_3 
.LBB0_1: 
    lea edi, dword ptr [rbx - 1] 
    call fibonacci(int) 
    mov ebp, eax 
    add ebx, -2 
    mov edi, ebx 
    call fibonacci(int) 
    add eax, ebp 
.LBB0_3: 
    add rsp, 8 
    pop rbx 
    pop rbp 
    ret 

http://goo.gl/SFPWsr

Nella versione GCC c'è solo una chiamata con più di 20 etichette per la chiamata in linea