Quanto l'ordine delle etichette caso pregiudicare l'efficienza delle istruzioni switch?

StackOverflow https://stackoverflow.com/questions/1827406

Domanda

Si consideri: 

if (condition1)
{
    // Code block 1
}
else
{
    // Code block 2
}

Se io so che condition1 sarà true la maggior parte del tempo, allora dovrei codificare la logica come scritto, invece che: 

if (!condition1)
{
    // Code block 2
}
else
{
    // Code block 1
}

dal eviterò la sanzione della jump al secondo blocco di codice (nota: ho una conoscenza limitata del linguaggio assembly). Questo idea portare avanti le dichiarazioni switch ed etichette case? 

switch (myCaseValue)
{
    case Case1:
        // Code block 1
        break;

    case Case2:
        // Code block 2
        break;

    // etc.
}

Se io so che uno dei casi accadrà più spesso, posso modificare l'ordine delle etichette case in modo che sia più efficiente? Dovrei? Nel mio codice ho ordinando le etichette caso in ordine alfabetico per la leggibilità del codice senza veramente pensarci. È questo micro-ottimizzazione?

È stato utile?

Soluzione

Alcuni fatti per l'hardware moderno come x86 o x86_64:

  • Un ramo incondizionatamente preso non ha quasi nessun costo aggiuntivo, oltre alla decodifica. Se volete un numero, si tratta di un ciclo di clock trimestre.
  • Un ramo condizionale, che è stato previsto correttamente, non ha quasi nessun costo aggiuntivo.
  • Un ramo condizionale, che non era stato previsto correttamente, ha una penalità pari alla lunghezza delle tubazioni processore, questo è circa 12-20 orologi, a seconda dell'hardware.
  • I meccanismi di previsione sono molto sofisticati. Loop con un basso numero di iterazioni (sul Core 2 ad esempio fino a 64) possono essere perfettamente previsto. I piccoli modelli di ripetere come "presa-presa-nottaken-presa" possono essere previsti, se non sono troppo lunghi (IIRC 6 su Core2).

Si può leggere di più su branch prediction in Agner nebbie ottimo manuale .

istruzioni switch sono generalmente sostituite da un tavolo salto dal compilatore. Nella maggior parte dei casi l'ordine dei casi non farà la differenza a tutti. Ci sono meccanismi di previsione per salti indiretti pure.

Quindi la domanda non è se i vostri salti sono più probabilità di essere preso, è se sono ben prevedibili, almeno per l'hardware si intende eseguire il codice su. Questa non è una domanda facile a tutti. Ma se si dispone di filiali a seconda di una condizione casuale (o pseudo casuale), si potrebbe provare a riformulare come una dichiarazione senza rami, se possibile.

Altri suggerimenti

Il tuo conclusione per quanto riguarda l'if non sarà vero sulla maggior parte dell'hardware ho familiarità con. Il problema non è che si stanno saltando, ma che si sta ramificazione. Il codice potrebbe andare in due modi diversi, a seconda del risultato di un confronto. Questo può stallo della pipeline sulla maggior parte delle moderne CPU. Branch prediction è comune, e corregge il problema il più delle volte, ma non ha niente a che fare con il vostro esempio. Il predittore può ugualmente bene prevedere che il confronto sarà falsa in quanto si può che sarà vero.

Come al solito, vedi Wikipedia: Branch Predictor

Dipende. Il compilatore utilizzi un gruppo di criteri interni di attuazione-dipendente per decidere se applicare il switch come una sequenza di if-test simile, o come tavolo salto. Questo potrebbe dipendere, ad esempio, su come "compatto" il set di etichette case è. Se i valori delle etichette case formano un insieme "densa", il compilatore è probabilmente più propensi a usare una tabella di salto, nel qual caso l'ordine di etichette case non importa. Se si decide di andare con quello che assomiglia ad una serie di test if-else, l'ordine potrebbe materia.

Tenete a mente, però, che il corpo di switch è una grande dichiarazione, con le etichette case che forniscono molteplici punti di ingresso in questa affermazione. Per questo motivo, la capacità compilatori (così come la tua) per riorganizzare le case "sub-blocchi" all'interno di tale dichiarazione potrebbe essere limitata.

etichette di caso devono essere ordinati nel modo più efficiente per migliorare la leggibilità.

Riordinamento etichette custodia per l'efficienza è un caso di ottimizzazione prematura a meno che un profiler ha specificatamente detto che questo è un problema.

Credo che anche il vostro premessa iniziale - che è possibile ottimizzare la dichiarazione if riorganizzando il condizionale potrebbe essere difettoso. In un accumulo non ottimizzato si potrebbe trovare a fare quello che stai parlando ha un certo valore - forse. Nel caso generale si sta andando ad avere per saltare almeno una volta per entrambi i casi, quindi non c'è alcun vantaggio (in generale) per organizzare il condizionale in ogni caso. Ma questo è non ottimizzato costruisce, quindi chi se ne frega che l'ottimizzazione?

In ottimizzato costruisce, penso che si potrebbe essere sorpresi da ciò che un compilatore a volte genera per un'istruzione if. Il compilatore può muovere uno o l'altro (o entrambi) i casi da qualche out-of-line. Penso che si cerca di ottimizzare questo ingenuamente giocando con la quale condizione 'viene prima' non necessariamente fare quello che vuoi. Nella migliore delle ipotesi si dovrebbe fare questa operazione solo dopo aver esaminato ciò che il compilatore sta generando. E, naturalmente, questo diventa un processo costoso, dal momento che anche il minimo cambiamento si effettua in giro la dichiarazione può cambiare come il compilatore decide di generare il codice di uscita.

Ora, per quanto riguarda l'istruzione switch è interessato, ho sempre andare con l'utilizzo di un switch quando si rende il codice più leggibile. La cosa peggiore che un compilatore dovrebbe fare con una dichiarazione switch che è equivalente a una dichiarazione if è quello di generare lo stesso codice. Per più di un paio di casi, passare le dichiarazioni saranno generalmente compilati come una tabella di salto. Ma poi di nuovo una serie di test if che stanno confrontando una singola variabile ad un insieme di valori potrebbe benissimo essere riconosciuto da un compilatore tale che farà lo stesso. Tuttavia, direi che l'utilizzo di un interruttore permetterà di compilatore di riconoscere la situazione molto più facilmente.

Se siete veramente interessati a ottenere il massimo delle prestazioni di quel condizionale, si potrebbe considerare l'utilizzo di qualcosa come Profilo guidata di MSVC Optimization (PGO o 'pogo'), che utilizza i risultati di profiling corre per ottimizzare il modo in condizionali vengono generati. Non so se o non se GCC ha funzionalità simili.

Non sono sicuro circa il compilatore C #, ma so che in assemblea un'istruzione switch può effettivamente essere programmato come un salto ad una linea specifica, piuttosto che valutare l'espressione come un'istruzione if. Dato che in un selezionato avete tutte le costanti, solo che tratta casi, come i numeri di riga e passare direttamente al numero della linea (valore caso) superato in senza alcuna valutazione. Questo rende l'ordine dei casi di dichiarazioni non importa a tutti.

Suppongo che tu sei consapevole che sarà importa solo se questo è un hotspot. Il modo migliore per dire se si tratta di un hotspot è quello di eseguire il codice, campionare il contatore di programma, e vedere se è in là oltre il 10% del tempo. Se si tratta di un hotspot, vedere quanto tempo viene speso nel fare la if o switch. Di solito è trascurabile, a meno che il Block 1 e / o Block 2 fanno quasi non . È possibile utilizzare un profiler per questo. Ho solo una pausa ripetutamente.

Se non hai familiarità con il linguaggio assembly Vorrei suggerire impararla, abbastanza per capire ciò che il compilatore genera. E 'interessante e non è difficile.

Come altri hanno detto, dipende da un sacco di cose, tra quanti casi ci sono, come l'ottimizzazione è fatto, e l'architettura si sta girando. Per una panoramica interessante, vedi http://ols.fedoraproject.org/ GCC / Ristampe-2008 / Sayle-reprint.pdf

Se si mettono i casi che si verificano più spesso prima, questo sarà ottimizzare il codice un po ', e per il modo in statments interruttore funzionano lo stesso è vero. Quando il programma va in interruttore e trova un caso che è vero, sarà eseguirlo e ha colpito pausa, che uscirà fuori dal giro. Il tuo pensiero è corretto.

Comunque, io credo che questa ottimizzazione è piuttosto minimale, e se rallenta i tempi di sviluppo per fare questo, probabilmente non vale la pena. Anche se si deve modificare il programma flusso drasticamente per ospitare questo, non è probabilmente vale la pena. Si sta salvando solo un paio di cicli al massimo e probabilmente non avrebbe mai vedere il miglioramento.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top