Está mudando bits mais rápido do que multiplicando e dividindo em Java? .LÍQUIDO?

Deslocar os bits para a esquerda e para a direita aparentemente é mais rápido do que as operações de multiplicação e divisão na maioria, talvez até em todos, CPUs se você estiver usando uma potência de 2. No entanto, pode reduzir a clareza do código para alguns leitores e alguns algoritmos. A mudança de bit é realmente necessária para o desempenho, ou posso esperar que o compilador ou VM perceba o caso e o otimize (em particular, quando a potência de 2 é literal)? Estou interessado principalmente no comportamento Java e .NET, mas também recebo insights sobre outras implementações de linguagem.

A maioria dos compiladores hoje fará mais do que converter multiplicação ou dividir por uma potência de dois para mudar as operações. Ao otimizar, muitos compiladores podem otimizar uma multiplicação ou dividir com uma constante de tempo de compilation, mesmo que não seja uma potência de 2. Muitas vezes, uma multiplicação ou divisão pode ser decomposta em uma série de turnos e adições, e se essa série de operações for mais rápida do que o multiplicar ou dividir, o compilador irá usá-lo.

Para divisão por uma constante, o compilador pode freqüentemente converter a operação para uma multiplicar por um ‘número mágico’ seguido por um deslocamento. Isso pode ser um grande economizador de ciclo de clock, já que a multiplicação é frequentemente muito mais rápida do que uma operação de divisão.

O livro de Henry Warren, Hacker’s Delight, tem uma riqueza de informações sobre esse tópico, que também é bastante abordado no site do companheiro:

Veja também uma discussão (com um link ou dois) em:

  • Lendo código assembly

De qualquer forma, tudo isso se resume a permitir que o compilador cuide dos detalhes tediosos de micro-otimizações. Já faz anos que fazer seus próprios turnos foi mais esperto do que o compilador.

Quase qualquer ambiente que valha a pena irá otimizar isso para você. E se isso não acontecer, você terá peixes maiores para fritar. Sério, não perca mais um segundo pensando sobre isso. Você saberá quando tiver problemas de desempenho. E depois de executar um profiler, você saberá o que está causando isso, e deve ficar bastante claro como corrigi-lo.

Você nunca vai ouvir ninguém dizer “meu aplicativo foi muito lento, então eu comecei a replace aleatoriamente x * 2 com x < < 1 e tudo foi corrigido!" Os problemas de desempenho geralmente são resolvidos encontrando uma maneira de fazer uma ordem de grandeza menos trabalho, não encontrando uma maneira de fazer o mesmo trabalho 1% mais rápido.

Os seres humanos estão errados nesses casos.

99% quando tentam adivinhar um compilador moderno (e todo futuro).
99,9% quando tentam adivinhar JITs modernos (e todos os futuros) ao mesmo tempo.
99,999% quando tentam adivinhar otimizações de CPU modernas (e todas futuras).

Programe de uma maneira que descreva com precisão o que você quer realizar, e não como fazê-lo. Futuras versões do JIT, VM, compilador e CPU podem ser independentemente melhoradas e otimizadas. Se você especificar algo tão pequeno e específico, perderá o benefício de todas as futuras otimizações.

É quase certo que você dependa da otimização da multiplicação literal-potência-de-dois para uma operação de mudança. Esta é uma das primeiras otimizações que os alunos da construção de compiladores aprenderão. 🙂

No entanto, não acho que exista alguma garantia para isso. Seu código-fonte deve refletir sua intenção , em vez de tentar dizer ao otimizador o que fazer. Se você está fazendo uma quantidade maior, use multiplicação. Se você estiver movendo um campo de bits de um lugar para outro (pense em manipulação de colors RGB), use uma operação de mudança. De qualquer maneira, seu código-fonte refletirá o que você está realmente fazendo.

Note que a mudança e a divisão (em Java, certamente) dão resultados diferentes para números ímpares negativos.

 int a = -7; System.out.println("Shift: "+(a >> 1)); System.out.println("Div: "+(a / 2)); 

Impressões:

 Shift: -4 Div: -3 

Como o Java não possui números não assinados, não é realmente possível que um compilador Java otimize isso.

Nos computadores que testei, as divisões de números inteiros são 4 a 10 vezes mais lentas que outras operações.

Quando compiladores podem replace divisões por múltiplos de 2 e fazer você não ver nenhuma diferença, as divisões por não múltiplos de 2 são significativamente mais lentas.

Por exemplo, eu tenho um programa (gráfico) com muitas muitas divisões em 255. Na verdade, meu cálculo é:

 r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23; 

Eu posso garantir que é muito mais rápido do que o meu cálculo anterior:

 r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255; 

então não, os compiladores não podem fazer todos os truques da otimização.

Eu perguntaria “o que você está fazendo que isso importaria?”. Primeiro, projete seu código para facilitar a leitura e a manutenção. A probabilidade de que fazer a mudança de bits versus a multiplicação padrão fará com que a diferença de desempenho seja EXTREMAMENTE pequena.

É dependente de hardware. Se estamos falando de micro-controlador ou i386, então o deslocamento pode ser mais rápido, mas, como várias respostas dizem, seu compilador normalmente fará a otimização para você.

No moderno (Pentium Pro e além) de hardware, o pipelining torna isso totalmente irrelevante e se desviar do caminho comumente significa que você perde muito mais otimizações do que pode ganhar.

Micro otimizações não são apenas um desperdício de seu tempo, elas também são extremamente difíceis de acertar.

Se o compilador (constante de tempo de compilation) ou JIT (constante de tempo de execução) souber que o divisor ou multiplicador é uma potência de dois e a aritmética inteira está sendo executada, ele será convertido em um deslocamento para você.

Estou atordoado quando acabei de escrever este código e percebi que a mudança por um é realmente mais lenta do que multiplicar por 2!

(EDIT: mudou o código para parar de transbordar após a sugestão de Michael Myers, mas os resultados são os mesmos! O que está errado aqui?)

 import java.util.Date; public class Test { public static void main(String[] args) { Date before = new Date(); for (int j = 1; j < 50000000; j++) { int a = 1 ; for (int i = 0; i< 10; i++){ a *=2; } } Date after = new Date(); System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds"); before = new Date(); for (int j = 1; j < 50000000; j++) { int a = 1 ; for (int i = 0; i< 10; i++){ a = a << 1; } } after = new Date(); System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds"); } } 

Os resultados são:

Multiplicando 639 milissegundos
Deslocando 718 milissegundos

De acordo com os resultados desse microbenchmark , o deslocamento é duas vezes mais rápido do que a divisão (Oracle Java 1.7.0_72).

A maioria dos compiladores transformará multiplicação e divisão em mudanças de bits quando apropriado. É uma das otimizações mais fáceis de fazer. Então, você deve fazer o que é mais facilmente legível e apropriado para a tarefa dada.

Esta é uma análise do benchmark feito pelo Savvas Dalkitsis. Embora este teste verifique a velocidade de multiplicação sobre o deslocamento de bits, os valores usados ​​não são os mesmos, verifique o código abaixo em C # que exibe os valores)

 for (int i = 0, j = 1, k = 1; i < 10; i++) { j = j * 2; k <<= 2; Console.WriteLine("{0} {1}", j, k); } 

O código equivalente do exemplo Savvas Dalkitsis com os valores exibidos em C # será

  public static void Main(String[] args) { for (int i = 0, j = 1, k = 1; i < 10; i++) { j = j * 2; k <<= 2; Console.WriteLine("{0} {1}", j, k); } Console.WriteLine("-----------------------------------------------"); DateTime before = DateTime.Now; for (int j = 1; j < 500000000; j++) { int a = 1; for (int i = 0; i < 10; i++) a *= 2; } DateTime after = DateTime.Now; Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds"); before = DateTime.Now; for (int j = 1; j < 500000000; j++) { int a = 1; for (int i = 0; i < 10; i++) a = a << 1; } after = DateTime.Now; Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds"); Console.ReadKey(); }