gcc ottimizza il mio ciclo con condizioni?

Question

Ho il seguente ciclo:

//condition will be set here to true or false 

for (int i = 0; i < LARGE_NUMBER; i++) { 
    if (condition) { 
     //do foo 
    } else { 
     //do bar 
    } 
} 

Assunzione: un ciclo se più velocemente senza una condizione che con una condizione. (È vero?) Domanda: GCC sarà in grado di calcolare il mio if, se condition è stato impostato al di fuori del ciclo for e il ciclo stesso non tocca condition?

In caso contrario, avrei dovuto cambiare il if e la for, duplicare il codice, violare DRY, ecc

Answer 1

Per coloro che non desiderano leggere un post lungo, questa ottimizzazione viene chiamata (in LLVM) Loop Unswitch.

Perché non chiedere un compilatore?

void foo(char* c); 

int main(int argc, char **argv) { 
    bool const condition = argc % 2; 

    for (int i = 0; i != argc; ++i) { 
    if (condition) { 
     foo(argv[1]); 
    } else { 
     foo(argv[0]); 
    } 
    } 
    return 0; 
} 

si trasforma in forma SSA (via LLVM try out):

define i32 @main(i32 %argc, i8** nocapture %argv) { 
entry: 
    %0 = icmp eq i32 %argc, 0      ; <i1> [#uses=1] 
    br i1 %0, label %bb5, label %bb.nph 

bb.nph:           ; preds = %entry 
    %1 = and i32 %argc, 1       ; <i32> [#uses=1] 
    %toBool = icmp eq i32 %1, 0      ; <i1> [#uses=1] 
    %2 = getelementptr inbounds i8** %argv, i64 1 ; <i8**> [#uses=1] 
    br i1 %toBool, label %bb3.us, label %bb3 

bb3.us:           ; preds = %bb3.us, %bb.nph 
    %i.07.us = phi i32 [ %4, %bb3.us ], [ 0, %bb.nph ] ; <i32> [#uses=1] 
    %3 = load i8** %argv, align 8     ; <i8*> [#uses=1] 
    tail call void @_Z3fooPc(i8* %3) 
    %4 = add nsw i32 %i.07.us, 1     ; <i32> [#uses=2] 
    %exitcond = icmp eq i32 %4, %argc    ; <i1> [#uses=1] 
    br i1 %exitcond, label %bb5, label %bb3.us 

bb3:            ; preds = %bb3, %bb.nph 
    %i.07 = phi i32 [ %6, %bb3 ], [ 0, %bb.nph ] ; <i32> [#uses=1] 
    %5 = load i8** %2, align 8      ; <i8*> [#uses=1] 
    tail call void @_Z3fooPc(i8* %5) 
    %6 = add nsw i32 %i.07, 1      ; <i32> [#uses=2] 
    %exitcond8 = icmp eq i32 %6, %argc    ; <i1> [#uses=1] 
    br i1 %exitcond8, label %bb5, label %bb3 

bb5:            ; preds = %bb3, %bb3.us, %entry 
    ret i32 0 
} 

Non troppo leggibile forse, così vorrei sottolineare ciò che è qui:

• entry: controllare se argc è uguale a 0, se lo è, vai a bb5 (uscita) altrimenti vai a bb.nph
• bb.nph: calcolare il valore di condition, se è vero, andare a bb3.us altro andare a bb3
• bb3.us e bb3: loop per il vero e il falso condizione rispettivamente
• bb5: uscita

Un compilatore abbastanza può molto trasforma il tuo codice come vuole, purché l'effetto sia simile a quello che hai chiesto. In questo caso, si ha effettivamente riscritto il codice come:

int main(int argc, char**argv) { 
    if (argc != 0) 
    { 
    int i = 0; 
    if (argc % 2) { 
     do { 
     foo(argv[1]); 
     ++i; 
     } while (i != argc); 
    } else { 
     do { 
     foo(argv[0]); 
     ++i; 
     } while (i != argc); 
    } 
    } 
    return 0; 
} 

E 'una forma di invariante di ciclo Optimization, combinato qui con un primo controllo per evitare il calcolo della condizione, se il ciclo non sta andando ottenere eseguito.

Per quelli di noi che penserebbero che la prima soluzione sia più chiara, siamo abbastanza contenti di avere il compilatore che fa l'ottimizzazione nitty gritty per noi!

Answer 2

Qualsiasi compilatore ottimizzato decente farà questo se condition può essere dimostrato di non cambiare durante l'iterazione.

Inoltre, anche se il compilatore in realtà non lo fa, si farebbe bene a supportare la propria decisione di riscrivere il codice in un formato meno leggibile dall'uomo con dati complessi dalla profilazione. Non ottimizzare in modo prematuro. Non vale la pena di dare ai lettori del codice un "huh?" momento per radersi alcuni millisecondi (e "lettori" sicuramente include te stesso in un momento futuro).

Answer 3

Non vorrei sostenere alcuna azione qui, con i soliti argomenti di "ottimizzazione prematura". Mantenere il codice chiaro è molto importante, e se l'intero programma è troppo lento, è possibile che si desideri creare un profilo e trovare i colli di bottiglia effettivi (che di solito non si può immaginare) dopo che il programma è stato completamente debugato.

Anche se il compilatore non ottimizza questo caso specifico per l'utente, è possibile sapere che la CPU esegue una qualche forma di branch prediction che ridurrà notevolmente il tempo necessario per elaborare la condizione nel caso in cui la condizione sia prevedibile.

Infatti, la maggior parte delle istruzioni di processo della CPU in un pipeline e nel momento in cui deve essere determinato l'indirizzo di salto, la variabile di condizione potrebbe essere sconosciuta. Ciò causerebbe uno stallo della pipeline , ed è qui che i processori più moderni cercano di indovinare (in modo intelligente di fatto) dove il programma salterà. Se la variabile di condizione è effettivamente nota (come nel tuo caso), l'ipotesi sarà perfetta.

Quindi dubito che anche con un compilatore "stupido", si vedrebbe effettivamente una differenza tra le due opzioni, almeno sulle macchine moderne.