Se vs. Velocidade do Comutador

As instruções switch são normalmente mais rápidas que as instruções if-else-if equivalentes (como por exemplo, descritas neste artigo ) devido às otimizações do compilador.

Como essa otimização realmente funciona? Alguém tem uma boa explicação?

O compilador pode construir tabelas de salto onde aplicável. Por exemplo, quando você usa o refletor para ver o código produzido, você verá que para grandes opções de strings, o compilador irá gerar código que usa uma tabela de hash para despachá-los. A tabela de hash usa as strings como chaves e delega os códigos de case como valores.

Isto tem melhor tempo de execução assintótico do que muitos encadeados if testes e é realmente mais rápido até mesmo para relativamente poucas strings.

Konrad está correto. No caso de ligar intervalos contíguos de inteiros (por exemplo, onde você tem o caso 0, caso 1, caso 2 .. caso n), o compilador pode fazer algo ainda melhor porque não precisa nem construir uma tabela de hash; ele simplesmente armazena uma matriz de pointers de function e, portanto, pode carregar seu destino de salto em tempo constante.

Esta é uma pequena simplificação, como normalmente qualquer compilador moderno que encontra uma seqüência if..else if .. que poderia ser convertida em uma declaração switch por uma pessoa, o compilador também. Mas apenas para adicionar diversão extra, o compilador não é restringido pela syntax, portanto, pode gerar internamente instruções semelhantes a “switch” que possuem uma combinação de intervalos, destinos únicos, etc – e eles podem (e fazem) para switch e if. instruções .else.

Anyhoo, uma extensão para a resposta do Konrad é que o compilador pode gerar uma tabela de salto, mas isso não é necessariamente garantido (nem desejável). Por uma variedade de motivos, as tabelas de salto fazem coisas ruins para os preditores de ramificação em processadores modernos, e as próprias tabelas fazem coisas ruins para armazenar em cache o comportamento, por exemplo.

 switch(a) { case 0: ...; break; case 1: ...; break; } 

Se um compilador realmente gerasse uma tabela de saltos para isto, provavelmente seria mais lento que a alternativa if..else if.. codifique o estilo por causa da tabela de salto que derrota a previsão de ramificação.

Como Konrad disse, o compilador pode construir uma tabela Jump.

Em C ++ uma razão que pode é por causa da limitação de switches.

  • O termo de comparação deve ser convertido em um int .
  • O case labl deve ser uma constante.

As declarações switch / case podem ser normalmente mais rápidas em 1 nível, mas quando você começa a entrar em 2 ou mais, as declarações switch / case começam a levar de 2 a 3 vezes as declarações if / else aninhadas.

Este artigo tem algumas comparações de velocidade destacando as diferenças de velocidade quando essas instruções são aninhadas.

Por exemplo, de acordo com seus testes, o código de amostra é semelhante ao seguinte:

 if (x % 3 == 0) if (y % 3 == 0) total += 3; else if (y % 3 == 1) total += 2; else if (y % 3 == 2) total += 1; else total += 0; else if (x % 3 == 1) if (y % 3 == 0) total += 3; else if (y % 3 == 1) total += 2; else if (y % 3 == 2) total += 1; else total += 0; else if (x % 3 == 2) if (y % 3 == 0) total += 3; else if (y % 3 == 1) total += 2; else if (y % 3 == 2) total += 1; else total += 0; else if (y % 3 == 0) total += 3; else if (y % 3 == 1) total += 2; else if (y % 3 == 2) total += 1; else total += 0; 

terminado na metade do tempo que o equivalente switch / case statement demorou para executar:

 switch (x % 3) { case 0: switch (y % 3) { case 0: total += 3; break; case 1: total += 2; break; case 2: total += 1; break; default: total += 0; break; } break; case 1: switch (y % 3) { case 0: total += 3; break; case 1: total += 2; break; case 2: total += 1; break; default: total += 0; break; } break; case 2: switch (y % 3) { case 0: total += 3; break; case 1: total += 2; break; case 2: total += 1; break; default: total += 0; break; } break; default: switch (y % 3) { case 0: total += 3; break; case 1: total += 2; break; case 2: total += 1; break; default: total += 0; break; } break; } 

Sim, é um exemplo rudimentar, mas ilustra o ponto.

Portanto, uma conclusão pode ser usar switch / case para tipos simples que tenham apenas um nível de profundidade, mas para comparações mais complexas e vários níveis nesteds use as construções clássicas if / else?

As statistics sem correspondência podem não ser boas.

Se você realmente fizer o download da origem, os valores sem correspondência serão 21, nos casos if e switch. Um compilador deve ser capaz de abstrair, saber qual instrução deve ser executada em todos os momentos, e uma CPU deve ser capaz de prever corretamente.

O caso mais interessante é quando nem todo caso quebra, na minha opinião, mas isso pode não ter sido o escopo do experimento.

Esse é o código para o microcontrolador PIC18 na linguagem C:

 void main() { int s1='0'; int d0; int d1; //if (s1 == '0') {d1 = '0'; d0 = '0';} //else if (s1 == '1') {d1 = '0';d0 = '1';} //else if (s1 == '2') {d1 = '1';d0 = '0';} //else if (s1 == '3') {d1 = '1';d0 = '1';} switch (s1) { case '0': {d1 = '0';d0 = '0';} break; case '1': {d1 = '0';d0 = '1';} break; case '2': {d1 = '1';d0 = '0';} break; case '3': {d1 = '1';d0 = '1';} break; } } 

Com ifs

 s1='0' - 14 cycles s1='1' - 21 cycles s1='2' - 28 cycles s1='3' - 33 cycles s1='4' - 34 cycles 

Com casos

 s1='0' - 17 cycles s2='1' - 23 cycles s3='2' - 29 cycles s4='3' - 35 cycles s5='4' - 32 cycles 

Então, posso supor que, em níveis muito baixos, o ifs é mais rápido. O código na ROM é mais curto também.

A única vantagem do caso if over é quando há um aumento perceptível da frequência de ocorrência do primeiro caso.

Não sei exatamente onde está o limite, mas uso a syntax de maiúsculas, a menos que o primeiro “quase sempre” passe no primeiro teste.