¿Por qué un switch no está optimizado de la misma manera que un if else encadenado en c/c++?

Question

Más

Fuente Versión no AMP Editar

¿Por qué un switch no está optimizado de la misma manera que un if else encadenado en c/c++?

La siguiente implementación de square produce una serie de sentencias cmp/je como la que esperaría de una sentencia if encadenada:

int cuadrado(int num) {
    si (num == 0){
        devuelve 0;
    } else if (num == 1){
        devuelve 1;
    } else if (num == 2){
        devuelve 4;
    } else if (num == 3){
        devuelve 9;
    } else if (num == 4){
        devuelve 16;
    } else if (num == 5){
        devuelve 25;
    } else if (num == 6){
        devuelve 36;
    } else if (num == 7){
        devuelve 49;
    } else {
        devuelve num * num;
    }
}

Y lo siguiente produce una tabla de datos para el retorno:

int cuadrado_2(int num) {
    switch (num){
        caso 0: devuelve 0
        caso 1: devuelve 1
        caso 2: devolver 4
        caso 3: devolver 9
        caso 4: devolver 16
        caso 5: devolver 25
        caso 6: return 36
        caso 7: devolver 49;
        por defecto: devuelve num * num;
    }
}

¿Por qué gcc no es capaz de optimizar el superior en el inferior?

Desmontaje como referencia: https://godbolt.org/z/UP_igi

EDIT: curiosamente, MSVC genera una tabla de saltos en lugar de una tabla de datos para el caso del switch. Y sorprendentemente, clang los optimiza con el mismo resultado.

Angela Cojocari

17541

Pregunta editada 19º septiembre 2021 в 7:37

chacham15

Pregunta editada 7º febrero 2020 в 8:59

Programación

gcc c++ c optimization compiler-optimization

7º febrero 2020 в 8:51

17 vistas

Comentarios sobre la pregunta (11)

th33lf · Answer 1 · 2020-02-07T09:38:35+00:00

El código generado para switch-case utiliza convencionalmente una tabla de saltos. En este caso, el retorno directo a través de una tabla de búsqueda parece ser una optimización que aprovecha el hecho de que cada caso aquí implica un retorno. Aunque la norma no garantiza nada al respecto, me sorprendería que un compilador generara una serie de comparaciones en lugar de una tabla de saltos para un switch-case convencional.

En cuanto a if-else, es exactamente lo contrario. Mientras que switch-case se ejecuta en tiempo constante, independientemente del número de ramas, if-else está optimizado para un número menor de ramas. En este caso, lo que se espera es que el compilador genere básicamente una serie de comparaciones en el orden en que se han escrito.

Así que si yo hubiera usado if-else porque espero que la mayoría de las llamadas a square() sean para 0 o 1 y raramente para otros valores, entonces 'optimizar' esto a una tabla de búsqueda podría realmente causar que mi código se ejecute más lento de lo que espero, derrotando mi propósito de usar un if en lugar de un switch. Así que, aunque es discutible, creo que GCC está haciendo lo correcto y clang está siendo demasiado agresivo en su optimización.

Alguien, en los comentarios, compartió un enlace donde clang hace esta optimización y genera código basado en tablas de búsqueda para if-else también. Algo notable sucede cuando reducimos el número de casos a sólo dos (y un defecto) con clang. Vuelve a generar un código idéntico tanto para if como para switch, pero esta vez cambia a comparaciones y movimientos en lugar del enfoque de tabla de búsqueda, ¡para ambos!

En resumen, una secuencia de comparaciones para if-else y una tabla de saltos para switch-case es el patrón estándar que los compiladores tienden a seguir y los desarrolladores tienden a esperar cuando escriben código. Sin embargo, para ciertos casos especiales, algunos compiladores pueden optar por romper este patrón si creen que proporciona una mejor optimización. Otros compiladores pueden optar por seguir el patrón de todos modos, aunque aparentemente no sea óptimo, confiando en que el desarrollador sabe lo que quiere. Ambos enfoques son válidos, con sus propias ventajas y desventajas.

vll · Answer 2 · 2020-02-07T09:00:07+00:00

Una posible razón es que si los valores bajos de num son más probables, por ejemplo siempre 0, el código generado para el primero podría ser más rápido. El código generado para el interruptor toma el mismo tiempo para todos los valores.

Comparando los mejores casos, según esta tabla. Ver esta respuesta para la explicación de la tabla.

Si num == 0, para "if" tienes xor, test, je (con salto), ret. Latencia: 1 + 1 + salto. Sin embargo, xor y test son independientes por lo que la velocidad de ejecución real sería más rápida que 1 + 1 ciclos.

Si num < 7, para "switch" tienes mov, cmp, ja (sin salto), mov, ret. Latencia: 2 + 1 + sin salto + 2.

Una instrucción de salto que no resulta en salto es más rápida que una que resulta en salto. Sin embargo, la tabla no define la latencia para un salto, así que no me queda claro cuál es mejor. Es posible que la última sea siempre mejor y que GCC simplemente no sea capaz de optimizarla.