Overhead di un'istruzione switch in C
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Io sono abbastanza competente programmatore Java che è molto di nuovo da C.Sto cercando di ottimizzare una routine che ha quattro modalità di funzionamento.
I loop su tutti i pixel di un'immagine e calcolare un nuovo valore del pixel a seconda della 'modalità' passato.
La mia domanda riguarda il sovraccarico di una istruzione switch all'interno di due cicli for annidati.Sarei interessato a eventuali collegamenti alla documentazione per quanto riguarda l'efficienza relativa di base C dichiarazioni, la matematica e le operazioni logiche.
Il codice dovrebbe andare come segue;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
case 1:
weight = (float)x/width;
break;
case 2:
weight = (float)y/height;
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
// Calculate the new pixel value given the weight
...
}
}
Ti aspetteresti di vedere molto in testa se questo era di oltre 5000 x 5000 pixel dell'immagine?Ho provato a fare qualche test, ma i miei risultati sono in tutto il luogo, come il sistema di un Dispositivo Mobile è un sacco di roba in esecuzione in background che potrebbe alterare i risultati.
L'altra opzione è di avere un metodo separato per ogni modalità, ciascuna con il proprio quattro passanti.Questo, ovviamente, introdurre il codice ridondante, ma l'efficienza è il nome del gioco qui.
Grazie in anticipo!
Gav
Soluzione
istruzioni switch compilano a un tavolo salto per valori consecutivi e ad un mazzo di dichiarazioni if-else per i valori sparse. In ogni caso, non si vuole un'istruzione switch nel vostro ciclo interno per l'elaborazione delle immagini, se vi preoccupate per le prestazioni. Si vuole come posto qui sotto.
Inoltre, notare che ho spostato il calcolo peso sul ciclo interno (e scambiato gli anelli per caso 2 per ottenere questo). Questo tipo di pensiero, movimento roba fuori dal ciclo interno, ti porterà le prestazioni desiderate dalla C.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 1:
for (x = 0; x < width; x++) {
weight = (float)x/width;
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 2:
// note - the loops have been swapped to get the weight calc out of the inner loop
for (y = 0; y < height; y++) {
weight = (float)y/height;
for (x = 0; x < width; x++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 4:
weight = dTopRight / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
default:
weight = 1;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
// etc..
}
Altri suggerimenti
Se l'efficienza è più importante della dimensione del codice, allora sì si dovrebbe creare routine ridondanti. L'istruzione case è una delle cose minori costi si possono fare in C, ma non è pari a zero - è costretta a ramificarsi in base alla modalità, e così sta andando a prendere tempo. Se si vuole veramente le prestazioni max, ottenere il caso fuori dal giro, anche a costo di duplicare il ciclo.
istruzioni switch sono circa efficienti come possono eventualmente essere. Sono compilati a una tabella salto. In realtà, questo è il motivo per cui l'interruttore è così limitata come lo è: si può solo scrivere un interruttore per il quale si possono compilare un tabelle di salto sulla base di un valore fisso
.In confronto con la matematica che si sta facendo nel circuito, il sovraccarico del commutatore sarà probabilmente minimo. Detto questo, l'unico modo per essere sicuri è quello di creare diverse versioni per i due approcci diversi, e il tempo loro.
switch / case è estremamente veloce rispetto alla equivalente con if / else: è in genere implementato come una tabella di salto. Tuttavia ha comunque un costo.
Mentre si sta ottimizzando le cose:
1) Prova a ciclo su linee, non oltre le colonne (interruttore x ed y "a" loop), una soluzione può essere incredibilmente più veloce rispetto agli altri, a causa di gestione della memoria cache.
2) Sostituzione di tutte le divisioni dal moltiplicazioni del pre-calcolato) inversa (vi darà guadagno notevole, e probabilmente una perdita di precisione accettabile.
Per l'amor di efficienza è meglio spostare switch al di fuori del ciclo.
mi piacerebbe utilizzare puntatori a funzione in questo modo:
double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */
double (*fun)(void);
switch (mode) /* select the type of calculation */
{
case 0: fun = fun0;
break;
case 1: fun = fun1;
break;
case 2: fun = fun2;
break;
case 3: fun = fun3;
break;
case 4: fun = fun3;
break;
default : fun = fun_default;
break;
}
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Si aggiunge la funzione di chiamata in testa, ma non dovrebbe essere troppo grande, come si passa nessun params alla funzione. Credo che sia un buon compromesso tra prestazioni e la leggibilità.
Modifica Se si utilizza GCC, sbarazzarsi di funzione di chiamata è possibile utilizzare goto e noreferrer etichette come valori: trovare l'etichetta giusta all'interno dello switch e poi basta saltare ad esso ogni volta. Penso che dovrebbe risparmiare qualche cicli.
Interruttori sognerei produrre alcun overhead significativo, vengono compilati in una sorta di matrice di puntatori alla fine bassa, allora è un caso di efficace:
JMP {} baseaddress + switchcasenum
Questo probabilmente dipenderà da quanto bene ramo predittore della CPU è, e come il compilatore genera il codice per l'interruttore. Per un piccolo numero di casi tale, essa può generare un albero di decisione, nel qual caso ramo normale CPU predizione dovrebbe essere in grado di rimuovere la maggior parte del sovraccarico. Le cose potrebbero essere un po 'peggio se genera un tavolo interruttore ...
Detto questo, il modo migliore per scoprirlo è al profilo e vedere.
Oltre ai consigli di Jim, provare a scambiare l'ordine dei cicli. Sia loop-scambio è l'ideale per il caso 1 richiederebbe test, ma ho il sospetto che sia. È quasi sempre vuole coordinare la vostra x all'interno del vostro ciclo interno, al fine di migliorare le prestazioni di paging, in quanto ciò fa sì che la funzione di avere una tendenza migliore per rimanere nella stessa area di memoria generale ogni iterazione. E un dispositivo mobile con le risorse limitted potrebbe avere poca RAM sufficiente che questa differenza sarà sottolineato.
Siamo spiacenti urtare questa discussione, ma mi sembra che l'interruttore è ben lungi dall'essere il problema.
Il vero problema con l'efficienza in questo caso sono le divisioni. Mi sembra che tutti denominatori delle operazioni di divisione sono costanti (larghezza, altezza, max ...) e questi non cambierà durante il corso dell'immagine. Se la mia ipotesi è giusta, allora questi sono semplici variabili che possono cambiare in base all'immagine caricata in modo che qualsiasi immagine formato può essere utilizzato in fase di esecuzione, ora questo permette di qualsiasi dimensione immagine da caricare, ma questo significa anche che il compilatore non è in grado di ottimizzare nella operazione di moltiplicazione più semplice che si potrebbe fare se sono stati dichiarati "const". Il mio suggerimento sarebbe quello di pre-calcolare le inverse di queste costanti e moltiplicarsi. Per quanto posso ricordare, l'operazione di moltiplicazione richiede circa 10 cicli di clock, in cui la divisione prende circa 70. Questo è un aumento di 60 cicli per pixel, e con le 5000x5000 sopra menzionati, che è un aumento stimato velocità di 1,5 secondi su un CPU da 1 GHz.
Dipende sul chip e il compilatore ei dettagli del codice, e ... ma questo sarà spesso essere implementato come una tabella di salto, che dovrebbe essere abbastanza veloce.
BTW-- La comprensione di questo genere di cose è un buon argomento per trascorrere un paio di settimane di apprendimento un po 'di assemblaggio ad un certo punto della tua carriera ...
Utilizzo di un interruttore è probabilmente meglio sia per la velocità e il tempo programmatore. Stai facendo il codice meno ridondante e probabilmente non sarà necessario un nuovo stack frame.
Gli interruttori sono così efficienti che possano utilizzato per magia nera .
ma l'efficienza è il nome del gioco qui.
l'iterazione su un buffer di immagine al fine di calcolare nuovi valori di pixel suona come un tipico problema imbarazzante in parallelo, in questo senso, si potrebbe prendere in considerazione che spinge una parte del lavoro in thread di lavoro, questo dovrebbe accelerare il funzionamento più in particolare di micro-ottimizzazioni ad esempio gli interruttori / caso riguarda.
Inoltre, invece di fare le istruzioni di ramificazione ogni volta, si potrebbe richiamare un puntatore a funzione da un array di puntatori a funzione, dove l'indice serve come identificatore modalità.
In modo che si finisce con le chiamate come ad esempio:
computeWeight[mode](pixel);
Con 5000x5000 pixel, la chiamata di funzione potrebbe anche essere ridotto tramite la funzione di un intervallo di pixel, piuttosto che i singoli pixel.
Si potrebbe anche usare ciclo srotolamento e il passaggio di parametri per riferimento / puntatore, al fine di ottimizzare ulteriormente.
Molti punti buoni sono già date. L'unica cosa che riuscivo a pensare ad aggiungere a questo, è quello di spostare i casi più frequenti in l'interruttore e il basso meno frequente.
Quindi, se caso 4 accade più spesso di quanto il caso 1, dovrebbe essere sopra di esso:
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
Peccato che non stava utilizzando C ++, perché allora l'istruzione switch potrebbe essere sostituito con il polimorfismo.
Cheers!
Ci sono un sacco di suggerimenti creativi in questo thread di modi per non dover scrivere 5 funzioni separate.
A meno che non leggiate 'modo' da un file o da input digitato il metodo di calcolo può essere determinato in fase di compilazione.Come regola generale, non si desidera spostare i calcoli da compilare tempo di esecuzione.
In ogni modo, il codice dovrebbe essere più facile da leggere e non essere confuso, come se o non si vuole mettere in istruzione break nel primo caso o non.
Anche quando si ottiene bug nei dintorni di codice non guardare se il enum è stato impostato su un valore errato o non.
Per quanto riguarda i cicli interni ... 0-> var è meglio fare Varo-> 0 come var-- innesca lo zero Flag (6502 giorni). Questo approccio significa anche "larghezza" viene caricato in x e può essere dimenticato, lo stesso vale per "altezza". pixels anche in memoria sono di solito sinistra> destra, top-> fondo in modo sicuramente x come vostro ciclo interno.
for (y = height; y--;) {
for (x = width; x--;) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Anche ... e molto importante è la vostra istruzioni switch hanno solo 2 casi che utilizzano x o y. Il resto sono costanti.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
break;
//case 1:
// weight = (float)x/width;
// break;
//case 2:
// weight = (float)y/height;
// break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
Quindi, in pratica a meno che la modalità 1 o 2 peso è calcolato prima del ciclo.
... Y loop code here
if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop
... X loop here
if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
calc_pixel_using_weight(weight);
Ho trovato istruzioni switch di essere molto scortese se i dati sono scarsi. Per <4 elementi mi piacerebbe andare per if-then-else e assicurarsi che i casi più comuni sono la parte superiore. Se la prima condizione cattura il 90% dei casi che avete fondamentalmente colpire un home run. Allo stesso modo se qualche altra condizione è <1% metterlo ultima.
