Por que uma opção não é otimizada da mesma maneira que encadeada, se mais no c / c ++?

39

A implementação a seguir do square produz uma série de instruções cmp / je, como eu esperaria de uma instrução if encadeada:

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

E o seguinte produz uma tabela de dados para 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 que o gcc não consegue otimizar o de cima para o de baixo?

Desmontagem para referência: https://godbolt.org/z/UP_igi

EDIT: curiosamente, o MSVC gera uma tabela de salto em vez de uma tabela de dados para o caso do comutador. E, surpreendentemente, o clang os otimiza para o mesmo resultado.

c++ c gcc optimization compiler-optimization chacham15
fonte
3
O que você quer dizer com "comportamento indefinido"? Contanto que o comportamento observável seja o mesmo, o compilador pode gerar qualquer código de montagem / máquina que desejar
bolov
2
@ user207421 ignorando os return; os casos não têm breaks, portanto, o switch também possui uma ordem específica de execução. A cadeia if / else tem retornos em todos os ramos, a semântica neste caso é equivalente. A otimização não é impossível . Como um contra-exemplo, o icc não otimiza nenhuma das funções.
user1810087 7/02
9
Talvez a resposta mais simples ... o gcc simplesmente não consiga ver essa estrutura e otimizá-la (ainda).
user1810087 7/02
3
Eu concordo com @ user1810087. Você simplesmente encontrou o limite atual do processo de refinamento do compilador. Um subconjunto de sub-casos que atualmente não é reconhecido como otimizável (por alguns compiladores). De fato, nem toda cadeia if-if pode ser otimizada dessa maneira, mas apenas o subconjunto no qual a variável SAME é testada em relação a valores constantes.
Roberto Caboni
11
O if-else possui uma ordem de execução diferente, de cima para baixo. Ainda assim, substituir o código por instruções just if não melhorou o código da máquina. O switch, por outro lado, não possui uma ordem de execução predefinida e é essencialmente apenas uma tabela de goto jump glorificada. Dito isto, um compilador pode raciocinar sobre o comportamento observável aqui; portanto, a baixa otimização da versão if-else é bastante decepcionante.
Lundin

Respostas:

29

O código gerado para switch-caseconvencionalmente usa uma tabela de salto. Nesse caso, o retorno direto através de uma tabela de consulta parece ser uma otimização, aproveitando o fato de que todos os casos aqui envolvem um retorno. Embora o padrão não garanta esse efeito, eu ficaria surpreso se um compilador gerasse uma série de comparações em vez de uma tabela de salto para um caso de comutação convencional.

Agora, chegando if-else, é exatamente o oposto. Embora seja switch-caseexecutado em tempo constante, independentemente do número de ramificações, if-elseé otimizado para um número menor de ramificações. Aqui, você esperaria que o compilador gere basicamente uma série de comparações na ordem em que você as escreveu.

Então, se eu tivesse usado if-elseporque espero maioria das chamadas para square()ser para 0ou 1e raramente por outros valores, em seguida, 'otimizar' a um table-lookup poderia realmente fazer com o meu código para executar mais lento do que eu esperava, derrotando o meu propósito para o uso de uma ifvez de um switch. Portanto, embora seja discutível, acho que o GCC está fazendo a coisa certa e o clang está sendo excessivamente agressivo em sua otimização.

Alguém, nos comentários, compartilhou um link em que o clang faz essa otimização e também gera código baseado em tabela de pesquisa if-else. Algo notável acontece quando reduzimos o número de casos para apenas dois (e o padrão) com o clang. Mais uma vez, gera código idêntico para if e switch, mas desta vez passa para compara e move, em vez da abordagem da tabela de pesquisa, para ambos. Isso significa que mesmo o clang que favorece a troca sabe que o padrão 'if' é mais ideal quando o número de casos é pequeno!

Em resumo, uma sequência de comparações para if-elsee uma tabela de salto para switch-caseé o padrão padrão que os compiladores tendem a seguir e os desenvolvedores tendem a esperar quando escrevem código. No entanto, em certos casos especiais, alguns compiladores podem optar por quebrar esse padrão quando acharem que ele fornece uma melhor otimização. Outros compiladores podem simplesmente optar por seguir o padrão de qualquer maneira, mesmo que aparentemente sejam abaixo do ideal, confiando no desenvolvedor para saber o que ele deseja. Ambas são abordagens válidas com suas próprias vantagens e desvantagens.

th33lf
fonte
2
Sim, a otimização é uma espada de vários gumes: o que eles escrevem, o que querem, o que recebem e quem amaldiçoamos por isso.
Deduplicator
11
"... então, 'otimizar' isso para uma pesquisa de tabela realmente faria com que meu código fosse mais lento do que eu esperava ..." Você pode fornecer uma justificativa para isso? Por que uma tabela de salto seria mais lenta que duas possíveis ramificações condicionais (para verificar entradas contra 0e 1)?
Cody Gray
@CodyGray Eu tenho que confessar que não cheguei ao nível de contagem de ciclos - apenas senti que a carga da memória através de um ponteiro pode levar mais ciclos do que comparar e pular, mas posso estar errado. No entanto, espero que você concorde comigo que mesmo neste caso, pelo menos para '0', ifé obviamente mais rápido? Agora, aqui está um exemplo de plataforma em que 0 e 1 seriam mais rápidos ao usar do ifque ao usar o switch: godbolt.org/z/wcJhvS (Observe que também há várias outras otimizações em jogo aqui)
th33lf
11
Bem, contar ciclos não funciona em arquiteturas modernas superescalares OOO. :-) As cargas da memória não serão mais lentas que as ramificações imprevisíveis; portanto, a questão é qual a probabilidade de previsão da ramificação? Essa pergunta se aplica a todo tipo de ramificações condicionais, sejam geradas por ifinstruções explícitas ou automaticamente pelo compilador. Como não sou especialista em ARM, não tenho muita certeza se a reivindicação que você está fazendo switché mais rápida do que ifé verdade. Isso dependeria da penalidade para ramos imprevisíveis, e isso realmente dependeria de qual ARM.
Cody Gray
0

Uma lógica possível é que, se os valores baixos de numsão mais prováveis, por exemplo sempre 0, o código gerado para o primeiro pode ser mais rápido. O código gerado para o switch leva tempo igual para todos os valores.

Comparando os melhores casos, de acordo com esta tabela . Veja esta resposta para a explicação da tabela.

Se num == 0, para "se" você tiver xor, teste, je (com salto), ret. Latência: 1 + 1 + salto. No entanto, xor e test são independentes, portanto a velocidade de execução real seria mais rápida que 1 + 1 ciclos.

Se num < 7, para "switch" você tiver mov, cmp, ja (sem salto), mov, ret. Latência: 2 + 1 + sem salto + 2.

Uma instrução de salto que não resulta em salto é mais rápida do que uma instrução que resulta em salto. No entanto, a tabela não define a latência para um salto, portanto, não está claro para mim qual é o melhor. É possível que o último seja sempre melhor e o GCC simplesmente não consiga otimizá-lo.

vll
fonte
11
Hmm, teoria interessante, mas para ifs vs switch você tem: xor, test, jmp vs mov, cmp jmp. Três instruções, cada uma com a última sendo um salto. Parece igual no melhor dos casos, não?
chacham15
3
"Uma instrução de salto que não resulta em salto é mais rápida que uma instrução que resulta em salto." É a previsão do ramo que importa.
geza 07/02