Aceleração do desempenho do ciclo de realizar unsigned long long módulo operação
-
23-12-2019 - |
Pergunta
Eu preciso para realizar muitas operações de localizar os restos da divisão unsigned long long
número 16-bit módulo:
unsigned long long largeNumber;
long residues[100];
unsigned long modules[100];
intiModules(modules); //set different 16-bit values
for(int i = 0; i < 100; i++){
residues[i] = largeNumber % modules[i];
}
Como posso acelerar este ciclo?
A contagem de iteração não é grande (32-128), mas esse loop é executado muito, muitas vezes, portanto, a sua velocidade é crítica.
Solução
Divisão por uma constante (e há apenas 65536 deles), pode ser realizada pela multiplicação do recíproca seguido/precedido por alguns ajustes.Uma vez que este método é preciso, para uma gama limitada, pode-se utilizar algumas técnicas para reduzir o 64-bit do operando para um valor muito menor (o que ainda é congruente com o valor original):
// pseudo code -- not c
a = 0x1234567890abcdefULL;
a = 0x1234 << 48 + 0x5678 << 32 + 0x90ab << 16 + 0xcdef;
a % N === ((0x1234 * (2^48 % N) + // === means 'is congruent'
(0x5678 * (2^32 % N)) + // ^ means exponentation
(0x90ab * (2^16 % N)) +
(0xcdef * 1)) % N;
O valor intermediário pode ser calculado com uma (pequena) multiplicações e o final restante (%N) tem potencial para ser calculado com comutatividade da multiplicação.
Outras dicas
Se a velocidade é fundamental, de acordo com este resposta sobre a previsão de ramificação e este, loop unrolling podem ser de ajuda, evitando o teste induzida pelo para instrução, reduzindo o número de testes e melhorar "a previsão de ramificação".
O ganho (ou nenhum, alguns compiladores fazer de otimização para você) varia com base na arquitectura / compilador.
Na minha máquina, alterando o ciclo preservando o número de operações de
for(int i = 0; i < 500000000; i++){
residues[i % 100] = largeNumber % modules[i % 100];
}
para
for(int i = 0; i < 500000000; i+=5){
residues[(i+0) % 100] = largeNumber % modules[(i+0) % 100];
residues[(i+1) % 100] = largeNumber % modules[(i+1) % 100];
residues[(i+2) % 100] = largeNumber % modules[(i+2) % 100];
residues[(i+3) % 100] = largeNumber % modules[(i+3) % 100];
residues[(i+4) % 100] = largeNumber % modules[(i+4) % 100];
}
com gcc -O2
o ganho é de ~15%.(500000000 em vez de 100 a observar mais significativo com a diferença de fuso horário)