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

140

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 sua arquitetura orientada a objetos (OO) é duvidosa - este é apenas um exemplo artificial!),

  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 um tipo integral esperado' e as instruções case falham com 'Um valor constante é esperado'.

Por que essas restrições estão em vigor e qual é a justificativa subjacente? Não vejo razão para que a instrução switch tenha que sucumbir apenas à análise estática e porque o valor que está sendo ativado precisa ser integral (ou seja, primitivo). Qual é a justificativa?

ljs
fonte
1
Ver possível solução alternativa Existe uma alternativa melhor do que essa para 'ativar o tipo'?
Michael Freidgeim 30/08/19
Outra opção para ativar os tipos internos é usar o TypeCode Enum .
Erik Philips

Respostas:

98

Este é o meu post original, que provocou algum debate ... porque está errado :

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


De fato, a instrução C # switch nem sempre é uma ramificação 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.

Isso é realmente fácil de verificar escrevendo várias instruções de opção C #, algumas esparsas, outras densas e observando o CIL resultante com a ferramenta ildasm.exe.

Brian Ensink
fonte
4
Conforme observado em outras respostas (incluindo a minha), as reivindicações feitas nesta resposta não estão corretas. Eu recomendaria a exclusão (apenas para evitar impor esse equívoco (provavelmente comum)).
mweerden
Por favor, veja meu post abaixo, onde mostro, em minha opinião conclusivamente, que a declaração switch muda constantemente de tempo.
Brian Ensink
Muito obrigado pela sua resposta, Brian. Consulte a resposta de Ivan Hamilton ((48259) [ beta.stackoverflow.com/questions/44905/#48259] ). Em resumo: você está falando sobre a switch instrução (do CIL) que não é a mesma que a switchdeclaração do C #.
mweerden 7/09/08
Não acredito que o compilador gere ramificações em tempo constante ao ativar as strings também.
Drew Noakes
Isso ainda é aplicável à correspondência de padrões nas instruções de maiúsculas e minúsculas no C # 7.0?
B. Darren Olson
114

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

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

Isso é útil apenas se os casos do comutador 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 cerca de 3000 entradas, com apenas 3 slots usados)

Com expressões não adjacentes, o compilador pode começar a executar verificações lineares se-se-se-se.

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

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

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

Eu repliquei seus resultados na minha máquina usando casos adjacentes:

tempo total para executar um comutador de 10 vias, 10000 iterações (ms): 25.1383
tempo aproximado por comutador de 10 vias (ms): 0,00251383

tempo total para executar um comutador de 50 direções, 10000 iterações (ms): 26,593
tempo aproximado por comutador de 50 direções (ms): 0,0026593

tempo total para executar um comutador de 5000 direções, 10000 iterações (ms): 23,7094
tempo aproximado por comutador de 5000 direções (ms): 0,00237094

tempo total para executar um comutador de 50000 vias, 10000 iterações (ms): 20,0933
tempo aproximado por comutador de 50000 vias (ms): 0,00200933

Então eu também fiz usando expressões de caso não adjacentes:

tempo total para executar um comutador de 10 vias, 10000 iterações (ms): 19,6189
tempo aproximado por comutador de 10 vias (ms): 0,00196189

tempo total para executar um comutador de 500 vias, 10000 iterações (ms): 19.1664
tempo aproximado por comutador de 500 vias (ms): 0,00191664

tempo total para executar um comutador de 5000 vias, 10000 iterações (ms): 19,5871
tempo aproximado por comutador de 5000 vias (ms): 0,00195871

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

O engraçado aqui é que a pesquisa em árvore binária aparece um pouco (provavelmente não estatisticamente) mais rapidamente do que a instrução CIL switch.

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

Isso nem resolve a situação String, na qual uma estática Generic.Dictionary<string,int32>pode ser criada, e sofrerá uma sobrecarga definida no primeiro uso. O desempenho aqui dependerá do desempenho de Generic.Dictionary.

Se você verificar a especificação de idioma C # (não a especificação CIL), encontrará "15.7.2 A instrução switch" não menciona "tempo constante" ou que a implementação subjacente ainda usa a instrução de opção CIL (tenha muito cuidado em assumir tais coisas).

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


É claro que esses tempos dependerão de máquinas e condições. Eu não prestaria atenção a esses testes de temporização, as durações de microssegundos que estamos falando são diminuídas 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 do IL DASM para examinar o CIL criado pelo compilador C #. Obviamente, isso não é final, pois as instruções reais que a CPU executa são criadas pelo JIT.

Verifiquei as instruções finais da CPU realmente executadas na minha máquina x86 e posso confirmar um simples comutador 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
Ivan Hamilton
fonte
Os resultados de suas experiências me surpreendem um pouco. Você trocou o seu pelo do Brian? Seus resultados mostram um aumento de tamanho, enquanto os seus não. Estou faltando alguma coisa? De qualquer forma, obrigado pela resposta clara.
Mweerden
É difícil calcular com precisão o tempo com uma operação tão pequena. Não compartilhamos código ou procedimentos de teste. Não vejo por que o tempo dele deve aumentar para casos adjacentes. As minas eram 10 vezes mais rápidas, portanto os ambientes e o código de teste podem variar bastante.
Ivan Hamilton
23

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

Como a maioria dos programadores em C, C ++ e Java não está acostumada a ter essas liberdades, eles não as exigem.

Outro motivo, mais válido, é que a complexidade do idioma aumentaria :

Antes de tudo, 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? Devemos permitir que o programador introduza seu próprio método de comparação?

Além disso, permitir a ativação de objetos quebraria suposições subjacentes sobre a instrução switch . Há duas regras que governam a instrução switch que o compilador não seria capaz de impor se os objetos pudessem ser ativados (consulte a especificação de linguagem do C # versão 3.0 , §8.7.2):

  • Que os valores dos rótulos dos interruptores sejam constantes
  • Que os valores dos rótulos dos comutadores são distintos (para que apenas um bloco do comutador possa ser selecionado para uma determinada expressão do comutador)

Considere este exemplo de código no caso hipotético de que valores de caso não constantes foram 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? De fato, uma das razões pelas quais o C # tornou ilegal a passagem do switch é que as instruções do switch podem ser arbitrariamente reorganizadas.

Essas regras existem por um motivo - para que o programador possa, olhando para um bloco de caso, saber com certeza a condição exata sob a qual o bloco é inserido. Quando a instrução switch mencionada cresce em 100 linhas ou mais (e será), esse conhecimento é inestimável.

Antti Kissaniemi
fonte
2
Nota sobre a reordenação do interruptor. A falha é legal se o caso não contiver código. Como, caso 1: caso 2: Console.WriteLine ("Hi"); pausa;
Joel McBeth
10

A propósito, o VB, com a mesma arquitetura subjacente, permite Select Caseinstruções muito mais flexíveis (o código acima funcionaria no VB) e ainda produz código eficiente onde isso é possível, de modo que o argumento por restrição técnica deve ser considerado com cuidado.

Konrad Rudolph
fonte
1
O Select Caseen VB é muito flexível e economiza muito tempo. Sinto muita falta disso.
Eduardo Molteni 31/03
@EduardoMolteni Alterne para F # então. Faz os switches de Pascal e VB parecerem filhos idiotas em comparação.
Luaan 13/04/2015
10

Principalmente, essas restrições existem devido a designers de idiomas. A justificativa subjacente pode ser a compatibilidade com o histórico de idiomas, os ideais ou a simplificação do design do compilador.

O compilador pode (e faz) optar por:

  • crie uma grande declaração if-else
  • use uma instrução de chave MSIL (tabela de salto)
  • crie um Generic.Dictionary <string, int32>, preencha-o no primeiro uso e chame Generic.Dictionary <> :: TryGetValue () para que um índice passe para uma instrução de opção MSIL (tabela de salto)
  • use uma combinação de if-elses e saltos "switch" do MSIL

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 geram código MSIL mais complicado, com alguns casos se ramificando antes que outros.

Para lidar com o caso String, o compilador acabará (em algum momento) usando a.Equals (b) (e possivelmente a.GetHashCode ()). Eu acho que seria um privilégio para o compilador usar qualquer objeto que satisfaça essas restrições.

Quanto à necessidade de expressões estáticas de caso ... algumas dessas otimizações (hash, cache, etc) não estariam disponíveis se as expressões de caso não fossem determinísticas. Mas já vimos que, às vezes, o compilador apenas escolhe a estrada simplista se-senão-se-senão ...

Edit: 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 é o trabalho do operador "is". O uso de "typeof" aqui para expressar um objeto é irrelevante.

Ivan Hamilton
fonte
6

Enquanto sobre o assunto, de acordo com Jeff Atwood, a declaração switch é uma atrocidade de programação . Use-os com moderação.

Geralmente, 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]);
Judah Gabriel Himango
fonte
7
Você está citando seriamente que alguém está fora do mangá no Twitter sem provas? Pelo menos, link para uma fonte confiável.
Ivan Hamilton
4
É de uma fonte confiável; a postagem do Twitter em questão é de Jeff Atwood, autor do site que você está visualizando. :-) Jeff tem um punhado de posts sobre esse tópico, se você estiver curioso.
Judah Gabriel Himango
Eu acredito que é total BS - independentemente de Jeff Atwood ter escrito. É engraçado como a instrução switch se presta a manipular máquinas de estado e outros exemplos de alteração do fluxo de código com base no valor de um enumtipo. Também não é coincidência que o intellisense preencha automaticamente uma instrução switch quando você ativa uma variável de um enumtipo.
Jonathon Reinhart
@ JonathonReinhart Sim, acho que esse é o ponto - há maneiras melhores de lidar com código polimórfico do que usar a switchdeclaração. Ele não está dizendo que você não deve escrever máquinas de estado, apenas que você pode fazer a mesma coisa usando tipos específicos agradáveis. Obviamente, isso é muito mais fácil em idiomas como o F #, que possuem tipos que podem facilmente cobrir estados bastante complexos. Para o seu exemplo, você pode usar uniões discriminadas onde o estado se torna parte do tipo e substituir a switchcorrespondência de padrão. Ou use interfaces, por exemplo.
Luaan 13/04/2015
Resposta / pergunta antiga, mas eu pensaria que (me corrija se estiver errado) Dictionaryteria sido consideravelmente mais lento que uma switchdeclaração otimizada ...?
Paul
6

Não vejo nenhuma razão pela qual a instrução switch tenha que se adaptar apenas à análise estática

É verdade que não é necessário , e muitos idiomas de fato usam instruções de troca dinâmica. Isso significa, no entanto, 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 incluídas no "switch" aqui: Por que a instrução C # switch foi projetada para não permitir falhas, mas ainda exigir uma pausa?

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

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

que francamente deveria apenas usar a if-elsedeclaração.

Roman Starkov
fonte
1
É isso que eu amo no PHP (agora, quando estou mudando para C #), é a liberdade. Com isso, surge a liberdade de escrever código ruim, mas isso é algo que eu realmente sinto falta em C #
silkfire
5

A Microsoft finalmente ouviu você!

Agora, com o 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));
}
dimaaan
fonte
3

Esse não é o motivo, mas a seção de especificação C # 8.7.2 indica o seguinte:

O tipo de governo 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, esse é o tipo de regra 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 de alternância para um dos seguintes tipos de governo possíveis: sbyte, byte, short, ushort, int, uint, long, ulong, char, string . Se não existir uma 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 do C # 3.0 está localizada em: http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

markus
fonte
3

A resposta de Judá acima me deu uma ideia. Você pode "falsificar" o comportamento do comutador 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 que a instrução switch. Acredito que tenha o benefício adicional de ser digitado em vez de uma tabela de salto no estilo de chave quando compilada para IL.

Dave Swersky
fonte
0

Suponho que não haja uma razão fundamental pela qual o compilador não possa traduzir automaticamente sua instrução switch em:

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

Mas não há muito ganho com isso.

Uma declaração de caso sobre tipos integrais permite que o compilador faça várias otimizações:

  1. Não há duplicação (a menos que você duplique os rótulos de caso, que o compilador detecta). No seu exemplo, t pode 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 sobre um tipo integral por uma tabela de salto para evitar todas as comparações. Se você estiver ativando uma enumeração que possua valores inteiros de 0 a 100, ela criará uma matriz com 100 ponteiros, um para cada instrução de chave. No tempo de execução, ele simplesmente procura o endereço da matriz com base no valor inteiro que está sendo ativado. Isso contribui para um desempenho de tempo de execução muito melhor do que realizar 100 comparações.

Rob Walker
fonte
1
Uma complexidade importante a ser observada aqui é que o modelo de memória .NET possui certas garantias fortes que tornam seu pseudocódigo não exatamente equivalente ao (hipotético, C # inválido ) switch (t) { case typeof(int): ... }porque sua tradução implica que a variável t deve ser buscada na memória duas vezes se t != typeof(int), enquanto o último seria (putativamente) sempre leia o valor t exatamente uma vez . Essa diferença pode quebrar a correção do código simultâneo que se baseia nessas excelentes garantias. Para mais informações sobre isso, consulte Joe Duffy Programação Concorrente no Windows
Glenn Slayden
0

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, será permitido. Eu acho que você está esperando um comportamento em que, para cada instrução de caso, ela seja substituída if (t == typeof(int)), mas isso abriria uma lata inteira de worms quando você sobrecarregasse esse operador. O comportamento mudaria quando os detalhes de implementação da instrução switch fossem alterados se você escrevesse sua substituição == incorretamente. Ao reduzir as comparações entre tipos e cadeias integrais e as coisas que podem ser reduzidas a tipos integrais (e se destinam a), eles evitam possíveis problemas.

fryguybob
fonte
0

escrevi:

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

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

@weweden - Ah entendo. Obrigado.

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

Henk
fonte
0

Eu acho que Henk acertou em cheio com a coisa "sem acesso estático ao sistema de tipos"

Outra opção é que não há ordem para os tipos em que números e seqüências de caracteres podem estar. Portanto, uma opção de tipo não pode construir uma árvore de pesquisa binária, apenas uma pesquisa linear.

BCS
fonte
0

Concordo com este comentário que o uso de uma abordagem orientada a tabelas geralmente é melhor.

No C # 1.0, isso não foi possível porque não havia delegados genéricos e anônimos. Novas versões do C # têm o andaime para fazer isso funcionar. Ter uma notação para literais de objetos também ajuda.

HS.
fonte
0

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

A rigor, você está absolutamente certo de que não há motivos 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 (declarações if-wrt) se eu usar números inteiros e alguns casos aleatórios (por exemplo, 345, -4574 e 1234203). E, de qualquer forma, qual é o mal em permitir tudo (ou pelo menos mais) e dizer que só é eficiente para casos específicos (como (quase) números consecutivos).

No entanto, posso imaginar que alguém possa querer excluir tipos devido a razões como a apresentada por lomaxx ( 44918 ).

Edit: @Henk ( 44970 ): Se 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 seqüências usadas nos casos sejam armazenadas consecutivamente na memória, poderá implementar o comutador com muita eficiência (ou seja, com execução na ordem de 2 compara, uma adição e dois saltos).

Mweerden
fonte
0

O C # 8 permite que você resolva esse problema de maneira elegante e compacta usando uma expressão de opção:

public string GetTypeName(object obj)
{
    return obj switch
    {
        int i => "Int32",
        string s => "String",
        { } => "Unknown",
        _ => throw new ArgumentNullException(nameof(obj))
    };
}

Como resultado, você obtém:

Console.WriteLine(GetTypeName(obj: 1));           // Int32
Console.WriteLine(GetTypeName(obj: "string"));    // String
Console.WriteLine(GetTypeName(obj: 1.2));         // Unknown
Console.WriteLine(GetTypeName(obj: null));        // System.ArgumentNullException

Você pode ler mais sobre o novo recurso aqui .

smolchanovsky
fonte