Por que os compiladores C otimizam o switch e, se diferentemente

Eu estava trabalhando recentemente em um projeto pessoal quando me deparei com uma questão estranha.

Em um loop muito fechado, tenho um número inteiro com um valor entre 0 e 15. Preciso obter -1 para os valores 0, 1, 8 e 9 e 1 e para os valores 4, 5, 12 e 13.

Eu me virei para o godbolt para verificar algumas opções e fiquei surpreso ao parecer que o compilador não poderia otimizar uma declaração de switch da mesma maneira que uma cadeia if.

O link está aqui: https://godbolt.org/z/WYVBFl

O código é:

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

Eu pensaria que bec produziriam os mesmos resultados, e esperava poder ler os bit-hacks para obter uma implementação eficiente, já que minha solução (a instrução switch - de outra forma) era bastante lenta.

Estranhamente, bcompilado para hacks de bits, enquanto cpraticamente não era otimizado ou reduzido a um caso diferente de adepender do hardware de destino.

Alguém pode explicar por que existe essa discrepância? Qual é a maneira 'correta' de otimizar esta consulta?

EDITAR:

Esclarecimento

Eu quero a solução chave para ser o mais rápido, ou uma solução semelhante "limpa". No entanto, quando compilado com otimizações na minha máquina, a solução if é significativamente mais rápida.

Eu escrevi um programa rápido para demonstrar e o TIO tem os mesmos resultados que encontro localmente: Experimente online!

Com static inlinea tabela de pesquisa acelera um pouco: Experimente online!

Se você enumerar explicitamente todos os casos, o gcc é muito 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;
    }
}

é apenas compilado em um simples ramo indexado:

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

Observe que, se não default:for comentado, o gcc retornará à sua versão de ramificação aninhada.

Os compiladores C têm casos especiais switch, porque esperam que os programadores entendam o idioma switche o explorem.

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;

não passaria na revisão por codificadores C competentes; três ou quatro revisores simultaneamente exclamariam "isso deve ser um switch!"

Não vale a pena que os compiladores C analisem a estrutura de ifinstruções para conversão em uma tabela de salto. As condições para isso precisam ser corretas e a quantidade de variação possível em várias ifdeclarações é astronômica. A análise é ao mesmo tempo complicada e provavelmente negativa (como em: "não, não podemos converter esses ifs em a switch").

O código a seguir calculará sua pesquisa sem ramificação, sem LUT, em ~ 3 ciclos de relógio, ~ 4 instruções úteis e ~ 13 bytes de inlinecódigo de máquina x86 altamente ativável.

Depende da representação inteira do complemento de 2.

Você deve, no entanto, garantir que o u32e s32typedefs realmente aponte para tipos inteiros não assinados e assinados de 32 bits. stdint.htipos uint32_te int32_tteria sido adequado, mas não tenho idéia se o cabeçalho está disponível para você.

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

Veja você mesmo aqui: https://godbolt.org/z/AcJWWf

Na seleção da constante

Sua pesquisa é para 16 constantes muito pequenas entre -1 e +1, inclusive. Cada um se encaixa dentro de 2 bits e há 16 deles, que podemos apresentar da seguinte maneira:

// 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;

Ao colocá-los com o índice 0 mais próximo do bit mais significativo, um único deslocamento de 2*numcolocará o bit de sinal do seu número de 2 bits no bit de sinal do registrador. Mudar para a direita o número de 2 bits por 32-2 = sinal de 30 bits o estende ao máximo int, completando o truque.

Você pode criar o mesmo efeito usando apenas 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 ) ) );
}

Mesmo assim, tecnicamente, essa ainda é uma pesquisa (bit a bit).

Se o exposto acima parecer muito misterioso, você também pode:

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