Ottimizza le istruzioni nidificate if in un ciclo in C/C++ con GCC

Question

Sto testando varie ottimizzazioni in C/C++ utilizzando il compilatore GCC. Attualmente ho un ciclo con più istruzioni nidificate if. Le condizioni sono calcolate all'inizio dell'esecuzione del programma. Sembra alquanto simili:

bool conditionA = getA(); 
bool conditionB = getB(); 
bool conditionC = getC(); 
//Etc. 

startTiming(); 

do { 
    if(conditionA) { 
     doATrueStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } else { 
     doAFalseStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } 
} while (testCondition()); 

endTiming(); 

Dove doATrueStuff() è una funzione inline che fa qualche semplice calcolo numerico quindi non c'è overhead nella chiamata esso.

Sfortunatamente, le condizioni non possono essere definite in anticipo, devono essere calcolate durante il runtime. Non possiamo nemmeno prevedere in modo affidabile la possibilità che siano veri o sbagliati. getA() potrebbe anche essere rand()%2. Ma una volta calcolato, il loro valore non cambia mai.

Ci sono due soluzioni che ho pensato, uno dei quali puntatori a funzione globali che vengono utilizzati per chiamare la funzione appropriata all'interno del ciclo, in questo modo:

void (*ptrA)(void); 
//Etc. 

int main(int argc, char **argv) { 
    //... 
    if (conditionA) { 
     ptrA=&aTrueFunc; 
    } else { 
     ptrA=&aFalseFunc; 
    } 
    //... 
    do { 
     (*ptrA)(); 
    } while (testCondition()); 
    //... 
} 

In questo modo posso eliminare tutti i rami dalla loop, comunque avrò il sovraccarico di chiamate a funzioni multiple che mi rallentano.

O potrei semplicemente avere un ciclo diverso per ogni combinazione di condizioni, qualcosa di simile:

if(conditionA) { 
    if(conditionB) { 
     do { 
      //Do A == true B == true stuff 
     } while (testCondition()); 
    } else { 
     do { 
      //Do A == true B == false stuff 
     } while (testCondition()); 
    } 
} else { 
    //Etc. 
} 

Tuttavia che è molto meno elegante e ottiene impossibile per uno per fare in modo efficiente una volta che si inizia ad avere troppo molte condizioni, poiché per le condizioni X è necessario scrivere 2^X cicli.

C'è un modo più elegante/più veloce per ottimizzare questo?

C'è addirittura qualche punto in questo o il compilatore in qualche modo capirà che la condizione non cambia durante il ciclo e la ottimizza da sola?

E per curiosità, esiste un altro linguaggio di programmazione che renderebbe la scrittura di tale codice più semplice/possibile? O sarebbe possibile solo usando l'assembly per cambiare le istruzioni del programma una volta caricato in memoria?

Answer 1

La teoria:

Cercando di ottimizzare il codice attraverso alcuni riscrittura stravagante potrebbe rendere difficile per il compilatore di rendere le sue abituali ottimizzazioni.Il compilatore e anche il processore può ottimizzare il codice utilizzando 2 tecniche:

1. Branch predizione: il compilatore può farlo usando profile guided optimizations, principalmente stimando la probabilità di ogni ramo. La CPU ha anche buffer di destinazione branch che cercano di rilevare il pattern di ramificazione, oltre al calcolo delle statistiche per ciascun target.
2. Branch predication: Il compilatore o CPU farà il codice esegue due rami in parallelo (perché oggi processori sono superscalare) e sulla base del risultato condizione, sarà solo ignorare i risultati del percorso non corretto (es cmov istruzioni). È possibile provare a disabilitare la previsione di ramo utilizzando utilizzando: -fno-if-conversion e -fno-if-conversion2. Questo potrebbe essere d'aiuto se ci sono molti calcoli su ciascun ramo e l'esecuzione di tutti i percorsi porterà a uno spreco di decodificatori di istruzioni e porte di esecuzione.

Come semplice sviluppatore, utilizzando gcc, si può anche aiutare branch prediction o la generazione di codice utilizzando le "probabili" e "improbabili" suggerimenti compilazione. Controllare here per ulteriori dettagli. Questo potrebbe funzionare se si è a conoscenza ad esempio che è più probabile che una condizione avvenga rispetto a un'altra.

Per vedere l'efficienza branch prediction, utilizzare perf stat ./binary e controllare il rapporto di ramo perdere, e il numero di miss filiali per ogni ottimizzazione che fai.

Nel tuo caso Codice:

Se conditionA, conditionB e conditionC sono calcolati prima del ciclo, e non cambiano, allora è facile per il predittore ramo per rilevare il modello. Il predittore della CPU lo fa tenendo traccia degli ultimi rami presi/non presi e userà la cronologia registrata per prevedere i seguenti rami. Quindi in realtà mi aspetto una penalità di prestazioni molto bassa a causa di rami nel codice, che puoi verificare come sopra.

Answer 2

Considera modelli. La sfida consiste nel mappare i valori di runtime ai parametri del modello in fase di compilazione. Il boilerplate in basso è una funzione di spedizione per parametro, e il compilatore creerà per te l'albero delle combinazioni. Non esattamente elegante, ma molto migliore della codifica a codice aperto di un piazzamento multiparametrico.

È inoltre possibile utilizzare i parametri del modello (o le loro funzioni) direttamente nei calcoli e anche quelli verranno ottimizzati, ad esempio scegliendo una costante in base a un parametro del modello o moltiplicando uno 0 in un termine di espressione che non vuoi contribuire.

template <bool B0, bool B1, bool B2> 
void doStuffStage3() 
{ 
    // Once you get here, you can use B0, B1, and B2 in 
    // any expressions you want, in the inner loop, and the compiler 
    // will optimize everything out since they're known compile-time. Basically, 
    // the compiler will create separate versions of this function 
    // for all required combinations of the input 
    do { 
     if(B0) { 

     } else { 

     } 
    } while(testCondition()); 
} 

template <bool B0, bool B1> 
void doStuffStage2(bool b2) 
{ 
    if(b2) doStuffStage3<B0,B1,true>(); 
    else doStuffStage3<B0,B1,false>(); 
} 

template <bool B0> 
void doStuffStage1(bool b1, bool b2) 
{ 
    if(b1) doStuffStage2<B0,true> (b2); 
    else doStuffStage2<B0,false>(b2); 
} 

void doStuff(bool b0, bool b1, bool b2) 
{ 
    if(b0) doStuffStage1<true> (b1, b2); 
    else doStuffStage1<false>(b1, b2); 
} 

int main() 
{ 
    doStuff(getA(), getB(), getC()); 
}