Limitações da instrução switch C # - por quê?

Question

Ao escrever uma instrução switch, parece haver duas limitações sobre o que você pode ativar nas instruções case.

Por exemplo (e sim, eu sei, se você está fazendo esse tipo de coisa, provavelmente significa que seu Orientado a Objeto (OO) é duvidosa - este é apenas um exemplo inventado!),

  Type t = typeof(int);

  switch (t) {

    case typeof(int):
      Console.WriteLine("int!");
      break;

    case typeof(string):
      Console.WriteLine("string!");
      break;

    default:
      Console.WriteLine("unknown!");
      break;
  }

Aqui, a instrução switch() falha com 'Um valor de tipo integral esperado' e as instruções case falham com 'Um valor constante é esperado'.

Por que razão existem estas restrições e qual é a justificação subjacente?Não vejo nenhuma razão para a instrução switch tem sucumbir apenas à análise estática e por que o valor ativado deve ser integral (ou seja, primitivo).Qual é a justificativa?

Answer 1

Esta é minha postagem original, que gerou algum debate ... porque está errado:

A instrução Switch não é a mesma coisa que uma grande instrução IF-ELSE.Cada caso deve ser único e avaliado estaticamente.A declaração do Switch faz uma ramificação constante de tempo, independentemente de quantos casos você tenha.A instrução IF-ELSE avalia cada condição até encontrar uma que seja verdadeira.

---

Na verdade, a instrução switch C# é não sempre um ramo de tempo constante.

Em alguns casos, o compilador usará uma instrução switch CIL que é de fato uma ramificação de tempo constante usando uma tabela de salto.No entanto, em casos esparsos, como apontado por Ivan Hamilton o compilador pode gerar algo totalmente diferente.

Na verdade, isso é muito fácil de verificar escrevendo várias instruções switch C#, algumas esparsas, outras densas, e observando o CIL resultante com a ferramenta ildasm.exe.

Answer 2

É importante não confundir a instrução switch C# com a instrução switch CIL.

O switch CIL é uma tabela de salto que requer um índice em um conjunto de endereços de salto.

Isso só é útil se os casos da opção C# forem adjacentes:

case 3: blah; break;
case 4: blah; break;
case 5: blah; break;

Mas de pouca utilidade se não forem:

case 10: blah; break;
case 200: blah; break;
case 3000: blah; break;

(Você precisaria de uma tabela com tamanho de aproximadamente 3.000 entradas, com apenas 3 slots usados)

Com expressões não adjacentes, o compilador pode começar a realizar verificações lineares if-else-if-else.

Com conjuntos maiores de expressões não adjacentes, o compilador pode começar com uma pesquisa em árvore binária e, finalmente, if-else-if-else, os últimos itens.

Com conjuntos de expressões contendo grupos de itens adjacentes, o compilador pode pesquisar em árvore binária e, finalmente, uma opção CIL.

Isso está cheio de "mays" e "mights" e depende do compilador (pode ser diferente com Mono ou Rotor).

Repliquei seus resultados em minha máquina usando casos adjacentes:

tempo total para executar uma chave de 10 vias, 10.000 iterações (ms):25.1383
tempo aproximado por interruptor de 10 vias (ms):0,00251383

tempo total para executar uma chave de 50 vias, 10.000 iterações (ms):26.593
tempo aproximado por chave de 50 vias (ms):0,0026593

tempo total para executar uma chave de 5.000 vias, 10.000 iterações (ms):23.7094
tempo aproximado por chave de 5.000 vias (ms):0,00237094

tempo total para executar uma chave de 50.000 vias, 10.000 iterações (ms):20.0933
tempo aproximado por interruptor de 50.000 vias (ms):0,00200933

Então também usei expressões case não adjacentes:

tempo total para executar uma chave de 10 vias, 10.000 iterações (ms):19.6189
tempo aproximado por interruptor de 10 vias (ms):0,00196189

tempo total para executar uma chave de 500 vias, 10.000 iterações (ms):19.1664
tempo aproximado por chave de 500 vias (ms):0,00191664

tempo total para executar uma chave de 5.000 vias, 10.000 iterações (ms):19.5871
tempo aproximado por chave de 5.000 vias (ms):0,00195871

Uma instrução switch de 50.000 casos não adjacente não seria compilada.
"Uma expressão é muito longa ou complexa para compilar perto de 'ConsoleApplication1.Program.Main(string[])'

O que é engraçado aqui é que a pesquisa na árvore binária aparece um pouco (provavelmente não estatisticamente) mais rápida do que a instrução de comutação CIL.

Brian, você usou a palavra "constante", que tem um significado muito definido do ponto de vista da teoria da complexidade computacional.Embora o exemplo simplista de inteiro adjacente possa produzir CIL que é considerado O(1) (constante), um exemplo esparso é O(log n) (logarítmico), os exemplos agrupados ficam em algum lugar no meio e os pequenos exemplos são O(n) (linear ).

Isso nem mesmo aborda a situação String, na qual um valor estático Generic.Dictionary<string,int32> podem ser criados e sofrerão sobrecarga definitiva no primeiro uso.O desempenho aqui dependerá do desempenho de Generic.Dictionary.

Se você verificar o Especificação da linguagem C# (não a especificação CIL) Você encontrará "15.7.2 A instrução Switch" não menciona "tempo constante" ou que a implementação subjacente usa a instrução CIL Switch (tenha muito cuidado para assumir essas coisas).

No final do dia, uma troca C# contra uma expressão inteira em um sistema moderno é uma operação de submicrossegundos e normalmente não vale a pena se preocupar.

---

É claro que estes tempos dependerão das máquinas e das condições.Eu não prestaria atenção a esses testes de tempo, as durações de microssegundos das quais estamos falando são ofuscadas por qualquer código “real” sendo executado (e você deve incluir algum “código real”, caso contrário o compilador otimizará a ramificação), ou instabilidade no sistema.Minhas respostas são baseadas no uso IL DASM para examinar o CIL criado pelo compilador C#.É claro que isso não é definitivo, pois as instruções reais que a CPU executa são então criadas pelo JIT.

Eu verifiquei as instruções finais da CPU realmente executadas em minha máquina x86 e posso confirmar uma simples opção de conjunto adjacente fazendo algo como:

  jmp     ds:300025F0[eax*4]

Onde uma pesquisa em árvore binária está cheia de:

  cmp     ebx, 79Eh
  jg      3000352B
  cmp     ebx, 654h
  jg      300032BB
  …
  cmp     ebx, 0F82h
  jz      30005EEE

Answer 3

A primeira razão que vem à mente é histórico:

Como a maioria dos programadores C, C++ e Java não estão acostumados a ter tais liberdades, eles não as exigem.

Outra razão, mais válida, é que o a complexidade da linguagem aumentaria:

Em primeiro lugar, os objetos devem ser comparados com .Equals() ou com o == operador?Ambos são válidos em alguns casos.Devemos introduzir uma nova sintaxe para fazer isso?Deveríamos permitir que o programador introduzisse seu próprio método de comparação?

Além disso, permitir ligar objetos quebrar suposições subjacentes sobre a instrução switch.Existem duas regras que governam a instrução switch que o compilador não seria capaz de impor se os objetos pudessem ser ativados (veja o Especificação da linguagem C# versão 3.0, §8.7.2):

• Que os valores dos rótulos dos switches são constante
• Que os valores dos rótulos dos switches são distinto (para que apenas um bloco switch possa ser selecionado para uma determinada expressão switch)

Considere este exemplo de código no caso hipotético em que valores de caso não constantes eram permitidos:

void DoIt()
{
    String foo = "bar";
    Switch(foo, foo);
}

void Switch(String val1, String val2)
{
    switch ("bar")
    {
        // The compiler will not know that val1 and val2 are not distinct
        case val1:
            // Is this case block selected?
            break;
        case val2:
            // Or this one?
            break;
        case "bar":
            // Or perhaps this one?
            break;
    }
}

O que o código fará?E se as declarações de caso forem reordenadas?Na verdade, uma das razões pelas quais o C# tornou ilegal o switch fall-through é que as instruções switch poderiam ser reorganizadas arbitrariamente.

Estas regras existem por uma razão - para que o programador possa, ao olhar para um bloco de caso, saber com certeza a condição precisa sob a qual o bloco é inserido.Quando a instrução switch acima mencionada cresce para 100 linhas ou mais (e crescerá), esse conhecimento é inestimável.

Answer 4

A propósito, o VB, tendo a mesma arquitetura subjacente, permite muito mais flexibilidade Select Case declarações (o código acima funcionaria em VB) e ainda produz código eficiente onde isso é possível, portanto o argumento por restrição técnica deve ser considerado cuidadosamente.

Answer 5

Principalmente, essas restrições existem por causa dos designers de linguagem.A justificativa subjacente pode ser a compatibilidade com a história, os ideais da linguagem ou a simplificação do design do compilador.

O compilador pode (e escolhe) escolher:

• crie uma grande declaração if-else
• use uma instrução de switch MSIL (tabela de salto)
• construir um genérico.dicionáriou003Cstring,int32> , preencha -o no primeiro uso e ligue para o genérico.dicionário <> :: trygetValue () para que um índice passe para uma instrução MSIL Switch (tabela de salto)
• Use uma combinação de saltos de if-els e msil "switch"

A instrução switch NÃO É uma ramificação de tempo constante.O compilador pode encontrar atalhos (usando buckets de hash, etc.), mas casos mais complicados gerarão código MSIL mais complicado, com alguns casos ramificando-se antes de outros.

Para lidar com o caso String, o compilador acabará (em algum momento) usando a.Equals(b) (e possivelmente a.GetHashCode() ).Acho que seria trivial para o compilador usar qualquer objeto que satisfizesse essas restrições.

Quanto à necessidade de expressões case estáticas...algumas dessas otimizações (hashing, cache, etc.) não estariam disponíveis se as expressões case não fossem determinísticas.Mas já vimos que às vezes o compilador apenas escolhe o caminho simplista do tipo if-else-if-else de qualquer maneira...

Editar: lomaxx - Seu entendimento do operador "typeof" não está correto.O operador "typeof" é usado para obter o objeto System.Type para um tipo (nada a ver com seus supertipos ou interfaces).Verificar a compatibilidade em tempo de execução de um objeto com um determinado tipo é tarefa do operador "is".O uso de “typeof” aqui para expressar um objeto é irrelevante.

Answer 6

Ainda no assunto, de acordo com Jeff Atwood, a instrução switch é uma atrocidade de programação.Use-os com moderação.

Muitas vezes você pode realizar a mesma tarefa usando uma tabela.Por exemplo:

var table = new Dictionary<Type, string>()
{
   { typeof(int), "it's an int!" }
   { typeof(string), "it's a string!" }
};

Type someType = typeof(int);
Console.WriteLine(table[someType]);

Answer 7

Não vejo nenhuma razão para que a instrução switch sucumba apenas à análise estática

É verdade, isso não ter para, e muitas linguagens de fato usam instruções switch dinâmicas.No entanto, isso significa que reordenar as cláusulas "case" pode alterar o comportamento do código.

Há algumas informações interessantes por trás das decisões de design que foram "trocadas" aqui: Por que a instrução switch C# foi projetada para não permitir falhas, mas ainda assim exigir uma pausa?

Permitir expressões case dinâmicas pode levar a monstruosidades como este código PHP:

switch (true) {
    case a == 5:
        ...
        break;
    case b == 10:
        ...
        break;
}

que francamente deveria apenas usar o if-else declaração.

Answer 8

A Microsoft finalmente ouviu você!

Agora com C# 7 você pode:

switch(shape)
{
case Circle c:
    WriteLine($"circle with radius {c.Radius}");
    break;
case Rectangle s when (s.Length == s.Height):
    WriteLine($"{s.Length} x {s.Height} square");
    break;
case Rectangle r:
    WriteLine($"{r.Length} x {r.Height} rectangle");
    break;
default:
    WriteLine("<unknown shape>");
    break;
case null:
    throw new ArgumentNullException(nameof(shape));
}

Answer 9

Este não é um motivo, mas a seção 8.7.2 da especificação C# afirma o seguinte:

O tipo governante de uma instrução switch é estabelecido pela expressão switch.Se o tipo da expressão switch for sbyte, byte, short, ushort, int, uint, long, ulong, char, string ou um tipo enum, então esse é o tipo governante da instrução switch.Caso contrário, deve existir exatamente uma conversão implícita definida pelo usuário (§6.4) do tipo da expressão switch para um dos seguintes tipos governantes possíveis:sbyte, byte, curto, ushort, int, uint, longo, ulong, char, string.Se não existir tal conversão implícita, ou se existir mais de uma conversão implícita, ocorrerá um erro em tempo de compilação.

A especificação C# 3.0 está localizada em:http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

Answer 10

A resposta de Judá acima me deu uma ideia.Você pode "falsificar" o comportamento do switch do OP acima usando um Dictionary<Type, Func<T>:

Dictionary<Type, Func<object, string,  string>> typeTable = new Dictionary<Type, Func<object, string, string>>();
typeTable.Add(typeof(int), (o, s) =>
                    {
                        return string.Format("{0}: {1}", s, o.ToString());
                    });

Isso permite associar o comportamento a um tipo no mesmo estilo da instrução switch.Acredito que tenha o benefício adicional de ser codificado em vez de uma tabela de salto estilo switch quando compilado para IL.

Answer 11

Suponho que não haja nenhuma razão fundamental para o compilador não poder traduzir automaticamente sua instrução switch em:

if (t == typeof(int))
{
...
}
elseif (t == typeof(string))
{
...
}
...

Mas não há muito ganho com isso.

Uma instrução case em tipos integrais permite que o compilador faça diversas otimizações:

1. Não há duplicação (a menos que você duplique rótulos de caso, que o compilador detecta).No seu exemplo, t poderia corresponder a vários tipos devido à herança.A primeira partida deve ser executada?Todos eles?

2. O compilador pode optar por implementar uma instrução switch em um tipo integral por meio de uma tabela de salto para evitar todas as comparações.Se você estiver ativando uma enumeração que possui valores inteiros de 0 a 100, ela criará um array com 100 ponteiros, um para cada instrução switch.Em tempo de execução, ele simplesmente procura o endereço do array com base no valor inteiro que está sendo ativado.Isso proporciona um desempenho de tempo de execução muito melhor do que realizar 100 comparações.

Answer 12

De acordo com a documentação da instrução switch se houver uma maneira inequívoca de converter implicitamente o objeto em um tipo integral, isso será permitido.Eu acho que você está esperando um comportamento em que para cada declaração de caso ela seja substituída por if (t == typeof(int)), mas isso abriria uma lata de worms quando você sobrecarregasse esse operador.O comportamento mudaria quando os detalhes de implementação da instrução switch mudassem se você escrevesse sua substituição == incorretamente.Ao reduzir as comparações a tipos integrais e strings e aquelas coisas que podem ser reduzidas a tipos integrais (e se destinam a isso), evitam possíveis problemas.

Answer 13

escreveu:

"A instrução switch faz uma ramificação de tempo constante, independentemente de quantos casos você tem."

Como a linguagem permite corda tipo a ser usado em uma instrução switch Presumo que o compilador não seja capaz de gerar código para uma implementação de ramificação de tempo constante para esse tipo e precise gerar um estilo if-then.

@mweerden - Ah, entendo.Obrigado.

Não tenho muita experiência em C# e .NET, mas parece que os designers da linguagem não permitem acesso estático ao sistema de tipos, exceto em circunstâncias restritas.O tipo de palavra-chave retorna um objeto para que ele seja acessível apenas em tempo de execução.

Answer 14

Acho que Henk acertou em cheio com a coisa "sem acesso estatístico ao sistema de tipos"

Outra opção é que não há ordem para os tipos onde números e strings podem estar.Assim, uma opção de tipo não poderia construir uma árvore de pesquisa binária, apenas uma pesquisa linear.

Answer 15

Eu concordo com este comentário que usar uma abordagem baseada em tabela geralmente é melhor.

No C# 1.0 isso não era possível porque não tinha delegados genéricos e anônimos.Novas versões do C# possuem a estrutura para fazer isso funcionar.Ter uma notação para literais de objetos também ajuda.

Answer 16

Praticamente não tenho conhecimento de C#, mas suspeito que qualquer uma das opções foi simplesmente adotada como ocorre em outras linguagens, sem pensar em torná-la mais geral ou o desenvolvedor decidiu que estendê-la não valia a pena.

Estritamente falando, você está absolutamente certo ao dizer que não há razão para impor essas restrições.Pode-se suspeitar que a razão é que para os casos permitidos a implementação é muito eficiente (como sugerido por Brian Ensink (44921)), mas duvido que a implementação seja muito eficiente (w.r.t.instruções if) se eu usar números inteiros e alguns casos aleatórios (por exemplo345, -4574 e 1234203).E em qualquer caso, qual o mal em permitir isso para tudo (ou pelo menos mais) e dizer que só é eficiente para casos específicos (como números (quase) consecutivos).

Posso, no entanto, imaginar que alguém possa querer excluir tipos por razões como a dada por lomaxx (44918).

Editar:@Henk (44970):Se as Strings forem compartilhadas ao máximo, as strings com conteúdo igual também serão ponteiros para o mesmo local de memória.Então, se você puder garantir que as strings usadas nos casos sejam armazenadas consecutivamente na memória, você poderá implementar a opção com muita eficiência (ou seja,com execução na ordem de 2 comparações, uma adição e dois saltos).