Einschränkungen der C#-Switch-Anweisung – warum?

https://stackoverflow.com/questions/44905

09-06-2019
|

Frage

Beim Schreiben einer Switch-Anweisung scheint es zwei Einschränkungen zu geben, was Sie in Case-Anweisungen einschalten können.

Zum Beispiel (und ja, ich weiß, wenn Sie so etwas tun, bedeutet das wahrscheinlich Ihre objektorientierte (OO) Architektur ist fraglich – das ist nur ein erfundenes Beispiel!),

  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;
  }

Hier schlägt die switch()-Anweisung mit „Ein Wert eines Integraltyps erwartet“ fehl und die case-Anweisungen schlagen mit „Ein konstanter Wert wird erwartet“ fehl.

Warum gibt es diese Beschränkungen und was ist die zugrunde liegende Begründung?Ich sehe keinen Grund für die switch-Anweisung hat nur der statischen Analyse zu unterliegen und warum der eingeschaltete Wert ganzzahlig (also primitiv) sein muss.Was ist die Begründung?

Lösung

Dies ist mein ursprünglicher Beitrag, der einige Debatten ausgelöst hat ... weil es falsch ist:

Die Switch-Anweisung ist nicht dasselbe wie eine große IF-ELSE-Aussage.Jeder Fall muss eindeutig sein und statisch bewertet werden.Die Switch -Anweisung führt einen konstanten Zeitzweig, unabhängig davon, wie viele Fälle Sie haben.Die IF-ELSE-Anweisung bewertet jede Bedingung, bis sie eine findet, die wahr ist.

Tatsächlich ist es die C#-Switch-Anweisung nicht immer ein konstanter Zeitzweig.

In einigen Fällen verwendet der Compiler eine CIL-Switch-Anweisung, bei der es sich tatsächlich um einen zeitkonstanten Zweig handelt, der eine Sprungtabelle verwendet.In seltenen Fällen jedoch, wie von hervorgehoben Ivan Hamilton Der Compiler generiert möglicherweise etwas ganz anderes.

Dies lässt sich eigentlich ganz einfach überprüfen, indem man verschiedene C#-Switch-Anweisungen schreibt, einige spärlich, andere dicht, und sich die resultierende CIL mit dem Tool ildasm.exe ansieht.

Andere Tipps

Es ist wichtig, die C#-Switch-Anweisung nicht mit der CIL-Switch-Anweisung zu verwechseln.

Der CIL-Switch ist eine Sprungtabelle, die einen Index in eine Reihe von Sprungadressen erfordert.

Dies ist nur dann sinnvoll, wenn die Fälle des C#-Schalters benachbart sind:

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

Aber es nützt wenig, wenn sie es nicht sind:

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

(Sie benötigen eine Tabelle mit einer Größe von ca. 3000 Einträgen und nur 3 belegten Slots.)

Bei nicht benachbarten Ausdrücken beginnt der Compiler möglicherweise mit der Durchführung linearer if-else-if-else-Prüfungen.

Bei größeren, nicht benachbarten Ausdruckssätzen beginnt der Compiler möglicherweise mit einer binären Baumsuche und schließlich mit if-else-if-else den letzten paar Elementen.

Bei Ausdruckssätzen, die Klumpen benachbarter Elemente enthalten, kann der Compiler eine Binärbaumsuche und schließlich einen CIL-Schalter durchführen.

Dies ist voller „Mays“ und „Mights“ und hängt vom Compiler ab (kann bei Mono oder Rotor unterschiedlich sein).

Ich habe Ihre Ergebnisse auf meinem Computer anhand der folgenden Fälle reproduziert:

Gesamtzeit zum Ausführen eines 10-Wege-Schalters, 10.000 Iterationen (ms):25.1383
ungefähre Zeit pro 10-Wege-Schalter (ms):0,00251383

Gesamtzeit zur Ausführung eines 50-Wege-Schalters, 10.000 Iterationen (ms):26.593
ungefähre Zeit pro 50-Wege-Schalter (ms):0,0026593

Gesamtzeit zur Ausführung eines 5000-Wege-Wechsels, 10000 Iterationen (ms):23.7094
ungefähre Zeit pro 5000-Wege-Schalter (ms):0,00237094

Gesamtzeit zur Ausführung eines 50.000-Wege-Wechsels, 10.000 Iterationen (ms):20.0933
Ungefähre Zeit pro 50000-Wege-Schalter (ms):0,00200933

Dann habe ich auch nicht benachbarte Groß-/Kleinschreibungsausdrücke verwendet:

Gesamtzeit zum Ausführen eines 10-Wege-Schalters, 10.000 Iterationen (ms):19.6189
ungefähre Zeit pro 10-Wege-Schalter (ms):0,00196189

Gesamtzeit zur Ausführung eines 500-Wege-Wechsels, 10.000 Iterationen (ms):19.1664
ungefähre Zeit pro 500-Wege-Schalter (ms):0,00191664

Gesamtzeit zur Ausführung eines 5000-Wege-Wechsels, 10000 Iterationen (ms):19.5871
ungefähre Zeit pro 5000-Wege-Schalter (ms):0,00195871

Eine nicht benachbarte 50.000-Case-Switch-Anweisung würde nicht kompiliert werden.
„Ein Ausdruck ist zu lang oder zu komplex, um in der Nähe von ‚ConsoleApplication1.Program.Main(string[])‘ kompiliert zu werden.

Das Lustige daran ist, dass die Binärbaumsuche etwas (wahrscheinlich nicht statistisch gesehen) schneller erscheint als der CIL-Switch-Befehl.

Brian, du hast das Wort „Konstante", was aus Sicht der rechnerischen Komplexitätstheorie eine sehr eindeutige Bedeutung hat.Während das vereinfachte Beispiel einer benachbarten Ganzzahl eine CIL erzeugen kann, die als O(1) (konstant) betrachtet wird, ist ein spärlich besetztes Beispiel O(log n) (logarithmisch), geclusterte Beispiele liegen irgendwo dazwischen und kleine Beispiele sind O(n) (linear). ).

Dies betrifft nicht einmal die String-Situation, in der eine statische Aufladung vorliegt Generic.Dictionary<string,int32> kann erstellt werden und verursacht bei der ersten Verwendung einen erheblichen Mehraufwand.Die Leistung hängt hier von der Leistung von ab Generic.Dictionary.

Wenn Sie das überprüfen C#-Sprachspezifikation (Nicht die CIL -Spezifikation) Sie werden "15.7.2 Die Switch -Anweisung" finden, dass "konstante Zeit" nicht erwähnt wird oder dass die zugrunde liegende Implementierung sogar den CIL -Switch -Anweisungen verwendet (vorsichtig mit der Annahme solcher Dinge annehmen).

Letztendlich ist ein C#-Wechsel zu einem ganzzahligen Ausdruck auf einem modernen System ein Vorgang im Submikrosekundenbereich und normalerweise nicht der Mühe wert.

Natürlich hängen diese Zeiten von den Maschinen und Bedingungen ab.Ich würde diesen Timing-Tests keine Beachtung schenken, die Mikrosekundendauern, von denen wir sprechen, werden durch jeden ausgeführten „echten“ Code in den Schatten gestellt (und Sie müssen „echten Code“ einschließen, sonst optimiert der Compiler den Zweig weg) oder Jitter im System.Meine Antworten basieren auf der Verwendung IL DASM um die vom C#-Compiler erstellte CIL zu untersuchen.Dies ist natürlich nicht endgültig, da die tatsächlichen Anweisungen, die die CPU ausführt, dann von der JIT erstellt werden.

Ich habe die endgültigen CPU-Anweisungen überprüft, die tatsächlich auf meiner x86-Maschine ausgeführt wurden, und kann bestätigen, dass ein einfacher benachbarter Set-Schalter etwa Folgendes ausführt:

  jmp     ds:300025F0[eax*4]

Wo eine binäre Baumsuche voll ist von:

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

Der erste Grund, der mir in den Sinn kommt, ist historisch:

Da die meisten C-, C++- und Java-Programmierer solche Freiheiten nicht gewohnt sind, fordern sie sie auch nicht.

Ein weiterer, stichhaltigerer Grund ist, dass die Die Sprachkomplexität würde zunehmen:

Zunächst sollten die Objekte verglichen werden .Equals() oder mit dem == Operator?In manchen Fällen gilt beides.Sollten wir dazu eine neue Syntax einführen?Sollten wir dem Programmierer erlauben, seine eigene Vergleichsmethode einzuführen?

Darüber hinaus wäre das Einschalten von Objekten möglich Brechen Sie die zugrunde liegenden Annahmen über die switch-Anweisung.Es gibt zwei Regeln für die switch-Anweisung, die der Compiler nicht durchsetzen könnte, wenn das Einschalten von Objekten zulässig wäre (siehe C#-Sprachspezifikation Version 3.0, §8.7.2):

Das sind die Werte der Schalterbezeichnungen Konstante
Das sind die Werte der Schalterbezeichnungen unterscheidbar (damit nur ein Schalterblock für einen bestimmten Schalterausdruck ausgewählt werden kann)

Betrachten Sie dieses Codebeispiel für den hypothetischen Fall, dass nicht konstante Fallwerte zulässig wären:

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;
    }
}

Was wird der Code bewirken?Was passiert, wenn die Fallanweisungen neu angeordnet werden?Tatsächlich ist einer der Gründe, warum C# den Switch-Fall-Through illegal gemacht hat, dass die Switch-Anweisungen willkürlich neu angeordnet werden konnten.

Diese Regeln gibt es aus einem bestimmten Grund – damit der Programmierer durch Betrachtung eines Case-Blocks mit Sicherheit die genaue Bedingung erkennen kann, unter der der Block eingegeben wird.Wenn die oben genannte Switch-Anweisung 100 Zeilen oder mehr umfasst (und das wird der Fall sein), ist dieses Wissen von unschätzbarem Wert.

Übrigens ermöglicht VB mit der gleichen zugrunde liegenden Architektur eine wesentlich größere Flexibilität Select Case Anweisungen (der obige Code würde in VB funktionieren) und dennoch effizienten Code erzeugen, wo dies möglich ist, daher muss das Argument aufgrund technischer Einschränkungen sorgfältig geprüft werden.

Meistens sind diese Einschränkungen auf die Sprachdesigner zurückzuführen.Die zugrunde liegende Begründung könnte die Kompatibilität mit der Sprachgeschichte, Ideale oder die Vereinfachung des Compiler-Designs sein.

Der Compiler kann (und tut) Folgendes wählen:

Erstellen Sie eine große if-else-Anweisung
Verwenden Sie eine MSIL-Switch-Anweisung (Sprungtabelle).
Bauen Sie ein generisches. Dictionaryu003Cstring,int32> , füllen Sie es beim ersten Gebrauch ein und rufen Sie generic.Dictionary <> :: trygetValue () auf, damit ein Index an einen MSIL -Switch -Befehl (Sprungtabelle) übergeben wird (Sprungtabelle).
Verwenden Sie eine Kombination aus IF-Elses & MSIL-Switch-Sprüngen

Die Switch-Anweisung ist KEIN konstanter Zeitzweig.Der Compiler findet möglicherweise Abkürzungen (mithilfe von Hash-Buckets usw.), aber kompliziertere Fälle erzeugen komplizierteren MSIL-Code, wobei einige Fälle früher verzweigen als andere.

Um den String-Fall zu behandeln, wird der Compiler (irgendwann) a.Equals(b) (und möglicherweise a.GetHashCode() ) verwenden.Ich denke, es wäre für den Compiler trival, jedes Objekt zu verwenden, das diese Einschränkungen erfüllt.

Was die Notwendigkeit statischer Fallausdrücke betrifft ...Einige dieser Optimierungen (Hashing, Caching usw.) wären nicht verfügbar, wenn die Fallausdrücke nicht deterministisch wären.Aber wir haben bereits gesehen, dass der Compiler manchmal sowieso einfach den vereinfachten If-else-if-else-Weg wählt ...

Bearbeiten: lomaxx - Ihr Verständnis des „typeof“-Operators ist nicht korrekt.Der „typeof“-Operator wird verwendet, um das System.Type-Objekt für einen Typ abzurufen (was nichts mit seinen Supertypen oder Schnittstellen zu tun hat).Die Prüfung der Laufzeitkompatibilität eines Objekts mit einem bestimmten Typ ist die Aufgabe des „is“-Operators.Die Verwendung von „typeof“ hier zum Ausdrücken eines Objekts ist irrelevant.

Während wir uns mit dem Thema befassen, sagt Jeff Atwood: Die Switch-Anweisung ist eine Programmiergräueltat.Gehen Sie sparsam damit um.

Sie können die gleiche Aufgabe oft auch mit einer Tabelle erledigen.Zum Beispiel:

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]);

Ich sehe keinen Grund, warum die Switch-Anweisung nur einer statischen Analyse unterliegen muss

Stimmt, das ist nicht der Fall haben zu, und viele Sprachen verwenden tatsächlich dynamische Switch-Anweisungen.Dies bedeutet jedoch, dass eine Neuordnung der „case“-Klauseln das Verhalten des Codes ändern kann.

Es gibt einige interessante Informationen zu den Designentscheidungen, die hier in „Switch“ eingeflossen sind: Warum ist die C#-switch-Anweisung so konzipiert, dass sie keinen Fall-Through zulässt, aber dennoch eine Unterbrechung erfordert?

Das Zulassen dynamischer Groß- und Kleinschreibung kann zu Monstrositäten wie diesem PHP-Code führen:

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

was ehrlich gesagt einfach das verwenden sollte if-else Stellungnahme.

Microsoft hat Sie endlich gehört!

Mit C# 7 können Sie jetzt:

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));
}

Dies ist kein Grund dafür, aber im Abschnitt 8.7.2 der C#-Spezifikation heißt es:

Der maßgebliche Typ einer Switch-Anweisung wird durch den Switch-Ausdruck festgelegt.Wenn der Typ des Switch-Ausdrucks sbyte, byte, short, ushort, int, uint, long, ulong, char, string oder ein Enum-Typ ist, dann ist dies der maßgebliche Typ der switch-Anweisung.Andernfalls muss genau eine benutzerdefinierte implizite Konvertierung (§6.4) vom Typ des Schalterausdrucks in einen der folgenden möglichen maßgeblichen Typen vorhanden sein:sbyte, byte, short, ushort, int, uint, long, ulong, char, string.Wenn keine solche implizite Konvertierung vorhanden ist oder wenn mehr als eine solche implizite Konvertierung vorhanden ist, tritt ein Fehler bei der Kompilierung auf.

Die C# 3.0-Spezifikation befindet sich unter:http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

Judahs Antwort oben brachte mich auf eine Idee.Sie können das oben beschriebene Schaltverhalten des OP mit a „fälschen“. 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());
                    });

Dadurch können Sie einem Typ Verhalten im gleichen Stil wie die switch-Anweisung zuordnen.Ich glaube, es hat den zusätzlichen Vorteil, dass es beim Kompilieren in IL verschlüsselt ist und nicht wie eine Sprungtabelle im Switch-Stil.

Ich nehme an, es gibt keinen grundsätzlichen Grund, warum der Compiler Ihre switch-Anweisung nicht automatisch übersetzen konnte in:

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

Aber damit ist nicht viel gewonnen.

Eine case-Anweisung für Integraltypen ermöglicht es dem Compiler, eine Reihe von Optimierungen vorzunehmen:

Es gibt keine Duplizierung (es sei denn, Sie duplizieren Fallbeschriftungen, was der Compiler erkennt).In Ihrem Beispiel könnte t aufgrund der Vererbung mit mehreren Typen übereinstimmen.Soll das erste Match ausgeführt werden?Alle von ihnen?
Der Compiler kann sich dafür entscheiden, eine Switch-Anweisung über einen Integraltyp durch eine Sprungtabelle zu implementieren, um alle Vergleiche zu vermeiden.Wenn Sie eine Aufzählung mit ganzzahligen Werten von 0 bis 100 einschalten, wird ein Array mit 100 Zeigern erstellt, einer für jede Switch-Anweisung.Zur Laufzeit sucht es einfach anhand des eingeschalteten Ganzzahlwerts nach der Adresse im Array.Dies führt zu einer viel besseren Laufzeitleistung als die Durchführung von 100 Vergleichen.

Entsprechend die Dokumentation der Switch-Anweisung Wenn es eine eindeutige Möglichkeit gibt, das Objekt implizit in einen Integraltyp zu konvertieren, ist dies zulässig.Ich denke, Sie erwarten ein Verhalten, bei dem jede case-Anweisung durch ersetzt wird if (t == typeof(int)), aber das würde eine ganze Reihe von Würmern öffnen, wenn Sie diesen Operator überlasten könnten.Das Verhalten würde sich ändern, wenn sich Implementierungsdetails für die Switch-Anweisung ändern würden, wenn Sie Ihre ==-Überschreibung falsch geschrieben hätten.Durch die Reduzierung der Vergleiche auf ganzzahlige Typen und Zeichenfolgen sowie auf Dinge, die auf ganzzahlige Typen reduziert werden können (und sollen), vermeiden sie potenzielle Probleme.

schrieb:

„Die switch-Anweisung führt eine konstante Zeitverzweigung durch, unabhängig davon, wie viele Fälle Sie haben.“

Da die Sprache das zulässt Zeichenfolge Typ, der in einer Switch-Anweisung verwendet werden soll. Ich gehe davon aus, dass der Compiler keinen Code für eine Verzweigungsimplementierung mit konstanter Zeit für diesen Typ generieren kann und einen Wenn-Dann-Stil generieren muss.

@mweerden – Ah, ich verstehe.Danke.

Ich habe nicht viel Erfahrung mit C# und .NET, aber es scheint, dass die Sprachdesigner keinen statischen Zugriff auf das Typsystem zulassen, außer unter bestimmten Umständen.Der Art der Das Schlüsselwort gibt ein Objekt zurück, sodass auf dieses nur zur Laufzeit zugegriffen werden kann.

Ich denke, Henk hat es mit der Sache „Kein statischer Zugriff auf das Typsystem“ auf den Punkt gebracht

Eine andere Möglichkeit besteht darin, dass es keine Reihenfolge für Typen gibt, wie dies bei Zahlen und Zeichenfolgen der Fall sein kann.Daher kann ein Typwechsel keinen binären Suchbaum erstellen, sondern nur eine lineare Suche.

Ich bin einverstanden mit dieser Kommentar dass die Verwendung eines tabellengesteuerten Ansatzes oft besser ist.

In C# 1.0 war dies nicht möglich, da es keine Generika und anonymen Delegaten gab.Neue Versionen von C# verfügen über das Gerüst, damit dies funktioniert.Eine Notation für Objektliterale ist ebenfalls hilfreich.

Ich habe so gut wie keine Kenntnisse von C#, aber ich vermute, dass einer der beiden Schalter einfach so übernommen wurde, wie er in anderen Sprachen vorkommt, ohne darüber nachzudenken, ihn allgemeiner zu machen, oder dass der Entwickler entschieden hat, dass sich eine Erweiterung nicht lohnt.

Streng genommen haben Sie völlig Recht, dass es keinen Grund gibt, diese Beschränkungen festzulegen.Man könnte vermuten, dass der Grund darin liegt, dass die Implementierung für die zulässigen Fälle sehr effizient ist (wie von Brian Ensink vorgeschlagen (44921)), aber ich bezweifle, dass die Implementierung sehr effizient ist (bzgl.if-Anweisungen), wenn ich ganze Zahlen und einige zufällige Fälle verwende (z. B.345, -4574 und 1234203).Und was schadet es auf jeden Fall, wenn man es für alles (oder zumindest für mehr) zulässt und sagt, dass es nur für bestimmte Fälle (wie (fast) aufeinanderfolgende Nummern) effizient ist?

Ich kann mir jedoch vorstellen, dass man aus Gründen wie dem von lomaxx (44918).

Bearbeiten:@Henk (44970):Wenn Strings maximal gemeinsam genutzt werden, sind Strings mit gleichem Inhalt auch Zeiger auf denselben Speicherort.Wenn Sie dann sicherstellen können, dass die in den Fällen verwendeten Zeichenfolgen nacheinander im Speicher gespeichert werden, können Sie den Schalter sehr effizient implementieren (d. h.mit Ausführung in der Reihenfolge von 2 Vergleichen, einer Addition und zwei Sprüngen).

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow