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

Question 1

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

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

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

int square_2(int num) {
    switch (num){
        case 0: return 0;
        case 1: return 1;
        case 2: return 4;
        case 3: return 9;
        case 4: return 16;
        case 5: return 25;
        case 6: return 36;
        case 7: return 49;
        default: return num * num;
    }
}

¿Por qué gcc no puede optimizar el superior en el inferior?

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

EDITAR: curiosamente, MSVC genera una tabla de salto en lugar de una tabla de datos para el caso del interruptor. Y, sorprendentemente, clang los optimiza para obtener el mismo resultado.

Question 2

El código generado para switch-case utiliza convencionalmente una tabla de salto. En este caso, la devolución directa a través de una tabla de búsqueda parece ser una optimización que aprovecha el hecho de que todos los casos aquí implican una devolución. Aunque el estándar no ofrece garantías en ese sentido, me sorprendería que un compilador generara una serie de comparaciones en lugar de una tabla de saltos para una caja de interruptores convencional.

ahora viene a if-else, es exactamente lo contrario. Tiempo switch-case se ejecuta en tiempo constante, independientemente del número de ramas, if-else está optimizado para un número menor de sucursales. Aquí, esperaría que el compilador genere básicamente una serie de comparaciones en el orden en que las ha escrito.

Así que si hubiera usado if-else porque espero que la mayoría de las llamadas sean square() ser para 0 o 1 y rara vez para otros valores, luego ‘optimizar’ esto a una tabla de búsqueda podría causar que mi código se ejecute más lento de lo que espero, anulando mi propósito de usar un if en lugar de un switch. Entonces, 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 solo dos (y uno predeterminado) con clang. Una vez más, genera un código idéntico para if y switch, pero esta vez,
cambia a compara y se mueve en lugar del enfoque de tabla de búsqueda, para ambos. ¡Esto significa que incluso el clan que favorece el cambio sabe que el patrón ‘si’ es más óptimo cuando el número de casos es pequeño!

En resumen, una secuencia de comparaciones para if-else y una mesa de salto 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 cuando sientan que proporciona una mejor optimización. Otros compiladores podrían optar por apegarse al patrón de todos modos, incluso si aparentemente no es óptimo, confiando en que el desarrollador sepa lo que quiere. Ambos son enfoques válidos con sus propias ventajas y desventajas.

Question 3

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 cambiar toma el mismo tiempo para todos los valores.

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

Si num == 0, por “si” tienes xor, prueba, 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 “cambiar” tienes mov, cmp, ja (sin salto), mov, ret. Latencia: 2 + 1 + sin salto + 2.

Una instrucción de salto que no da como resultado un salto es más rápida que una que da como resultado un salto. Sin embargo, la tabla no define la latencia para un salto, por lo que no me queda claro cuál es mejor. Es posible que el último siempre sea mejor y GCC simplemente no sea capaz de optimizarlo.

¿Ha sido útil esta solución?