c# - switch - En un conmutador vs diccionario para un valor de Func, ¿cuál es más rápido y por qué?

que es un hub

Question

Supongamos que existe el siguiente código:

private static int DoSwitch(string arg)
{
    switch (arg)
    {
        case "a": return 0;
        case "b": return 1;
        case "c": return 2;
        case "d": return 3;
    }
    return -1;
}

private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
    {
        {"a", () => 0 },
        {"b", () => 1 },
        {"c", () => 2 },
        {"d", () => 3 },
    };

private static int DoDictionary(string arg)
{
    return dict[arg]();
}

Al iterar sobre ambos métodos y comparar, entiendo que el diccionario es un poco más rápido, incluso cuando "a", "b", "c", "d" se expanden para incluir más teclas. ¿Por qué esto es tan?

¿Tiene esto que ver con la complejidad ciclomática? ¿Se debe a que el jitter compila las declaraciones de devolución en el diccionario con el código nativo solo una vez? ¿Es porque la búsqueda del diccionario es O (1), que puede no ser el caso para una instrucción switch ? (Estas son solo conjeturas)

Answer 1

Al igual que con muchas preguntas que implican decisiones de codegen de compilador, la respuesta es "depende".

Construir su propia tabla hash probablemente se ejecute más rápido que el código generado por el compilador en muchos casos porque el compilador tiene otras métricas de costos que está tratando de equilibrar que usted no tiene: principalmente, el consumo de memoria.

Una tabla hash usará más memoria que un puñado de instrucciones IL de if-then-else. Si el compilador escupió una tabla hash para cada instrucción switch en un programa, el uso de la memoria explotaría.

A medida que crece el número de bloques de casos en la instrucción switch, probablemente verá que el compilador produce código diferente. Con más casos, existe una mayor justificación para que el compilador abandone los pequeños y simples patrones if-then-else a favor de alternativas más rápidas pero más gordas.

No sé de manera directa si los compiladores C # o JIT realizan esta optimización en particular, pero un truco de compilación común para las declaraciones de cambio cuando los selectores de caso son muchos y la mayoría es secuencial es calcular un vector de salto. Esto requiere más memoria (en forma de tablas de salto generadas por el compilador incrustadas en la secuencia de código) pero se ejecuta en tiempo constante. Reste arg - "a", use el resultado como índice en la tabla de salto para saltar al bloque de caso apropiado. Boom, ya está hecho, independientemente de si hay 20 o 2000 casos.

Es más probable que un compilador cambie al modo de tabla de salto cuando el tipo de selector de interruptor es char o int o enum y los valores de los selectores de caso son en su mayoría secuenciales ("densa"), ya que estos tipos se pueden restar fácilmente para crear un desplazamiento o índice. Los selectores de cadenas son un poco más difíciles.

Los selectores de cadenas son "internados" por el compilador de C #, lo que significa que el compilador agrega los valores de los selectores de cadenas a un grupo interno de cadenas únicas. La dirección o token de una cadena interna se puede usar como su identidad, lo que permite optimizaciones similares a la int cuando se comparan cadenas internas para identidad / igualdad de byte. Con suficientes selectores de casos, el compilador C # producirá un código IL que busca el equivalente interno de la cadena arg (búsqueda de tablas hash), luego compara (o salta tablas) el token interno con los tokens del selector de casos precalculados.

Si puede convencer al compilador para que produzca código de tabla de salto en el caso del selector char / int / enum, esto puede ejecutarse más rápido que utilizando su propia tabla hash.

Para el caso del selector de cadenas, el código IL todavía tiene que hacer una búsqueda hash, por lo que cualquier diferencia en el rendimiento respecto al uso de su propia tabla hash probablemente sea un lavado.

En general, sin embargo, no debe insistir demasiado en estos matices del compilador al escribir el código de la aplicación. Las instrucciones de cambio generalmente son mucho más fáciles de leer y entender que una tabla de hash de punteros de función. Las sentencias de conmutación que son lo suficientemente grandes como para empujar al compilador al modo de tabla de salto a menudo son demasiado grandes para ser humanamente legibles.

Si encuentra una declaración de cambio en un punto de acceso de rendimiento de su código, y ha medido con un generador de perfiles que tiene un impacto tangible en el rendimiento, entonces cambiar su código para usar su propio diccionario es una compensación razonable para una ganancia de rendimiento.

Escribir su código para usar una tabla hash desde el principio, sin mediciones de rendimiento para justificar esta elección, es una sobreingeniería que conducirá a un código insondable con un costo de mantenimiento innecesariamente mayor. Mantenlo simple.

Answer 2

Este es un buen ejemplo de por qué los micro-puntos de referencia pueden ser engañosos. El compilador de C # genera IL diferentes dependiendo del tamaño del interruptor / caja. Así que encender una cadena como esta

switch (text) 
{
     case "a": Console.WriteLine("A"); break;
     case "b": Console.WriteLine("B"); break;
     case "c": Console.WriteLine("C"); break;
     case "d": Console.WriteLine("D"); break;
     default: Console.WriteLine("def"); break;
}

produce IL que esencialmente hace lo siguiente para cada caso:

L_0009: ldloc.1 
L_000a: ldstr "a"
L_000f: call bool [mscorlib]System.String::op_Equality(string, string)
L_0014: brtrue.s L_003f

y después

L_003f: ldstr "A"
L_0044: call void [mscorlib]System.Console::WriteLine(string)
L_0049: ret 

Es decir, es una serie de comparaciones. Entonces el tiempo de ejecución es lineal.

Sin embargo, agregar casos adicionales, por ejemplo, para incluir todas las letras de az, cambia el IL generado a algo como esto para cada uno:

L_0020: ldstr "a"
L_0025: ldc.i4.0 
L_0026: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

y

L_0176: ldloc.1 
L_0177: ldloca.s CS$0$0001
L_0179: call instance bool [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
L_017e: brfalse L_0314

y finalmente

L_01f6: ldstr "A"
L_01fb: call void [mscorlib]System.Console::WriteLine(string)
L_0200: ret 

Es decir, ahora usa un diccionario en lugar de una serie de comparaciones de cadenas, y así obtiene el rendimiento de un diccionario.

En otras palabras, el código IL generado para estos son diferentes y esto es solo en el nivel IL. El compilador JIT puede optimizar aún más.

TL; DR : Entonces la moral de la historia es mirar los datos reales y el perfil en lugar de tratar de optimizar en base a micro-puntos de referencia.

Answer 3

La respuesta corta es que la instrucción switch se ejecuta linealmente, mientras que el diccionario se ejecuta de forma logarítmica.

En el nivel de IL, una pequeña declaración de cambio generalmente se implementa como una serie de enunciados if-elseif que comparan la igualdad de la variable conmutada con cada caso. Por lo tanto, esta instrucción se ejecutará en un tiempo linealmente proporcional al número de opciones válidas para myVar; los casos se compararán en el orden en que aparecen, y el peor de los casos es que todas las comparaciones se prueban y el último coincide o ninguno. Entonces, con 32 opciones, el peor caso es que no es ninguna de ellas, y el código habrá hecho 32 comparaciones para determinar esto.

Un diccionario, por otro lado, usa una colección optimizada por índice para almacenar valores. En .NET, un diccionario se basa en un Hashtable, que tiene un tiempo de acceso constante (la desventaja es una eficiencia de espacio extremadamente pobre). Otras opciones comúnmente usadas para "mapear" colecciones como Dictionaries incluyen estructuras de árbol balanceadas como árboles rojo-negro, que proporcionan acceso logarítmico (y eficiencia de espacio lineal). Cualquiera de estos permitirá que el código encuentre la clave correspondiente al "caso" apropiado en la colección (o determine que no existe) mucho más rápido que una declaración de cambio puede hacer lo mismo.

EDITAR : Otras respuestas y comentaristas han tocado esto, por lo que, en aras de la integridad, lo haré también. El compilador de Microsoft no siempre compila un cambio a un if / elseif como inferí originalmente. Normalmente lo hace con un número pequeño de casos, y / o con casos "dispersos" (valores no incrementales, como 1, 200, 4000). Con conjuntos más grandes de casos adyacentes, el compilador convertirá el interruptor en una "tabla de salto" usando una declaración CIL. Con grandes conjuntos de casos dispersos, el compilador puede implementar una búsqueda binaria para reducir el campo, y luego "desaparecer" un pequeño número de casos dispersos o implementar una tabla de salto para casos adyacentes.

Sin embargo, el compilador generalmente elegirá la implementación que es el mejor compromiso de rendimiento y eficiencia de espacio, por lo que solo usará una tabla de salto para una gran cantidad de casos densamente empaquetados. Esto se debe a que una tabla de salto requiere un espacio en la memoria en el orden del rango de casos que debe cubrir, que para los casos dispersos es terriblemente ineficiente en cuanto a la memoria. Al usar un diccionario en el código fuente, básicamente fuerza la mano del compilador; lo hará a su manera, en lugar de comprometer el rendimiento para aumentar la eficiencia de la memoria.

Por lo tanto, esperaría que la mayoría de los casos en los que una instrucción switch o un diccionario se puedan utilizar en la fuente tengan un mejor rendimiento cuando se usa un diccionario. En cualquier caso, deben evitarse grandes cantidades de casos en instrucciones de conmutación, ya que son menos fáciles de mantener.

Answer 4

Por defecto, un interruptor en una cadena se implementa como una construcción if / else / if / else. Según lo sugerido por Brian, el compilador convertirá el cambio a una tabla hash cuando crezca. Bart de Smet muestra esto en este video de channel9 , (el cambio se discute a las 13:50)

El compilador no lo hace por 4 elementos porque es conservador, para evitar que el costo de la optimización supere los beneficios. Construir el hashtable cuesta un poco de tiempo y memoria.