Limitations de l'instruction switch en C# - pourquoi ?

Question

Lors de l'écriture d'une instruction switch, il semble y avoir deux limitations sur ce que vous pouvez activer dans les instructions case.

Par exemple (et oui, je sais, si vous faites ce genre de chose, cela veut probablement dire que votre orienté objet L'architecture (OO) est douteuse - il ne s'agit que d'un exemple artificiel !)

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

Ici, l'instruction switch() échoue avec 'Une valeur de type intégral attendue' et les instructions case échouent avec 'Une valeur constante est attendue'.

Pourquoi ces restrictions sont-elles en place, et quelle est la justification sous-jacente ? Je ne vois aucune raison pour laquelle la déclaration de commutation a pour ne succomber qu'à l'analyse statique, et pourquoi la valeur activée doit être intégrale (c'est-à-dire primitive). Quelle est la justification ?

Answer 1

Il est important de ne pas confondre l'instruction switch C# avec l'instruction switch CIL.

Le commutateur CIL est une table de saut, qui nécessite un index dans un ensemble d'adresses de saut.

Ceci n'est utile que si les cas du commutateur C# sont adjacents :

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

Mais ça ne sert pas à grand-chose s'ils ne le sont pas :

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

(Vous auriez besoin d'une table de ~3000 entrées, avec seulement 3 slots utilisés).

Avec des expressions non adjacentes, le compilateur peut commencer à effectuer des vérifications linéaires if-else-if-else.

Avec de plus grands ensembles d'expressions non adjacentes, le compilateur peut commencer par une recherche dans un arbre binaire, et finalement if-else-if-else les derniers éléments.

Avec des ensembles d'expressions contenant des groupes d'éléments adjacents, le compilateur peut effectuer une recherche d'arbre binaire, et enfin un commutateur CIL.

C'est plein de "mays" et "mights", et cela dépend du compilateur (peut différer avec Mono ou Rotor).

J'ai reproduit vos résultats sur ma machine en utilisant des cas adjacents :

temps total pour exécuter un interrupteur à 10 voies, 10000 itérations (ms) : 25.1383
temps approximatif par interrupteur à 10 voies (ms) : 0.00251383

temps total pour exécuter un interrupteur à 50 voies, 10000 itérations (ms) : 26.593
temps approximatif par interrupteur à 50 voies (ms) : 0.0026593

temps total pour exécuter un interrupteur à 5000 voies, 10000 itérations (ms) : 23.7094
temps approximatif par interrupteur 5000 voies (ms) : 0.00237094

temps total pour exécuter un commutateur de 50000 voies, 10000 itérations (ms) : 20.0933
temps approximatif pour un interrupteur de 50000 voies (ms) : 0.00200933

Ensuite, j'ai également utilisé des expressions de cas non adjacents :

temps total pour exécuter un interrupteur à 10 voies, 10000 itérations (ms) : 19.6189
temps approximatif par interrupteur à 10 voies (ms) : 0.00196189

temps total pour exécuter un interrupteur à 500 voies, 10000 itérations (ms) : 19.1664
temps approximatif par interrupteur de 500 voies (ms) : 0.00191664

temps total pour exécuter un interrupteur à 5000 voies, 10000 itérations (ms) : 19.5871
temps approximatif par interrupteur 5000 voies (ms) : 0.00195871

Une instruction switch case non adjacente de 50 000 ne serait pas compilée.
"Une expression est trop longue ou trop complexe pour être compilée à proximité de 'ConsoleApplication1.Program.Main(string[])'.

Ce qui est amusant ici, c'est que la recherche dans l'arbre binaire semble un peu plus rapide (probablement pas statistiquement) que l'instruction de commutation CIL.

Brian, tu as utilisé le mot " constant "Ce terme a une signification très précise du point de vue de la théorie de la complexité informatique. Alors que l'exemple simpliste d'un nombre entier adjacent peut produire un CIL considéré comme O(1) (constant), un exemple clairsemé est O(log n) (logarithmique), les exemples groupés se situent quelque part entre les deux et les petits exemples sont O(n) (linéaires).

Cela n'aborde même pas la situation de String, dans laquelle un statique Generic.Dictionary<string,int32> peuvent être créés, et subiront une surcharge certaine lors de leur première utilisation. La performance ici dépendra de la performance de Generic.Dictionary .

Si vous vérifiez le Spécification du langage C# (pas la spécification CIL) vous trouverez que "15.7.2 L'instruction switch" ne mentionne pas de "temps constant" ou que l'implémentation sous-jacente utilise même l'instruction switch du CIL (soyez très prudent lorsque vous supposez de telles choses).

En fin de compte, une commutation C# par rapport à une expression entière sur un système moderne est une opération de l'ordre de la microseconde, et ne mérite normalement pas qu'on s'en préoccupe.

---

Bien entendu, ces délais dépendent des machines et des conditions. Je ne prêterais pas attention à ces tests de timing, les durées de quelques microsecondes dont nous parlons sont éclipsées par tout code "réel" en cours d'exécution (et vous devez inclure du "code réel", sinon le compilateur optimisera la branche), ou par la gigue du système. Mes réponses sont basées sur l'utilisation de IL DASM pour examiner le CIL créé par le compilateur C#. Bien sûr, ce n'est pas définitif, car les instructions réelles que le CPU exécute sont ensuite créées par le JIT.

J'ai vérifié les instructions finales du CPU réellement exécutées sur ma machine x86, et je peux confirmer qu'un simple interrupteur adjacent fait quelque chose comme ça :

  jmp     ds:300025F0[eax*4]

Là où une recherche par arbre binaire est pleine de :

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

Answer 2

Voici mon message original, qui a suscité un certain débat... parce que c'est mal :

La déclaration de commutation n'est pas la même chose qu'une grande instruction if-else. Chaque cas doit être unique et évalué statiquement. L'instruction switch effectue un branchement en temps constant, quel que soit combien de cas vous avez. L'instruction if-else évalue chaque condition jusqu'à ce qu'elle en trouve une qui soit vraie.

---

En fait, l'instruction de commutation C# est no toujours une branche à temps constant.

Dans certains cas, le compilateur utilisera une instruction switch CIL qui est en fait une branche en temps constant utilisant une table de saut. Cependant, dans les cas épars, comme l'a fait remarquer Ivan Hamilton le compilateur peut générer quelque chose d'entièrement différent.

Il est en fait assez facile de le vérifier en écrivant diverses instructions de commutation C#, certaines éparses, d'autres denses, et en examinant le CIL résultant avec l'outil ildasm.exe.

Answer 3

La première raison qui vient à l'esprit est historique :

Comme la plupart des programmeurs C, C++ et Java ne sont pas habitués à disposer de telles libertés, ils ne les exigent pas.

Une autre raison, plus valable, est que le la complexité de la langue augmenterait :

Tout d'abord, faut-il comparer les objets avec .Equals() ou avec le == opérateur ? Les deux sont valables dans certains cas. Devrions-nous introduire une nouvelle syntaxe pour ce faire ? Devrions-nous permettre au programmeur d'introduire sa propre méthode de comparaison ?

En outre, le fait d'autoriser l'allumage des objets briser les hypothèses sous-jacentes à l'énoncé du commutateur . Il existe deux règles régissant l'instruction switch que le compilateur ne serait pas en mesure d'appliquer si les objets étaient autorisés à être activés (voir l'instruction Spécification du langage C# version 3.0 , §8.7.2) :

• Que les valeurs des étiquettes des interrupteurs sont constant
• Que les valeurs des étiquettes des interrupteurs sont distinct (afin qu'un seul bloc de commutation puisse être sélectionné pour une expression de commutation donnée)

Considérons cet exemple de code dans le cas hypothétique où les valeurs de cas non constantes étaient autorisées :

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

Que fera le code ? Que se passera-t-il si les déclarations de cas sont réorganisées ? En effet, l'une des raisons pour lesquelles C# a rendu les interrupteurs illégaux est que les instructions d'interrupteur peuvent être réorganisées de manière arbitraire.

Ces règles ont une raison d'être : elles permettent au programmeur, en examinant un bloc de cas, de connaître avec certitude la condition précise dans laquelle le bloc est saisi. Lorsque l'instruction switch susmentionnée compte 100 lignes ou plus (et cela arrivera), cette connaissance est inestimable.

Answer 4

La plupart du temps, ces restrictions sont mises en place par les concepteurs du langage. La justification sous-jacente peut être la compatibilité avec l'histoire du langage, les idéaux, ou la simplification de la conception du compilateur.

Le compilateur peut choisir (et le fait) de le faire :

• créer une grande déclaration if-else
• utiliser une instruction de commutation MSIL (table de saut)
• construire un Generic.Dictionary<string,int32>, le remplir à la première utilisation, et appeler Generic.Dictionary<>::TryGetValue() pour obtenir un index à transmettre à une instruction MSIL switch (table de saut)
• utiliser une combinaison de if-elses et MSIL Sauts "switch".

L'instruction switch N'EST PAS une branche à temps constant. Le compilateur peut trouver des raccourcis (en utilisant des seaux de hachage, etc.), mais les cas plus compliqués génèreront un code MSIL plus compliqué, certains cas se ramifiant plus tôt que d'autres.

Pour gérer le cas de la chaîne, le compilateur finira (à un moment donné) par utiliser a.Equals(b) (et éventuellement a.GetHashCode() ). Je pense qu'il serait trivial pour le compilateur d'utiliser tout objet qui satisfait à ces contraintes.

Quant à la nécessité des expressions de cas statiques... certaines de ces optimisations (hachage, mise en cache, etc.) ne seraient pas disponibles si les expressions de cas n'étaient pas déterministes. Mais nous avons déjà vu que parfois le compilateur choisit simplement la voie simpliste if-else-if-else de toute façon...

Edit : lomaxx - Votre compréhension de l'opérateur "typeof" n'est pas correcte. L'opérateur "typeof" est utilisé pour obtenir l'objet System.Type pour un type (rien à voir avec ses supertypes ou interfaces). La vérification de la compatibilité d'exécution d'un objet avec un type donné est le travail de l'opérateur "is". L'utilisation de "typeof" ici pour exprimer un objet n'est pas pertinente.

Answer 5

D'ailleurs, VB, qui a la même architecture sous-jacente, permet une flexibilité beaucoup plus grande. Select Case (le code ci-dessus fonctionnerait en VB) et produit toujours un code efficace lorsque cela est possible. L'argument de la contrainte technique doit donc être considéré avec attention.