¿Por qué los compiladores de C optimizan el interruptor y si es diferente?

Estaba trabajando en un proyecto personal recientemente cuando me topé con un problema extraño.

En un ciclo muy cerrado, tengo un número entero con un valor entre 0 y 15. Necesito obtener -1 para los valores 0, 1, 8 y 9 y 1 para los valores 4, 5, 12 y 13.

Me volví a Godbolt para verificar algunas opciones y me sorprendió que pareciera que el compilador no podía optimizar una declaración de cambio de la misma manera que una cadena if.

El enlace está aquí: https://godbolt.org/z/WYVBFl

El codigo es:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

Pensé que byc produciría los mismos resultados, y esperaba poder leer los trucos de bits para obtener una implementación eficiente yo mismo, ya que mi solución (la declaración de cambio, en otra forma) fue bastante lenta.

Curiosamente, se bcompiló en bit-hacks mientras no cestaba optimizado o se redujo a un caso diferente adependiendo del hardware de destino.

¿Alguien puede explicar por qué existe esta discrepancia? ¿Cuál es la forma 'correcta' de optimizar esta consulta?

EDITAR:

Aclaración

Yo quiero la solución cambie a ser el más rápido, o una solución similar "limpia". Sin embargo, cuando se compila con optimizaciones en mi máquina, la solución if es significativamente más rápida.

Escribí un programa rápido para demostrar y TIO tiene los mismos resultados que encuentro localmente: ¡ Pruébelo en línea!

Con static inlinela tabla de búsqueda se acelera un poco: ¡ Pruébelo en línea!

Si enumera explícitamente todos los casos, gcc es muy eficiente:

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

solo se compila en una rama indizada simple:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Tenga en cuenta que si no default:está comentado, gcc vuelve a su versión de rama anidada.

Los compiladores de C tienen casos especiales switch, porque esperan que los programadores entiendan el idioma switchy lo exploten.

Código como:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

no pasaría la revisión de los codificadores C competentes tres o cuatro revisores exclamarían simultáneamente "¡esto debería ser un switch!"

No vale la pena que los compiladores de C analicen la estructura de las ifdeclaraciones para la conversión a una tabla de salto. Las condiciones para eso tienen que ser correctas, y la cantidad de variación que es posible en un montón de ifdeclaraciones es astronómica. El análisis es complicado y es probable que resulte negativo (como en "no, no podemos convertir estos ifs en a switch").

El siguiente código calculará su búsqueda sin bifurcación, sin LUT, en ~ 3 ciclos de reloj, ~ 4 instrucciones útiles y ~ 13 bytes de inlinecódigo de máquina x86 de alta capacidad .

Depende de la representación entera del complemento a 2.

Sin embargo, debe asegurarse de que los u32y s32typedefs realmente apunten a tipos enteros sin signo y con signo de 32 bits. stdint.htipos uint32_ty int32_thabría sido adecuado, pero no tengo idea si el encabezado está disponible para usted.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Véalo usted mismo aquí: https://godbolt.org/z/AcJWWf

Sobre la selección de la constante

Su búsqueda es de 16 constantes muy pequeñas entre -1 y +1 inclusive. Cada uno cabe dentro de 2 bits y hay 16 de ellos, que podemos presentar de la siguiente manera:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

Al colocarlos con el índice 0 más cercano al bit más significativo, un solo desplazamiento de 2*numcolocará el bit de signo de su número de 2 bits en el bit de signo del registro. Desplazar a la derecha el número de 2 bits por 32-2 = signo de 30 bits, lo extiende al completo int, completando el truco.

Puede crear el mismo efecto usando solo aritmética:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Aunque, técnicamente, esta sigue siendo una búsqueda (bit a bit).

Si lo anterior parece demasiado arcano, también puedes hacer:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}