Você pode usar <<
para multiplicar e >>
dividir números em python quando eu cronometro eles, acho que o uso da maneira de deslocamento binário é 10x mais rápido do que dividir ou multiplicar da maneira regular.
Por que usar <<
e >>
muito mais rápido que *
e /
?
Quais são os processos por trás dos bastidores *
e /
tão lentos?
operators
bitwise-operators
Crizly
fonte
fonte
Respostas:
Vamos olhar para dois pequenos programas C que mudam e dividem um pouco.
Estes são então compilados
gcc -S
para ver qual será a montagem real.Com a versão de troca de bits, da chamada
atoi
para retornar:Enquanto a versão dividida:
Só de olhar para isso, há várias outras instruções na versão dividida em comparação com a mudança de bits.
A chave é o que eles fazem?
Na versão de deslocamento de bits, a instrução principal é
shll $2, %eax
qual é o deslocamento deixado lógico - existe a divisão, e todo o resto está apenas movendo valores.Na versão dividida, você pode ver o
idivl %r8d
- mas logo acima disso há umacltd
(converter muito para o dobro) e alguma lógica adicional em torno do derramamento e do recarregamento. Esse trabalho adicional, sabendo que estamos lidando com uma matemática em vez de bits, é frequentemente necessário para evitar vários erros que podem ocorrer ao fazer apenas a matemática de bits.Vamos fazer uma multiplicação rápida:
Em vez de passar por tudo isso, há uma linha diferente:
Aqui, o compilador foi capaz de identificar que a matemática poderia ser feita com uma mudança, no entanto, em vez de uma mudança lógica, ela faz uma mudança aritmética. A diferença entre estes seria óbvia se os executássemos -
sarl
preserva o sinal. Então,-2 * 4 = -8
enquantoshll
isso não acontece.Vamos analisar isso em um script perl rápido:
Resultado:
Um ...
-4 << 2
é o18446744073709551600
que não é exatamente o que você provavelmente espera ao lidar com multiplicação e divisão. Está certo, mas não é uma multiplicação inteira.E, portanto, tenha cuidado com a otimização prematura. Deixe o compilador otimizar para você - ele sabe o que realmente está tentando fazer e provavelmente fará um trabalho melhor com menos bugs.
fonte
<< 2
com* 4
e>> 2
com/ 4
manter as direções de mudança iguais em cada exemplo.As respostas existentes realmente não abordam o lado do hardware, então aqui está um pouco desse ângulo. A sabedoria convencional é que multiplicação e divisão são muito mais lentas do que mudanças, mas a história atual hoje é mais sutil.
Por exemplo, certamente é verdade que a multiplicação é uma operação mais complexa para implementar no hardware, mas nem sempre acaba sempre mais lenta . Como se vê,
add
também é significativamente mais complexo de implementar do quexor
(ou em geral qualquer operação bit a bit), masadd
(esub
) normalmente recebe transistores suficientes dedicados à sua operação que acabam sendo tão rápidos quanto os operadores bit a bit. Portanto, você não pode apenas olhar para a complexidade da implementação de hardware como um guia de velocidade.Então, vamos analisar em detalhes as mudanças versus os operadores "completos", como multiplicação e mudança.
Mudança
Em quase todo o hardware, a troca por uma quantidade constante (ou seja, uma quantidade que o compilador pode determinar em tempo de compilação) é rápida . Em particular, isso geralmente acontece com a latência de um único ciclo e com uma taxa de transferência de 1 por ciclo ou melhor. Em alguns hardwares (por exemplo, alguns chips Intel e ARM), certas mudanças por uma constante podem até ser "livres", pois podem ser incorporadas a outra instrução (
lea
na Intel, as habilidades especiais de mudança da primeira fonte no ARM).Mudar por uma quantidade variável é mais uma área cinzenta. No hardware antigo, isso às vezes era muito lento e a velocidade mudava de geração para geração. Por exemplo, no lançamento inicial do P4 da Intel, a troca por uma quantidade variável era notoriamente lenta - exigindo tempo proporcional à quantidade de troca! Nessa plataforma, o uso de multiplicações para substituir turnos pode ser lucrativo (ou seja, o mundo ficou de cabeça para baixo). Nos chips anteriores da Intel, bem como nas gerações subseqüentes, a troca por uma quantidade variável não era tão dolorosa.
Nos chips Intel atuais, a troca por uma quantidade variável não é particularmente rápida, mas também não é terrível. A arquitetura x86 é prejudicada quando se trata de turnos variáveis, porque eles definem a operação de uma maneira incomum: as quantidades de turnos de 0 não modificam os sinalizadores de condição, mas todos os outros turnos. Isso inibe a renomeação eficiente do registrador de sinalizadores, pois ele não pode ser determinado até que o turno execute se instruções subsequentes devem ler os códigos de condição escritos pelo turno ou alguma instrução anterior. Além disso, os turnos gravam apenas em parte do registro de sinalizadores, o que pode causar uma paralisação parcial dos sinalizadores.
O resultado é que, nas arquiteturas recentes da Intel, o deslocamento por uma quantidade variável leva três "micro-operações", enquanto a maioria das outras operações simples (adição, operações bit a bit e até multiplicação) leva apenas 1. Essas mudanças podem ser executadas no máximo uma vez a cada 2 ciclos .
Multiplicação
A tendência no hardware moderno de desktop e laptop é tornar a multiplicação uma operação rápida. Nos recentes chips Intel e AMD, de fato, uma multiplicação pode ser emitida a cada ciclo (chamamos isso de taxa de transferência recíproca ). A latência , no entanto, de uma multiplicação é de 3 ciclos. Isso significa que você obtém o resultado de qualquer multiplicação 3 ciclos depois de iniciá-lo, mas é possível iniciar uma nova multiplicação a cada ciclo. Qual valor (1 ciclo ou 3 ciclos) é mais importante depende da estrutura do seu algoritmo. Se a multiplicação fizer parte de uma cadeia de dependência crítica, a latência é importante. Caso contrário, a taxa de transferência recíproca ou outros fatores podem ser mais importantes.
O principal argumento é que, nos modernos chips de laptop (ou melhor), a multiplicação é uma operação rápida e provavelmente mais rápida que a sequência de instruções 3 ou 4 que um compilador emitiria para "acertar o arredondamento" para mudanças de força reduzidas. Para turnos variáveis, na Intel, a multiplicação também seria geralmente preferida devido aos problemas mencionados acima.
Em plataformas de fator de forma menores, a multiplicação ainda pode ser mais lenta, pois a criação de um multiplicador completo e rápido de 32 ou 64 bits requer muitos transistores e energia. Se alguém puder preencher os detalhes do desempenho da multiplicação em chips móveis recentes, isso será muito apreciado.
Dividir
A divisão é uma operação mais complexa, em termos de hardware, do que multiplicação e também é muito menos comum no código real - o que significa que menos recursos provavelmente serão alocados a ela. A tendência nos chips modernos ainda é em direção a divisores mais rápidos, mas mesmo os chips topo de linha modernos levam de 10 a 40 ciclos para fazer uma divisão, e eles são canalizados apenas parcialmente. Em geral, as divisões de 64 bits são ainda mais lentas que as de 32 bits. Diferentemente da maioria das outras operações, a divisão pode levar um número variável de ciclos, dependendo dos argumentos.
Evite divisões e substitua por turnos (ou deixe o compilador fazê-lo, mas pode ser necessário verificar a montagem), se puder!
fonte
BINARY_LSHIFT e BINARY_RSHIFT são processos mais simples algoritmicamente que BINARY_MULTIPLY e BINARY_FLOOR_DIVIDE e podem levar menos ciclos de relógio. Ou seja, se você tiver qualquer número binário e precisar mudar de bits por N, tudo o que você precisa fazer é mudar os dígitos por muitos espaços e substituir por zeros. A multiplicação binária é geralmente mais complicada , embora técnicas como o multiplicador Dadda o tornem bastante rápido.
Concedido, é possível que um compilador de otimização reconheça casos quando você multiplica / divide por potências de dois e substitui pelo deslocamento de esquerda / direita apropriado. Observando o código de bytes desmontado, o python aparentemente não faz isso:
No entanto, no meu processador, acho que a multiplicação e o deslocamento para a esquerda / direita têm um timing semelhante, e a divisão do piso (por uma potência de dois) é cerca de 25% mais lenta:
fonte