A multiplicação e a divisão usando operadores de turno em C são realmente mais rápidas?

288

A multiplicação e a divisão podem ser obtidas usando operadores de bits, por exemplo

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

e assim por diante.

É realmente mais rápido usar o say (i<<3)+(i<<1)para multiplicar por 10 do que usar i*10diretamente? Existe algum tipo de entrada que não possa ser multiplicada ou dividida dessa maneira?

eku
fonte
8
Na verdade, a divisão barata por uma constante que não seja uma potência de dois é possível, mas um assunto complicado ao qual você não está fazendo justiça com "/ Divisão ... / dividido" em sua pergunta. Veja, por exemplo, hackersdelight.org/divcMore.pdf (ou obtenha o livro " Delícia do hacker", se puder).
Pascal Cuoq
46
Parece algo que poderia ser facilmente testado.
Juanchopanza
25
Como sempre - depende. Era uma vez eu tentei isso em assembler em um Intel 8088 (IBM PC / XT), onde uma multiplicação levou um bazilhão de relógios. Os turnos e as adições são executados muito mais rapidamente, por isso parecia uma boa ideia. No entanto, ao multiplicar, a unidade de barramento estava livre para preencher a fila de instruções e a próxima instrução poderia começar imediatamente. Após uma série de mudanças e acréscimos, a fila de instruções fica vazia e a CPU precisa aguardar a busca da próxima instrução da memória (um byte de cada vez!). Meça, meça, meça!
Bo Persson
19
Além disso, lembre-se de que o deslocamento à direita é bem definido apenas para números inteiros não assinados . Se você tiver um número inteiro assinado, não será definido se 0 ou o bit mais alto será preenchido da esquerda. (E não se esqueça o tempo que leva para outra pessoa (mesmo você mesmo) para ler o código de um ano depois!)
Kerrek SB
29
Na verdade, um bom compilador de otimização implementará multiplicação e divisão com turnos quando forem mais rápidos.
Peter G.

Respostas:

487

Resposta curta: improvável.

Resposta longa: Seu compilador possui um otimizador que sabe como multiplicar tão rapidamente quanto a arquitetura do processador de destino. Sua melhor aposta é informar claramente ao seu compilador sua intenção (ou seja, i * 2 em vez de i << 1) e deixar que ele decida qual é a sequência de código de montagem / máquina mais rápida. É até possível que o próprio processador tenha implementado a instrução de multiplicação como uma sequência de turnos e acréscimos no microcódigo.

Conclusão - não gaste muito tempo se preocupando com isso. Se você quer mudar, mude. Se você deseja multiplicar, multiplique. Faça o que é semanticamente mais claro - seus colegas de trabalho agradecerão mais tarde. Ou, mais provavelmente, amaldiçoá-lo mais tarde, se você fizer o contrário.

Drew Hall
fonte
31
Sim, como dito, os possíveis ganhos para quase todas as aplicações superam totalmente a obscuridade introduzida. Não se preocupe com esse tipo de otimização prematuramente. Construir o que é sematically clara, identificar gargalos e otimizar de lá ...
Dave
4
Concordando, otimizar a legibilidade e a manutenção provavelmente fornecerá mais tempo para você gastar na otimização de coisas que o criador de perfil diz serem caminhos de código quente.
doug65536
5
Esses comentários fazem parecer que você está desistindo de um desempenho potencial ao dizer ao compilador como fazer seu trabalho. Este não é o caso. Na verdade, você obtém um código melhor gcc -O3no x86 do return i*10que na versão shift . Como alguém que olha muito para o compilador (veja muitas das minhas respostas asm / otimização), não estou surpreso. Há momentos em que pode ajudar a segurar o compilador manualmente em uma maneira de fazer as coisas , mas essa não é uma delas. O gcc é bom em matemática de números inteiros, porque é importante.
Peter Cordes
Acabei de baixar um esboço do arduino que possui millis() >> 2; Teria sido pedir demais para apenas dividir?
Paul Wieland
1
Testei i / 32vs i >> 5e i / 4vs i >> 2no gcc para o córtex-a9 (que não possui divisão de hardware) com otimização -O3 e o conjunto resultante foi exatamente o mesmo. Eu não gostei de usar divisões primeiro, mas ele descreve minha intenção e a saída é a mesma.
robsn 24/04
91

Apenas um ponto de medida concreto: muitos anos atrás, eu comparei duas versões do meu algoritmo de hash:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

e

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Em todas as máquinas em que eu comparava, a primeira era pelo menos tão rápida quanto a segunda. Surpreendentemente, às vezes era mais rápido (por exemplo, em um Sun Sparc). Quando o hardware não suportava multiplicação rápida (e a maioria não era na época), o compilador convertia a multiplicação nas combinações apropriadas de turnos e add / sub. E porque sabia o objetivo final, às vezes podia fazê-lo em menos instruções do que quando você escrevia explicitamente os turnos e os add / subs.

Observe que isso foi algo como 15 anos atrás. Felizmente, os compiladores só ficaram melhores desde então, então você pode contar com o compilador fazendo a coisa certa, provavelmente melhor do que você poderia. (Além disso, a razão pela qual o código parece tão C'ish é porque era há mais de 15 anos. Eu obviamente usaria std::stringe iteradores hoje.)

James Kanze
fonte
5
Você pode estar interessado na seguinte postagem no blog, na qual o autor observa que os compiladores de otimização modernos parecem fazer engenharia reversa de padrões comuns que os programadores podem usar, pensando-os mais eficientes em suas formas matemáticas, a fim de realmente gerar a sequência de instruções mais eficiente para eles. . shape-of-code.coding-guidelines.com/2009/06/30/…
Pascal Cuoq 8/12/12
@PascalCuoq Nada realmente novo sobre isso. Descobri praticamente a mesma coisa para o Sun CC há quase 20 anos.
James Kanze 8/12
67

Além de todas as outras boas respostas aqui, deixe-me apontar outro motivo para não usar turno quando você quer dizer dividir ou multiplicar. Nunca vi alguém introduzir um bug esquecendo a relativa precedência da multiplicação e adição. Vi bugs introduzidos quando os programadores de manutenção esqueceram que "multiplicar" por meio de um turno é logicamente uma multiplicação, mas não sintaticamente da mesma precedência que a multiplicação. x * 2 + ze x << 1 + zsão muito diferentes!

Se você estiver trabalhando em números , use operadores aritméticos como + - * / %. Se você estiver trabalhando em matrizes de bits, use operadores de ajuste de bits como & ^ | >>. Não os misture; uma expressão que tanto modifica como aritmética é um bug que está esperando para acontecer.

Eric Lippert
fonte
5
Evitável com parênteses simples?
Joel B
21
@ Joel: Claro. Se você se lembra que precisa deles. Meu argumento é que é fácil esquecer que você faz. As pessoas que adquirem o hábito mental de ler "x << 1" como se fosse "x * 2" adquirem o hábito mental de pensar que << é a mesma precedência da multiplicação, o que não é.
precisa
1
Bem, acho a expressão "(oi << 8) + lo" mais reveladora do que "oi * 256 + lo". Provavelmente é uma questão de gosto, mas às vezes é mais claro escrever um pouco de brincadeira. Na maioria dos casos, embora eu concorde totalmente com o seu argumento.
Ivan Danilov
32
@ Ivan: E "(oi << 8) | lo" é ainda mais claro. Definir os bits baixos de uma matriz de bits não é adição de números inteiros . Ele está configurando bits , então escreva o código que define os bits.
Eric Lippert
1
Uau. Não pensei nisso dessa maneira antes. Obrigado.
Ivan Danilov
50

Isso depende do processador e do compilador. Alguns compiladores já otimizam o código dessa maneira, outros não. Portanto, você precisa verificar sempre que seu código precisar ser otimizado dessa maneira.

A menos que você precise desesperadamente otimizar, eu não codificaria meu código-fonte apenas para salvar uma instrução de montagem ou um ciclo do processador.

Jens
fonte
3
Apenas para adicionar uma estimativa aproximada: Em um processador típico de 16 bits (80C166), a adição de duas entradas vem em 1-2 ciclos, uma multiplicação em 10 ciclos e uma divisão em 20 ciclos. Além de algumas operações de movimentação, se você otimizar i * 10 em várias operações (cada uma mova outro ciclo de +1). Os compiladores comuns a maioria (Keil / Multitarefas) não otimizar a menos de multiplicações / divisões por uma potência de 2.
Jens
55
E, em geral, o compilador otimiza o código melhor do que você.
user703016
Concordo que, ao multiplicar "quantidades", o operador de multiplicação geralmente é melhor, mas ao dividir valores assinados por potências de 2, o >> operador é mais rápido que /, e se os valores assinados podem ser negativos, também é semanticamente superior. Se alguém precisa do valor que x>>4produziria, isso é muito mais claro que x < 0 ? -((-1-x)/16)-1 : x/16;, e não consigo imaginar como um compilador poderia otimizar essa última expressão para algo agradável.
Supercat #
38

É realmente mais rápido usar say (i << 3) + (i << 1) para multiplicar por 10 do que usar i * 10 diretamente?

Pode ou não estar em sua máquina - se você se importa, meça seu uso no mundo real.

Um estudo de caso - do 486 ao core i7

O benchmarking é muito difícil de ser feito de maneira significativa, mas podemos observar alguns fatos. Em http://www.penguin.cz/~literakl/intel/s.html#SAL e http://www.penguin.cz/~literakl/intel/i.html#IMUL, temos uma idéia dos ciclos do relógio x86 necessário para mudança aritmética e multiplicação. Digamos que aderimos ao "486" (o mais novo listado), registradores e imediatos de 32 bits, o IMUL leva 13-42 ciclos e o IDIV 44. Cada SAL pega 2 e adiciona 1, portanto, mesmo com alguns desses que mudam superficialmente a aparência como um vencedor.

Hoje em dia, com o core i7:

(em http://software.intel.com/en-us/forums/showthread.php?t=61481 )

A latência é de 1 ciclo para uma adição inteira e 3 ciclos para uma multiplicação inteira . Você pode encontrar as latências e a capacidade de processamento no Apêndice C do "Manual de referência da otimização de arquiteturas Intel® 64 e IA-32", localizado em http://www.intel.com/products/processor/manuals/ .

(de alguns anúncios da Intel)

Usando o SSE, o Core i7 pode emitir instruções simultâneas de adição e multiplicação, resultando em uma taxa de pico de 8 operações de ponto flutuante (FLOP) por ciclo de clock

Isso dá uma idéia de quão longe as coisas chegaram. A trivialidade da otimização - como deslocamento de bits versus* - que foi levada a sério até os anos 90 é obsoleta agora. A troca de bits ainda é mais rápida, mas, para uma potência de dois mul / div, no momento em que você faz todos os seus turnos e adiciona os resultados, é mais lento novamente. Então, mais instruções significam mais falhas de cache, mais problemas em potencial no pipelining, mais uso de registros temporários podem significar mais economia e restauração do conteúdo do registro da pilha ... rapidamente fica muito complicado quantificar definitivamente todos os impactos, mas eles são predominantemente negativo.

funcionalidade no código fonte versus implementação

De maneira mais geral, sua pergunta é marcada como C e C ++. Como linguagens de terceira geração, eles são projetados especificamente para ocultar os detalhes do conjunto de instruções da CPU subjacente. Para satisfazer seus padrões de idioma, eles devem oferecer suporte a operações de multiplicação e deslocamento (e muitas outras), mesmo que o hardware subjacente não o faça . Nesses casos, eles devem sintetizar o resultado necessário usando muitas outras instruções. Da mesma forma, eles devem fornecer suporte de software para operações de ponto flutuante se a CPU não tiver e não houver FPU. CPUs modernas suportam* e<<, portanto, isso pode parecer absurdamente teórico e histórico, mas o importante é que a liberdade de escolher a implementação seja nos dois sentidos: mesmo que a CPU possua uma instrução que implemente a operação solicitada no código-fonte no caso geral, o compilador estará livre para escolha outra coisa que prefira, porque é melhor para o caso específico que o compilador enfrenta.

Exemplos (com uma linguagem de montagem hipotética)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Instruções como exclusive ou ( xor) não têm relação com o código-fonte, mas armazenar qualquer coisa por si só limpa todos os bits; portanto, pode ser usado para definir algo como 0. O código-fonte que implica endereços de memória pode não implicar o uso.

Esses tipos de hacks são utilizados há tanto tempo quanto os computadores existem. Nos primeiros dias do 3GLs, para garantir a aceitação do desenvolvedor, a saída do compilador tinha que satisfazer o desenvolvedor de linguagem assembly otimizado para mão, já existente. comunidade que o código produzido não era mais lento, mais detalhado ou pior. Os compiladores adotaram rapidamente muitas ótimas otimizações - eles se tornaram um repositório centralizado melhor do que qualquer programador de linguagem assembly poderia ser, embora sempre haja a chance de que eles percam uma otimização específica que é crucial em um caso específico - às vezes os humanos podem enlouqueça e procure algo melhor, enquanto os compiladores fazem o que lhes foi dito até que alguém os devolva a experiência.

Portanto, mesmo que a troca e a adição ainda sejam mais rápidas em algum hardware específico, é provável que o gravador do compilador tenha funcionado exatamente quando é seguro e benéfico.

Manutenção

Se o seu hardware mudar, você poderá recompilar e ele olhará para a CPU de destino e fará outra melhor escolha, enquanto é improvável que você queira revisitar suas "otimizações" ou listar quais ambientes de compilação devem usar multiplicação e quais devem mudar. Pense em todas as "otimizações" sem deslocamento de dois bits, escritas há mais de 10 anos, que agora estão diminuindo o código em que estão, enquanto são executadas nos processadores modernos ...!

Felizmente, bons compiladores como o GCC podem substituir uma série de turnos de bits e aritmética por uma multiplicação direta quando qualquer otimização é ativada (por exemplo, ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax), para que uma recompilação possa ajudar mesmo sem corrigir o código, mas isso não é garantido.

Código estranho de mudança de bits que implementa multiplicação ou divisão é muito menos expressivo do que você estava tentando alcançar conceitualmente; portanto, outros desenvolvedores ficarão confusos com isso, e um programador confuso terá mais chances de introduzir bugs ou remover algo essencial em um esforço para restaurar a aparente sanidade. Se você só faz coisas não óbvias quando elas são realmente benéficas tangíveis e depois as documenta bem (mas não documenta outras coisas que são intuitivas de qualquer maneira), todos ficarão mais felizes.

Soluções gerais versus soluções parciais

Se você tem algum conhecimento extra, tal como a sua intvontade realmente apenas ser armazenar valores x, ye z, em seguida, você pode ser capaz de trabalhar para fora algumas instruções que o trabalho para esses valores e que você obtenha o seu resultado mais rapidamente do que quando o compilador de não ter esse insight e precisa de uma implementação que funcione para todos os intvalores. Por exemplo, considere sua pergunta:

A multiplicação e a divisão podem ser obtidas usando operadores de bits ...

Você ilustra a multiplicação, mas e a divisão?

int x;
x >> 1;   // divide by 2?

De acordo com o C ++ Standard 5.8:

-3- O valor de E1 >> E2 é E1 com posições de bits E2 deslocadas à direita. Se E1 tiver um tipo não assinado ou E1 tiver um tipo assinado e um valor não negativo, o valor do resultado será a parte integrante do quociente de E1 dividido pela quantidade 2 elevada à potência E2. Se E1 tiver um tipo assinado e um valor negativo, o valor resultante será definido pela implementação.

Portanto, seu deslocamento de bits tem um resultado definido de implementação quando xé negativo: pode não funcionar da mesma maneira em máquinas diferentes. Mas, /funciona muito mais previsivelmente. (Também pode não ser perfeitamente consistente, pois máquinas diferentes podem ter representações diferentes de números negativos e, portanto, intervalos diferentes, mesmo quando há o mesmo número de bits que compõem a representação.)

Você pode dizer "eu não ligo ... isso inté armazenar a idade do funcionário, nunca pode ser negativo". Se você tiver esse tipo de insight especial, sim - sua >>otimização segura pode ser ignorada pelo compilador, a menos que você faça isso explicitamente em seu código. Porém, é arriscado e raramente útil, na maioria das vezes você não terá esse tipo de insight, e outros programadores trabalhando no mesmo código não saberão que você apostou em algumas expectativas incomuns dos dados que você ' vou lidar com ... o que parece uma mudança totalmente segura para eles pode sair pela culatra por causa da sua "otimização".

Existe algum tipo de entrada que não possa ser multiplicada ou dividida dessa maneira?

Sim ... como mencionado acima, os números negativos têm um comportamento definido pela implementação quando "dividido" pela troca de bits.

Tony Delroy
fonte
2
Resposta muito boa. A comparação do Core i7 vs. 486 é esclarecedora!
Tirou Salão
Em todas as arquiteturas comuns, intVal>>1terá a mesma semântica que difere da de intVal/2uma maneira que às vezes é útil. Se for necessário calcular de maneira portátil o valor que as arquiteturas comuns renderiam intVal >> 1, a expressão precisaria ser um pouco mais complicada e difícil de ler, e provavelmente geraria um código substancialmente inferior ao produzido intVal >> 1.
Supercat
35

Apenas tentei na minha máquina compilar isso:

int a = ...;
int b = a * 10;

Ao desmontar, produz saída:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Esta versão é mais rápida que o seu código otimizado para as mãos, com pura mudança e adição.

Você realmente nunca sabe o que o compilador criará, então é melhor simplesmente escrever uma multiplicação normal e deixá-lo otimizar da maneira que ele deseja, exceto em casos muito precisos em que você sabe que o compilador não pode otimizar.

user703016
fonte
1
Você teria conseguido uma grande votação para isso se tivesse pulado a parte sobre o vetor. Se o compilador puder corrigir a multiplicação, também poderá ver que o vetor não muda.
Bo Persson
Como um compilador pode saber que um tamanho de vetor não mudará sem fazer algumas suposições realmente perigosas? Ou você nunca ouviu falar de simultaneidade ...
Charles Goodwin
1
Ok, então você passa por um vetor global sem bloqueios? E faço um loop sobre um vetor local cujo endereço não foi usado e chamo apenas funções membros const. Pelo menos meu compilador percebe que o tamanho do vetor não será alterado. (e em breve alguém provavelmente nos sinalizará para conversar :-).
Bo Persson
1
@BoPersson Finalmente, depois de todo esse tempo, removi minha declaração sobre o compilador não conseguir otimizar vector<T>::size(). Meu compilador era bastante antigo! :)
user703016
21

Mudar é geralmente muito mais rápido do que multiplicar em um nível de instrução, mas você pode estar perdendo seu tempo fazendo otimizações prematuras. O compilador pode muito bem executar essas otimizações em tempo de compilação. Fazer você mesmo afetará a legibilidade e possivelmente não terá efeito no desempenho. Provavelmente, só vale a pena fazer coisas assim se você criar um perfil e achar que isso é um gargalo.

Na verdade, o truque da divisão, conhecido como 'divisão mágica', pode realmente render grandes recompensas. Novamente, você deve criar um perfil primeiro para ver se é necessário. Mas se você o usar, existem programas úteis para ajudá-lo a descobrir quais instruções são necessárias para a mesma semântica de divisão. Aqui está um exemplo: http://www.masm32.com/board/index.php?topic=12421.0

Um exemplo que tirei do thread do OP no MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Geraria:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16
Mike Kwan
fonte
7
@ Drew, por algum motivo, seu comentário me fez rir e derramar meu café. obrigado.
asawyer
30
Não há tópicos aleatórios no fórum sobre gostar de matemática. Quem gosta de matemática sabe como é difícil gerar um verdadeiro tópico "aleatório" no fórum.
Joel B
1
Provavelmente vale a pena fazer coisas como essa se você tiver perfilado e considerado um gargalo e implementado as alternativas e o perfil novamente e obter pelo menos 10 vezes a vantagem de desempenho .
Lie Ryan
12

As instruções de mudança e multiplicação de números inteiros têm desempenho semelhante na maioria das CPUs modernas - as instruções de multiplicação de números inteiros eram relativamente lentas nos anos 80, mas, em geral, isso não é mais verdade. Instruções de multiplicação de número inteiro podem ter maior latência ; portanto, ainda pode haver casos em que uma mudança é preferível. O mesmo vale para os casos em que você pode manter mais unidades de execução ocupadas (embora isso possa ocorrer nos dois sentidos).

A divisão de números inteiros ainda é relativamente lenta, portanto, usar uma mudança em vez de divisão por uma potência de 2 ainda é uma vitória, e a maioria dos compiladores implementará isso como uma otimização. Observe, no entanto, que para que essa otimização seja válida, o dividendo precisa ser não assinado ou deve ser positivo. Para um dividendo negativo, o deslocamento e a divisão não são equivalentes!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Resultado:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Portanto, se você deseja ajudar o compilador, verifique se a variável ou expressão no dividendo está explicitamente sem sinal.

Paul R
fonte
4
Multiplicações inteiras são microcodificadas, por exemplo, na PPU do PlayStation 3 e paralisam todo o pipeline. É recomendado para evitar inteiro multiplica em algumas plataformas ainda :)
Maister
2
Muitas divisões não assinadas são - assumindo que o compilador saiba como - implementadas usando multiplicações não assinadas. Um ou dois multiplicam @ alguns ciclos de relógio, cada um pode fazer o mesmo trabalho que uma divisão @ 40 ciclos cada e acima.
Olof Forshell 29/03/12
1
@Olof: true, mas válido apenas para divisão por uma constante em tempo de compilação, é claro #
Paul R
4

Depende completamente do dispositivo de destino, idioma, finalidade etc.

Trituração de pixels em um driver de placa de vídeo? Muito provavelmente sim!

Aplicativo de negócios .NET para o seu departamento? Absolutamente nenhuma razão para sequer olhar para ele.

Para um jogo de alto desempenho para um dispositivo móvel, pode valer a pena investigar, mas somente após a otimização mais fácil.

Brady Moritz
fonte
2

Não faça isso, a menos que seja absolutamente necessário e sua intenção de código exija mudança em vez de multiplicação / divisão.

Em um dia típico - você pode economizar potencialmente poucos ciclos de máquina (ou menos, já que o compilador sabe melhor o que otimizar), mas o custo não vale a pena - você gasta tempo com pequenos detalhes em vez de trabalhos reais, mantendo o código mais difícil e seus colegas de trabalho o amaldiçoarão.

Pode ser necessário fazer isso para cálculos de alta carga, em que cada ciclo salvo significa minutos de tempo de execução. Porém, você deve otimizar um local de cada vez e fazer testes de desempenho a cada vez para ver se realmente tornou mais rápido ou quebrou a lógica dos compiladores.

Kromster
fonte
1

Tanto quanto sei em algumas máquinas, a multiplicação pode precisar de 16 a 32 ciclos de máquina. Portanto , sim , dependendo do tipo de máquina, os operadores de deslocamento de bits são mais rápidos que a multiplicação / divisão.

No entanto, certas máquinas possuem seu processador matemático, que contém instruções especiais para multiplicação / divisão.

iammilind
fonte
7
As pessoas que escrevem compiladores para essas máquinas também provavelmente leram o Hackers Delight e otimizaram de acordo.
Bo Persson
1

Concordo com a resposta marcada por Drew Hall. A resposta pode usar algumas notas adicionais.

Para a grande maioria dos desenvolvedores de software, o processador e o compilador não são mais relevantes para a questão. A maioria de nós está muito além do 8088 e do MS-DOS. Talvez seja relevante apenas para aqueles que ainda estão desenvolvendo para processadores embarcados ...

Na minha empresa de software, Math (add / sub / mul / div) deve ser usado para toda a matemática. Enquanto Shift deve ser usado ao converter entre tipos de dados, por exemplo. ushort para byte como n >> 8 e não n / 256.

deegee
fonte
Eu concordo contigo também. Sigo a mesma orientação inconscientemente, embora nunca tenha tido um requisito formal para fazê-lo.
Drew Hall
0

No caso de números inteiros assinados e deslocamento à direita x divisão, isso pode fazer a diferença. Para números negativos, o turno arredonda para o infinito negativo, enquanto a divisão arredonda para o zero. É claro que o compilador mudará a divisão para algo mais barato, mas geralmente mudará para algo que tenha o mesmo comportamento de arredondamento da divisão, porque é incapaz de provar que a variável não será negativa ou simplesmente não Cuidado. Portanto, se você puder provar que um número não será negativo ou se não se importar com a maneira como ele arredondará, poderá fazer essa otimização de uma maneira que seja mais provável que faça a diferença.

harold
fonte
ou jogue o número paraunsigned
Lie Ryan
4
Você tem certeza de que o comportamento de mudança é padronizado? Fiquei com a impressão de que o deslocamento à direita em ints negativos é definido pela implementação.
Kerrek SB
1
Embora você deva mencionar que o código que se baseia em qualquer comportamento específico para números negativos à direita deve documentar esse requisito, a vantagem de mudar à direita é enorme nos casos em que naturalmente produz o valor certo e o operador da divisão geraria código para desperdiçar tempo calculando um valor indesejado que o código do usuário teria que perder tempo ajustando para produzir o que a mudança daria em primeiro lugar. Na verdade, se eu tivesse meus druthers, os compiladores teriam a opção de gritar nas tentativas de executar a divisão assinada, já que ... #
687
1
... código que sabe que os operandos são positivos pode melhorar a otimização se convertido em não assinado antes da divisão (possivelmente convertido novamente em assinado posteriormente), e o código que sabe que os operandos podem ser negativos geralmente deve lidar com esse caso de forma explícita (nesse caso) pode-se supor que eles sejam positivos).
Supercat ''
0

Teste Python executando a mesma multiplicação 100 milhões de vezes contra os mesmos números aleatórios.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Portanto, ao fazer uma mudança em vez de multiplicar / divisão por uma potência de dois em python, há uma ligeira melhora (~ 10% para divisão; ~ 1% para multiplicação). Se não for dois, provavelmente haverá uma desaceleração considerável.

Novamente, esses #s mudam dependendo do seu processador, compilador (ou intérprete - feito em python por simplicidade).

Como com todos os outros, não otimize prematuramente. Escreva um código muito legível, crie um perfil, se não for rápido o suficiente, e tente otimizar as partes lentas. Lembre-se de que seu compilador é muito melhor em otimização do que você.

dr jimbob
fonte
0

Existem otimizações que o compilador não pode fazer porque elas funcionam apenas para um conjunto reduzido de entradas.

Abaixo, há um código de exemplo c ++ que pode fazer uma divisão mais rápida executando uma "Multiplicação pelo inverso" de 64 bits. O numerador e o denominador devem estar abaixo de determinado limite. Observe que ele deve ser compilado para usar instruções de 64 bits para ser realmente mais rápido que a divisão normal.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}
user2044859
fonte
0

Eu acho que, no caso em que você deseja multiplicar ou dividir por uma potência de dois, você não pode errar ao usar operadores de deslocamento de bits, mesmo que o compilador os converta em um MUL / DIV, porque alguns processadores microcódigo (na verdade, um macro) de qualquer maneira, portanto, nesses casos, você obterá uma melhoria, especialmente se o deslocamento for maior que 1. Ou mais explicitamente, se a CPU não tiver operadores de deslocamento de bits, será um MUL / DIV de qualquer maneira, mas se a CPU tiver operadores de deslocamento de bits, você evita uma ramificação de microcódigo e estas são algumas instruções a menos.

Estou escrevendo algum código agora que requer muitas operações de duplicação / redução pela metade porque está trabalhando em uma árvore binária densa, e há mais uma operação que eu suspeito que possa ser mais ideal do que uma adição - uma esquerda (potência de duas multiplique ) mudar com uma adição. Isso pode ser substituído por um deslocamento à esquerda e um xor se o deslocamento for maior que o número de bits que você deseja adicionar; o exemplo fácil é (i << 1) ^ 1, que adiciona um a um valor dobrado. Obviamente, isso não se aplica a um deslocamento à direita (potência de duas divisões) porque apenas um deslocamento à esquerda (little endian) preenche a lacuna com zeros.

No meu código, essas multiplicações / divisões por duas e potências de duas operações são usadas intensivamente e, como as fórmulas já são bastante curtas, cada instrução que pode ser eliminada pode ser um ganho substancial. Se o processador não suportar esses operadores de deslocamento de bits, nenhum ganho ocorrerá, mas também não haverá perda.

Além disso, nos algoritmos que estou escrevendo, eles representam visualmente os movimentos que ocorrem e, nesse sentido, são de fato mais claros. O lado esquerdo de uma árvore binária é maior e o direito é menor. Além disso, no meu código, os números pares e ímpares têm um significado especial, e todos os filhos da esquerda na árvore são ímpares e todos os filhos da mão direita e a raiz são pares. Em alguns casos, que eu ainda não encontrei, mas talvez não tenha pensado nisso, x & 1 pode ser uma operação mais ideal em comparação com x% 2. x e 1 em um número par produzirão zero, mas produzirão 1 para um número ímpar.

Indo um pouco além da identificação ímpar / par, se eu receber zero para x e 3, sei que 4 é um fator do nosso número e o mesmo para x% 7 para 8 e assim por diante. Sei que esses casos provavelmente têm utilidade limitada, mas é bom saber que você pode evitar uma operação de módulo e usar uma operação lógica bit a bit, porque as operações bit a bit são quase sempre as mais rápidas e com menor probabilidade de serem ambíguas para o compilador.

Estou inventando praticamente o campo de árvores binárias densas, por isso espero que as pessoas não compreendam o valor desse comentário, pois muito raramente as pessoas querem apenas executar fatorações com apenas potências de dois ou apenas multiplicar / dividir potências de duas.

Louki Sumirniy
fonte
0

Se é realmente mais rápido depende do hardware e compilador realmente usado.

Albert van der Horst
fonte
0

Se você comparar a saída para a sintaxe x + x, x * 2 e x << 1 em um compilador gcc, obterá o mesmo resultado no assembly x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

Portanto, você pode considerar o gcc suficientemente inteligente para determinar sua melhor solução independentemente do que você digitou.

Buridan
fonte
0

Eu também queria ver se eu poderia bater a casa. este é um bit a bit mais geral para qualquer número por qualquer multiplicação de números. as macros que fiz são cerca de 25% a mais que o dobro da multiplicação normal *. como dito por outros, se for próximo de um múltiplo de 2 ou composto de poucos múltiplos de 2, você poderá ganhar. como X * 23 composto por (X << 4) + (X << 2) + (X << 1) + X será mais lento que X * 65 composto por (X << 6) + X.

#include <stdio.h>
#include <time.h>

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}
AlexanderLife
fonte