A divisão é uma das operações mais caras nos processadores modernos. Você não precisa ir muito longe para a prova: a Agner Fog [
1 ] transmite que nos processadores Intel / AMD podemos obter facilmente latência em 25-119 ciclos de clock e taxa de transferência recíproca - 25-120. Traduzido para o russo -
LENTO ! No entanto, há uma oportunidade de evitar a instrução de divisão no seu código. E neste artigo, mostrarei como ele funciona, em particular nos compiladores modernos (eles já podem fazer isso há 20 anos), e também mostrarei como o conhecimento adquirido pode ser usado para tornar o código melhor, mais rápido e mais poderoso.
Na verdade, estou falando: se o divisor é conhecido no estágio de compilação, é possível substituir a divisão inteira pela multiplicação e uma mudança lógica para a direita (e às vezes você pode ficar sem ela - estou falando sobre a implementação na linguagem de programação). Parece muito encorajador: a operação de multiplicação de números inteiros e uma mudança para a direita, por exemplo, a Intel Haswell não levará mais que 5 ciclos de clock. Resta apenas entender como, por exemplo, executando a divisão inteira por 10, para obter o mesmo resultado por multiplicação de números inteiros e uma mudança lógica para a direita? A resposta a esta pergunta está no entendimento ... Aritmética de ponto fixo (doravante denominado FPA). Um pouco do básico.
Ao usar FP, o expoente (expoente 2 => a posição do ponto na representação binária do número) não é salvo no número (diferente da aritmética do ponto flutuante, consulte IEE754), mas é considerado uma quantidade acordada e conhecida pelos programadores. Somente a mantissa (o que vem depois do ponto decimal) é mantida. Um exemplo:
0.1 - em notação binária, possui 'representação infinita', que é indicada por parênteses no exemplo acima - essa parte será repetida de tempos em tempos, seguindo-se na notação FP binária do número 0.1.No exemplo acima, se usarmos registradores de 16 bits para armazenar números FP, não podemos ajustar a representação FP do número 0.1 em um registro sem perder a precisão, e isso, por sua vez, afetará o resultado de todos os cálculos adicionais nos quais o valor desse registro estiver envolvido.
Suponha que recebamos um número inteiro de 16 bits A e uma parte de Fração de 16 bits de B. O produto de A por B resulta em um número com 16 bits na parte inteira e 16 bits na parte fracionária. Para obter apenas a parte inteira, obviamente, você precisa mudar o resultado em 16 bits para a direita.
Parabéns, a introdução ao FPA terminou.
Formamos a seguinte hipótese: para realizar uma divisão inteira por 10, precisamos multiplicar o Número Divisível pela representação FP do número 0,1, pegar a parte inteira e a matéria no chapéu ... espere um minuto ... O resultado será preciso, mais precisamente, a parte inteira? - Afinal, como lembramos, em nossa memória apenas uma versão aproximada do número 0.1 é armazenada. Abaixo, escrevi três representações diferentes de 0,1: uma representação infinitamente precisa de 0,1, truncada após o 16º bit sem arredondamento, uma representação de 0,1 e truncada após o 16º bit com arredondamento, uma representação de 0,1.
Vamos estimar os erros das representações truncadas do número 0.1:
Para que o resultado da multiplicação do número inteiro A pela Aproximação de 0,1 forneça a parte inteira exata, precisamos:
ou
É mais conveniente usar a primeira expressão: quando
sempre obtemos a identidade (mas lembre-se, nem todas as decisões são mais que suficientes na estrutura deste problema). Resolvendo, temos
. Ou seja, multiplicando qualquer número de 14 bits A, truncando com arredondamento a representação de 0,1, sempre obtemos a parte inteira exata, que obteríamos multiplicando infinitamente exatamente 0,1 por A. Mas, por convenção, multiplicamos números de 16 bits, o que significa , no nosso caso, a resposta será imprecisa e não podemos confiar na multiplicação simples, truncando com o arredondamento para 0,1. Agora, se pudéssemos salvar na representação FP do número 0.1, não 16 bits, mas, digamos, 19, 20, tudo ficaria bem. E depois de tudo o que podemos!
Analisamos cuidadosamente a representação binária - truncando com arredondamento para 0,1: os três bits mais altos são zero, o que significa que eles não dão nenhuma contribuição ao resultado da multiplicação (novos bits).
Portanto, podemos mudar nosso número para a esquerda em três bits, arredondar para cima e, após fazer a multiplicação e o deslocamento lógico para a direita, primeiro por 16 e depois por 3 (ou seja, geralmente falando de uma vez por 19) - obtemos a parte inteira exata e desejada . A prova da correção de uma multiplicação de 19 bits é semelhante à anterior, com a única diferença de que funciona corretamente para números de 16 bits. Raciocínio semelhante também é verdadeiro para números de maior capacidade, e não apenas para divisão por 10.
Escrevi anteriormente que, de um modo geral, você pode passar sem nenhuma mudança, limitando-se à multiplicação. Como Montador x86 / x64 no tambor:
Nos processadores modernos, existe um comando MUL (também existem análogos de IMUL, MULX - BMI2), que, usando um, digamos, parâmetro de 32/64 bits, é capaz de executar a multiplicação de 64/128 bits, salvando o resultado em partes em dois registradores (altos 32/64 bits) e mais jovens, respectivamente):
MUL RCX ; RCX RAX, (128 ) RDX:RAX
Deixe um número inteiro A de 62 bits A ser armazenado no registro RCX e a representação FA de 64 bits truncada com arredondamento do número 0,1 seja armazenada no registro RAX (observe que não há turnos à esquerda). Após concluir a multiplicação de 64 bits, obtemos que os 64 bits mais altos do resultado são armazenados no registro RDX ou, mais precisamente, na parte inteira, que será exata para números de 62 bits. Ou seja, não é necessária uma mudança para a direita (SHR, SHRX). A presença de tal mudança carrega o Pipeline do processador, independentemente de suportar ou não o OOOE: pelo menos há uma dependência extra na cadeia já mais provável de tais dependências (também conhecida como cadeia de dependência). E aqui, é muito importante mencionar que os compiladores modernos, vendo uma expressão no formato some_integer / 10, geram automaticamente o código do assembler para todo o intervalo de números divisíveis. Ou seja, se você souber que seus números são sempre de 53 bits (foi exatamente o que aconteceu na minha tarefa), você receberá a instrução de turno extra de qualquer maneira. Mas agora que você entende como isso funciona, você pode facilmente substituir a divisão por multiplicação, sem depender da misericórdia do compilador. A propósito, obter os bits altos de um produto de 64 bits no código C ++ é implementado por algo como mulh, que, de acordo com o código Asm, deve ser equivalente às linhas da instrução {I} MUL {X} acima.
Talvez com o advento dos contratos (em C ++ 20, não estamos esperando) a situação melhore e, em alguns casos, possamos confiar no carro! Embora seja C ++, o programador é responsável por tudo aqui - não pelo contrário.
O raciocínio descrito acima - aplica-se a todos os divisores de constantes, bem e abaixo está uma lista de links úteis:
[1] https://www.agner.org/optimize/instruction_tables.pdf[2] Mais íngreme que Agner Fogh[3] Canal de telegrama com informações úteis sobre otimizações para Intel / AMD / ARM[4] Sobre divisão inteiramente, mas em inglês