objetivo - declaracion de cambio significado

¿El orden de los casos en una declaración de cambio afecta el rendimiento?

Question

Tengo un programa de switch caso:

Casos de cambio de orden ascendente:

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 1:
                        a = 1;
                        break;
                case 2:
                        a = 2;
                        break;
        }
}

Asamblea de código:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        je      .L4
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L4:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

Casos de interruptor de orden descendente:

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 2:
                        a = 1;
                        break;
                case 1:
                        a = 2;
                        break;
        }
}

Asamblea de código:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        jne     .L2
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

Aquí, los casos de orden ascendente generaron más ensamblaje que orden descendente .

Entonces, si tengo más números de casos de cambio, ¿el orden de los casos afecta el rendimiento?

Answer 1

El rendimiento dependería principalmente de la cantidad de fallas de sucursal para un conjunto de datos determinado, no tanto del número total de casos. Y eso, a su vez, depende en gran medida de los datos reales y de cómo el compilador optó por implementar el conmutador (tabla de despacho, condicionales encadenados, árbol de condicionales, no estoy seguro de si puede controlar esto desde C).

Answer 2

En los casos donde la mayoría de las etiquetas de casos son consecutivas, los compiladores a menudo procesarán las instrucciones de cambio para usar tablas de salto en lugar de comparaciones. Los medios exactos por los cuales los compiladores deciden qué forma de salto computarizado utilizar (si corresponde) variarán entre las diferentes implementaciones. A veces, agregar casos adicionales a una declaración de cambio puede mejorar el rendimiento al simplificar el código generado por un compilador (por ejemplo, si el código usa los casos 4-11, mientras que los casos 0-3 se manejan de manera predeterminada, agregando el case 0:; case 1:; case 2:; case 3:; explícito case 0:; case 1:; case 2:; case 3:; antes del default: puede hacer que el compilador compare el operando con 12 y, si es menos, que use una tabla de salto de 12 elementos. La omisión de esos casos puede hacer que el compilador reste 4 antes de comparar la diferencia con 8, y luego usar una tabla de 8 elementos.

Una dificultad al tratar de optimizar las sentencias de conmutación es que los compiladores generalmente saben mejor que los programadores cómo variaría el rendimiento de los diferentes enfoques cuando se les dan ciertas entradas, pero los programadores pueden saber mejor que los compiladores qué distribución de entradas recibiría un programa. Dado algo como:

if (x==0)
  y++;
else switch(x)
{
  ...
}

un compilador "inteligente" puede reconocer que cambiar el código a:

switch(x)
{
  case 0:
    y++;
    break;
  ...
}

podría eliminar una comparación en todos los casos donde x no es cero, al costo de un salto calculado cuando x es cero. Si x no es cero la mayor parte del tiempo, sería un buen intercambio. Sin embargo, si x es cero el 99.9% del tiempo, eso podría ser una mala operación. Diferentes escritores de compiladores difieren en cuanto al grado en que intentarán optimizar las construcciones como las primeras en las últimas.

Answer 3

Estás viendo un código no optimizado, por lo que estudiarlo para obtener un rendimiento no es muy significativo. Si observa el código optimizado para sus ejemplos, ¡encontrará que no hace las comparaciones en absoluto! El optimizador se da cuenta de que la variable de cambio sc siempre tiene el valor 1 , por lo que elimina el case 2 inalcanzable case 2 .

El optimizador también ve que la variable a no se usa después de asignarse, por lo que también elimina el código en el case 1 , dejando main() una función vacía. Y elimina la función prólogo / epílogo que manipula rbp ya que ese registro no está en uso.

Entonces, el código optimizado termina igual para cualquiera de las versiones de su función main() :

main:
    xor eax, eax
    ret

En resumen, para el código de la pregunta, no importa en qué orden coloque las declaraciones del case , ya que no se generará nada de ese código.

¿Importaría el orden de los case en un ejemplo más real en el que el código realmente se genera y se utiliza? Probablemente no. Tenga en cuenta que incluso en su código generado no optimizado , ambas versiones prueban los dos valores de case en orden numérico, verificando primero 1 y luego 2 , independientemente del orden en el código fuente. Claramente, el compilador está haciendo algunas clasificaciones incluso en el código no optimizado.

Asegúrese de tener en cuenta los comentarios de Glenn y Lundin: el orden de las secciones del case no es el único cambio entre sus dos ejemplos, el código real también es diferente. En uno de ellos, los valores de caso coinciden con los valores establecidos en a , pero no en el otro.

Los compiladores utilizan diversas estrategias para las declaraciones de switch / case función de los valores reales utilizados. Pueden usar una serie de comparaciones como en estos ejemplos, o tal vez una tabla de salto. Puede ser interesante estudiar el código generado, pero como siempre, si el rendimiento es importante, observe sus configuraciones de optimización y pruébelo en una situación de la vida real.

Answer 4

La instrucción de cambio generalmente se compila a través de tablas de salto, no por comparaciones simples.

Por lo tanto, no hay pérdida en el rendimiento si permuta las declaraciones de caso.

Sin embargo, a veces es útil mantener más casos en orden consecutivo y no usar ruptura / retorno en algunas entradas, para que el flujo de ejecución vaya al siguiente caso y evite duplicar el código.

Cuando las diferencias de números entre los números de caso son grandes de un caso a otro, como en el case 10: y el case 200000: el compilador seguramente no generará tablas de salto, ya que debería llenar aproximadamente 200K entradas casi todas con un puntero hacia el default: caso, y en este caso utilizará comparaciones.

Answer 5

Probablemente debería habilitar las optimizaciones para su compilador antes de comparar el código de ensamblaje, sin embargo, el problema es que su variable es conocida en el momento de la compilación, por lo que el compilador puede eliminar todo de su función porque no tiene ningún efecto secundario.

Este ejemplo muestra que incluso si cambia el orden de los casos en una declaración de cambio en su ejemplo, GCC y la mayoría de los otros compiladores los reordenarán si las optimizaciones están habilitadas. Utilicé funciones externas para asegurarme de que los valores solo se conocen en tiempo de ejecución, pero también podría haber usado rand por ejemplo.

Además, cuando agrega más casos, el compilador puede reemplazar los saltos condicionales por una tabla que contiene las direcciones de las funciones y GCC aún podrá reordenarlos como se puede ver here .

Answer 6

Su pregunta es muy simple: su código no es el mismo, por lo que no producirá el mismo ensamblaje. El código optimizado no solo depende de las declaraciones individuales, sino también de todo lo que lo rodea. Y en este caso, es fácil explicar la optimización.

En su primer ejemplo, el caso 1 da como resultado a = 1, y el caso 2 da como resultado a = 2. El compilador puede optimizar esto para establecer a = sc para esos dos casos, que es una sola declaración.

En su segundo ejemplo, el caso 1 da como resultado a = 2, y el caso 2 da como resultado a = 1. El compilador ya no puede tomar ese acceso directo, por lo que tiene que establecer explícitamente a = 1 o a = 2 para ambos casos. Por supuesto esto necesita más código.

Si simplemente tomó su primer ejemplo e intercambió el orden de los casos y el código condicional , debería obtener el mismo ensamblador.

Puedes probar esta optimización usando el código

int main()
{
    int a, sc = 1;

    switch (sc)
    {
        case 1:
        case 2:
            a = sc;
            break;
    }
}

Que también debe dar exactamente el mismo ensamblador.

Por cierto, su código de prueba supone que se lee realmente sc. La mayoría de los compiladores de optimización modernos pueden detectar que sc no cambia entre la asignación y la instrucción de cambio, y reemplazan la lectura sc con un valor constante 1. Una optimización adicional eliminará las ramas redundantes de la instrucción de cambio, y luego incluso la asignación podría ser optimizada fuera porque un no cambia realmente. Y desde el punto de vista de la variable a, el compilador también puede descubrir que a no se lee en otro lugar y, por lo tanto, eliminar esa variable del código por completo.

Si realmente desea que se lea un sc y que se establezca, debe declararlos volatile . Afortunadamente, el compilador parece haberlo implementado de la forma que esperaba, pero no puede esperar esto cuando tiene la optimización activada.

Answer 7

La optimización del compilador de las instrucciones de switch es complicada. Por supuesto, debe habilitar las optimizaciones (por ejemplo, intente compilar su código con gcc -O2 -fverbose-asm -S con GCC y busque en el archivo de ensamblador .s generado). Por cierto, en tus dos ejemplos, mi GCC 7 en Debian / Sid / x86-64 simplemente da:

        .type   main, @function
main:
.LFB0:
        .cfi_startproc
# rsp.c:13: }
        xorl    %eax, %eax      #
        ret
        .cfi_endproc

^{(por lo que no hay rastro de switch en ese código generado)}

Si necesita comprender cómo un compilador podría optimizar el switch , hay algunos documentos sobre ese tema, como this .

Si tengo más números de casos de cambio, ¿un orden de casos afecta al rendimiento?

No en general, si está utilizando algún compilador de optimización y pidiéndole que optimice. Véase también this .

Si eso te importa tanto (pero no debería, ¡deja las micro-optimizaciones a tu compilador!), Necesitas un punto de referencia, un perfil y tal vez estudiar el código del ensamblador generado. Por cierto, el caché falla y la asignación de registros podría importar mucho más que el orden de los case así que creo que no debería molestarse en absoluto. Tenga en cuenta las estimaciones de tiempo aproximadas de las computadoras recientes. Ponga los case en el orden más legible (para el siguiente desarrollador que trabaje en el mismo código fuente). Lea también sobre el código roscado . Si tiene razones objetivas (relacionadas con el rendimiento) para reordenar los case (lo cual es muy improbable y debería suceder como máximo una vez en su vida), escriba un buen comentario que explique esas razones.

Si le importa mucho el rendimiento, asegúrese de realizar una benchmark y un profile , y elija un buen compilador y úselo con las opciones de optimización relevantes. Tal vez experimente varias configuraciones de optimization diferentes (y tal vez varios compiladores). Es posible que desee agregar -march=native (además de -O2 o -O2 ). Podría considerar la posibilidad de compilar y vincular con -flto -O2 para habilitar las optimizaciones de tiempo de enlace, etc. También puede desear optimizaciones basadas en perfiles.

Por cierto, muchos compiladores son enormes proyectos de software libre (en particular GCC y Clang ). Si le importa mucho el rendimiento, puede parchear el compilador, extenderlo agregando algún paso de optimización adicional (al forking el código fuente, agregando algún complemento a GCC o algunas extensiones GCC MELT ). Eso requiere meses o años de trabajo (especialmente para comprender las representaciones internas y la organización de ese compilador).

^{(No olvide tener en cuenta los costos de desarrollo; en la mayoría de los casos, cuestan mucho más)}