A seguinte implementação do quadrado produz uma série de declarações cmp/je como eu esperaria de uma declaração encadeada se fosse uma declaração:
int quadrado(int num) {\i1}
se (num === 0){
devolver 0;
} senão se (num == 1){
devolução 1;
} senão se (num == 2){
devolução 4;
} senão se (num == 3){
devolver 9;
} caso contrário, se (num == 4){
devolver 16;
} caso contrário, se (num == 5){
devolver 25;
} caso contrário, se (num == 6){
devolver 36;
} caso contrário, se (num == 7){
devolver 49;
} else {
devolver num * num;
}
}
E o que se segue produz uma tabela de dados para devolução:
int quadrado_2(int num) {
interruptor (num){
caso 0: devolução 0;
caso 1: devolução 1;
caso 2: devolução 4;
caso 3: devolução 9;
caixa 4: devolução 16;
caixa 5: devolução 25;
caso 6: devolução 36; caso 6: devolução 36;
caso 7: devolução 49; caso 7: devolução 49;
devolução num * num;
}
}
Porque é que o gcc não é capaz de optimizar a parte superior para a inferior?
Dissassembly for reference: https://godbolt.org/z/UP_igi
EDIT: curiosamente, MSVC gera uma tabela de salto em vez de uma tabela de dados para o caso de interruptor. E, surpreendentemente, o clang optimiza-os para o mesmo resultado.
O código gerado para a "caixa de interruptores" utiliza convencionalmente uma tabela de salto. Neste caso, o retorno directo através de uma tabela de "look-up" parece ser uma optimização, fazendo uso do facto de que cada caso aqui envolve um retorno. Embora a norma não dê garantias nesse sentido, ficaria surpreendido se um compilador gerasse uma série de comparações em vez de uma tabela de salto para uma caixa de comutação convencional.
Agora chegando ao "se-else", é exactamente o oposto. Enquanto que o "caso de troca" executa-se em tempo constante, independentemente do número de ramos, o "se-else" é optimizado para um número menor de ramos. Aqui, seria de esperar que o compilador gerasse basicamente uma série de comparações na ordem em que as escreveu.
Assim, se eu tivesse utilizado o "se-else" porque espero que a maioria das chamadas para o "quadrado()square()
ser para 0
ou 1
e raramente para outros valores, então 'optimizar' isto para um "table-lookup" poderia de facto fazer com que o meu código corresse mais devagar do que espero, derrotando o meu propósito de utilizar um "se" em vez de um "switch". Assim, embora seja discutível, sinto que o GCC está a fazer a coisa certa e que está a ser excessivamente agressivo na sua optimização.
Alguém tinha, nos comentários, partilhado uma ligação onde clang faz esta optimização e gera um código baseado em tabelas de pesquisa também para 'if-else'. Algo notável acontece quando reduzimos o número de casos para apenas dois (e um por defeito) com o clang. Mais uma vez gera um código idêntico para ambos se e mudar, mas desta vez, muda para comparações e movimentos em vez da abordagem da tabela de pesquisa, para ambos!
Em resumo, uma sequência de comparações para "se-else" e uma tabela de salto para "caso a caso" é o padrão padrão que os compiladores tendem a seguir e os programadores tendem a esperar quando escrevem código. Contudo, para certos casos especiais, alguns compiladores podem optar por quebrar este padrão onde acham que ele proporciona uma melhor optimização. Outros compiladores podem simplesmente optar por aderir ao padrão de qualquer forma, mesmo que aparentemente subaproveitado, confiando que o programador saiba o que quer. Ambas são abordagens válidas com as suas próprias vantagens e desvantagens.
Uma das razões possíveis é que se os valores baixos de num
sã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 a troca leva o mesmo tempo para todos os valores.
Comparando os melhores casos, de acordo com esta tabela. Ver esta resposta para a explicação da tabela.
Se num == 0
, for "if" tem xor, test, je (com salto), ret. Latência: 1 + 1 + salto. No entanto, xor e teste são independentes, pelo que a velocidade real de execução seria mais rápida do que 1 + 1 ciclos.
Se num < 7
, para " switch" tem mov, cmp, ja (sem salto), mov, ret. Latência: 2 + 1 + sem saltar + 2.
Uma instrução de salto que não resulta em saltar é mais rápida do que uma que resulta em saltar. No entanto, a tabela não define a latência de um salto, pelo que não está claro para mim qual é melhor. É possível que a última seja sempre melhor e que a GCC simplesmente não seja capaz de a optimizar.