15

Vendo esses comentários sobre o uso do switch fica a dúvida como ele funciona mesmo e porque ele é diferente do if quando apenas comprar pela igualdade de uma variável única contra uma sequência de valores.

Como isso é compilado?

Ele deve ser preferido ao if?

0

1 Resposta 1

15

Como isso funciona é detalhe de implementação, não é especificado e você não pode se valer disto para fazer algo que só funcione se for implementado de uma forma específica.

O que nós sabemos é que o compilador faz o melhor possível para otimizar o seu uso. Nem sempre ele consegue ou é viável, por isso não há garantias do que ocorrerá. Ele pode funcionar de forma análoga ao if em alguns casos, mesmo que não exatamente da mesma forma.

Mas ele vai tentar gerar uma tabela de desvios (branch table). Com isso ele precisa fazer só uma comparação e pode achar o endereço que ele deve dar um salto na execução de acordo com uma tabela, mais ou menos como um array.

  • Obviamente precisa ser uma comparação simples com dados simples,
  • deve ser denso, ou seja, não pode ter muitas lacunas entre os valores possíveis. Mesmo que não tenha algo a executar para um valor no meio da sequência, ele precisa criar um espaço na tabela para ele. Se tiver muitas lacunas o espaço ocupado pela tabela pode ser grande demais,
  • precisa ter um número mínimo de opções para compensa a tabela,
  • não ocorre desvios durante cada bloco de case.

Tem uma série de detalhes que pode variar em cada caso, mas a ideia é que uma busca que poderia levar tempo O(n), passe levar O(1). Obviamente que um bom compilador considera a arquitetura alvo e gera o código que é mais adequado para ela.

Internamente ele funciona muito como um polimorfismo.

Não ligue para os detalhes não importantes para esse assunto nos códigos abaixo.

Se criarmos um switch para pegar nomes de meses poderemos ver qual o Assembly gerado:

#include <string.h>
#include <stdlib.h>
char *mes(int i) {
  char *texto = (char *)malloc(10);
    switch (i) {
      case 0:
        strcpy(texto, "janeiro");
        break;
      case 1:
        strcpy(texto, "fevereiro");
        break;
      case 2:
        strcpy(texto, "marco");
        break;
      case 3:
        strcpy(texto, "abril");
        break;
      case 4:
        strcpy(texto, "maio");
        break;
      case 5:
        strcpy(texto, "junho");
        break;
      case 6:
        strcpy(texto, "julho");
        break;
      case 7:
        strcpy(texto, "agosto");
        break;
      case 8:
        strcpy(texto, "setembro");
        break;
      case 9:
        strcpy(texto, "outubro");
        break;
      case 10:
        strcpy(texto, "novembro");
        break;
      case 11:
        strcpy(texto, "dezembro");
        break;
    }
    return texto;
}

Veja o Assembly gerado no Compiler Explorer. Também coloquei no Github para referência futura.

Aqui ele faz a comparação uma vez e acha o endereço na tabela:

    cmp     DWORD PTR [rbp-20], 11
    ja      .L2
    mov     eax, DWORD PTR [rbp-20]
    mov     rax, QWORD PTR .L4[0+rax*8]
    jmp     rax

Logo abaixo está a tabela e em seguida os blocos de código que devem ser executados.

Se fizer um if haverá uma comparação para cada valor:

#include <string.h>
#include <stdlib.h>

char *mes(int i) {
  char *texto = (char *)malloc(10);
    if (i == 0) {
      strcpy(texto, "janeiro");
    } else if (i == 1) {
      strcpy(texto, "fevereiro");
    } else if (i == 2) {
      strcpy(texto, "marco");
    } else if (i == 3) {
      strcpy(texto, "abril");
    } else if (i == 4) {
      strcpy(texto, "maio");
    } else if (i == 5) {
      strcpy(texto, "junho");
    } else if (i == 6) {
      strcpy(texto, "julho");
    } else if (i == 7) {
      strcpy(texto, "agosto");
    } else if (i == 8) {
      strcpy(texto, "setembro");
    } else if (i == 9) {
      strcpy(texto, "outubro");
    } else if (i == 10) {
      strcpy(texto, "novembro");
    } else if (i == 11) {
      strcpy(texto, "dezembro");
    }
    return texto;
}

Veja o Assembly gerado no Compiler Explorer. Também no Github.

Pode ver o código se tiver poucas opções (Github). Não otimiza tanto.

Agrupar cases não é um problema e otimiza, como pode ser visto no código (Github). Quando há a cascata ele coloca um item na tabela para cada case, mas a otimização ocorre do mesmo jeito. O break é usado para determinar quando deve encerrar e não continuar andando na tabela.

Já ter muitas lacunas é um problema e praticamente transforma no código do if. Veja como fica (Github).

Mas esse código fica melhor se for um array mesmo. Veja como é mais simples (Github).

Você pode estar pensando que só pode usar um array se for para pegar um valor simples e guardar em algum lugar. Na verdade é possível fazer o mesmo com blocos de código em função e chamar cada função de acordo com o valor de busca, a tabela seria dos endereços das funções.

O GCC tem até uma forma mais explícita de fazer isto, mas não funciona em outros compiladores.

Conclusão

Então é isso, a performance costuma ser melhor. Mais do que a performance deve preferir ele sempre que ele fizer sentido, sempre que for uma sequência a ser analisada. Isso valor para números, caracteres, enumerações, ou outras formas que se resumem a números simples.

O mesmo vale para muitas linguagens que prezam pela performance. Tem linguagem que tem isso mais para enfeite mesmo, ou mais para dar uma sintaxe mais adequada e não traz muita vantagem interna. Mas de forma geral ele não é só porque é mais "bonitinho", ele tem uma função própria e se for usado corretamente não tem desvantagens.

Não use onde não precisa, não tenha medo onde ele é adequado.

4
  • Pensando em alternativas de linguagens, qual forma mais fácil de saber se aquela específica está usando o jeito "mais bonitinho" e não o jeito mais performático?
    – viana
    Commented 11/01/2017 às 12:15
  • @AckLay não sei se entendi o que quer saber.
    – Maniero
    Commented 11/01/2017 às 12:51
  • Basicamente isso - com a outra diferença que nos computadores de hoje, a sequencia if/else if será quase instântanea - com várias camadas de otimização desde o código gerado pelo compilador até a previsão de saltos interna da CPU - mas quando a linguagem C foi criada podia haver diferença de vários ciclos de clock entre a tabela de saltos gerada pelo switch/case e a sequencia de if/else if/
    – jsbueno
    Commented 12/01/2017 às 2:06
  • Mas ainda há ganho em fazer desta forma, os compiladores estão baseados em muito estudo para garantir que o que está sendo feito é o melhor sempre, tanto que se não for o melhor a otimização não é feita. Se for o mesmo resultado e ocupar mais espaço, ele já não fará a otimização. Pelo menos em compiladores decentes.
    – Maniero
    Commented 12/01/2017 às 9:22

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .