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

9

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!

LambdaBeta
fuente
44
Sospecho que la respuesta es "Los compiladores no siempre toman decisiones sensatas". Acabo de compilar su código en un objeto con GCC 8.3.0 con -O3, y compiló calgo probablemente peor ao b( ctenía dos saltos condicionales más algunas manipulaciones de bits, frente a un solo salto condicional y una manipulación de bits más simple b), pero aún así mejor que las pruebas ingenuas ítem por ítem. No estoy seguro de lo que realmente estás pidiendo aquí; El simple hecho es que un compilador optimizador puede convertir cualquiera de estos en cualquiera de los otros si así lo desea, y no hay reglas estrictas para lo que hará o no hará.
ShadowRanger
Mi problema es que necesito que sea rápido, pero la solución if no es demasiado fácil de mantener. ¿Hay alguna forma de lograr que el compilador optimice una solución más limpia de manera suficiente? ¿Alguien puede explicar por qué no puede hacerlo en este caso?
LambdaBeta
Comenzaría definiendo al menos las funciones como estáticas, o incluso mejor, alineándolas.
wildplasser
@wildplasser lo acelera, pero ifaún late switch(la búsqueda extraña se vuelve aún más rápida) [TIO a seguir]
LambdaBeta
@LambdaBeta No hay forma de decirle a un compilador que optimice de una manera específica. Notarás que clang y msvc generan un código completamente diferente para estos. Si no te importa y solo quieres lo que funciona mejor en gcc, elige eso. Las optimizaciones del compilador se basan en la heurística, y no ofrecen la solución óptima en todos los casos; Están tratando de ser buenos en el caso promedio, no óptimos en todos los casos.
Cubic

Respuestas:

6

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.

Alain Merigot
fuente
1
@LambdaBeta Debería considerar no aceptar mi respuesta y aceptar esta, porque las CPU modernas de Intel pueden hacer dos lecturas / ciclos de memoria indexada en paralelo, mientras que el rendimiento de mi truco es probablemente 1 búsqueda / ciclo. Por otro lado, tal vez mi pirateo sea más susceptible a la vectorización de 4 vías con SSE2 pslld/ psrado sus equivalentes AVX2 de 8 vías. Mucho depende de las otras particularidades de su código.
Iwillnotexist Idonotexist
4

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").

Kaz
fuente
Lo sé, por eso empecé con el interruptor. Sin embargo, la solución if es significativamente más rápida en mi caso. Básicamente, estoy preguntando si hay una manera de convencer al compilador de que use una mejor solución para el conmutador, ya que pudo encontrar el patrón en los ifs, pero no el conmutador. (No me gustan los ifs específicamente porque no son tan claros o mantenibles)
LambdaBeta
Votado pero no aceptado ya que el sentimiento es exactamente la razón por la que hice esta pregunta. Yo quiero utilizar el interruptor, pero es demasiado lento en mi caso, quiero evitar el ifsi es posible.
LambdaBeta
@LambdaBeta: ¿Hay alguna razón para evitar la tabla de búsqueda? Hágalo staticy use inicializadores designados C99 si desea dejar un poco más claro lo que está asignando, y está claramente perfectamente bien.
ShadowRanger
1
Comenzaría al menos descartando el bit bajo para que el optimizador tenga menos trabajo que hacer.
R .. GitHub DEJA DE AYUDAR AL HIELO
@ShadowRanger Desafortunadamente, eso todavía es más lento que el if(ver edición). @R .. Desarrollé la solución bit a bit completa para el compilador, que es lo que estoy usando por ahora. Desafortunadamente en mi caso, estos son enumvalores, no enteros desnudos, por lo que los hacks bit a bit no son muy fáciles de mantener.
LambdaBeta
4

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.

Iwillnotexist Idonotexist
fuente
Esta podría ser la forma más limpia de hacerlo con un magiccomentario que explica cómo regenerarlo. ¿Podría explicar cómo se le ocurrió?
LambdaBeta
Aceptado ya que esto se puede hacer 'limpio' mientras que también es rápido. (a través de algún preprocesador mágico :) < xkcd.com/541 >)
LambdaBeta
1
Supera mi intento sin ramas:!!(12336 & (1<<x))-!!(771 & (1<<x));
technosaurus
0

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;
}
KevinZ
fuente