Accelerazione delle prestazioni del loop che esegue operazioni modulo lungo lungo senza segno
-
23-12-2019 - |
Domanda
Devo eseguire molte operazioni per trovare i resti della divisione unsigned long long
numero dal modulo a 16 bit:
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];
}
Come posso accelerare questo ciclo?
Il numero di iterazioni non è elevato (32-128), ma questo ciclo viene eseguito molto spesso, quindi la sua velocità è fondamentale.
Soluzione
La divisione per una costante (e ce ne sono solo 65536) può essere eseguita mediante moltiplicazione del reciproco seguita/preceduta da qualche regolazione fine.Poiché questo metodo è accurato per un intervallo limitato, è possibile utilizzare alcune tecniche per ridurre l'operando a 64 bit a un valore molto più piccolo (che è ancora congruente al valore originale):
// 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;
Il valore intermedio può essere calcolato solo con (piccole) moltiplicazioni e il resto finale (%N) può essere calcolato potenzialmente con moltiplicazione reciproca.
Altri suggerimenti
Se la velocità è fondamentale, secondo questo risposta sulla previsione del ramo E Questo, lo srotolamento del loop può essere di aiuto, evitando il test indotto dal per istruzioni, riducendo il numero di test e migliorando la "previsione dei rami".
Il guadagno (o nessuno, alcuni compilatori eseguono l'ottimizzazione per te) varia in base all'architettura/al compilatore.
Sulla mia macchina, modificando il ciclo preservando il numero di operazioni da
for(int i = 0; i < 500000000; i++){
residues[i % 100] = largeNumber % modules[i % 100];
}
A
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];
}
con gcc -O2
il guadagno è del ~15%.(500000000 invece di 100 per osservare una differenza oraria più significativa)