Sovraccarico di un'istruzione switch in C

Question

Sono un programmatore Java abbastanza competente che è molto nuovo per C. Sto cercando di ottimizzare una routine che ha quattro modalità operative.

I loop su tutti i pixel di un'immagine e calcola un nuovo valore di pixel in base alla "modalità" passata.

La mia domanda riguarda il sovraccarico di un'istruzione switch all'interno di due cicli annidati. Sarei interessato a qualsiasi link alla documentazione riguardante l'efficienza relativa delle istruzioni di base C, matematica e operazioni logiche.

Il codice dovrebbe essere 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 
      ... 
      }    

    } 

Ci si aspetterebbe di vedere molte spese generali se si tratta di un'immagine di 5000 x 5000 pixel? Ho provato a fare qualche test, ma i miei risultati sono dappertutto perché il sistema (dispositivo mobile) ha tutti i tipi di roba in esecuzione in background che potrebbero distorcere i risultati.

L'altra opzione consiste nell'avere un metodo separato per ciascuna modalità, ognuna con i suoi quattro loop. Questo ovviamente introdurrebbe codice ridondante ma l'efficienza è il nome del gioco qui.

Grazie in anticipo!

Gav

Answer 1

istruzioni switch compilare una tabella salto per valori consecutivi e ad un gruppo di istruzioni if-else per valori sparse. In ogni caso, non vuoi un'istruzione switch nel tuo ciclo interno per l'elaborazione delle immagini se ti interessi delle prestazioni. Vuoi invece come 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 da 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.. 
} 

Answer 2

Rispetto la matematica che si sta facendo nel circuito, il sovraccarico del commutatore sarà probabilmente minimo. Detto questo, l'unico modo per essere sicuri è creare versioni differenti per i due diversi approcci e crearli.

Answer 3

Le dichiarazioni di commutazione sono più efficienti che possono essere. Sono compilati su un tavolo da salto. In effetti, questo è il motivo per cui l'interruttore è limitato così com'è: puoi solo scrivere un interruttore per il quale tu è possibile compilare una tabella di salto basata su un valore fisso.

Answer 4

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

Answer 5

Se l'efficienza è più importante della dimensione del codice, quindi sì, dovresti creare routine ridondanti. La dichiarazione del caso è una delle cose generali più basse che puoi fare in C, ma non è zero: dovrà essere basata sulla modalità, quindi ci vorrà del tempo. Se vuoi davvero prestazioni massime, estrai il caso, anche a costo di duplicare il ciclo.

Answer 6

Ciò dipenderà probabilmente dalla qualità del predittore di ramo della CPU e dal modo in cui il compilatore genera il codice per lo switch. Per un numero così limitato di casi, potrebbe generare un albero decisionale, nel qual caso la normale previsione del ramo CPU dovrebbe essere in grado di rimuovere la maggior parte del sovraccarico. Le cose potrebbero essere un po 'peggiori se genera un tavolo degli interruttori ...

Detto questo, il modo migliore per scoprirlo è profilare e vedere.

Answer 7

Dipende dal chip e dal compilatore e dai dettagli del codice, e ... ma questo sarà spesso implementato come una tabella di salto, che dovrebbe essere piuttosto veloce.

BTW-- Capire questo tipo di cose è una buona argomentazione per passare un paio di settimane ad imparare qualche assemblea ad un certo punto della tua carriera ...

Answer 8

L'utilizzo di un interruttore è probabilmente migliore sia per la velocità che per il tempo del programmatore. Stai facendo un codice ridondante e probabilmente non richiederà un nuovo stack frame.

interruttori sono così efficaci che possano utilizzato per davvero strano e confuso black magic.

Answer 9

Oltre ai consigli di Jim, provare a scambiare l'ordine dei cicli. Se lo scambio di cicli è ideale per il caso 1 richiederebbe un test, ma sospetto che lo sia. Quasi sempre vuoi la tua coordinata x all'interno del tuo loop interno per migliorare le prestazioni di paging, poiché questo fa sì che la tua funzione abbia una migliore tendenza a rimanere nella stessa area di memoria generale ogni iterazione. E un dispositivo mobile con risorse limitate potrebbe avere una ram abbastanza bassa che questa differenza verrà enfatizzata.

Answer 10

Switch/case è estremamente veloce rispetto all'equivalente con if/else: in genere viene implementato come tabella di salto. Tuttavia ha ancora un costo.

cose mentre si sta ottimizzando:

1) cercare di ciclo su linee, non sopra le colonne (interruttore x e y "per" loop), una soluzione può essere incredibilmente più veloce rispetto agli altri, a causa di memoria cache gestione.

2) Sostituzione di tutte le divisioni dal moltiplicazioni del pre-calcolato) inversa (vi darà guadagno notevole, e probabilmente una perdita di precisione accettabile.

Answer 11

ma l'efficienza è il nome del gioco qui.

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 delle micro-ottimizzazioni come i problemi di switch/case.

Inoltre, invece di eseguire ogni volta le istruzioni di ramificazione, è possibile richiamare un puntatore a funzione da una serie di puntatori di funzione, in cui l'indice funge da identificatore di modalità.

In modo che si finisce con le chiamate, quali:

computeWeight[mode](pixel); 

Con 5000x5000 pixel, il sovraccarico di funzione di chiamata potrebbe anche essere ridotto chiamando la funzione per una serie 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 questo ulteriore.

Answer 12

Per l'amor di efficienza è meglio spostare switch fuori del ciclo.

userei 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 
      ... 
     } 
} 

aggiunge la funzione di chiamata in testa, ma non dovrebbe essere troppo grande, come si passa nessun params alla funzione. Penso che sia un buon compromesso tra prestazioni e leggibilità.

EDIT: Se si utilizza GCC, sbarazzarsi di funzione di chiamata è possibile utilizzare goto e labels as values: trovare l'etichetta giusta all'interno dello switch e poi basta saltare ad ogni volta. Penso che dovrebbe risparmiare qualche altro ciclo.

Answer 13

Molti buoni punti sono già dati. L'unica cosa che potrei pensare di aggiungere a questo, è spostare i casi più frequenti nell'interruttore e il minimo frequente in basso.

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!

Answer 14

Ci scusiamo per il bump di questo thread, ma mi sembra che l'interruttore sia LONTANO rispetto al problema.

Il vero problema con l'efficienza in questo caso sono le divisioni. Mi sembra che tutti i denominatori delle operazioni di divisione siano costanti (larghezza, altezza, massimo ...) e questi non cambieranno nel corso dell'immagine. Se la mia ipotesi è giusta, allora queste sono variabili semplici che possono cambiare in base all'immagine caricata in modo che qualsiasi immagine di dimensione possa essere utilizzata in fase di esecuzione, ora questo consente di caricare qualsiasi dimensione dell'immagine, ma ciò significa anche che il compilatore non può ottimizzarle nell'operazione di moltiplicazione molto più semplice che potrebbe fare se venissero dichiarati "const". Il mio suggerimento sarebbe di pre-calcolare gli invers di queste costanti e moltiplicare. Per quanto posso ricordare, l'operazione di moltiplicazione richiede circa 10 cicli di clock, dove la divisione impiega circa 70. Si tratta di un aumento di 60 cicli per pixel, e con il già citato 5000x5000, si tratta di un aumento di velocità stimato di 1,5 secondi su un CPU da 1 GHz.

Answer 15

Ci sono molti suggerimenti creativi in ​​questo thread di modi per non dover scrivere 5 funzioni separate.

A meno che non si legge "modo" da un file o da un input immesso, il metodo di calcolo può essere determinato al momento della compilazione. Come regola generale, non si desidera spostare i calcoli dal tempo di compilazione al tempo di esecuzione.

In entrambi i casi il codice sarebbe più facile da leggere e nessuno sarebbe confuso sul fatto che si intendesse o meno inserire l'istruzione break nel primo caso oppure no.

Inoltre, quando si ricevono errori nel codice circostante, non è necessario cercare se l'enum è stato impostato sul valore errato oppure no.