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

9

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!

LambdaBeta
fonte
4
Eu suspeito que a resposta é "Compiladores nem sempre fazem escolhas sensatas". Acabei de compilar seu código para um objeto com o GCC 8.3.0 com -O3, e ele compilou cpara algo provavelmente pior que aou b( cteve dois saltos condicionais mais algumas manipulações de bits, versus apenas um salto condicional e manipulação de bits mais simples b), mas ainda assim item melhor do que ingênuo por testes de itens. Não tenho certeza do que você realmente está pedindo aqui; o simples fato é que um compilador otimizador pode transformar qualquer um desses itens em qualquer um dos outros, se assim o desejar, e não há regras rígidas para o que ele fará ou não fará.
ShadowRanger
Meu problema é que preciso que seja rápido, mas a solução if não é excessivamente sustentável. Existe alguma maneira de fazer o compilador otimizar suficientemente uma solução mais limpa? Alguém pode explicar por que não pode fazê-lo neste caso?
LambdaBeta 10/10/19
Eu começaria definindo pelo menos as funções como estáticas, ou -incluindo-as melhor.
wildplasser 10/10/19
@wildplasser faz acelerá-lo, mas ifainda bate switch(estranhamente pesquisa torna-se ainda mais rápido) [TIO seguir]
LambdaBeta
@LambdaBeta Não há como dizer a um compilador para otimizar de uma maneira específica. Você notará que clang e msvc geram código completamente diferente para eles. Se você não se importa e quer apenas o que funciona melhor no gcc, escolha isso. As otimizações do compilador são baseadas em heurísticas, e elas não produzem a solução ideal em todos os casos; Eles estão tentando ser bons no caso médio, não ideais em todos os casos.
Cubic

Respostas:

6

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.

Alain Merigot
fonte
11
@LambdaBeta Você deve aceitar minha resposta e aceitar esta, porque as modernas CPUs Intel podem fazer duas leituras / ciclos de memória indexada paralela, enquanto o rendimento do meu truque é provavelmente uma pesquisa / ciclo. Por outro lado, talvez meu hack seja mais passível de vetorização em quatro direções com SSE2 pslld/ psradou seus equivalentes em AVX2 em 8 vias. Depende muito das outras particularidades do seu código.
Iwillnotexist Idonotexist 11/11/19
4

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

Kaz
fonte
Eu sei, é por isso que comecei com o switch. No entanto, a solução if é significativamente mais rápida no meu caso. Estou basicamente perguntando se existe uma maneira de convencer o compilador a usar uma solução melhor para o switch, pois ele conseguiu encontrar o padrão no ifs, mas não no switch. (Eu não gosto do ifs especificamente porque eles não são tão claras ou sustentável)
LambdaBeta
Votado mas não aceito, já que o sentimento é exatamente o motivo pelo qual fiz essa pergunta. Eu quero usar o interruptor, mas é muito lento no meu caso, eu quero evitar o ifse possível.
LambdaBeta 10/10/19
@LambdaBeta: Existe algum motivo para evitar a tabela de pesquisa? Faça isso statice use os inicializadores designados C99 se quiser deixar um pouco mais claro o que você está atribuindo, e está claramente perfeitamente bem.
ShadowRanger
11
Eu começaria pelo menos descartando o pouco, para que haja menos trabalho para o otimizador.
R .. GitHub PARE DE AJUDAR O GELO
@ShadowRanger Infelizmente ainda é mais lento que o if(veja editar). @R .. Eu trabalhei com a solução bit a bit completa para o compilador, que é o que estou usando no momento. Infelizmente, no meu caso, esses são enumvalores, não números inteiros nus; portanto, os hacks bit a bit não são muito sustentáveis.
LambdaBeta 10/10
4

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.

Não existirá idonotexist
fonte
Essa pode ser a maneira mais limpa de fazê-lo com um magiccomentário explicando como regenerá-la. Você poderia explicar como surgiu?
LambdaBeta 10/10/19
Aceito, pois isso pode ser feito 'limpo' enquanto também é rápido. (via alguma mágica pré-processador :) < xkcd.com/541 >)
LambdaBeta
11
Supera minha tentativa sem ramificação:!!(12336 & (1<<x))-!!(771 & (1<<x));
technosaurus 11/11
0

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