Tempo di elaborazione sproporzionato con operazioni aritmetiche [C]

Question

Qualcuno può spiegare cosa sta succedendo qui con questo piccolo programma?

#include<stdio.h> 

int main() 
{ 
    float a=0.577; 
    float b=0.921; 
    float c; 
    int i; 

    for (i=0;i<100000000;i+=1){ 
     c=0.7*a-0.2*b; 
     //a=0.145*c+2.7*b; 
    } 

    printf ("%.3f\n",c); 
} 

Nota, c'è una riga commentata.

L'ho compilato prima senza linea e poi con la linea. (Usato gcc -O2 ...). E ha misurato il tempo di elaborazione. Sono stato molto sorpreso di scoprire che il tempo di esecuzione era 0.001s versus 2.444s. E questo non ha molto senso. O meglio, ci deve essere una logica dietro questo.

Potete spiegare cosa sta succedendo e come mitigare questo problema?

Lavoro su un programma che elabora enormi quantità di dati e mi sembra che ci si imbatta in un problema di prestazioni molto simile.

Stavo considerando di passare da float a interi ma sembra che con gli interi si comporti lo stesso.

EDIT: Alla fine la soluzione era banale e logica. Quindi ringrazio per tutte le risposte e le spiegazioni!

Answer 1

Nel primo caso il valore calcolato era costante. Il compilatore avrebbe calcolato c = 0.7 * 0.577 - 0.2 * 0.921 al tempo di compilazione. È anche libero di ottimizzare il ciclo in quanto nulla cambia al suo interno (a, b & c sono invarianti).

Nella seconda istanza, a e c variano per ogni iterazione, quindi è necessario calcolare 100000000 volte.

Answer 2

Senza la riga commentata, il compilatore può ottimizzare l'intero ciclo. Il valore impostato non cambia rispetto al loop.

Con la riga con commento, il valore di a cambia ad ogni avvio del ciclo, quindi il ciclo non può essere ottimizzato.

Cioè, il programma e questo:

int main() 
{ 
    float a=0.577; 
    float b=0.921; 
    float c; 
    int i; 

    c=0.7*a-0.2*b; 
    for (i=0;i<100000000;i+=1){ 
     //a=0.145*c+2.7*b; 
    } 

    printf ("%.3f\n",c); 
} 

producono la stessa risposta se e solo se tale linea è commentata.

Answer 3

I buoni ottimizzatori sono molto buoni.

Poiché il calcolo su una riga restituisce lo stesso valore su ogni iterazione, non è necessario ricalcolare nulla nel ciclo, quindi l'ottimizzatore non lo fa.

Quando si modifica anche a (con il calcolo a due righe), è necessario eseguire il ciclo.

Da qui la differenza di tempo.

Answer 4

Ecco il codice che ricevo da compilare vostro esempio con le ottimizzazioni abilitato:

(__TEXT,__text) section 
_main: 
0000000100000f20 pushq %rbp 
0000000100000f21 movq %rsp, %rbp 
0000000100000f24 leaq 61(%rip), %rdi ## literal pool for: %.3f 

0000000100000f2b movsd 45(%rip), %xmm0 
0000000100000f33 movb $1, %al 
0000000100000f35 callq 0x100000f3e ## symbol stub for: _printf 
0000000100000f3a xorl %eax, %eax 
0000000100000f3c popq %rbp 
0000000100000f3d ret 

Si noti che il ciclo non ha nemmeno correre - il compilatore ha ottimizzato fuori del tutto, dal momento che può dire che l'unica assegnazione di c che conta è l'ultimo.

Al contrario, con la linea commentato reinserito, il ciclo deve correre, e il codice di uscita si presenta come:

(__TEXT,__text) section 
_main: 
0000000100000ea0 pushq %rbp 
0000000100000ea1 movq %rsp, %rbp 
0000000100000ea4 movss 148(%rip), %xmm5 
0000000100000eac movl $100000000, %eax 
0000000100000eb1 movsd 143(%rip), %xmm1 
0000000100000eb9 movsd 143(%rip), %xmm2 
0000000100000ec1 movsd 143(%rip), %xmm3 
0000000100000ec9 movsd 143(%rip), %xmm4 
0000000100000ed1 nopw %cs:(%rax,%rax) 
0000000100000ee0 xorps %xmm0, %xmm0 
0000000100000ee3 cvtss2sd %xmm5, %xmm0 
0000000100000ee7 mulsd %xmm1, %xmm0 
0000000100000eeb addsd %xmm2, %xmm0 
0000000100000eef cvtsd2ss %xmm0, %xmm0 
0000000100000ef3 cvtss2sd %xmm0, %xmm0 
0000000100000ef7 movaps %xmm0, %xmm5 
0000000100000efa mulsd %xmm3, %xmm5 
0000000100000efe addsd %xmm4, %xmm5 
0000000100000f02 decl %eax 
0000000100000f04 cvtsd2ss %xmm5, %xmm5 
0000000100000f08 jne 0x100000ee0 
0000000100000f0a leaq 87(%rip), %rdi ## literal pool for: %.3f 

0000000100000f11 movb $1, %al 
0000000100000f13 callq 0x100000f1C## symbol stub for: _printf 
0000000100000f18 xorl %eax, %eax 
0000000100000f1a popq %rbp 
0000000100000f1b ret 

Ben diversa, come si può vedere.

Answer 5

Con la riga a=0.145*c+2.7*b; commentata, l'unica espressione all'interno del ciclo è loop-invariant. Il tuo ottimizzatore lo sa, quindi sposta il calcolo fuori dal ciclo. Quindi l'ottimizzatore rileva che non c'è nulla nel ciclo, quindi elimina il ciclo.

Quando si reimposta la linea, l'espressione non è più inversa di ciclo.