Perché il ciclo di test in basso è preferibile?

Ho sentito qualcuno dire che i compilatori spostano frequentemente le condizioni del ciclo fino alla fine del ciclo. Cioè, loop come questi:Perché il ciclo di test in basso è preferibile?

while (condition) { 
    ... 
}

è così modificata:

if (condition) { 
    do { 
     ... 
    } while (condition); 
}

per quanto riguarda l'ottimizzazione della macchina indipendenti, per cui è preferibile quest'ultima?

fonte

2012-03-20 JohnTortugo

In effetti, il secondo ciclo non valuta la condizione nella parte superiore del ciclo. Salta giù fino al momento in cui continua, come se avesse appena terminato un'iterazione. –

Senza ottimizzazione del compilatore, il primo ciclo va a codice assembly in questo modo:

@@: 
cmp ... ; or test ... 
jz @f 

... 
jmp @b

considerando che il secondo ciclo va a qualcosa di simile:

jmp bottom 

    @@: 
... 

    bottom: 
cmp ... ; or test ... 
jz @b

salti condizionati sono di solito previsti da prendere quindi il primo metodo potrebbe potenzialmente portare a ulteriori svuotamenti della cache delle istruzioni/della pipeline.

Tuttavia, la cosa più importante è che per il primo ciclo, sono disponibili due rami per iterazione del ciclo (2N), mentre nel secondo, ogni iterazione del ciclo ha solo un ramo con un sovraccarico fisso del primo salto incondizionato (N+1).

Per ulteriori informazioni sull'ottimizzazione del loop, vedere pagina 88 di questo assembly optimisation guide.

fonte

2012-03-20 00:25:03

+1 per aver menzionato il predittore di ramo, tuttavia, nel secondo esempio hai dimenticato il salto incondizionato. (Il secondo esempio è un ciclo 'do', vogliamo un ciclo' while'.) Non sei corretto nel dire che il secondo ciclo occupa meno spazio. –

@KendallFrey: buona cattura, aggiornato il codice. –

Un CFG costruito dalla seconda "struttura del loop" ha qualche vantaggio che non è presente quando lo si costruisce dal primo ciclo? Voglio dire, è più incline all'ottimizzazione? – JohnTortugo

Si è parzialmente in errore. L'ottimizzazione tipico è questo:

jmp $test; 
$loop: 
    ; loop statements 
$test: 
    test <condition>; 
    branch-true $loop;

anziché questo:

$loop: 
    test <condition>; 
    branch-false $end; 
    ; loop statements 
    branch loop; 
$end:

che ha due rami in ogni iterazione del ciclo. Un altro vantaggio è che la parte dopo il salto iniziale è identica al codice generato per do/while.

fonte

2012-03-20 09:29:58 EJP

Per la vista di assieme, un ciclo è solo un'istruzione di salto che salta indietro del codice. Quindi il compilatore deve inserire un salto alla fine del ciclo.

Molte istruzioni impostate, come x86, ARM, MIPS forniscono tutte istruzioni di salto/derivazione condizionale. Se il salto avverrà in base alle condizioni specificate nell'istruzione.

Quindi i compilatori preferiscono questo tipo di istruzioni e spostano la condizione alla fine del ciclo per utilizzare le istruzioni.

fonte

2012-03-20 14:36:27

Perché il ciclo di test in basso è preferibile?

risposta

Problemi correlati