Limitazioni delle istruzioni switch C#: perché?

StackOverflow https://stackoverflow.com/questions/44905

  •  09-06-2019
  •  | 
  •  

Domanda

Quando si scrive un'istruzione switch, sembrano esserci due limitazioni su ciò che è possibile attivare nelle istruzioni case.

Per esempio (e sì, lo so, se stai facendo questo genere di cose probabilmente significa che il tuo orientato agli oggetti (OO) l'architettura è incerta: questo è solo un esempio inventato!),

  Type t = typeof(int);

  switch (t) {

    case typeof(int):
      Console.WriteLine("int!");
      break;

    case typeof(string):
      Console.WriteLine("string!");
      break;

    default:
      Console.WriteLine("unknown!");
      break;
  }

Qui l'istruzione switch() fallisce con "È previsto un valore di tipo integrale" e le istruzioni case falliscono con "È previsto un valore costante".

Perché sono in vigore queste restrizioni e qual è la giustificazione sottostante?Non vedo alcun motivo per cui l'istruzione switch ha soccombere solo all'analisi statica e perché il valore da attivare deve essere intero (cioè primitivo).Qual è la giustificazione?

È stato utile?

Soluzione

Questo è il mio post originale, che ha suscitato qualche dibattito... perché è sbagliato:

L'istruzione Switch non è la stessa cosa di una grande istruzione IF-ELSE.Ogni caso deve essere unico e valutato staticamente.L'istruzione Switch fa un ramo di tempo costante indipendentemente da quanti casi hai.L'istruzione IF-ELSE valuta ogni condizione fino a quando non ne trova una vera.

In effetti, l'istruzione switch C# lo è non sempre un ramo temporale costante.

In alcuni casi il compilatore utilizzerà un'istruzione switch CIL che è in effetti un ramo temporale costante che utilizza una tabella di salto.Tuttavia, in rari casi, come sottolineato da Ivan Hamilton il compilatore potrebbe generare qualcos'altro completamente.

Questo è in realtà abbastanza semplice da verificare scrivendo varie istruzioni switch C#, alcune sparse, altre dense, e osservando il CIL risultante con lo strumento ildasm.exe.

Altri suggerimenti

È importante non confondere l'istruzione switch C# con l'istruzione switch CIL.

Lo switch CIL è una tabella di salto che richiede un indice in un insieme di indirizzi di salto.

Ciò è utile solo se i casi dell'opzione C# sono adiacenti:

case 3: blah; break;
case 4: blah; break;
case 5: blah; break;

Ma di scarsa utilità se non lo sono:

case 10: blah; break;
case 200: blah; break;
case 3000: blah; break;

(Avresti bisogno di una tabella di circa 3000 voci, con solo 3 slot utilizzati)

Con espressioni non adiacenti, il compilatore può iniziare a eseguire controlli lineari if-else-if-else.

Con insiemi di espressioni non adiacenti più grandi, il compilatore può iniziare con una ricerca nell'albero binario e infine con if-else-if-else gli ultimi elementi.

Con i set di espressioni contenenti gruppi di elementi adiacenti, il compilatore può eseguire la ricerca nell'albero binario e infine uno switch CIL.

Questo è pieno di "mays" e "mights" e dipende dal compilatore (può differire con Mono o Rotor).

Ho replicato i tuoi risultati sulla mia macchina utilizzando casi adiacenti:

tempo totale per eseguire un cambio a 10 vie, 10000 iterazioni (ms):25.1383
tempo approssimativo per interruttore a 10 vie (ms):0,00251383

tempo totale per eseguire un cambio a 50 vie, 10000 iterazioni (ms):26.593
tempo approssimativo per interruttore a 50 vie (ms):0,0026593

tempo totale per eseguire un cambio a 5000 vie, 10000 iterazioni (ms):23.7094
tempo approssimativo per interruttore a 5000 vie (ms):0,00237094

tempo totale per eseguire un cambio di 50000 vie, 10000 iterazioni (ms):20.0933
tempo approssimativo per cambio di 50000 vie (ms):0.00200933

Poi ho anche usato espressioni maiuscole e minuscole non adiacenti:

tempo totale per eseguire un cambio a 10 vie, 10000 iterazioni (ms):19.6189
tempo approssimativo per interruttore a 10 vie (ms):0,00196189

tempo totale per eseguire un cambio a 500 vie, 10000 iterazioni (ms):19.1664
tempo approssimativo per interruttore a 500 vie (ms):0,00191664

tempo totale per eseguire un cambio a 5000 vie, 10000 iterazioni (ms):19.5871
tempo approssimativo per interruttore a 5000 vie (ms):0,00195871

Un'istruzione case switch 50.000 non adiacente non verrebbe compilata.
"Un'espressione è troppo lunga o complessa per essere compilata vicino a 'ConsoleApplication1.Program.Main(string[])'

La cosa divertente qui è che la ricerca dell'albero binario appare un po' (probabilmente non statisticamente) più veloce dell'istruzione di commutazione CIL.

Brian, hai usato la parola "costante", che ha un significato molto preciso dal punto di vista della teoria della complessità computazionale.Mentre il semplicistico esempio di intero adiacente può produrre CIL che è considerato O(1) (costante), un esempio sparso è O(log n) (logaritmico), gli esempi raggruppati si trovano da qualche parte nel mezzo e gli esempi piccoli sono O(n) (lineare ).

Questo non risolve nemmeno la situazione String, in cui un file static Generic.Dictionary<string,int32> può essere creato e subirà un sovraccarico definito al primo utilizzo.Le prestazioni qui dipenderanno dalle prestazioni di Generic.Dictionary.

Se controlli il Specifica del linguaggio C# (non le specifiche CIL) Troverai "15.7.2 L'istruzione Switch" non fa menzione di "tempo costante" o che l'implementazione sottostante utilizzi anche l'istruzione CIL switch (fai molta attenzione a assumere tali cose).

In fin dei conti, uno switch C# rispetto a un'espressione intera in un sistema moderno è un'operazione inferiore al microsecondo e normalmente non vale la pena preoccuparsi.

Naturalmente questi tempi dipenderanno dalle macchine e dalle condizioni.Non presterei attenzione a questi test di temporizzazione, le durate dei microsecondi di cui stiamo parlando sono sminuite da qualsiasi codice "reale" eseguito (e devi includere del "codice reale" altrimenti il ​​compilatore ottimizzerà il ramo), o jitter nel sistema.Le mie risposte si basano sull'utilizzo IL DASM per esaminare il CIL creato dal compilatore C#.Naturalmente, questo non è definitivo, poiché le istruzioni effettive eseguite dalla CPU vengono quindi create dal JIT.

Ho controllato le istruzioni finali della CPU effettivamente eseguite sulla mia macchina x86 e posso confermare un semplice interruttore di set adiacente che fa qualcosa del tipo:

  jmp     ds:300025F0[eax*4]

Dove una ricerca di albero binario è piena di:

  cmp     ebx, 79Eh
  jg      3000352B
  cmp     ebx, 654h
  jg      300032BB
  …
  cmp     ebx, 0F82h
  jz      30005EEE

Il primo motivo che mi viene in mente è storico:

Poiché la maggior parte dei programmatori C, C++ e Java non sono abituati ad avere tali libertà, non le richiedono.

Un altro motivo, più valido, è che il la complessità del linguaggio aumenterebbe:

Innanzitutto occorre confrontare gli oggetti .Equals() o con il == operatore?Entrambi sono validi in alcuni casi.Dovremmo introdurre una nuova sintassi per fare questo?Dovremmo consentire al programmatore di introdurre il proprio metodo di confronto?

Inoltre, consentirebbe di accendere gli oggetti rompere le ipotesi sottostanti sull'istruzione switch.Ci sono due regole che governano l'istruzione switch che il compilatore non sarebbe in grado di applicare se gli oggetti potessero essere attivati ​​(vedere la sezione Specifica del linguaggio C# versione 3.0, §8.7.2):

  • Che i valori delle etichette degli interruttori lo sono costante
  • Che i valori delle etichette degli interruttori lo sono distinto (in modo che sia possibile selezionare un solo blocco di switch per una determinata espressione di switch)

Considera questo esempio di codice nel caso ipotetico in cui fossero consentiti valori case non costanti:

void DoIt()
{
    String foo = "bar";
    Switch(foo, foo);
}

void Switch(String val1, String val2)
{
    switch ("bar")
    {
        // The compiler will not know that val1 and val2 are not distinct
        case val1:
            // Is this case block selected?
            break;
        case val2:
            // Or this one?
            break;
        case "bar":
            // Or perhaps this one?
            break;
    }
}

Cosa farà il codice?Cosa succede se le dichiarazioni dei casi vengono riordinate?In effetti, uno dei motivi per cui C# ha reso illegale il fall-through dello switch è che le istruzioni switch potrebbero essere riorganizzate arbitrariamente.

Queste regole esistono per una ragione: in modo che il programmatore possa, osservando un blocco caso, sapere con certezza la condizione precisa in cui viene inserito il blocco.Quando la suddetta istruzione switch raggiunge le 100 righe o più (e lo farà), tale conoscenza ha un valore inestimabile.

A proposito, VB, avendo la stessa architettura sottostante, consente una maggiore flessibilità Select Case istruzioni (il codice sopra funzionerebbe in VB) e produce comunque codice efficiente dove ciò è possibile, quindi l'argomento relativo al vincolo tecnico deve essere considerato attentamente.

Per lo più, tali restrizioni sono in vigore a causa dei progettisti del linguaggio.La giustificazione di fondo potrebbe essere la compatibilità con la storia del linguaggio, gli ideali o la semplificazione della progettazione del compilatore.

Il compilatore può (e lo fa) scegliere di:

  • creare una grande dichiarazione if-else
  • utilizzare un'istruzione di commutazione MSIL (tabella di salto)
  • Costruisci un dizionario genericou003Cstring,int32> , popolalo al primo utilizzo e chiama generico.dizionario <> :: trygetValue () per un indice da passare a un'istruzione switch MSIL (tabella di salto)
  • Utilizzare una combinazione di salti IF-ElSes & MSIL "Switch"

L'istruzione switch NON È un ramo temporale costante.Il compilatore potrebbe trovare scorciatoie (usando hash bucket, ecc.), ma casi più complicati genereranno codice MSIL più complicato con alcuni casi che si diramano prima di altri.

Per gestire il caso String, il compilatore finirà (ad un certo punto) per utilizzare a.Equals(b) (e possibilmente a.GetHashCode() ).Penso che sarebbe banale per il compilatore utilizzare qualsiasi oggetto che soddisfi questi vincoli.

Per quanto riguarda la necessità di espressioni maiuscole e minuscole statiche...alcune di queste ottimizzazioni (hashing, memorizzazione nella cache, ecc.) non sarebbero disponibili se le espressioni maiuscole e minuscole non fossero deterministiche.Ma abbiamo già visto che a volte il compilatore sceglie comunque la semplicistica strada if-else-if-else...

Modificare: lomaxx - La tua comprensione dell'operatore "typeof" non è corretta.L'operatore "typeof" viene utilizzato per ottenere l'oggetto System.Type per un tipo (niente a che fare con i relativi supertipi o interfacce).Controllare la compatibilità in fase di esecuzione di un oggetto con un determinato tipo è compito dell'operatore "is".L'uso di "typeof" qui per esprimere un oggetto è irrilevante.

Mentre sull'argomento, secondo Jeff Atwood, l'affermazione switch è un'atrocità di programmazione.Usateli con parsimonia.

Spesso è possibile eseguire la stessa operazione utilizzando una tabella.Per esempio:

var table = new Dictionary<Type, string>()
{
   { typeof(int), "it's an int!" }
   { typeof(string), "it's a string!" }
};

Type someType = typeof(int);
Console.WriteLine(table[someType]);

Non vedo alcun motivo per cui l'istruzione switch debba soccombere solo all'analisi statica

È vero, non è così Avere to, e molti linguaggi infatti utilizzano istruzioni switch dinamiche.Ciò significa tuttavia che riordinare le clausole "case" può modificare il comportamento del codice.

Ci sono alcune informazioni interessanti dietro le decisioni di progettazione che sono entrate in "switch" qui: Perché l'istruzione switch C# è progettata per non consentire il fall-through, ma richiede comunque un'interruzione?

Consentire espressioni maiuscole e minuscole dinamiche può portare a mostruosità come questo codice PHP:

switch (true) {
    case a == 5:
        ...
        break;
    case b == 10:
        ...
        break;
}

che francamente dovrebbe semplicemente usare il file if-else dichiarazione.

Microsoft finalmente ti ha sentito!

Ora con C# 7 puoi:

switch(shape)
{
case Circle c:
    WriteLine($"circle with radius {c.Radius}");
    break;
case Rectangle s when (s.Length == s.Height):
    WriteLine($"{s.Length} x {s.Height} square");
    break;
case Rectangle r:
    WriteLine($"{r.Length} x {r.Height} rectangle");
    break;
default:
    WriteLine("<unknown shape>");
    break;
case null:
    throw new ArgumentNullException(nameof(shape));
}

Questo non è un motivo per cui, ma la sezione 8.7.2 delle specifiche C# afferma quanto segue:

Il tipo che governa un'istruzione switch è stabilito dall'espressione switch.Se il tipo dell'espressione switch è sbyte, byte, short, ushort, int, uint, long, ulong, char, string o un tipo enum, allora quello è il tipo che governa l'istruzione switch.Altrimenti deve esistere esattamente una conversione implicita definita dall'utente (§6.4) dal tipo dell'espressione switch a uno dei seguenti possibili tipi governanti:sbyte, byte, short, ushort, int, uint, long, ulong, char, stringa.Se non esiste alcuna conversione implicita o se esiste più di una conversione implicita, si verifica un errore in fase di compilazione.

La specifica C# 3.0 si trova in:http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

La risposta di Judah sopra mi ha dato un'idea.Puoi "falsificare" il comportamento dell'interruttore dell'OP sopra usando a Dictionary<Type, Func<T>:

Dictionary<Type, Func<object, string,  string>> typeTable = new Dictionary<Type, Func<object, string, string>>();
typeTable.Add(typeof(int), (o, s) =>
                    {
                        return string.Format("{0}: {1}", s, o.ToString());
                    });

Ciò consente di associare il comportamento a un tipo nello stesso stile dell'istruzione switch.Credo che abbia l'ulteriore vantaggio di essere codificato invece di una tabella di salto in stile interruttore quando compilato in IL.

Suppongo che non vi sia alcun motivo fondamentale per cui il compilatore non possa tradurre automaticamente la tua istruzione switch in:

if (t == typeof(int))
{
...
}
elseif (t == typeof(string))
{
...
}
...

Ma non c'è molto da guadagnare da questo.

Un'istruzione case sui tipi integrali consente al compilatore di apportare una serie di ottimizzazioni:

  1. Non c'è duplicazione (a meno che non si duplichino le etichette dei casi, rilevate dal compilatore).Nel tuo esempio potrebbe corrispondere a più tipi a causa dell'ereditarietà.La prima partita dovrebbe essere eseguita?Tutti loro?

  2. Il compilatore può scegliere di implementare un'istruzione switch su un tipo integrale tramite una tabella di salto per evitare tutti i confronti.Se stai attivando un'enumerazione che ha valori interi da 0 a 100, crea un array con 100 puntatori al suo interno, uno per ciascuna istruzione switch.In fase di esecuzione cerca semplicemente l'indirizzo dall'array in base al valore intero attivato.Ciò garantisce prestazioni di runtime molto migliori rispetto all'esecuzione di 100 confronti.

Secondo la documentazione dell'istruzione switch se esiste un modo inequivocabile per convertire implicitamente l'oggetto in un tipo integrale, allora sarà consentito.Penso che ti aspetti un comportamento in cui per ogni affermazione del caso verrebbe sostituita if (t == typeof(int)), ma ciò aprirebbe un intero vaso di fiori quando si arriva a sovraccaricare quell'operatore.Il comportamento cambierebbe quando i dettagli di implementazione per l'istruzione switch cambiassero se scrivessi il tuo == override in modo errato.Riducendo i confronti con tipi integrali e stringhe e con quelle cose che possono essere ridotte a tipi integrali (e sono destinate a farlo) si evitano potenziali problemi.

ha scritto:

"L'istruzione switch esegue un ramo temporale costante indipendentemente dal numero di casi presenti."

Poiché la lingua lo consente corda tipo da utilizzare in un'istruzione switch presumo che il compilatore non sia in grado di generare codice per un'implementazione di ramo temporale costante per questo tipo e debba generare uno stile if-then.

@mweerden - Ah, capisco.Grazie.

Non ho molta esperienza in C# e .NET, ma sembra che i progettisti del linguaggio non consentano l'accesso statico al sistema di tipi se non in circostanze ristrette.IL tipo di La parola chiave restituisce un oggetto, quindi è accessibile solo in fase di esecuzione.

Penso che Henk abbia centrato l'obiettivo con la cosa "nessun accesso statico al sistema dei tipi".

Un'altra opzione è che non esiste un ordine per i tipi dove possono essere numeri e stringhe.Pertanto un cambio di tipo non può costruire un albero di ricerca binario, ma solo una ricerca lineare.

Sono d'accordo con questo commento che utilizzare un approccio basato su tabelle è spesso migliore.

In C# 1.0 ciò non era possibile perché non disponeva di delegati generici e anonimi.Le nuove versioni di C# dispongono dell'impalcatura per far funzionare tutto questo.Anche avere una notazione per i letterali degli oggetti è utile.

Non ho praticamente alcuna conoscenza di C#, ma sospetto che uno dei due cambiamenti sia stato semplicemente adottato come avviene in altri linguaggi senza pensare a renderlo più generale o che lo sviluppatore abbia deciso che non ne valeva la pena.

A rigor di termini, hai assolutamente ragione nel dire che non c'è motivo di imporre queste restrizioni.Si potrebbe sospettare che il motivo sia che per i casi consentiti l'implementazione è molto efficiente (come suggerito da Brian Ensink (44921)), ma dubito che l'implementazione sia molto efficiente (w.r.t.istruzioni if) se utilizzo numeri interi e alcuni casi casuali (ad es.345, -4574 e 1234203).E in ogni caso, che male c’è nel permetterlo per tutto (o almeno di più) e dire che è efficace solo per casi specifici (come i numeri (quasi) consecutivi).

Posso, tuttavia, immaginare che si potrebbe voler escludere i tipi per ragioni come quella fornita da lomaxx (44918).

Modificare:@Henk (44970):Se le stringhe sono condivise al massimo, anche le stringhe con lo stesso contenuto saranno puntatori alla stessa posizione di memoria.Quindi, se puoi assicurarti che le stringhe utilizzate nei casi siano archiviate consecutivamente in memoria, puoi implementare in modo molto efficiente lo switch (cioècon esecuzione nell'ordine di 2 confronti, un'addizione e due salti).

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top