Come si trasformerebbe un compilatore in un altro se fosse cascata in un interruttore?

Question

Come si trasformerebbe un compilatore in un altro se fosse cascata in un interruttore?

#1 da (14 voti)

1

Non mi piace switch in C e i suoi discendenti. Forse è il bisogno di una pausa o la goffaggine della sintassi che richiede uno spostamento di ingranaggi mentali, non lo so.

Qualunque sia la ragione, scriverò quasi sempre una sequenza di altre condizioni, se le condizioni esaminano la stessa variabile piuttosto che scrivere un interruttore.

Vedo da Esiste una differenza significativa tra l'utilizzo di if / else e di switch-case in C #? che l'opzione è più efficiente nella maggior parte dei casi e mi sono chiesto ...

In che modo un compilatore (per una lingua con C-like if , else e switch ) rileva un numero di condizioni else-if sullo stesso valore e lo riscrive internamente in uno switch?

language-agnostic compiler efficiency

posta billpg 27.03.2015 - 11:41

fonte

1 risposta

Leggi altre domande sui tag language-agnostic compiler efficiency

In che modo il proprietario del prodotto decide in che misura ha avuto successo lo Sprint? [chiuso] Come eseguire il debug di javascript nei browser che non dispongono di un'interfaccia console? [chiuso]

score 14 · Accepted Answer

Il tuo desiderio di ottimizzazione (di trasformare una sequenza di if nell'equivalente di switch ) ha senso solo (come Jörg W Mittag commentato saggiamente) per condizioni idempotenti (che sono indecidibili da rilevare in generale). Ma potremmo limitare queste condizioni ad essere una disgiunzione di test di uguaglianza come x == k dove x è sempre lo stesso ( Modulo SSA ) semplice variabile scalare (ad esempio alcuni dichiarati int variabile locale in C o C ++) che non è modificato nelle parti quindi e k è una costante in fase di compilazione.

Per quanto ne so, alcune versioni di GCC in alcune modalità di ottimizzazione sono state in grado di tale ottimizzazione. E ho appena controllato (a marzo 2015), il mio Clang 3.5 (invocato come clang -O3 -fverbose-asm -S ) sta facendo una tale ottimizzazione con il codice sottostante, mentre il mio GCC 4.9 don ' Farlo (su GNU / Linux / Debian / Sid / x86-64):

 extern void f_a(int);
 extern void f_b(int);
 extern void f_c(int);
 extern void f_d(int);
 extern void f_e(int);
 extern void f_f(int);
 extern void f_g(int);
 extern void f_h(int);
 extern void f_i(int);
 extern void f_j(int);
 extern void f_k(int);
 extern void f_l(int);
 extern void f_m(int);
 extern void f_n(int);

 void f1(int x, int y)
 {
   if (x=='a') f_a(y);
   else if (x=='b') f_b(y);
   else if (x=='c') f_c(y);
   else if (x=='d') f_d(y);
   else if (x=='e') f_e(y);
   else if (x=='f') f_f(y);
   else if (x=='g') f_g(y);
   else if (x=='h') f_h(y);
   else if (x=='i') f_i(y);
   else if (x=='j') f_j(y);
   else if (x=='k') f_k(y);
   else if (x=='l') f_l(y);
   else if (x=='m') f_m(y);
   else if (x=='n') f_n(y);
 }

^{Immagino che GCC non ottimizzi come vuoi perché non vale la pena farlo. GCC sta spesso producendo un codice leggermente più veloce di Clang.}

BTW, switch non è sempre compilato in un salto indiretto. In particolare un interruttore con una dozzina di casi ampiamente diffusi è non compilato usando una tabella di salto, ad es. codice come

unsigned u = something(x); /// practically would be some hash function
switch (u) {
  case 3935272677: do_some_A(x); break;
  case 2389398680: do_some_B(x); break;
  case 1384792968: do_some_C(x); break;
  case 3957729125: do_some_D(x); break;
  case 4174747340: do_some_E(x); break;
  /// etc...
  default: do_other_thing(x); break;
}

^{In pratica con gcc -O3 -fverbose-asm -S tale codice è compilato come un albero di rami.}

Dovresti leggere il documento di Roger Anthony Sayle Un'analisi di Superoptimizer della generazione di codice di rami multipli (Vertice del GCC 2008)

Inoltre, le espressioni match in Ocaml sono forse rilevanti, non sono sempre compilate come una sequenza di test ingenua, ma solitamente come un albero di test.

C'è una letteratura significativa sulla compilazione della corrispondenza del modello . Per cominciare, vedi Algoritmo di rete , e Luc Maranget & Fabrice Le Fessant carta su Ottimizzazione della corrispondenza del modello (ICFP2001); troverai molti articoli e conferenze sull'argomento.

BTW, la tua implicita ipotesi che qualche ramo indiretto sia sempre più veloce di una serie di salti è ingenuo (sui processori correnti), perché di TLB , cache della CPU , predittori di ramo , pipeline di istruzioni , istruzioni di movimenti condizionali della macchina, ecc. ecc. Leggi anche il codice filettato e noti che entrambi GCC e Clang / LLVM accettano il (molto utile) etichetta come valori e estensione goto a C.

Leggi anche GNU gperf generatore di hash perfetto.

Infine, non dovresti preoccuparti e lasciare tali micro-ottimizzazioni al compilatore ! Se ritieni (ma non lo so) che una lunga serie di if è più leggibile di un codice switch lungo come preferisci.