c++ L'istruzione `if` è ridondante prima del modulo e prima di assegnare le operazioni?




performance arm (4)

Considera il prossimo codice:

unsigned idx;
//.. some work with idx
if( idx >= idx_max )
    idx %= idx_max;

Potrebbe essere semplificato solo alla seconda riga:

idx %= idx_max;

e otterrà lo stesso risultato.

Più volte ho incontrato il prossimo codice:

unsigned x;
//... some work with x
if( x!=0 )
  x=0;

Potrebbe essere semplificato a

x=0;

Le domande:

  • Ha senso usare if e perché? Soprattutto con il set di istruzioni ARM Thumb.
  • Questi potrebbero essere omessi?
  • Quale ottimizzazione fa il compilatore?

Answer #1

Sembra una cattiva idea usare il se c'è, per me.

Hai ragione. Indipendentemente da idx >= idx_max , sarà in idx_max dopo idx %= idx_max . Se idx < idx_max , sarà invariato, indipendentemente dal fatto che if sia seguito o meno.

Mentre si potrebbe pensare che la ramificazione attorno al modulo possa far risparmiare tempo, direi che il vero colpevole è che quando vengono seguite le diramazioni, la pipeline delle moderne CPU deve reimpostare la propria pipeline e questo costa un tempo relativamente lungo. Meglio non dover seguire un ramo, piuttosto che un modulo intero, che costa all'incirca quanto una divisione intera.

EDIT: Risulta che il modulo è piuttosto lento rispetto al ramo, come suggerito da altri qui. Ecco un ragazzo che esamina esattamente la stessa domanda: CppCon 2015: Chandler Carruth "Tuning C ++: Benchmarks, CPU e compilatori! Oh My!" (suggerito in un'altra domanda SO collegata a un'altra risposta a questa domanda).

Questo ragazzo scrive compilatori e ha pensato che sarebbe stato più veloce senza il ramo; ma i suoi parametri di riferimento lo hanno smentito. Anche quando il ramo è stato utilizzato solo il 20% delle volte, è stato testato più rapidamente.

Un altro motivo per non avere il se: una riga di codice in meno da mantenere, e per qualcun altro per enucleare ciò che significa. Il tizio nel link sopra ha effettivamente creato una macro "modulo più veloce". IMHO, questa o una funzione inline è la strada da percorrere per le applicazioni critiche per le prestazioni, perché il tuo codice sarà sempre molto più comprensibile senza il ramo, ma verrà eseguito altrettanto velocemente.

Infine, il ragazzo nel video sopra ha intenzione di rendere nota questa ottimizzazione agli scrittori di compilatori. Pertanto, il if verrà probabilmente aggiunto per te, se non nel codice. Quindi, solo il mod da solo farà, quando ciò avverrà.


Answer #2

Riguarda il primo blocco di codice: si tratta di un micro-ottimizzazione basato sulle raccomandazioni di Chandler Carruth per Clang (vedi here per maggiori informazioni), tuttavia non necessariamente sostiene che sarebbe un micro-ottimizzazione valido in questa forma (usando se piuttosto ternario) o su qualsiasi compilatore.

Modulo è un'operazione ragionevolmente costosa, se il codice viene eseguito spesso e c'è un forte orientamento statistico a un lato o l'altro del condizionale, la previsione del ramo della CPU (data una CPU moderna) ridurrà significativamente il costo dell'istruzione di ramo .


Answer #3

Ci sono un certo numero di situazioni in cui scrivere una variabile con un valore che già detiene può essere più lento di leggerlo, scoprire già tiene il valore desiderato e saltare la scrittura. Alcuni sistemi hanno una cache del processore che invia immediatamente tutte le richieste di scrittura alla memoria. Mentre tali progetti non sono comuni oggi, erano piuttosto comuni in quanto possono offrire una parte sostanziale del miglioramento delle prestazioni che può offrire una cache di lettura / scrittura completa, ma con una piccola parte del costo.

Il codice come sopra può anche essere rilevante in alcune situazioni multi-CPU. La situazione più comune sarebbe quando il codice in esecuzione simultaneamente su due o più core della CPU colpire ripetutamente la variabile. In un sistema di cache multi-core con un modello di memoria forte, un core che vuole scrivere una variabile deve prima negoziare con altri core per acquisire la proprietà esclusiva della linea cache che lo contiene, e deve quindi negoziare nuovamente per rinunciare a tale controllo la prossima volta qualsiasi altro nucleo vuole leggerlo o scriverlo. Tali operazioni possono essere molto costose e i costi dovranno essere sostenuti anche se ogni scrittura memorizza semplicemente il valore già immagazzinato. Se la posizione diventa zero e non viene mai più scritta, tuttavia, entrambi i core possono mantenere simultaneamente la linea della cache per l'accesso non esclusivo in sola lettura e non devono mai negoziare ulteriormente per essa.

In quasi tutte le situazioni in cui più CPU potrebbero colpire una variabile, la variabile dovrebbe essere almeno dichiarata volatile . L'unica eccezione, che potrebbe essere applicabile qui, sarebbe nei casi in cui tutte le scritture su una variabile che si verificano dopo l'inizio di main() memorizzeranno lo stesso valore, e il codice si comporterebbe correttamente indipendentemente dal fatto che qualsiasi negozio di una CPU fosse visibile o meno in un altro. Se fare qualche operazione più volte sarebbe dispendioso ma altrimenti innocuo, e lo scopo della variabile è dire se è necessario farlo, allora molte implementazioni potrebbero essere in grado di generare un codice migliore senza il qualificatore volatile che con, a condizione che non cercare di migliorare l'efficienza rendendo la scrittura incondizionata.

Per inciso, se l'oggetto fosse accessibile tramite puntatore, ci sarebbe un altro motivo possibile per il codice precedente: se una funzione è progettata per accettare o un oggetto const dove un certo campo è zero, o un oggetto non const che dovrebbe avere quel campo impostato su zero, il codice come sopra potrebbe essere necessario per garantire un comportamento definito in entrambi i casi.


Answer #4

Se vuoi capire che cosa sta facendo il compilatore, dovrai solo fare un po 'di montaggio. Raccomando questo sito (ho già inserito il codice dalla domanda)): https://godbolt.org/g/FwZZOb .

Il primo esempio è più interessante.

int div(unsigned int num, unsigned int num2) {
    if( num >= num2 ) return num % num2;
    return num;
}

int div2(unsigned int num, unsigned int num2) {
    return num % num2;
}

genera:

div(unsigned int, unsigned int):          # @div(unsigned int, unsigned int)
        mov     eax, edi
        cmp     eax, esi
        jb      .LBB0_2
        xor     edx, edx
        div     esi
        mov     eax, edx
.LBB0_2:
        ret

div2(unsigned int, unsigned int):         # @div2(unsigned int, unsigned int)
        xor     edx, edx
        mov     eax, edi
        div     esi
        mov     eax, edx
        ret

Fondamentalmente, il compilatore non ottimizzerà il ramo, per ragioni molto specifiche e logiche. Se la divisione intera avesse lo stesso costo del confronto, allora il ramo sarebbe piuttosto inutile. Ma la divisione intera (il quale modulo viene eseguito insieme a quello tipico) è in realtà molto costosa: http://www.agner.org/optimize/instruction_tables.pdf . I numeri variano notevolmente in base all'architettura e alle dimensioni dei numeri interi, ma in genere potrebbe essere una latenza da 15 a 100 cicli.

Prendendo un ramo prima di eseguire il modulo, puoi davvero risparmiare molto lavoro. Notate però: anche il compilatore non trasforma il codice senza un ramo in un ramo a livello di assieme. Questo perché il ramo ha anche un rovescio della medaglia: se il modulo finisce per essere comunque necessario, hai solo perso un po 'di tempo.

Non c'è modo di prendere una decisione ragionevole sull'ottimizzazione corretta senza conoscere la frequenza relativa con cui idx < idx_max sarà vero. Quindi i compilatori (gcc e clang fanno la stessa cosa) scelgono di mappare il codice in modo relativamente trasparente, lasciando questa scelta nelle mani dello sviluppatore.

Quindi quel ramo avrebbe potuto essere una scelta molto ragionevole.

Il secondo ramo dovrebbe essere completamente inutile, perché il confronto e l'assegnazione sono di costo comparabile. Detto questo, puoi vedere nel link che i compilatori non eseguiranno questa ottimizzazione se hanno un riferimento alla variabile. Se il valore è una variabile locale (come nel codice dimostrato), il compilatore ottimizzerà il ramo.

In sintesi, il primo pezzo di codice è forse una ragionevole ottimizzazione, il secondo, probabilmente solo un programmatore stanco.





thumb