c++ shift Multiplicação e divisão usando operadores de turno em C são realmente mais rápidos?




c shift operations (13)

Multiplicação e divisão podem ser alcançadas usando operadores de bit, 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 de usar dizer (i<<3)+(i<<1) para multiplicar com 10 do que usando i*10 diretamente? Existe algum tipo de entrada que não possa ser multiplicada ou dividida dessa maneira?


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

Abaixo, há um exemplo de código c ++ que pode fazer uma divisão mais rápida, fazendo uma "Multiplicação pelo recíproco" de 64 bits. Tanto o numerador quanto o denominador devem estar abaixo de certo limite. Note 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;
}

Resposta curta: não provável.

Resposta longa: Seu compilador possui um otimizador que sabe multiplicar-se tão rapidamente quanto sua arquitetura de processador de destino é capaz. Sua melhor aposta é dizer ao compilador sua intenção claramente (ou seja, i * 2 ao invés de i << 1) e deixá-lo decidir 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 multiplicada como uma sequência de mudanças e adições no microcódigo.

Bottom line - não gaste muito tempo se preocupando com isso. Se você quer mudar, mude. Se você pretende 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.


As instruções Shift e Integer Multiply têm desempenho semelhante na maioria das CPUs modernas - as instruções de multiplicação de números inteiros foram relativamente lentas na década de 1980, mas em geral isso não é mais verdade. As instruções de número inteiro multiplicado podem ter latência mais alta, portanto ainda pode haver casos em que um deslocamento é preferível. Idem para os casos em que você pode manter mais unidades de execução ocupadas (embora isso possa cortar nos dois sentidos).

A divisão inteira ainda é relativamente lenta, então 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, entretanto, que para que essa otimização seja válida, o dividendo precisa ser não assinado ou ser conhecido como positivo. Para um dividendo negativo, o turno 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;
}

Saída:

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ê quiser ajudar o compilador, certifique-se de que a variável ou expressão no dividendo seja explicitamente não assinada.


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

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


Eu acho que em um caso que você quer multiplicar ou dividir por um poder de dois, você não pode errar usando operadores bitshift, mesmo se o compilador os converter em um MUL / DIV, porque alguns processadores são microcódigo (realmente, um macro) de qualquer maneira, então, nesses casos, você obterá uma melhoria, especialmente se o deslocamento for maior que 1. Ou, mais explicitamente, se a CPU não tiver operadores bithift, será um MUL / DIV, mas se a CPU tiver operadores bitshift, você evita um ramo de microcódigo e isso é algumas instruções menos.

Eu estou escrevendo algum código agora que requer muitas operações de duplicação / redução porque está trabalhando em uma densa árvore binária, e há mais uma operação que eu suspeito que poderia ser mais ótima que uma adição - uma esquerda (poder de dois multiplica ) mudar com uma adição. Isso pode ser substituído por um turno à esquerda e um xor se o deslocamento for maior que o número de bits que você deseja adicionar, exemplo simples é (i << 1) ^ 1, que adiciona um a um valor duplicado. Isso obviamente não se aplica a um deslocamento à direita (poder de duas divisões), porque somente um deslocamento à esquerda (little endian) preenche a lacuna com zeros.

No meu código, estes multiplicar / dividir por dois e os poderes de duas operações são muito intensamente utilizados e porque 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 bit shift, 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, de modo que, na verdade, eles são mais claros. O lado esquerdo de uma árvore binária é maior e a direita é menor. Além disso, no meu código, números ímpares e pares têm um significado especial, e todos os filhos da mão esquerda na árvore são estranhos e todos os filhos da mão direita, e a raiz, são pares. Em alguns casos, que ainda não encontrei, mas que, na verdade, nem sequer pensei nisso, x & 1 pode ser uma operação mais ideal em comparação com x% 2. x & 1 em um número par produzirá zero, mas produzirá 1 para um número ímpar.

Indo um pouco mais longe do que apenas uma identificação ímpar / par, se eu obtiver zero para x e 3, sei que 4 é um fator de nosso número e o mesmo para x% 7 para 8, e assim por diante. Eu 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 bitwise, porque as operações bit a bit são quase sempre as mais rápidas e menos prováveis ​​de serem ambíguas para o compilador.

Eu estou praticamente inventando o campo denso de árvores binárias, então eu espero que as pessoas não entendam o valor deste comentário, já que muito raramente as pessoas querem apenas realizar fatorações apenas em potências de dois, ou apenas multiplicar / dividir poderes de dois.


No caso de números inteiros assinados e deslocamento à direita vs divisão, pode fazer a diferença. Para números negativos, o turno arredonda para o infinito negativo, enquanto a divisão arredonda para zero. É claro que o compilador mudará a divisão para algo mais barato, mas normalmente ele será alterado 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 o caminho que será feito, você poderá fazer essa otimização de uma maneira que provavelmente fará a diferença.


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

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


Não faça, a menos que você realmente precise e sua intenção de código requer mudança em vez de multiplicação / divisão.

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

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


Apenas um ponto concreto de medida: muitos anos atrás, eu testei 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 cada máquina em que eu comparava, a primeira era pelo menos tão rápida quanto a segunda. Surpreendentemente, algumas vezes foi mais rápido (por exemplo, em um Sun Sparc). Quando o hardware não suportava multiplicação rápida (e a maioria não o fazia), o compilador converteria a multiplicação nas combinações apropriadas de turnos e add / sub. E porque ele sabia o objetivo final, às vezes ele poderia fazê-lo em menos instruções do que quando você explicitamente escreveu os turnos e os add / subs.

Note que isso foi algo como 15 anos atrás. Esperançosamente, os compiladores só melhoraram desde então, então você pode muito bem 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 mais de 15 anos atrás. Eu obviamente usaria std::string e iteradores hoje.)


Deslocamento é geralmente muito mais rápido do que multiplicar a um nível de instrução, mas você pode estar perdendo seu tempo fazendo otimizações prematuras. O compilador pode bem realizar essas otimizações no compiletime. Fazê-lo você mesmo afetará a legibilidade e possivelmente não terá efeito no desempenho. É provável que valha a pena fazer coisas assim se você tiver perfilado e achado que isso seja um gargalo.

Na verdade, o truque de divisão, conhecido como "divisão mágica", pode render enormes recompensas. Mais uma vez você deve primeiro perfil para ver se é necessário. Mas se você usá-lo, 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 eu elevei 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

Tanto quanto eu sei em algumas máquinas multiplicação pode precisar de até 16 a 32 ciclo da máquina. Então, sim , dependendo do tipo de máquina, os operadores de troca de bits são mais rápidos que a multiplicação / divisão.

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


Eu concordo com a resposta marcada por Drew Hall. A resposta poderia usar algumas notas adicionais embora.

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, o 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.


É realmente mais rápido de usar dizer (i << 3) + (i << 1) para multiplicar com 10 do que usando i * 10 diretamente?

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

Um estudo de caso - do 486 ao core i7

O benchmarking é muito difícil de ser feito de forma significativa, mas podemos observar alguns fatos. A partir de http://www.penguin.cz/~literakl/intel/s.html#SAL e http://www.penguin.cz/~literakl/intel/i.html#IMUL temos uma ideia dos ciclos de relógio x86 necessário para a mudança e multiplicação aritmética. Digamos que nos mantemos em "486" (o mais novo listado), registros de 32 bits e imediatos, o IMUL leva de 13 a 42 ciclos e IDIV 44. Cada SAL leva 2 e adiciona 1, então mesmo com alguns juntos mudando superficialmente como um vencedor.

Hoje em dia, com o core i7:

(de 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 de números inteiros . Você pode encontrar as latências e informar no Apêndice C do "Manual de referência de otimização de arquiteturas Intel® 64 e IA-32", localizado em http://www.intel.com/products/processor/manuals/ .

(de alguma sinopse da Intel)

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

Isso dá uma ideia de quanto as coisas chegaram. A trivialidade da otimização - como a mudança de bit versus * - que foi levada a sério até os anos 90, agora está obsoleta. O deslocamento de bits ainda é mais rápido, mas no caso de não-energia de dois mul / div no momento em que você faz todos os seus turnos e adiciona os resultados, ele fica mais lento novamente. Então, mais instruções significam mais falhas de cache, mais problemas potenciais em pipelining, mais uso de registradores temporários pode significar mais economia e restauração do conteúdo de registros da pilha ... rapidamente fica muito complicado quantificar todos os impactos definitivamente, mas eles são predominantemente negativo.

funcionalidade no código-fonte vs implementação

Mais geralmente, sua pergunta é marcada com C e C ++. Como linguagens de 3ª geração, elas são projetadas 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 muitos outros), mesmo que o hardware subjacente não o faça . Em tais casos, eles devem sintetizar o resultado exigido 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. Todas as CPUs modernas suportam * e << , então isso pode parecer absurdamente teórico e histórico, mas o importante é que a liberdade de escolher a implementação vai nos dois sentidos: mesmo se a CPU tiver uma instrução que implemente a operação solicitada no código fonte No caso geral, o compilador está livre para escolher outra coisa que prefira porque é melhor para o caso específico com que o compilador se depara.

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 xor-ing qualquer coisa com ele limpa todos os bits, então ele pode ser usado para definir algo como 0. O código fonte que implica endereços de memória pode não implicar qualquer uso .

Esses tipos de hacks são usados ​​há tanto tempo quanto os computadores existem. Nos primeiros dias de 3GLs, para garantir a absorção do desenvolvedor, a saída do compilador tinha que satisfazer o desenvolvimento de linguagem de montagem de otimização de mão hardcore existente. comunidade que o código produzido não era mais lento, mais detalhado ou pior. Compiladores rapidamente adotaram muitas otimizações - eles se tornaram uma loja melhor centralizada do que qualquer programador de linguagem de montagem individual poderia ser, embora sempre haja a chance de perder uma otimização específica que é crucial em um caso específico - os humanos podem às vezes enlouqueça e busque algo melhor, enquanto os compiladores apenas fazem o que lhes foi dito até que alguém reponha essa experiência.

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

Manutenção

Se o seu hardware mudar, você pode recompilar e ele vai olhar para a CPU alvo e fazer outra melhor escolha, enquanto você provavelmente nunca vai querer 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" não-poder-de-dois-bits, escritas há mais de 10 anos atrás, que agora estão retardando o código em que elas estão, já que roda em processadores modernos ...!

Felizmente, bons compiladores como o GCC podem normalmente substituir uma série de bitshifts e aritmética com uma multiplicação direta quando qualquer otimização é ativada (ie ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax ) então uma recompilação pode ajudar mesmo sem consertar o código, mas isso não é garantido.

Estranho código de bits que implementa multiplicação ou divisão é muito menos expressivo do que você estava tentando conceitualmente alcançar, então outros desenvolvedores ficarão confusos com isso, e um programador confuso tem mais probabilidade de introduzir erros ou remover algo essencial em um esforço para restaurar aparente sanidade. Se você só faz coisas não óbvias quando elas são realmente benéficas, 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ê tiver algum conhecimento extra, como por exemplo, se o seu int realmente estiver armazenando apenas os valores x , y , então você poderá descobrir algumas instruções que funcionam para esses valores e obter seu resultado mais rapidamente do que quando o compilador não tem essa percepção e precisa de uma implementação que funcione para todos os valores int . Por exemplo, considere sua pergunta:

Multiplicação e divisão podem ser alcançadas usando operadores de bit ...

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

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

De acordo com o padrão C ++ 5.8:

-3- O valor de E1 >> E2 é E1 deslocadas para a direita nas posições E2. Se E1 tiver um tipo não assinado ou se E1 tiver um tipo assinado e um valor não negativo, o valor do resultado será a parte integral do quociente 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.

Então, seu bit shift 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. (Pode não ser perfeitamente consistente também, já que máquinas diferentes podem ter diferentes representações de números negativos e, portanto, diferentes faixas, mesmo quando há o mesmo número de bits que compõem a representação.)

Você pode dizer "eu não me importo ... que int está armazenando a idade do empregado, nunca pode ser negativo". Se você tem esse tipo de percepção especial, então sim - sua >> otimização segura pode ser ignorada pelo compilador, a menos que você o faça explicitamente em seu código. Mas, é arriscado e raramente útil na maior parte do tempo em que você não terá esse tipo de percepção, e outros programadores trabalhando no mesmo código não saberão que você apostou na casa com algumas expectativas incomuns sobre os dados que você Estarei lidando ... o que parece ser 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 comportamento definido pela implementação quando "dividido" por deslocamento de bits.







bit-shift