Estou trabalhando em algum código Java que precisa ser altamente otimizado, pois será executado em funções ativadas que são invocadas em muitos pontos da lógica do meu programa principal. Parte desse código envolve a multiplicação de doublevariáveis por 10elevadas para int exponents não negativos arbitrários . Uma maneira rápida (edit: mas não o mais rápido possível, consulte Update 2 abaixo) para obter o valor multiplicado é switchsobre a exponent:
double multiplyByPowerOfTen(final double d, final int exponent) {
switch (exponent) {
case 0:
return d;
case 1:
return d*10;
case 2:
return d*100;
// ... same pattern
case 9:
return d*1000000000;
case 10:
return d*10000000000L;
// ... same pattern with long literals
case 18:
return d*1000000000000000000L;
default:
throw new ParseException("Unhandled power of ten " + power, 0);
}
}As elipses comentadas acima indicam que as case intconstantes continuam incrementando em 1, então existem realmente 19 cases no snippet de código acima. Desde que eu não tinha certeza se eu realmente precisa de todas as potências de 10, em casedeclarações 10através 18, eu corri alguns microbenchmarks comparando o tempo para completar 10 milhões de operações com essa switchdeclaração contra um switchcom apenas caseé 0através 9(com o exponentlimitado a 9 ou menos evite quebrar o aparado switch). Eu obtive o resultado bastante surpreendente (para mim, pelo menos!) De que quanto mais tempo switchcom mais caseinstruções realmente corria mais rápido.
Em uma cotovia, tentei adicionar ainda mais cases, que apenas retornavam valores fictícios, e descobri que era possível executar o switch ainda mais rápido com cerca de 22 a 27 cases declarados (mesmo que esses casos fictícios nunca sejam realmente atingidos enquanto o código está sendo executado). ) (Novamente, cases foram adicionados de maneira contígua, incrementando a caseconstante anterior em 1.) Essas diferenças no tempo de execução não são muito significativas: para uma aleatória exponententre 0e 10, a switchinstrução dummy padded termina 10 milhões de execuções em 1,49 segundos versus 1,54 segundos para os não preenchidos versão, para uma grande economia total de 5ns por execução. Portanto, não é o tipo de coisa que torna obsessivo o preenchimento de umswitchdeclaração vale o esforço do ponto de vista de otimização. Mas ainda acho curioso e contra-intuitivo que a switchnão se torne mais lento (ou, na melhor das hipóteses, mantenha o tempo O (1) constante ) para executar à medida que mais cases são adicionados a ela.
Estes são os resultados que obtive ao executar com vários limites nos exponentvalores gerados aleatoriamente . Não incluí os resultados até 1o exponentlimite, mas a forma geral da curva permanece a mesma, com uma crista em torno da marca de 12 a 17 e um vale entre 18 e 28. Todos os testes foram executados no JUnitBenchmarks usando contêineres compartilhados para os valores aleatórios para garantir entradas de teste idênticas. Também executei os testes na ordem da switchdeclaração mais longa à mais curta e vice-versa, para tentar eliminar a possibilidade de problemas de teste relacionados ao pedido. Coloquei meu código de teste em um repositório do github se alguém quiser tentar reproduzir esses resultados.
Então, o que está acontecendo aqui? Alguns caprichos da minha arquitetura ou construção de micro-benchmark? Ou é o Java switchrealmente um pouco mais rápido para executar no 18a 28 casegama do que é de 11até 17?
repositório de teste do github "switch-experiment"
UPDATE: Limpei bastante a biblioteca de benchmarking e adicionei um arquivo de texto em / results com alguma saída em uma faixa mais ampla de exponentvalores possíveis . Também adicionei uma opção no código de teste para não lançar um Exceptionfrom default, mas isso não parece afetar os resultados.
ATUALIZAÇÃO 2: Encontrei uma discussão bastante boa sobre esse problema em 2009 no fórum xkcd aqui: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . A discussão do OP sobre o uso Array.binarySearch()me deu a ideia de uma implementação simples baseada em array do padrão de exponenciação acima. Não há necessidade de pesquisa binária, pois sei quais são as entradas no array. Parece funcionar três vezes mais rápido que o uso switch, obviamente à custa de parte do fluxo de controle que switchproporciona. Esse código também foi adicionado ao repositório do github.
fonte
switchdeclarações, pois é claramente a solução mais ideal. : D (não mostre isso à minha liderança, por favor.) #lookupswitchpara umtableswitch. Desmontar seu códigojavapmostraria a você com certeza.Respostas:
Conforme apontado pela outra resposta , como os valores de maiúsculas e minúsculas são contíguos (ao contrário de esparsos), o bytecode gerado para seus vários testes usa uma tabela de comutação (instrução bytecode
tableswitch).No entanto, uma vez que o JIT inicia seu trabalho e compila o bytecode em assembly, a
tableswitchinstrução nem sempre resulta em uma matriz de ponteiros: às vezes a tabela de comutação é transformada no que parece serlookupswitch(semelhante a uma estruturaif/else if).A descompilação do assembly gerado pelo JIT (ponto de acesso JDK 1.7) mostra que ele usa uma sucessão de if / else se quando houver 17 casos ou menos, uma matriz de ponteiros quando houver mais de 18 (mais eficiente).
A razão pela qual esse número mágico de 18 é usado parece estar no valor padrão do
MinJumpTableSizesinalizador JVM (em torno da linha 352 no código).Eu levantei o problema na lista do compilador de hotspot e parece ser um legado de testes anteriores . Observe que esse valor padrão foi removido no JDK 8 após a realização de mais testes de referência .
Finalmente, quando o método se torna muito longo (> 25 casos nos meus testes), ele não é mais incorporado com as configurações padrão da JVM - essa é a causa mais provável da queda no desempenho naquele momento.
Com 5 casos, o código descompilado fica assim (observe as instruções cmp / je / jg / jmp, o conjunto para if / goto):
Com 18 casos, a montagem fica assim (observe a matriz de ponteiros que é usada e suprime a necessidade de todas as comparações:
jmp QWORD PTR [r8+r10*1]salta diretamente para a multiplicação correta) - esse é o provável motivo da melhoria de desempenho:E, finalmente, a montagem com 30 casos (abaixo) é semelhante a 18 casos, exceto pelo adicional
movapd xmm0,xmm1que aparece no meio do código, conforme observado por @cHao - no entanto, o motivo mais provável para a queda no desempenho é que o método é muito por muito tempo para ser alinhado com as configurações padrão da JVM:fonte
A caixa de comutação é mais rápida se os valores da caixa forem colocados em uma faixa estreita, por exemplo.
Porque, nesse caso, o compilador pode evitar a comparação de todos os trechos do caso na instrução switch. O compilador cria uma tabela de salto que contém endereços das ações a serem executadas em diferentes partes. O valor no qual a opção está sendo executada é manipulado para convertê-lo em um índice para
jump table. Nesta implementação, o tempo gasto na instrução switch é muito menor que o tempo gasto em uma cascata equivalente da instrução if-else-if. Além disso, o tempo gasto na instrução switch é independente do número de pernas da caixa na instrução switch.Conforme indicado na wikipedia sobre a instrução switch na seção Compilação.
fonte
A resposta está no bytecode:
SwitchTest10.java
Bytecode correspondente; Apenas partes relevantes mostradas:
SwitchTest22.java:
Bytecode correspondente; novamente, apenas as partes relevantes mostradas:
No primeiro caso, com intervalos estreitos, o bytecode compilado usa a
tableswitch. No segundo caso, o bytecode compilado usa alookupswitch.Em
tableswitch, o valor inteiro na parte superior da pilha é usado para indexar na tabela, para encontrar o alvo de ramificação / salto. Esse salto / ramificação é realizado imediatamente. Portanto, esta é umaO(1)operação.A
lookupswitché mais complicado. Nesse caso, o valor inteiro precisa ser comparado com todas as chaves da tabela até que a chave correta seja encontrada. Depois que a chave é encontrada, o alvo de ramificação / salto (para o qual essa chave é mapeada) é usado para o salto. A tabela usadalookupswitché classificada e um algoritmo de pesquisa binária pode ser usado para encontrar a chave correta. O desempenho para uma pesquisa binária éO(log n), e todo o processo também éO(log n), porque o salto ainda éO(1). Portanto, a razão pela qual o desempenho é mais baixo no caso de intervalos esparsos é que a chave correta deve ser procurada primeiro porque você não pode indexar diretamente na tabela.Se houver valores esparsos e você apenas tiver
tableswitchque usar, a tabela conterá essencialmente entradas falsas que apontam para adefaultopção Por exemplo, supondo que a última entradaSwitchTest10.javafoi em21vez de10, você obtém:Portanto, o compilador basicamente cria essa enorme tabela contendo entradas falsas entre as lacunas, apontando para o alvo da ramificação da
defaultinstrução. Mesmo se não houver umdefault, ele conterá entradas apontando para a instrução após o bloco do comutador. Fiz alguns testes básicos e descobri que, se a diferença entre o último índice e o anterior (9) for maior que35, ele usa a emlookupswitchvez de atableswitch.O comportamento da
switchinstrução é definido em Java Virtual Machine Specification (§3.10) :fonte
lookupswitch?Como a pergunta já foi respondida (mais ou menos), aqui está uma dica. Usar
Esse código usa significativamente menos IC (cache de instruções) e será sempre incorporado. A matriz estará no cache de dados L1 se o código estiver quente. A tabela de pesquisa quase sempre é uma vitória. (especialmente nas marcas de micro-marcas: D)
Editar: se você deseja que o método seja hot-inline, considere os caminhos não rápidos como o
throw new ParseException()mais curto possível ou mova-os para separar o método estático (tornando-o mais curto). Essa éthrow new ParseException("Unhandled power of ten " + power, 0);uma idéia fraca, pois ela consome muito do orçamento interno do código que pode ser interpretado - a concatenação de strings é bastante detalhada no bytecode. Mais informações e um caso real com ArrayListfonte