Perché una versione ricorsiva di una funzione sarebbe più veloce di una iterativa in C?

Question

Sto verificando la differenza tra due implementazioni della discesa del gradiente, suppongo che dopo l'ottimizzazione del compilatore entrambe le versioni dell'algoritmo sarebbero equivalenti.

Per la mia sorpresa, la versione ricorsiva era significativamente più veloce. Non ho scartato un difetto reale su nessuna delle versioni o persino nel modo in cui sto misurando il tempo. Ragazzi, potete darmi qualche informazione per favore?

Questo è il mio codice:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#include <stdint.h> 

double f(double x) 
{ 
     return 2*x; 
} 

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
//  printf("step ... x:%f Xp:%f, delta:%f\n",xo,xnew,fabs(xnew - xo)); 

     if (fabs(xnew - xo) < precision) 
     { 
       return xnew; 
     } 
     else 
     { 
       descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision) 
{ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision) 
     { 
       //printf("step ... x:%f Xp:%f, delta:%f\n",Xo,Xn,fabs(Xn - Xo)); 
       Xo = Xn; 
       Xn = Xo - eps * f(Xo); 
     } 

     return Xn; 
} 

int64_t timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p) 
{ 
    return ((timeA_p->tv_sec * 1000000000) + timeA_p->tv_nsec) - 
      ((timeB_p->tv_sec * 1000000000) + timeB_p->tv_nsec); 
} 

int main() 
{ 
     struct timespec s1, e1, s2, e2; 

     clock_gettime(CLOCK_MONOTONIC, &s1); 
     printf("Minimum : %f\n",descgraditer(100,99,0.01,0.00001)); 
     clock_gettime(CLOCK_MONOTONIC, &e1); 

     clock_gettime(CLOCK_MONOTONIC, &s2); 
     printf("Minimum : %f\n",descgrad(100,99,0.01,0.00001)); 
     clock_gettime(CLOCK_MONOTONIC, &e2); 

     uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
     uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

     printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

     printf("End. \n"); 
} 

sto compilazione con gcc 4.5.2 su Ubuntu 11.04 con le seguenti opzioni: gcc grad.c -O3 -lrt -o dg

L'uscita del mio codice è:

Minimum : 0.000487 
Minimum : 0.000487 
time_iter:127 ms, time_rec:19 ms, ratio (dif1/dif2) :6.68421 
End. 

ho letto un thread che chiedono anche di una versione ricorsiva di un algoritmo di essere più veloce di quello iterativo. La spiegazione laggiù era che essendo la versione ricorsiva che utilizzava lo stack e l'altra versione che utilizzava alcuni vettori, l'accesso all'heap stava rallentando la versione iterativa. Ma in questo caso (nel migliore dei casi) sto usando lo stack in entrambi i casi.

Mi manca qualcosa? Qualcosa di ovvio che non vedo? Il mio modo di misurare il tempo è sbagliato? Qualche intuizione?

MODIFICA: Mistero risolto in un commento. Come ha affermato @TonyK, l'inizializzazione di printf stava rallentando la prima esecuzione. Mi dispiace di aver perso quella cosa ovvia.

BTW, il codice viene compilato correttamente senza avvisi. Non credo che il "descgrad ritorno (.." è necessaria in quanto la condizione di arresto sta accadendo prima

Answer 1

Ho compilato ed eseguito il codice localmente. Lo spostamento del printf al di fuori del blocco temporizzato fa eseguire entrambe le versioni in ~ 5ms ogni volta.

Quindi un errore centrale nella tempistica è che si misura la bestia complessa di printf e il suo runtime sovrascrive il codice che si sta tentando di misurare.

mio main() -funzione ora assomiglia a questo:

int main() { 
    struct timespec s1, e1, s2, e2; 

    double d = 0.0; 

    clock_gettime(CLOCK_MONOTONIC, &s1); 
    d = descgraditer(100,99,0.01,0.00001); 
    clock_gettime(CLOCK_MONOTONIC, &e1); 
    printf("Minimum : %f\n", d); 

    clock_gettime(CLOCK_MONOTONIC, &s2); 
    d = descgrad(100,99,0.01,0.00001); 
    clock_gettime(CLOCK_MONOTONIC, &e2); 
    printf("Minimum : %f\n",d); 

    uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
    uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

    printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

    printf("End. \n"); 
} 

Answer 2

Per prima cosa, il tuo passo ricorsivo sbaglia un return:.

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
    if (fabs(xnew - xo) < precision) 
     return xnew; 
    else 
     descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
} 

dovrebbe essere:

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
    if (fabs(xnew - xo) < precision) 
     return xnew; 
    else 
     return descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
} 

Questa svista determina il valore restituito di descgrad essere definito, in modo che il compilatore ha appena per generare il codice per affatto;)

Answer 3

In molti casi, i moderni errori di cache hardware sono il fattore limitante delle prestazioni per i costrutti a loop ridotto. Un'implementazione ricorsiva ha meno probabilità di creare errori di cache sul percorso dell'istruzione.

Answer 4

Il mio modo di misurare il tempo è sbagliato?

Sì. Nei tempi brevi che stai misurando, lo scheduler può avere un impatto enorme sul tuo programma. È necessario eseguire il test molto più a lungo per valutare tali differenze o utilizzare CLOCK_PROCESS_CPUTIME_ID per misurare il tempo di CPU utilizzato dal processo.

Answer 5

Per cominciare, si sono stati, tra cui un printf nel tempo si stava tentando di misurare. È sempre un no-no enorme perché può, e molto probabilmente lo farà, sospendere il processo mentre si esegue l'output della console. Effettivamente qualsiasi chiamata di sistema può completamente lanciare misure del tempo come queste.

E in secondo luogo, come qualcuno ha menzionato, in questo breve periodo di campionamento, gli interrupt di scheduler possono avere un impatto enorme.

Questo non è perfetto, ma prova questo per il tuo principale e vedrai che c'è davvero poca differenza. Aumentando il numero di cicli, il rapporto si avvicina a 1.0.

#define LOOPCOUNT 100000 
int main() 
{ 
    struct timespec s1, e1, s2, e2; 
    int i; 
    clock_gettime(CLOCK_MONOTONIC, &s1); 
    for(i=0; i<LOOPCOUNT; i++) 
    { 
     descgraditer(100,99,0.01,0.00001); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &e1); 

    clock_gettime(CLOCK_MONOTONIC, &s2); 
    for(i=0; i<LOOPCOUNT; i++) 
    { 
     descgrad(100,99,0.01,0.00001); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &e2); 

    uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
    uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

    printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

    printf("End. \n"); 

}

EDIT: Dopo aver guardato l'uscita smontato utilizzando objdump -dS ho notato un paio di cose:
Con -O3 ottimizzazione, il codice sopra ottimizza la chiamata di funzione via completamente. Tuttavia, produce ancora codice per le due funzioni e nessuno dei due è effettivamente ricorsivo.

In secondo luogo, con -O0, tale che il codice risultante è effettivamente ricorsivo, la versione ricorsiva è letteralmente un trilione volte più lento. La mia ipotesi è che lo stack di chiamate forza le variabili a finire in memoria dove la versione iterativa esaurisce i registri e/o la cache.

Answer 6

Innanzitutto, clock_gettime sembra misurare l'ora dell'orologio a muro, non il tempo di esecuzione . In secondo luogo, il tempo effettivo che stai misurando è il tempo di esecuzione di printf, non il tempo di esecuzione della tua funzione. E in terzo luogo, la prima volta che si chiama printf, non è in memoria, pertanto è necessario eseguire il paging in , con un numero significativo di I/O disco. Inversa l'ordine si eseguono i test e anche i risultati si invertono.

Se si desidera ottenere alcune misure significative, è necessario fare in modo che

1. solo il codice che si vuole misurare è nei punti di misura, o almeno, il codice addizionale è molto minima rispetto a quello che stai misura,
2. si fa qualcosa con i risultati, in modo che il compilatore non può ottimizzare tutto il codice fuori (non è un problema nei test),
3. si esegue il codice di essere misurato un numero elevato di volte, prendendo la media,
4. di misurare il tempo di CPU, e non di parete di tempo di orologio, e
5. è assicurarsi che tutto sia in paginata prima di iniziare le misurazioni .

Answer 7

La risposta accettata è errata.

Esiste una differenza nei tempi di esecuzione della funzione iterativa e della funzione ricorsiva e il motivo è l'ottimizzazione del compilatore -foptimize-sibling-calls aggiunta da -O3.

In primo luogo, il codice:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#include <stdint.h> 

double descgrad(double xo, double xnew, double eps, double precision){ 
     if (fabs(xnew - xo) <= precision) { 
       return xnew; 
     } else { 
       return descgrad(xnew, xnew - eps*2*xnew, eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision){ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision){ 
       Xo = Xn; 
       Xn = Xo - eps * 2*Xo; 
     } 
     return Xn; 
} 

int main() { 
     time_t s1, e1, d1, s2, e2, d2; 
     int i, iter = 10000000; 
     double a1, a2; 

     s1 = time(NULL); 
     for(i = 0; i < iter; i++){ 
      a1 = descgraditer(100,99,0.01,0.00001); 
     } 
     e1 = time(NULL); 
     d1 = difftime(e1, s1); 

     s2 = time(NULL); 
     for(i = 0; i < iter; i++){ 
      a2 = descgrad(100,99,0.01,0.00001); 
     } 
     e2 = time(NULL); 
     d2 = difftime(e2, s2); 

    printf("time_iter: %d s, time_rec: %d s, ratio (iter/rec): %f\n", d1, d2, (double)d1/d2) ; 
    printf("return values: %f, %f\n", a1, a2); 
} 

messaggi precedenti erano corrette nel sottolineare che è necessario iterare più volte al fine di mediare via interferenze dell'ambiente. Detto questo, ho scartato la funzione di differenziazione in favore della funzione difftimedifftime su time_t dati, dal momento che su molte iterazioni, qualsiasi cosa migliore di un secondo non ha senso. Inoltre, ho rimosso la stampa nel benchmark.

Ho anche corretto un bug nell'implementazione ricorsiva. La dichiarazione if del codice originale è stata verificata per fabs(xnew-xo) < precision, che non è corretto (o almeno diverso dall'implementazione iterativa). I loop iterativi mentre fabs()> precisione, quindi la funzione ricorsiva non dovrebbe recitare quando fabs < = precisione. L'aggiunta di contatori di 'iterazione' a entrambe le funzioni conferma che questa correzione rende la funzione logicamente equivalente.

Compilazione ed esecuzione con -O3:

$ gcc test.c -O3 -lrt -o dg 
$ ./dg 
time_iter: 34 s, time_rec: 0 s, ratio (iter/rec): inf 
return values: 0.000487, 0.000487 

Compilazione ed esecuzione senza -O3

$ gcc test.c -lrt -o dg 
$ ./dg 
time_iter: 54 s, time_rec: 90 s, ratio (iter/rec): 0.600000 
return values: 0.000487, 0.000487 

In nessun ottimizzazione, l'iterazione si comporta meglio di ricorsione.

Sotto l'ottimizzazione -O3, tuttavia, la ricorsione esegue dieci milioni di iterazioni in meno di un secondo. Il motivo è che aggiunge -foptimize-sibling-calls, che ottimizza le chiamate ricorsive di fratello e sorella, che è esattamente ciò che sta sfruttando la funzione ricorsiva.

A dire il vero, mi sono imbattuto sarà tutto -O3 ottimizzazioni ECCETTO -foptimize-sibling-calls:

$ gcc test.c -lrt -o dg -fcprop-registers -fdefer-pop -fdelayed-branch -fguess-branch-probability -fif-conversion2 -fif-conversion -fipa-pure-const -fipa-reference -fmerge-constants -ftree-ccp -ftree-ch -ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-sra -ftree-ter -funit-at-a-time -fthread-jumps -falign-functions -falign-jumps -falign-loops -falign-labels -fcaller-saves -fcrossjumping -fcse-follow-jumps -fcse-skip-blocks -fdelete-null-pointer-checks -fexpensive-optimizations -fgcse -fgcse-lm -fpeephole2 -fregmove -freorder-blocks -freorder-functions -frerun-cse-after-loop -fsched-interblock -fsched-spec -fschedule-insns -fschedule-insns2 -fstrict-aliasing -ftree-pre -ftree-vrp -finline-functions -funswitch-loops -fgcse-after-reload -ftree-vectorize 
$ ./dg 
time_iter: 55 s, time_rec: 89 s, ratio (iter/rec): 0.617978 
return values: 0.000487, 0.000487 

ricorsione, senza l'ottimizzazione coda-chiamata, esegue peggio di iterazione, nello stesso modo di quando si compila con nessuna ottimizzazione. Read about compiler optimizations here.

EDIT:

come una verifica della correttezza ho aggiornato il mio codice comprendono i valori di ritorno. Inoltre, ho impostato due variabili statiche a 0 e incrementato ogni ricorsione e iterazione verificare output corretto:

int a = 0; 
int b = 0; 

double descgrad(double xo, double xnew, double eps, double precision){ 
     if (fabs(xnew - xo) <= precision) { 
       return xnew; 
     } else { 
       a++; 
       return descgrad(xnew, xnew - eps*2*xnew, eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision){ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision){ 
       b++; 
       Xo = Xn; 
       Xn = Xo - eps * 2*Xo; 
     } 
     return Xn; 
} 

int main() { 
    time_t s1, e1, d1, s2, e2, d2; 
    int i, iter = 10000000; 
    double a1, a2; 

    s1 = time(NULL); 
    for(i = 0; i < iter; i++){ 
     a1 = descgraditer(100,99,0.01,0.00001); 
    } 
    e1 = time(NULL); 
    d1 = difftime(e1, s1); 

    s2 = time(NULL); 
    for(i = 0; i < iter; i++){ 
     a2 = descgrad(100,99,0.01,0.00001); 
    } 
    e2 = time(NULL); 
    d2 = difftime(e2, s2); 

    printf("time_iter: %d s, time_rec: %d s, ratio (iter/rec): %f\n", d1, d2, (double)d1/d2) ; 
    printf("return values: %f, %f\n", a1, a2); 
    printf("number of recurs/iters: %d, %d\n", a, b); 
} 

L'output:

$ gcc optimization.c -O3 -lrt -o dg 
$ ./dg 
time_iter: 41 s, time_rec: 24 s, ratio (iter/rec): 1.708333 
return values: 0.000487, 0.000487 
number of recurs/iters: 1755032704, 1755032704 

Le risposte sono gli stessi, e la ripetizione è la stessa .

Anche interessante notare, il recupero/incremento della variabile statica ha un impatto considerevole sull'ottimizzazione di chiamata di coda, tuttavia la ricorsione ancora supera l'iterazione.