Quando testo a diferença de tempo entre mudar e multiplicar em C, não há diferença. Por quê?

28

Foi-me ensinado que mudar em binário é muito mais eficiente do que multiplicar por 2 ^ k. Então, eu queria experimentar e usei o seguinte código para testar isso:

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

int main() {
    clock_t launch = clock();
    int test = 0x01;
    int runs;

    //simple loop that oscillates between int 1 and int 2
    for (runs = 0; runs < 100000000; runs++) {


    // I first compiled + ran it a few times with this:
    test *= 2;

    // then I recompiled + ran it a few times with:
    test <<= 1;

    // set back to 1 each time
    test >>= 1;
    }

    clock_t done = clock();
    double diff = (done - launch);
    printf("%f\n",diff);
}

Para ambas as versões, a impressão foi de aproximadamente 440000, mais ou menos 10000. Não houve (visualmente, pelo menos) diferença significativa entre os resultados das duas versões. Então, minha pergunta é: há algo errado com minha metodologia? Deveria haver mesmo uma diferença visual? Isso tem algo a ver com a arquitetura do meu computador, do compilador ou de alguma outra coisa?

NicholasFolk
fonte
47
Quem lhe ensinou isso estava claramente enganado. Essa crença não é verdadeira desde a década de 1970, para compiladores normalmente usados ​​em arquiteturas normalmente usadas. É bom para você testar esta reivindicação. Eu ouvi essa afirmação absurda feita sobre JavaScript pelo amor de Deus.
Eric Lippert
21
A melhor maneira de responder a perguntas como essas é olhar para o código de montagem que o compilador está produzindo. Compiladores normalmente têm uma opção para produzir uma cópia da linguagem assembly que estão gerando. Para os compiladores GNU GCC, este é '-S'.
Charles E. Grant
8
É importante ressaltar que, depois de analisar isso gcc -S, o código para test *= 2é realmente compilado para shll $1, %eax Quando chamado com, gcc -O3 -Snão há nem mesmo um loop. As duas chamadas de relógio são separadas por uma linha:callq _clock movq %rax, %rbx callq _clock
6
"Fui ensinado que mudar no binário é muito mais eficiente do que multiplicar por 2 ^ k"; aprendemos muitas coisas que acabam erradas (ou pelo menos desatualizadas). Um compilador esperto usará a mesma operação de turno para ambos.
John Bode
9
Sempre, sempre verifique o código de montagem gerado ao trabalhar nesse tipo de otimização, para ter certeza de que está medindo o que pensa estar medindo. Um grande número de perguntas "por que estou vendo esses tempos" no SO acaba se resumindo ao compilador, eliminando completamente as operações, porque os resultados não são usados.
Russell Borogove

Respostas:

44

Como dito na outra resposta, a maioria dos compiladores otimiza automaticamente as multiplicações a serem feitas com deslocamento de bits.

Essa é uma regra muito geral ao otimizar: a maioria das 'otimizações' na verdade irá orientar mal a compilação sobre o que você realmente quer dizer e pode até diminuir o desempenho.

Otimize apenas quando você perceber um problema de desempenho e medir qual é o problema. (e a maioria dos códigos que escrevemos não é executada com tanta frequência, portanto não precisamos nos preocupar)

A grande desvantagem da otimização é que o código 'otimizado' geralmente é muito menos legível. Portanto, no seu caso, sempre vá para a multiplicação quando estiver procurando multiplicar. E faça uma mudança de bit quando quiser mover bits.

Thirler
fonte
20
Sempre use a operação semanticamente correta. Se você estava manipulando máscaras de bits ou posicionando números inteiros pequenos em números inteiros maiores, shift é a operação apropriada.
Ddyer 21/07
2
Haveria (praticamente falando) a necessidade de otimizar uma multiplicação para um operador de turno em um aplicativo de software de alto nível? Parece que, como o compilador já otimiza, que o único momento em que é útil ter esse conhecimento é ao programar em um nível muito baixo (pelo menos abaixo do compilador).
NicholasFolk
11
@NicholasFolk nope. Faça o que é mais simples de entender. Se você estivesse escrevendo o assembly diretamente, ele poderia ser útil ... ou se você estivesse escrevendo um compilador otimizador, novamente poderia ser útil. Mas fora desses dois casos, é um truque que obscurece o que você está fazendo e faz com que o próximo programador (que é um machado que sabe onde você mora ) amaldiçoe seu nome e pense em assumir um hobby.
2
@ NicolasFolk: As otimizações nesse nível são quase sempre obscurecidas ou discutidas pela arquitetura da CPU. Quem se importa se você salvar 50 ciclos ao buscar os argumentos na memória e gravá-los de volta, leva mais de 100? Micro-otimizações como essa faziam sentido quando a memória era executada na (ou próximo a) velocidade da CPU, mas não tanto hoje.
TMN
2
Porque eu estou cansado de ver esses 10% dessa citação e porque atinge a cabeça na cabeça aqui: "Não há dúvida de que o grau de eficiência leva ao abuso. Os programadores perdem muito tempo pensando ou se preocupando sobre a velocidade das partes não críticas de seus programas e essas tentativas de eficiência realmente têm um forte impacto negativo quando são consideradas a depuração e a manutenção.Nos devemos esquecer pequenas eficiências, digamos cerca de 97% das vezes: a otimização prematura é a raiz de todo o mal ....
Chao
25

O compilador reconhece constantes e converte multiplicações em turnos, quando apropriado.

ddyer
fonte
O compilador reconhece constantes que são potências de 2 .... e converte em turnos. Nem todas as constantes podem ser alteradas em turnos.
quickly_now
4
@ quick_now: eles podem ser convertidos em combinações de turnos e adições / subtrações.
Mehrdad
2
Um erro clássico do otimizador de compilador é converter as divisões em turnos certos, o que funciona com dividendos positivos, mas é 1 em negativo.
Ddyer
11
@quickly_now Acredito que o termo 'onde apropriado' cubra a ideia de que algumas constantes não podem ser reescritas como turnos.
Pharap
21

Se a mudança é mais rápida que a multiplicação depende da arquitetura da sua CPU. Nos tempos do Pentium e anteriores, o deslocamento era geralmente mais rápido que a multiplicação, dependendo do número de 1 bits no seu multiplicando. Por exemplo, se o seu multiplicando for 320, são 101000000, dois bits.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Mas se você tivesse mais de dois bits ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

Em um pequeno microcontrolador como um PIC18 com multiplicação de ciclo único, mas sem deslocamento de barril , a multiplicação é mais rápida se você estiver mudando mais de 1 bit.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

Observe que isso é o oposto do que era verdade em CPUs Intel mais antigas.

Mas ainda não é assim tão simples. Se bem me lembro, devido à sua arquitetura superescalar, um Pentium conseguiu processar uma instrução de multiplicação ou duas instruções de turno simultaneamente (desde que não dependessem uma da outra). Isso significa que, se você deseja multiplicar duas variáveis ​​por uma potência de 2, a mudança pode ser melhor.

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 
Rocketmagnet
fonte
5
+1 "Se a mudança é mais rápida que a multiplicação depende da arquitetura da sua CPU." Obrigado por realmente entrar um pouco na história e mostrar que a maioria dos mitos da computação tem alguma base lógica.
Pharap
11

Você tem vários problemas com seu programa de teste.

Primeiro, você não está realmente usando o valor de test. Não há como, dentro do padrão C, que o valor seja testimportante. O otimizador é totalmente gratuito para removê-lo. Uma vez removido, seu loop estará vazio. O único efeito visível seria definir runs = 100000000, mas runstambém não é usado. Portanto, o otimizador pode (e deve!) Remover o loop inteiro. Solução fácil: imprima também o valor calculado. Observe que um otimizador suficientemente determinado ainda pode otimizar o loop (depende inteiramente de constantes conhecidas em tempo de compilação).

Segundo, você realiza duas operações que se cancelam. O otimizador pode perceber isso e cancelá-lo . Novamente deixando um loop vazio e removido. Este é absolutamente difícil de corrigir. Você pode mudar para um unsigned int(para que o excesso não seja um comportamento indefinido), mas é claro que resulta apenas em 0. E coisas simples (como, por exemplo, test += 1) são fáceis o suficiente para o otimizador descobrir, e é o que acontece.

Finalmente, você assume que, test *= 2na verdade, será compilado para uma multiplicação. Essa é uma otimização muito simples; se o deslocamento de bits for mais rápido, o otimizador o utilizará. Para contornar isso, você teria que usar algo como um assembly específico da implementação em linha.

Ou, suponho, basta verificar a folha de dados do microprocessador para ver qual é mais rápida.

Quando verifiquei a saída de montagem da compilação do seu programa gcc -S -O3usando a versão 4.9, o otimizador realmente viu todas as variações simples acima e várias outras. Em todos os casos, ele removeu o loop (atribuindo uma constante a test), a única coisa que restava eram as chamadas para clock(), a conversão / subtração e a printf.

derobert
fonte
11
Observe também que o otimizador pode (e irá) otimizar as operações em constantes (mesmo em um loop), como mostrado em sqrt c # vs sqrt c ++, em que o otimizador conseguiu substituir um loop que soma um valor pela soma real. Para derrotar essa otimização, você precisa usar algo determinado em tempo de execução (como um argumento de linha de comando).
@MichaelT Yep. Isso é o que eu quis dizer com "Observe que um otimizador suficientemente determinado ainda pode otimizar o loop (ele depende inteiramente de constantes conhecidas em tempo de compilação)".
22414 derobert
Entendi o que você está dizendo, mas não acho que o compilador esteja removendo o loop inteiro. Você pode testar facilmente essa teoria simplesmente aumentando o número de iterações. Você verá que o aumento das iterações faz com que o programa demore mais. Se o loop foi totalmente removido, não seria esse o caso.
DollarAkshay
@AkshayLAradhya Não posso dizer o que seu compilador está fazendo, mas confirmei novamente que gcc -O3(agora com 7.3) ainda remove completamente o loop. (Certifique-se de mudar para um longo em vez de int, se necessário, caso contrário, ele será otimizado em um loop infinito devido ao estouro).
Derobert
8

Eu acho que seria mais útil para o questionador ter uma resposta mais diferenciada, porque vejo várias suposições não examinadas nas perguntas e em algumas das respostas ou comentários.

O tempo de execução relativo resultante de deslocamento e multiplicação não tem nada a ver com C. Quando digo C, não me refiro à instância de uma implementação específica, como aquela ou aquela versão do GCC, mas a linguagem. Não pretendo tomar esse ad absurdum, mas usar um exemplo extremo para ilustração: você pode implementar um compilador C completamente compatível com os padrões e fazer com que a multiplicação demore uma hora, enquanto a mudança leva milissegundos - ou o contrário. Não conheço nenhuma restrição de desempenho em C ou C ++.

Você pode não se importar com esse tecnicismo na argumentação. Sua intenção era provavelmente apenas testar o desempenho relativo de turnos versus multiplicações e você escolheu C, porque geralmente é percebida como uma linguagem de programação de baixo nível; portanto, pode-se esperar que seu código-fonte seja traduzido em instruções correspondentes mais diretamente. Tais perguntas são muito comuns e acho que uma boa resposta deve apontar que, mesmo em C, seu código-fonte não se traduz em instruções tão diretamente quanto você pensa em um determinado caso. Dei a você alguns resultados possíveis de compilação abaixo.

É aqui que entram os comentários que questionam a utilidade de substituir essa equivalência no software do mundo real. Você pode ver alguns nos comentários da sua pergunta, como o de Eric Lippert. Está de acordo com a reação que você geralmente obtém de engenheiros mais experientes em resposta a essas otimizações. Se você usar mudanças binárias no código de produção como um meio geral de multiplicar e dividir, as pessoas provavelmente se assustarão com o seu código e terão algum grau de reação emocional ("eu ouvi essa afirmação absurda feita sobre o JavaScript, pelo amor de Deus"). isso pode não fazer sentido para programadores iniciantes, a menos que eles entendam melhor os motivos dessas reações.

Esses motivos são principalmente uma combinação da diminuição da legibilidade e da futilidade dessa otimização, como você já deve ter descoberto ao comparar seu desempenho relativo. No entanto, não acho que as pessoas teriam uma reação tão forte se a substituição do turno pela multiplicação fosse o único exemplo dessas otimizações. Perguntas como a sua costumam aparecer de várias formas e em vários contextos. Acho que o que mais engenheiros seniores realmente reagem tão fortemente, pelo menos às vezes, é que há potencial para uma gama muito maior de danos quando as pessoas empregam essas micro otimizações liberalmente em toda a base de código. Se você trabalha em uma empresa como a Microsoft em uma grande base de códigos, passa muito tempo lendo o código-fonte de outros engenheiros ou tenta localizar determinado código nele. Pode até ser o seu próprio código que você tentará entender daqui a alguns anos, particularmente em alguns dos momentos mais inoportunos, como quando você precisa corrigir uma interrupção da produção após uma chamada que você recebeu no pager dever em uma noite de sexta-feira, prestes a sair para uma noite de diversão com os amigos ... Se você gastar tanto tempo lendo código, apreciará que seja o mais legível possível. Imagine ler seu romance favorito, mas a editora decidiu lançar uma nova edição em que eles usam a abrev. tudo sobre plc bcs thy thnk svs spc. Isso é semelhante às reações que outros engenheiros podem ter ao seu código, se você as derramar com essas otimizações. Como outras respostas apontaram, é melhor indicar claramente o que você quer dizer,

Mesmo nesses ambientes, você pode resolver uma questão de entrevista em que espera conhecer essa ou alguma outra equivalência. Conhecê-los não é ruim e um bom engenheiro estaria ciente do efeito aritmético da mudança binária. Note que eu não disse que isso é um bom engenheiro, mas que um bom engenheiro saberia, na minha opinião. Em particular, você ainda pode encontrar algum gerente, geralmente no final do ciclo de entrevistas, que sorrirá amplamente para você, antecipando o prazer de revelar esse "truque" inteligente de engenharia em uma questão de codificação e provar que ele / ela também costumava ser ou é um dos engenheiros mais experientes e não "apenas" um gerente. Nessas situações, tente parecer impressionado e agradeça pela entrevista esclarecedora.

Por que você não viu uma diferença de velocidade em C? A resposta mais provável é que ambos resultaram no mesmo código de montagem:

int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }

Os dois podem compilar em

shift(int):
    lea eax, [0+rdi*4]
    ret

No GCC sem otimizações, ou seja, usando o sinalizador "-O0", você pode obter o seguinte:

shift(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    sal eax, 2
    pop rbp
    ret
multiply(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    add eax, eax
    pop rbp
    ret

Como você pode ver, passar "-O0" para o GCC não significa que não será um pouco inteligente sobre o tipo de código que produz. Em particular, observe que, mesmo nesse caso, o compilador evitou o uso de uma instrução de multiplicação. Você pode repetir o mesmo experimento com turnos de outros números e até multiplicações de números que não são potências de dois. Provavelmente, em sua plataforma, você verá uma combinação de turnos e acréscimos, mas sem multiplicações. Parece uma coincidência para o compilador aparentemente evitar o uso de multiplicações em todos esses casos, se multiplicações e trocas realmente tiverem o mesmo custo, não é? Mas eu não pretendo fornecer suposição para prova, então vamos seguir em frente.

Você pode executar novamente seu teste com o código acima e ver se percebe uma diferença de velocidade agora. Mesmo assim, você não está testando shift versus multiplicar, como é possível ver pela ausência de multiplicação, mas o código que foi gerado com um determinado conjunto de sinalizadores pelo GCC para as operações C de shift e multiplicar em uma instância específica . Portanto, em outro teste, você pode editar o código do assembly manualmente e, em vez disso, usar uma instrução "imul" no código para o método "multiplicar".

Se você quiser derrotar alguns desses pontos inteligentes do compilador, defina um método de mudança e multiplicação mais geral e acabará com algo assim:

int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }

O que pode gerar o seguinte código de montagem:

shift(int, int):
    mov eax, edi
    mov ecx, esi
    sal eax, cl
    ret
multiply(int, int):
    mov eax, edi
    imul    eax, esi
    ret

Finalmente, temos finalmente, mesmo no nível mais alto de otimização do GCC 4.9, a expressão nas instruções de montagem que você pode esperar quando iniciou o teste. Eu acho que por si só pode ser uma lição importante na otimização de desempenho. Podemos ver a diferença que ele fez para substituir constantes concretas pelas variáveis ​​em nosso código, em termos de inteligência que o compilador é capaz de aplicar. Micro-otimizações, como a substituição de multiplicação por turno, são algumas otimizações de nível muito baixo que um compilador geralmente pode fazer sozinho. Outras otimizações que são muito mais impactantes no desempenho exigem uma compreensão da intenção do códigoisso geralmente não é acessível pelo compilador ou pode ser adivinhado apenas por algumas heurísticas. É aí que você entra como engenheiro de software e, certamente, normalmente não envolve substituir multiplicações por turnos. Envolve fatores como evitar uma chamada redundante para um serviço que produz E / S e pode bloquear um processo. Se você for ao seu disco rígido ou, se Deus permitir, a um banco de dados remoto para obter alguns dados extras que você poderia ter derivado do que você já tem na memória, o tempo gasto em espera será superior à execução de um milhão de instruções. Agora, acho que nos afastamos um pouco da sua pergunta original, mas acho que isso é apontado para um interlocutor, especialmente se supusermos que alguém está começando a entender a tradução e a execução do código,

Então, qual será mais rápido? Eu acho que é uma boa abordagem que você escolheu para testar a diferença de desempenho. Em geral, é fácil se surpreender com o desempenho em tempo de execução de algumas alterações no código. Existem muitas técnicas que os processadores modernos empregam e a interação entre softwares também pode ser complexa. Mesmo se você obtiver resultados benéficos de desempenho para uma determinada mudança em uma situação, acho perigoso concluir que esse tipo de alteração sempre trará benefícios de desempenho. Eu acho que é perigoso executar esses testes uma vez, diga "Ok, agora eu sei qual é o mais rápido!" e aplique indiscriminadamente essa mesma otimização ao código de produção sem repetir suas medições.

E daí se a mudança for mais rápida que a multiplicação? Certamente há indicações de por que isso seria verdade. O GCC, como você pode ver acima, parece pensar (mesmo sem otimização) que evitar a multiplicação direta em favor de outras instruções é uma boa idéia. O Manual de referência da otimização de arquiteturas Intel 64 e IA-32 fornecerá uma idéia do custo relativo das instruções da CPU. Outro recurso, mais focado na latência e no rendimento das instruções, é http://www.agner.org/optimize/instruction_tables.pdf. Observe que eles não são um bom predicador de tempo de execução absoluto, mas do desempenho de instruções relativas uma à outra. Em um loop restrito, enquanto seu teste está simulando, a métrica de "taxa de transferência" deve ser mais relevante. É o número de ciclos pelos quais uma unidade de execução normalmente estará vinculada ao executar uma determinada instrução.

E daí que a mudança NÃO é mais rápida que a multiplicação? Como eu disse acima, arquiteturas modernas podem ser bastante complexas e coisas como unidades de previsão de ramificação, armazenamento em cache, pipelining e execução paralela podem dificultar a previsão do desempenho relativo de duas partes de código logicamente equivalentes às vezes. Eu realmente quero enfatizar isso, porque é aqui que não estou feliz com a maioria das respostas para perguntas como estas e com o grupo de pessoas dizendo que simplesmente não é verdade (mais) que a mudança é mais rápida que a multiplicação.

Não, até onde sei, não inventamos um molho secreto de engenharia nos anos 70 ou quando anulamos repentinamente a diferença de custo de uma unidade de multiplicação e um pouco de shifter. Uma multiplicação geral, em termos de portas lógicas, e certamente em termos de operações lógicas, ainda é mais complexa do que uma mudança com um deslocador de barril em muitos cenários, em muitas arquiteturas. Como isso se traduz no tempo de execução geral em um computador desktop pode ser um pouco opaco. Não sei ao certo como eles são implementados em processadores específicos, mas aqui está uma explicação de uma multiplicação: A multiplicação inteira é realmente a mesma velocidade da adição na CPU moderna

Enquanto aqui está uma explicação de um deslocador de tambor . Os documentos que mencionei no parágrafo anterior oferecem outra visão sobre o custo relativo das operações, por proxy das instruções da CPU. Os engenheiros da Intel frequentemente parecem ter perguntas semelhantes: os fóruns da zona de desenvolvedor da intel criam ciclos de multiplicação de números inteiros e adição no processador core 2 duo

Sim, na maioria dos cenários da vida real, e quase certamente em JavaScript, tentar explorar essa equivalência pelo desempenho é provavelmente uma tarefa fútil. No entanto, mesmo se forçarmos o uso de instruções de multiplicação e não vermos diferença no tempo de execução, isso se deve mais à natureza da métrica de custo que usamos, para ser mais preciso, e não porque não há diferença de custo. O tempo de execução de ponta a ponta é uma métrica e, se é a única com a qual nos preocupamos, tudo está bem. Mas isso não significa que todas as diferenças de custo entre multiplicação e deslocamento simplesmente desapareceram. E acho que certamente não é uma boa ideia transmitir essa ideia a um questionador, por implicação ou não, que obviamente está apenas começando a ter uma idéia dos fatores envolvidos no tempo de execução e no custo do código moderno. A engenharia é sempre sobre compensações. A investigação e a explicação sobre quais compensações os processadores modernos fizeram para exibir o tempo de execução que nós, como usuários acabamos vendo, pode produzir uma resposta mais diferenciada. E acho que uma resposta mais diferenciada do que "isso simplesmente não é mais verdade" é justificada se quisermos ver menos engenheiros verificando o código micro-otimizado obliterando a legibilidade, porque é necessário um entendimento mais geral da natureza dessas "otimizações" para identifique suas várias encarnações diversas do que simplesmente se referir a alguns casos específicos como desatualizados.

user2880576
fonte
6

O que você vê é o efeito do otimizador.

O trabalho dos otimizadores é tornar o código compilado resultante menor ou mais rápido (mas raramente ambos ao mesmo tempo ... mas como muitas coisas ... DEPENDE do código).

Em PRINCIPLE, qualquer chamada para uma biblioteca de multiplicação ou, freqüentemente, até o uso de um multiplicador de hardware será mais lenta do que apenas uma mudança bit a bit.

Então ... se o compilador ingênuo gerasse uma chamada para uma biblioteca para a operação * 2, é claro que seria mais lento que um turno de bits *.

No entanto, existem otimizadores para detectar padrões e descobrir como tornar o código menor / mais rápido / o que for. E o que você viu é o compilador detectando que * 2 é o mesmo que uma mudança.

Apenas por uma questão de interesse, eu estava apenas hoje olhando o assembler gerado para algumas operações como * 5 ... não olhando realmente para isso, mas para outras coisas, e ao longo do caminho notei que o compilador transformou * 5 em:

  • mudança
  • mudança
  • adicionar número original

Portanto, o otimizador do meu compilador era inteligente o suficiente (pelo menos para determinadas pequenas constantes) para gerar trocas inline e adiciona, em vez de chamadas, a uma biblioteca de multiplicação de uso geral.

A arte dos otimizadores de compiladores é um assunto totalmente separado, cheio de magia e realmente bem entendido por cerca de 6 pessoas em todo o planeta :)

rapid_now
fonte
3

Tente cronometrar com:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

O compilador deve reconhecer que o valor de testé inalterado após cada iteração do loop, e o valor final de testnão é utilizado, e eliminando o loop completamente.

Russell Borogove
fonte
2

Multiplicação é uma combinação de turnos e acréscimos.

No caso que você mencionou, não acredito que seja importante se o compilador a otimiza ou não - "multiplicar xpor dois" pode ser implementado como:

  • Desloque bits de xum lugar para a esquerda.
  • Adicionar xa x.

Estas são operações atômicas básicas; um não é mais rápido que o outro.

Altere para "multiplicar xpor quatro" (ou qualquer 2^k, k>1) e é um pouco diferente:

  • Deslocar bits de x dois lugares para a esquerda.
  • Adicionar xpara xe chamá-lo y, adicione ya y.

Em uma arquitetura básica, é simples para ver que a mudança é mais eficiente - dando um contra duas operações, uma vez que não é possível adicionar ya yaté sabermos o quey é.

Experimente o último (ou qualquer outro 2^k, k>1), com as opções apropriadas para impedir que você os otimize para que seja a mesma coisa na implementação. Você deve achar que a mudança é mais rápida, O(1)comparada à adição repetida emO(k) .

Obviamente, onde o multiplicando não é uma potência de dois, é necessária uma combinação de turnos e adições (uma onde o número de cada um seja diferente de zero).

OJFord
fonte
11
O que é uma "operação atômica básica"? Não se pode argumentar que, em um turno, a operação pode ser aplicada a todos os bits em paralelo, enquanto os bits mais à esquerda dependem dos outros bits?
Bergi
2
@ Bergi: Eu acho que ele quer dizer que tanto shift quanto add são instruções de uma única máquina. Você precisaria examinar a documentação do conjunto de instruções para ver a contagem de ciclos de cada um, mas sim, uma adição geralmente é uma operação de vários ciclos, enquanto uma mudança geralmente é realizada em um único ciclo.
TMN
Sim, isso pode ser o caso, mas a multiplicação é uma única instrução de máquina, bem como (embora, naturalmente, pode precisar de mais ciclos)
Bergi
@ Bergi, isso também depende do arco. Em que arco você está pensando que muda em menos ciclos do que a adição de 32 bits (ou x-bit, conforme aplicável)?
OJFord
Não conheço nenhuma arquitetura em particular, não (e meus cursos de engenharia de computadores se desvaneceram); provavelmente ambas as instruções levam menos de um ciclo. Eu provavelmente estava pensando em termos de microcódigo ou mesmo portas lógicas, onde uma mudança provavelmente seria mais barata.
Bergi
1

A multiplicação de valores assinados ou não assinados por potências de dois é equivalente a deslocamento à esquerda, e a maioria dos compiladores fará a substituição. A divisão de valores não assinados ou valores assinados que o compilador pode provar nunca é negativa , é equivalente à mudança à direita, e a maioria dos compiladores fará essa substituição (embora alguns não sejam sofisticados o suficiente para provar quando os valores assinados não podem ser negativos) .

Deve-se notar, no entanto, que a divisão dos valores assinados potencialmente negativos não é equivalente à mudança à direita. Uma expressão como (x+8)>>4não é equivalente a (x+8)/16. O primeiro, em 99% dos compiladores, mapeará valores de -24 a -9 a -1, -8 a +7 a 0 e +8 a +23 a 1 [números de arredondamento quase simetricamente em torno de zero]. O último mapeará -39 a -24 a -1, -23 a +7 a 0 e +8 a +23 a +1 [grosseiramente assimétrico, e provavelmente não o que foi planejado]. Observe que, mesmo quando não se espera que os valores sejam negativos, o uso de >>4provavelmente produzirá um código mais rápido do que /16, a menos que o compilador possa provar que os valores não podem ser negativos.

supercat
fonte
0

Mais algumas informações que acabei de conferir.

No x86_64, o código de operação MUL possui uma latência de 10 ciclos e uma taxa de transferência de 1/2 ciclo. MOV, ADD e SHL têm uma latência de 1 ciclo, com taxa de transferência de 2,5, 2,5 e 1,7 ciclo.

Uma multiplicação por 15 exigiria 3 SHL e 3 ADD ops no mínimo e provavelmente alguns MOVs.

https://gmplib.org/~tege/x86-timing.pdf

Rich Remer
fonte
0

Sua metodologia é falha. O incremento do loop e a verificação de condição estão demorando muito tempo.

  • Tente executar um loop vazio e meça o tempo (chame base).
  • Agora adicione uma operação de turno e meça o tempo (chame s1).
  • Em seguida, adicione 10 operações de turno e meça o tempo (chame s2)

Se tudo está indo corretamente base-s2deve ser 10 vezes mais que base-s1. Caso contrário, algo mais está entrando em jogo aqui.

Agora, eu realmente tentei isso sozinho e pensei: se os loops estão causando um problema, por que não removê-los completamente? Então fui em frente e fiz o seguinte:

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

E aí você tem o seu resultado

1 milhão de operações de turno em menos de 1 milissegundo? .

Fiz o mesmo para multiplicação por 64 e obtive o mesmo resultado. Portanto, provavelmente o compilador está ignorando a operação completamente, já que outros mencionaram que o valor do teste nunca é alterado.

Resultado do Operador Shiftwise

DólarAkshay
fonte