2015-03-07 12 views
17

Ho scritto una semplice funzione di Fibonacci come esercizio in C++ (usando Visual Studio) per testare la ricorsione di coda e vedere come funziona.Ricorsione di coda C++ usando variabili a 64 bit

Questo è il codice:

int fib_tail(int n, int res, int next) { 
    if (n == 0) { 
    return res; 
    } 
    return fib_tail(n - 1, next, res + next); 
} 

int main() 
{ 
    fib_tail(10,0,1); //Tail Recursion works 
} 

quando ho compilato utilizzando la modalità di uscita ho visto il gruppo ottimizzato utilizzando l'istruzione JMP a dispetto di una chiamata. Quindi la mia conclusione è stata: la ricorsione della coda funziona. Vedi immagine qui sotto:

Tail Recursion

ho voluto fare alcuni test di performance aumentando la variabile di ingresso n nella mia funzione di Fibonacci. Ho quindi deciso di modificare il tipo di variabile, utilizzato nella funzione, da int a unsigned long long. Poi ho passato un gran numero come: 10e + 08

Questo è ora la nuova funzione:

typedef unsigned long long ULONG64; 

ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) { 
    if (n == 0) { 
    return res; 
    } 
    return fib_tail(n - 1, next, res + next); 
} 

int main() 
{ 
    fib_tail(10e+9,0,1); //Tail recursion does not work 
} 

Quando ho eseguito il codice di cui sopra ho ottenuto un'eccezione di overflow dello stack, che mi ha fatto pensare che la ricorsione in coda è stato non funziona. Ho guardato il montaggio e in effetti ho trovato questo:

Tail Recursion doesn't work

Come si vede ora c'è un chiamata istruzioni mentre io aspettavo solo un semplice JMP. Non capisco il motivo per cui l'uso di una variabile da 8 byte disabilita la ricorsione della coda. Perché il compilatore non esegue un'ottimizzazione in questo caso?

+0

Stai mirando a una piattaforma a 32 bit? –

+0

sì, sto prendendo di mira Win32 – codingadventures

+0

@JohnField È possibile fornire lo smontaggio della funzione VS generato con tipi lunghi lunghi? – rutsky

risposta

8

Questa è una di quelle domande che dovresti chiedere ai ragazzi che eseguono l'ottimizzazione del compilatore per MS: non c'è davvero alcuna ragione tecnica per cui QUALSIASI tipo di ritorno dovrebbe impedire alla coda-ricorsione di essere un salto in quanto tale - ci può essere ALTRI motivi come "il codice è troppo complesso per capire" o alcuni di questi.

clang 3.7 come di un paio di settimane fa chiaramente figure it out:

_Z8fib_tailyyy:       # @_Z8fib_tailyyy 
    pushl %ebp 
    pushl %ebx 
    pushl %edi 
    pushl %esi 
    pushl %eax 
    movl 36(%esp), %ecx 
    movl 32(%esp), %esi 
    movl 28(%esp), %edi 
    movl 24(%esp), %ebx 
    movl %ebx, %eax 
    orl %edi, %eax 
    je .LBB0_1 
    movl 44(%esp), %ebp 
    movl 40(%esp), %eax 
    movl %eax, (%esp)   # 4-byte Spill 
.LBB0_3:        # %if.end 
    movl %ebp, %edx 
    movl (%esp), %eax   # 4-byte Reload 
    addl $-1, %ebx 
    adcl $-1, %edi 
    addl %eax, %esi 
    adcl %edx, %ecx 
    movl %ebx, %ebp 
    orl %edi, %ebp 
    movl %esi, (%esp)   # 4-byte Spill 
    movl %ecx, %ebp 
    movl %eax, %esi 
    movl %edx, %ecx 
    jne .LBB0_3 
    jmp .LBB0_4 
.LBB0_1: 
    movl %esi, %eax 
    movl %ecx, %edx 
.LBB0_4:        # %return 
    addl $4, %esp 
    popl %esi 
    popl %edi 
    popl %ebx 
    popl %ebp 
    retl 


main:         # @main 
    subl $28, %esp 
    movl $0, 20(%esp) 
    movl $1, 16(%esp) 
    movl $0, 12(%esp) 
    movl $0, 8(%esp) 
    movl $2, 4(%esp) 
    movl $1410065408, (%esp)  # imm = 0x540BE400 
    calll _Z8fib_tailyyy 
    movl %edx, f+4 
    movl %eax, f 
    xorl %eax, %eax 
    addl $28, %esp 
    retl 

Lo stesso vale per gcc 4.9.2 se gli date -O2 (ma non in -O1 che era tutto clang necessario)

(E, naturalmente, anche in modalità 64 bit)

Problemi correlati