I compilatori C++ possono ottimizzare le istruzioni "if" all'interno dei cicli "for"?

Question

Si consideri un esempio come questo:

if (flag) 
    for (condition) 
    do_something(); 
else 
    for (condition) 
    do_something_else(); 

Se flag non cambia all'interno delle for loop, questo dovrebbe essere semanticamente equivalente a:

for (condition) 
    if (flag) 
    do_something(); 
    else 
    do_something_else(); 

Solo nel primo caso, il codice potrebbe essere molto più tempo (ad esempio se vengono utilizzati più loop for o se do_something() è un blocco di codice che è per lo più identico a do_something_else()), mentre nel secondo caso, il flag viene controllato più volte.

Sono curioso di sapere se gli attuali compilatori C++ (soprattutto, g ++) sarebbero in grado di ottimizzare il secondo esempio per sbarazzarsi dei test ripetuti all'interno del ciclo for. In tal caso, a quali condizioni è possibile?

Answer 1

Sì, se viene stabilito che il flag non cambia e non può essere modificato da do_qualcosa o do_something_else, può essere estratto all'esterno del ciclo. Ho sentito parlare di questo fenomeno chiamato sollevamento del ciclo, ma Wikipedia ha uno entry chiamato "loop invariant code motion".

Se flags è una variabile locale, il compilatore dovrebbe essere in grado di eseguire questa ottimizzazione poiché è garantito che non ha alcun effetto sul comportamento del codice generato.

Se flags è una variabile globale e si chiamano funzioni all'interno del proprio ciclo, potrebbe non eseguire l'ottimizzazione - potrebbe non essere possibile determinare se tali funzioni modificano il globale.

Questo può anche essere influenzato dal tipo di ottimizzazione che si fa - l'ottimizzazione per le dimensioni favorirebbe la versione non sollevata mentre l'ottimizzazione per la velocità probabilmente favorirebbe la versione sollevata.

In generale, questo non è il tipo di cosa di cui dovresti preoccuparti, a meno che la profilatura non ti dica che la funzione è un hotspot e vedi che un codice meno efficiente viene effettivamente generato andando oltre l'assemblaggio del compilatore uscite. Micro-ottimizzazioni come questa dovresti sempre lasciare il compilatore a meno che tu non sia assolutamente necessario.

Answer 2

Sono sicuro che se il compilatore in grado di determinare che la bandiera rimarrà costante, si può fare un po 'shufflling:

const bool flag = /* ... */; 
for (..;..;..;) 
{ 
    if (flag) 
    { 
     // ... 
    } 
    else 
    { 
     // ... 
    } 
} 

Se il flag non è const, il compilatore non può necessariamente ottimizzare il ciclo, perché non posso essere sicuro che flag non cambierà. Può se fa analisi statiche, ma non tutti i compilatori, penso. const è il modo infallibile di dire al compilatore che il flag non cambierà, dopodiché è compito del compilatore.

Come al solito, profilo e scoprire se è davvero un problema.

Answer 3

Si chiama invariante di ciclo e l'ottimizzazione è chiamato ciclo codice invariante movimento e anche codice di sollevamento. Il fatto che sia in un condizionale renderà sicuramente l'analisi del codice più complessa e il compilatore può o non può invertire il ciclo e il condizionale a seconda di quanto intelligente sia l'ottimizzatore.

C'è una risposta generale per ogni caso specifico di questo tipo di domanda, e cioè per compilare il programma e guardare il codice generato.

Answer 4

Sarei cauto nel dire che lo farà. Può garantire che il valore non venga modificato da questo o da un altro thread?

Detto questo, la seconda versione del codice è generalmente più leggibile e probabilmente sarebbe l'ultima cosa da ottimizzare in un blocco di codice.

Answer 5

In generale, sì. Ma non c'è garanzia, e i luoghi in cui il compilatore lo farà sono probabilmente rari.

Ciò che la maggior parte dei compilatori fa senza problemi è il sollevamento di valutazioni immutabili fuori dal ciclo, ad es. se la sua condizione è

if (a<b) .... 

quando A e B non sono influenzati dal ciclo, il confronto verrà effettuato una volta prima del ciclo.

Ciò significa che se il compilatore può determinare la condizione non cambia, il test è economico e il salto previsto è previsto. Ciò a sua volta significa che il test stesso costa un ciclo o nessun ciclo (davvero).

In quali casi la suddivisione del ciclo sarebbe vantaggiosa?

a) un ciclo molto stretto dove il ciclo 1 è un costo significativo
b) l'intero anello con entrambe le parti non si adatta il codice di cache

Ora, il compilatore può solo fare ipotesi sul codice cache, e di solito può ordinare il codice in modo che un ramo si adatti alla cache.

Senza alcuna prova, I'dexpect a) l'unico caso in cui sarebbe stato applicato un tale ottimizzazione, lo stavano ristrutturando è nto sempre la scelta migliore:

In quali casi la divisione del ciclo sarebbe male?

Quando si suddivide il ciclo aumenta la dimensione del codice oltre la cache del codice, si avrà un colpo significativo. Ora, questo riguarda solo te se il ciclo stesso viene chiamato all'interno di un altro ciclo, ma questo è qualcosa che il compilatore di solito non è in grado di determinare.

[modifica]
non ho potuto ottenere VC9 per dividere il seguente ciclo (uno dei pochi casi in cui si potrebbe effettivamente essere utile)

extern volatile int vflag = 0; 

int foo(int count) 
{ 
    int sum = 0; 
    int flag = vflag; 
    for(int i=0; i<count; ++i) 
    { 
     if (flag) 
     sum += i; 
     else 
     sum -= i; 
    } 

    return sum; 
} 

[EDIT 2]
si noti che con int flag = true; il secondo ramo viene ottimizzato. (e no, const non fa la differenza qui;))

Che cosa significa? O non lo supporta, non importa, la mia analisi è sbagliata ;-)

In generale, direi che si tratta di un'ottimizzazione che è valida solo in pochissimi casi e può essere eseguita a mano facilmente nella maggior parte degli scenari.

Answer 6

Come molti hanno detto: dipende.

Se si vuole essere sicuro, si dovrebbe provare a forzare una decisione in fase di compilazione. Modelli spesso sono utili per questo:

for (condition) 
    do_it<flag>(); 

Answer 7

provato con GCC e -O3:

void foo(); 
void bar(); 

int main() 
{ 
    bool doesnt_change = true; 
    for (int i = 0; i != 3; ++i) { 
     if (doesnt_change) { 
      foo(); 
     } 
     else { 
      bar(); 
     } 
    } 
} 

Risultato per la conduttura:

_main: 
pushl %ebp 
movl %esp, %ebp 
andl $-16, %esp 
call ___main 
call __Z3foov 
call __Z3foov 
call __Z3foov 
xorl %eax, %eax 
leave 
ret 

in modo che ottimizzano via la scelta (e srotola anelli più piccoli).

Questa ottimizzazione non viene eseguita se doesnt_change è globale.