Limitaciones de las declaraciones de cambio de C#: ¿por qué?

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

  •  09-06-2019
  •  | 
  •  

Pregunta

Al escribir una declaración de cambio, parece haber dos limitaciones sobre lo que puede activar en las declaraciones de caso.

Por ejemplo (y sí, lo sé, si estás haciendo este tipo de cosas probablemente significa que tu orientado a objetos (OO) la arquitectura es dudosa: ¡esto es sólo un ejemplo artificial!),

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

Aquí la declaración switch() falla con "Se espera un valor de tipo integral" y las declaraciones de caso fallan con "Se espera un valor constante".

¿Por qué existen estas restricciones y cuál es la justificación subyacente?No veo ninguna razón por la cual la declaración de cambio tiene sucumbir únicamente al análisis estático, y por qué el valor que se activa tiene que ser integral (es decir, primitivo).¿Cuál es la justificación?

¿Fue útil?

Solución

Esta es mi publicación original, que provocó cierto debate... porque esta mal:

La instrucción Switch no es lo mismo que una gran declaración if-else.Cada caso debe ser único y evaluado estáticamente.La instrucción Switch hace una rama de tiempo constante independientemente de cuántos casos tenga.La declaración IF-Else evalúa cada condición hasta que encuentre una que sea verdadera.

De hecho, la declaración de cambio de C# es no Siempre una rama de tiempo constante.

En algunos casos, el compilador utilizará una declaración de cambio CIL que de hecho es una rama de tiempo constante que utiliza una tabla de salto.Sin embargo, en casos escasos, como lo señala Iván Hamilton el compilador puede generar algo completamente distinto.

En realidad, esto es bastante fácil de verificar escribiendo varias declaraciones de cambio de C#, algunas escasas, otras densas, y observando el CIL resultante con la herramienta ildasm.exe.

Otros consejos

Es importante no confundir la instrucción de cambio de C# con la instrucción de cambio de CIL.

El conmutador CIL es una tabla de salto que requiere un índice en un conjunto de direcciones de salto.

Esto solo es útil si los casos del modificador C# son adyacentes:

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

Pero de poco sirven si no lo son:

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

(Necesitaría una tabla de ~3000 entradas de tamaño, con solo 3 ranuras utilizadas)

Con expresiones no adyacentes, el compilador puede comenzar a realizar comprobaciones lineales if-else-if-else.

Con conjuntos de expresiones no adyacentes más grandes, el compilador puede comenzar con una búsqueda de árbol binario y, finalmente, if-else-if-else los últimos elementos.

Con conjuntos de expresiones que contienen grupos de elementos adyacentes, el compilador puede realizar una búsqueda en un árbol binario y, finalmente, un cambio CIL.

Está lleno de "mays" y "mights" y depende del compilador (puede diferir con Mono o Rotor).

Repliqué sus resultados en mi máquina usando casos adyacentes:

tiempo total para ejecutar un cambio de 10 vías, 10000 iteraciones (ms):25.1383
tiempo aproximado por interruptor de 10 vías (ms):0.00251383

tiempo total para ejecutar un cambio de 50 vías, 10000 iteraciones (ms):26.593
tiempo aproximado por interruptor de 50 vías (ms):0.0026593

tiempo total para ejecutar un cambio de 5000 vías, 10000 iteraciones (ms):23.7094
tiempo aproximado por cambio de 5000 vías (ms):0.00237094

tiempo total para ejecutar un cambio de 50000 vías, 10000 iteraciones (ms):20.0933
Tiempo aproximado por cambio de 50000 vías (ms):0.00200933

Luego también usé expresiones de casos no adyacentes:

tiempo total para ejecutar un cambio de 10 vías, 10000 iteraciones (ms):19.6189
tiempo aproximado por interruptor de 10 vías (ms):0.00196189

tiempo total para ejecutar un cambio de 500 vías, 10000 iteraciones (ms):19.1664
tiempo aproximado por cambio de 500 vías (ms):0.00191664

tiempo total para ejecutar un cambio de 5000 vías, 10000 iteraciones (ms):19.5871
tiempo aproximado por cambio de 5000 vías (ms):0.00195871

Una declaración de cambio de 50.000 casos no adyacente no se compilaría.
"Una expresión es demasiado larga o compleja para compilarla cerca de 'ConsoleApplication1.Program.Main(string[])'

Lo curioso aquí es que la búsqueda del árbol binario aparece un poco (probablemente no estadísticamente) más rápida que la instrucción de cambio CIL.

Brian, has usado la palabra "constante", que tiene un significado muy definido desde la perspectiva de la teoría de la complejidad computacional.Si bien el ejemplo simplista de entero adyacente puede producir CIL que se considera O(1) (constante), un ejemplo escaso es O(log n) (logarítmico), los ejemplos agrupados se encuentran en algún punto intermedio y los ejemplos pequeños son O(n) (lineal). ).

Esto ni siquiera aborda la situación de String, en la que una estática Generic.Dictionary<string,int32> pueden crearse y sufrirán una sobrecarga definitiva en el primer uso.El rendimiento aquí dependerá del rendimiento de Generic.Dictionary.

Si marca el Especificación del lenguaje C# (no la especificación CIL) Encontrará "15.7.2 La instrucción Switch" no menciona "tiempo constante" o que la implementación subyacente incluso usa la instrucción del interruptor CIL (tenga mucho cuidado de asumir tales cosas).

Al final del día, un cambio de C# contra una expresión entera en un sistema moderno es una operación de menos de un microsegundo y normalmente no vale la pena preocuparse.

Por supuesto estos tiempos dependerán de las máquinas y las condiciones.No prestaría atención a estas pruebas de tiempo, las duraciones de microsegundos de las que estamos hablando quedan eclipsadas por cualquier código "real" que se esté ejecutando (y debe incluir algún "código real", de lo contrario el compilador optimizará la rama), o inquietud en el sistema.Mis respuestas se basan en el uso EL DASM para examinar el CIL creado por el compilador de C#.Por supuesto, esto no es definitivo, ya que el JIT crea las instrucciones reales que ejecuta la CPU.

He verificado las instrucciones finales de la CPU realmente ejecutadas en mi máquina x86 y puedo confirmar un simple interruptor de configuración adyacente que hace algo como:

  jmp     ds:300025F0[eax*4]

Donde una búsqueda de árbol binario está llena de:

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

La primera razón que me viene a la mente es histórico:

Dado que la mayoría de los programadores de C, C++ y Java no están acostumbrados a tener tales libertades, no las exigen.

Otra razón, más válida, es que el La complejidad del lenguaje aumentaría.:

En primer lugar, ¿deben compararse los objetos con .Equals() o con el == ¿operador?Ambos son válidos en algunos casos.¿Deberíamos introducir una nueva sintaxis para hacer esto?¿Deberíamos permitir que el programador introduzca su propio método de comparación?

Además, permitir encender objetos romper las suposiciones subyacentes sobre la declaración de cambio.Hay dos reglas que rigen la declaración de cambio que el compilador no podría aplicar si se permitiera activar los objetos (consulte la Especificación del lenguaje C# versión 3.0, §8.7.2):

  • Que los valores de las etiquetas de los interruptores sean constante
  • Que los valores de las etiquetas de los interruptores sean distinto (para que solo se pueda seleccionar un bloque de conmutación para una expresión de conmutación determinada)

Considere este ejemplo de código en el caso hipotético de que se permitieran valores de caso no constantes:

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

¿Qué hará el código?¿Qué pasa si se reordenan las declaraciones del caso?De hecho, una de las razones por las que C# hizo ilegal la caída del interruptor es que las declaraciones de cambio podrían reorganizarse arbitrariamente.

Estas reglas existen por una razón: para que el programador pueda, al observar un bloque de caso, saber con certeza la condición precisa bajo la cual se ingresa al bloque.Cuando la declaración de cambio antes mencionada crece hasta tener 100 líneas o más (y así será), dicho conocimiento es invaluable.

Por cierto, VB, al tener la misma arquitectura subyacente, permite una configuración mucho más flexible. Select Case declaraciones (el código anterior funcionaría en VB) y aún produce código eficiente cuando esto es posible, por lo que el argumento por restricción técnica debe considerarse cuidadosamente.

En su mayoría, esas restricciones se deben a los diseñadores de lenguajes.La justificación subyacente puede ser la compatibilidad con la historia del lenguaje, los ideales o la simplificación del diseño del compilador.

El compilador puede (y elige) elegir:

  • crear una gran declaración if-else
  • utilizar una instrucción de cambio MSIL (tabla de salto)
  • construir un genic.dictionaryu003Cstring,int32> , llévelo en primer uso y llame a Generic.Dictionary <> :: trygetValue () para que un índice pase a una instrucción de conmutador MSIL (tabla de salto)
  • Use una combinación de saltos de "conmutador" de if-elses y msil

La declaración de cambio NO ES una rama de tiempo constante.El compilador puede encontrar atajos (usando depósitos de hash, etc.), pero los casos más complicados generarán código MSIL más complicado y algunos casos se ramificarán antes que otros.

Para manejar el caso String, el compilador terminará (en algún momento) usando a.Equals(b) (y posiblemente a.GetHashCode() ).Creo que sería trivial para el compilador utilizar cualquier objeto que satisfaga estas restricciones.

En cuanto a la necesidad de expresiones de casos estáticos...algunas de esas optimizaciones (hash, almacenamiento en caché, etc.) no estarían disponibles si las expresiones de caso no fueran deterministas.Pero ya hemos visto que a veces el compilador simplemente elige el camino si-si-si-si-simple de todos modos...

Editar: lomaxx - Su comprensión del operador "typeof" no es correcta.El operador "typeof" se utiliza para obtener el objeto System.Type para un tipo (nada que ver con sus supertipos o interfaces).Verificar la compatibilidad en tiempo de ejecución de un objeto con un tipo determinado es el trabajo del operador "is".El uso de "typeof" aquí para expresar un objeto es irrelevante.

Hablando del tema, según Jeff Atwood, la declaración de cambio es una atrocidad de programación.Úsalos con moderación.

A menudo puedes realizar la misma tarea usando una mesa.Por ejemplo:

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

No veo ninguna razón por la que la declaración de cambio deba sucumbir solo al análisis estático.

Es cierto que no tener y muchos lenguajes de hecho usan declaraciones de cambio dinámicas.Sin embargo, esto significa que reordenar las cláusulas "case" puede cambiar el comportamiento del código.

Hay información interesante detrás de las decisiones de diseño que se tomaron en "cambiar" aquí: ¿Por qué la instrucción de cambio de C# está diseñada para no permitir fallas, pero aun así requiere una interrupción?

Permitir expresiones dinámicas de casos puede llevar a monstruosidades como este código PHP:

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

que francamente debería usar el if-else declaración.

¡Microsoft finalmente te escuchó!

Ahora con C# 7 puedes:

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

Esta no es la razón, pero la sección 8.7.2 de la especificación C# establece lo siguiente:

El tipo que rige una declaración de cambio lo establece la expresión de cambio.Si el tipo de expresión de cambio es sbyte, byte, short, ushort, int, uint, long, ulong, char, string o un tipo de enumeración, entonces ese es el tipo que rige la declaración de cambio.De lo contrario, debe existir exactamente una conversión implícita definida por el usuario (§6.4) del tipo de expresión de cambio a uno de los siguientes tipos de gobierno posibles:sbyte, byte, corto, ushort, int, uint, largo, ulong, char, cadena.Si no existe ninguna conversión implícita, o si existe más de una conversión implícita, se produce un error en tiempo de compilación.

La especificación C# 3.0 se encuentra en:http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

La respuesta anterior de Judah me dio una idea.Puede "falsificar" el comportamiento del interruptor del OP anterior usando un 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());
                    });

Esto le permite asociar el comportamiento con un tipo en el mismo estilo que la declaración de cambio.Creo que tiene el beneficio adicional de tener una clave en lugar de una tabla de salto estilo interruptor cuando se compila en IL.

Supongo que no hay ninguna razón fundamental por la que el compilador no pueda traducir automáticamente su declaración de cambio a:

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

Pero no se gana mucho con eso.

Una declaración de caso sobre tipos integrales permite al compilador realizar una serie de optimizaciones:

  1. No hay duplicación (a menos que duplique las etiquetas de los casos, lo cual detecta el compilador).En su ejemplo, podría coincidir con varios tipos debido a la herencia.¿Debería ejecutarse el primer partido?¿Todos ellos?

  2. El compilador puede optar por implementar una declaración de cambio sobre un tipo integral mediante una tabla de salto para evitar todas las comparaciones.Si está activando una enumeración que tiene valores enteros de 0 a 100, entonces crea una matriz con 100 punteros, uno para cada instrucción de cambio.En tiempo de ejecución, simplemente busca la dirección de la matriz en función del valor entero que se activa.Esto genera un rendimiento en tiempo de ejecución mucho mejor que realizar 100 comparaciones.

De acuerdo a la documentación de la declaración de cambio Si hay una forma inequívoca de convertir implícitamente el objeto a un tipo integral, entonces se permitirá.Creo que esperas un comportamiento en el que para cada declaración de caso se reemplace con if (t == typeof(int)), pero eso abriría toda una lata de gusanos cuando llegues a sobrecargar a ese operador.El comportamiento cambiaría cuando los detalles de implementación de la declaración de cambio cambiaran si escribiera su anulación == incorrectamente.Al reducir las comparaciones a tipos integrales y cadenas y aquellas cosas que se pueden reducir a tipos integrales (y están destinadas a hacerlo), se evitan problemas potenciales.

escribió:

"La declaración de cambio realiza una bifurcación de tiempo constante independientemente de cuántos casos tenga".

Dado que el lenguaje permite cadena tipo que se utilizará en una declaración de cambio. Supongo que el compilador no puede generar código para una implementación de rama de tiempo constante para este tipo y necesita generar un estilo si-entonces.

@mweerden - Ah, ya veo.Gracias.

No tengo mucha experiencia en C# y .NET, pero parece que los diseñadores del lenguaje no permiten el acceso estático al sistema de tipos excepto en circunstancias limitadas.El tipo de La palabra clave devuelve un objeto, por lo que solo se puede acceder a él en tiempo de ejecución.

Creo que Henk acertó con lo de "no tener acceso estático al sistema de tipos".

Otra opción es que no haya orden en los tipos donde pueden estar los números y las cadenas.Por lo tanto, un cambio de tipo no podría construir un árbol de búsqueda binario, solo una búsqueda lineal.

estoy de acuerdo con este comentario que utilizar un enfoque basado en tablas suele ser mejor.

En C# 1.0 esto no era posible porque no tenía genéricos ni delegados anónimos.Las nuevas versiones de C# tienen la estructura necesaria para que esto funcione.También ayuda tener una notación para los literales de objetos.

Prácticamente no tengo conocimiento de C#, pero sospecho que cualquiera de los cambios simplemente se tomó como ocurre en otros lenguajes sin pensar en hacerlo más general o el desarrollador decidió que no valía la pena extenderlo.

Estrictamente hablando, tiene toda la razón en que no hay motivo para imponerle estas restricciones.Se podría sospechar que la razón es que para los casos permitidos la implementación es muy eficiente (como lo sugiere Brian Ensink (44921)), pero dudo que la implementación sea muy eficiente (w.r.t.declaraciones if) si uso números enteros y algunos casos aleatorios (p. ej.345, -4574 y 1234203).Y en cualquier caso, ¿qué hay de malo en permitirlo para todo (o al menos para más) y decir que sólo es eficiente para casos concretos (como números (casi) consecutivos)?

Sin embargo, puedo imaginar que uno podría querer excluir tipos por razones como la dada por lomaxx (44918).

Editar:@Henk (44970):Si las cadenas se comparten al máximo, las cadenas con el mismo contenido también serán punteros a la misma ubicación de memoria.Luego, si puede asegurarse de que las cadenas utilizadas en los casos se almacenen consecutivamente en la memoria, puede implementar el cambio de manera muy eficiente (es decir,con ejecución en el orden de 2 comparaciones, una suma y dos saltos).

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top