Newsgroup: it.comp.lang.c++
Titolo: E' più veloce il case o l' if ?

E' più veloce il case o l' if ?
                                        Alex

E' più veloce il case o l' if ?
Non é tanto una questione di velocità ma di chiarezza e praticità. In
ogni caso 'switch-case' per le condizioni multiple é più veloce di 'if',
poiche quando trova la condizione giusta salta subito in fondo(in
presenza del 'break' ovviamente)mentre di fronte ad una serie di 'if' il
compilatore é costretto a controllarli tutti.
Il Ghenio

E' più veloce il case o l' if ?
Dipende... in generale oltre al fatto che la
switch-case e` piu` leggibile quando ci sono di mezzo molte alternative
(oltretutto non necessariamente in contrasto), e` possibile ottimizzarla
assai piu` di una serie di if. Bisogna considerare diversi fattori, in
primo luogo la bonta` del compilatore, perche` le tecniche esistono ma
potrebbero non essere implementate. Compilatori aggressivi potrebbero
poi fare ottimizzazioni platform dependend (ad esempio penso nei
processori che supportano la predicated execution, tipo il
nuovo processore intel, ma su questo potrei sbagliarmi).
Paolo
-----------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------

 compilatore é costretto a controllarli tutti.
Non è vero. Ad esempio questo
switch ( n )
{
    case 1: pippo(); break;
    case 2: pluto(); break;
    case 3: paperino(); break;
}
è equivalente a questo
if ( n == 1 ) pippo();
else if ( n == 2 ) pluto();
else if ( n == 3 ) paperino();
a meno di eventuali ottimizzazioni (come qualcuno ha sottolineato).
EMG

else if ( n == 3 ) paperino();
E chi mai si metterebbe a programmare in un modo tanto ingarbugliato?
Il Ghenio

 potrebbero non essere implementate.
E' vero che una serie di case è più veloce di una serie di if, ed anche
realizzando un programmino di prova si verifica che se il valore di
confronto è ugulae nel primo if, utilizzare switch o if impiega lo stesso
tempo, ma se il valore di confronto è uguale nell'ultimo if, utlizzare lo
switch è più veloce. Quello che non riesco a capire è il perchè. Come fa lo
switch a non analizzare anche le condizioni precedenti? Dipende dal fatto
che i case possono utilizzare solo valori costanti?


No, probabilmente dipende dai salti e relativi svuotamenti della cda di
prefetch, ma comunque e' "implementation-dependent".
Di solito la catena di if-elseif esegue un test e un salto per ogni
confronto fallito, fino a quello buono che conporta un confronto,
l'esecuzione del corpo e un salto (se non e' l'ultimo) alla fine della
catena. Lo switch esegue n confronti e un salto quando trova quello
buono. Ogni salto potrebbe generare una penalita' di parecchi cicli (a
parte brench-prediction e altre particolarita'). Se il primo test e'
quello giusto, i due metodi dovrebbero essere preticamente identici, o
forse potrebbe essere piu' veloce l'if (un salto in meno, difficile da
misurare).
switch(a)
{
  case 0:
    ...
  case 2:
  default:
}
diventa:
if (a==0) goto label_0;
if (a==2) goto label_0;
....
<default-code>
goto switch_end;
label_0:
  <case_0-code>
  goto switch_end;	// solo se c'e' il break, ovviamente
label_2:
  <case_2-code>
  goto switch_end;
...
switch_end:
....
Piu' o meno. Inoltre, generalmente, lo switch usa un registro per i vari
confronti, anche se non sono state richieste delle ottimizzazioni, e
valuta una volta sola a, mentre l'if valuta a per ogni confronto. Le
cose possono cambiare in caso di ottimizzazioni. Il compilatore potrebbe
modificare la sequenza di if in modo da ottenere piu' o meno lo stesso
codice dello switch.
In caso di test su interi, lo switch potrebbe essere ottimizzato con una
jump table (magari riempita con salti al default):
const void *jmp_table[&label_0, &default, &label_2, ..., &default];	//
ho usato void perche' non esiste un tipo adatto 
if (a<min_label || a>max_label) goto default;
goto jmp_table[a];
....
In caso di parametro 'volatile', lo switch dovrebbe comunque valutare
l'argomento una volta sola, mentre la catena di if e' costretta a
rivalutare sempre, ma questo e' da verificare (al momento non ho a
disposizione ne lo standard ne un compilatore per verificare).
Saluti, A.

 che i case possono utilizzare solo valori costanti?
Mi sa che hai ragione e che ho preso una toppa...
EMG

 E chi mai si metterebbe a programmare in un modo tanto ingarbugliato?
A parte la toppa già dichiarata che ho preso, non capisco dove trovi
ingarbugliamento. Non guardare al fatto che i confronti sono di quel
tipo ma pensa a confronti generici non esprimibili con una costante
(quindi non puoi utilizzare il costrutto switch). Come faresti in modo
più pulito?
EMG



La cosa importante da osservare e` che lo switch-case implementa un
salto a molte vie, mentre l'if ti fornisce un salto a 2 vie.
A. Chessa ti ha gia` detto molto su possibili ottimizzazioni e quindi 
mi limito ad alcune aggiunte...
La prima osservazione e` che grazie alle restrizioni sul tipo di
condizione (sostanzialmente valori interi in qualsiasi linguaggio) e`
possibile arrangiare opportunamente le operazioni per il confronto
tra il valore della guardia e quello delle etichette dei vari rami in
modo da evitare metodi "troppo lenti".
Ma la cosa piu` importante e` che per switch con molte possibilita`
(diciamo piu` di 10) e` possibile pensare all'uso di tabelle hash
con tempi sostanzialmente costanti e paragonabili a
quelli di un if semplice.
Insomma il punto fondamentale e` che lo switch riesce a ridurre
il numero di salti, ma anche il numero di test necessari a capire
cosa eseguire.
Paolo
P.s.
  Prova ad analizzare il codice assembler per una serie di if annidati
  e l'equivalente con un case. Tracciane l'esecuzione con un buon
  debugger e capirai diverse cosette...


in modo più pulito?
In questo caso utilizzare una serie di 'if' é d'obbligo.Anche senza
usare il metodo da te descritto la velocità d'esecuzione non
dovrebbe risultare un problema.
Il Ghenio

 più pulito?
Ma il subject è chiaro in proposito. Se non puoi usare lo switch, ovviamente
è più veloce l'if, dato che non esiste un'alternativa, no?
--
Alessandro Monti


Aspetta. Ricominciamo da capo. Io ho riportato due costrutti da
confrontare, uno switch ed un if-elseif, che danno lo stesso risultato e
un amico ha obiettato che l'if-elseif gli risultava ingarbugliato. A me
questo non sembrava. Tutto qui.
EMG

 Purtroppo di assembler non capisco niente.
Ed e' un vero peccato: se ti interessano questi aspetti ti conviene studiare
un po' di assembler e poi andare a vedere il codice prodotto dal
compilatore. Anche se non sai l'assembler, con il VC puoi provare a seguire
l'esecuzione nella finestra del disassembler. Vedrai anche il codice C++
originale e riuscirai comunque a renderti conto delle differenze.
Nel caso specifico, anche senza conoscere l'asm, si puo dire che:
- If1: esegue sempre tutti test e un assegnamento: giustamente il tempo
impiegato e' invariante.
- If2: se il valore giusto e' l'ultimo, degenera in un If1, deve eseguire
tutti i test, un assegnamento e lo stesso numero di salti. Se il valore e'
il primo, e giustamente il piu' veloce: un test, un assegnamento, un salto e
ha finito. Il tempo impiegato cresce linearmente rispetto al numero di test
che deve fare per ottenere il risultato, cioe' dipende dall'ordine dei
confronti.
- switch: questo sembra proprio un mistero. Prova a farlo girare anche per
2, 3, 4. Con il VC 5.0 si evidenziano tre gruppi di performance:
- medio: value=1 e 4 (hanno in comune il valore dell'assegnamento: bo=3)
- veloce: value=10000 (limite del range)
- lento: tutti gli altri (in range)
Dato che abbiamo un'insieme di performance simili (lento) per piu' valori,
viene da pensare che sia implementato con una jump table (vedi mio msg
precedente), che ha la caratteristica di essere invariante al variare
dell'input. Dato che la jump table implica la verifica dei limiti, il tutto
e' mediamente piu' lento di if2. Se il numero di label fosse molto alto,
mediamente vincerebbe lo switch. L'eccezione su 10000 si spiega con il fatto
che, dovendo verificare i limiti, il compilatore ne approfitta per
verificare anche l'uguaglianza, tipo:
  int tmp=e-10000;
  if (e<0)  goto out_of_range;
  if (e==0) goto case_10000;
(Il vantaggio e' evidente solo se si conosce l'assembler).
Rimane l'eccezione del caso medio. Per svelare l'arcano bisogna guardare
l'assembler: il compilatore, vedendo che ci sono due label con lo stesso
valore (=3), precarica 3 in un registro e nel caso lo usa. Il sistema e'
molto discutibile: aggiungo un tara per precaricare il registro (lo fa
sempre, prima di valutare l'argomento dello switch) per risparmiare qualche
byte. Questa e' un'ottimizzazione in dimensione del codice piuttosto che in
velocita' (VC). In questo caso, il compilatore ha scelto l'ottimizzazione
sbagliata. La jmp table funziona bene per tabelle grandi, in questo caso
sarebbe stato meglio optare per la serie di confronti.
Come vedi i fattori da considerare sono molti e non esiste un'ottimizzazione
migliore in assoluto. Comunque con un gran numero di label lo swtich vince
(mediamente).
Saluti, Alberto.

 questo non sembrava. Tutto qui.
Ah, beh!
Anche a me sembra più ingarbugliato, soprattutto se i confronti sono una
decina invece di 3.
Io poi uso indentare correttamente il codice, per cui mi troverei ad avere
poi difficoltà a leggere e stampare il codice.
Noto invece che in questi casi, tu indenti in modo diverso, posso dire "allo
stesso modo di uno switch"?
In pratica quello che fai tu è "simulare" uno switch con vari <else if>,
cosa comoda (indentazione compresa) quando il confronto da effettuare non è
costruibile con uno switch (anche io faccio così), ma estenderlo anche nei
casi in cui uno switch è applicabile mi sembra una pigrizia mentale inutile,
no?
Quarda qui:
--
Alessandro Monti

 stesso modo di uno switch"?
Premesso che l'indentazione ha sempre un fattore "personale" da considerare,
l'indentazione degli if-elsif in "modo switch" mi sembra corretta da un
pounto di vista della struttura del codice ( il corpo degli if/else dovrebbe
essere indentato, ma non dimentichiamoci che quello era solo un esempio).
if (..)
  else if (..)
     else if (...)
e' "sbagliato", nel senso che fa pensare che la valutazione degli 'if' piu'
interni dipenda dal verificarsi delle condizioni precedenti, mentre in
questo caso e' il contrario. Il ramo 'else' dovrebbe, IMHO, essere sempre
allo stesso livello dell'if principare.
Saluti, A.

 no?
Forse non mi sono ancora spiegato bene: io se si può utilizzare uno
switch lo uso sicuramente. Quello era solo un esempio per far vedere
l'equivalenza tra i due costrutti (equivalenza a meno di
ottimizzazioni).
EMG