Come vengono gestiti switch / case per evitare confronti con i valori del caso?

Question

Come vengono gestiti switch / case per evitare confronti con i valori del caso?

#1 da (7 voti)
#2 da (2 voti)

4

Ho letto più risposte che switch / case evitano confronti "non necessari", ma non l'ho mai imparato all'università, e sono un po 'perplesso su come il programma possa capire a quale caso saltare senza fare un confronto.

Ovviamente, nel caso di int switchVar=3; switch (switchVar) { case 0: ... case 1: ... case 2: ... case 3: ... case n: ... } , questo sarebbe abbastanza semplice, poiché potrebbe semplicemente creare una serie di puntatori che puntano all'inizio del blocco di codice di ogni caso e farebbe semplicemente qualcosa sulla falsariga di% % co_de.

Tuttavia, ciò si interrompe se si dovesse fare un cambio / caso su una stringa, ad es. instructionPointer = switchJumpTable[switchVar]; dove tentare di accedere all'indice "Nord" di un array causerebbe un errore (o se il compilatore ha permesso questo dietro le quinte, non vedo ancora come eviterebbe i confronti quando converte il char array in un intero in per accedere all'array.)

Posso pensare a un modo per aggirare i confronti non necessari, ma non sarebbe terribilmente efficiente, quindi sono curioso di sapere come questo sia effettivamente fatto, dato che non posso immaginare che i compilatori stiano usando il metodo che ho in mente.

optimization switch-statement

posta Michael 28.07.2011 - 06:42

fonte

2 risposte

2

Per gli switch di stringa il compilatore potrebbe creare un trie per controllare rapidamente il caso in cui deve saltare. Potrebbe anche generare uno switch basato sui valori hash dei casi e un doppio controllo in ogni caso.

Questi sono molto più veloci (O (n) con n è la lunghezza della stringa se nessuna collisione hash) di una cascata if-else (O (n * k) n è la lunghezza della stringa k è la quantità di condizioni if).

risposta data 28.07.2011 - 16:13

fonte

Leggi altre domande sui tag optimization switch-statement

Revisione del contratto per la contrattazione internazionale Daily Scrum Meeting (grafico di Burndown)

score 7 · Accepted Answer

La risposta varia Enormous dal singolo compilatore, ma ci sono alcune strategie che "potrebbero" essere usate.

La solita risposta è un jump table. La variabile case viene cercata in una tabella che contiene tutti i valori consentiti e il programma salta all'indirizzo specificato dalla tabella.

Ovviamente, questa è una buona strategia sui modelli di indirizzi piatti usati nelle CPU più vecchie, ma il costo di un ramo indiretto sulle condotte profonde delle moderne CPU è spesso un ordine di grandezza maggiore di un semplice ramo condizionale, (che è a sua volta più costoso di nessun ramo). la ramificazione indiretta di solito interrompe la logica di predizione del ramo sulla maggior parte delle CPU che lo hanno, e quindi le istruzioni dopo il ramo non possono essere precaricate fino a quando l'istruzione di ricerca non è stata completata. Un ramo condizionale regolare può precaricare un lato del ramo e avere una buona possibilità di "indovinare correttamente".

E quindi questa ottimizzazione viene raramente adottata dai compilatori che hanno come target quelle della CPU, e invece l'istruzione case è compilata come un albero di rami condizionali annidati.