Accélération des performances de la boucle effectuant une opération modulo longue et longue non signée

Question

Je dois effectuer de nombreuses opérations pour trouver les restes de la division unsigned long long nombre par le module 16 bits :

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];
}

Comment puis-je accélérer cette boucle ?

Le nombre d'itérations n'est pas grand (32-128), mais cette boucle s'exécute très souvent donc sa vitesse est critique.

Answer 1

La division par une constante (et il n'y en a que 65536) peut être effectuée par multiplication de l'inverse suivie/précédée de quelques ajustements.Puisque cette méthode est précise pour une plage limitée, on peut utiliser certaines techniques pour réduire l'opérande de 64 bits à une valeur beaucoup plus petite (qui est toujours conforme à la valeur d'origine) :

// 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;

La valeur intermédiaire peut être calculée uniquement avec de (petites) multiplications et le reste final (%N) peut potentiellement être calculé avec une multiplication réciproque.

Answer 2

Si la vitesse est critique, selon ceci réponse sur la prédiction de branche et celui-ci, le déroulement de la boucle peut être utile, en évitant le test induit par le pour instruction, réduisant le nombre de tests et améliorant la « prédiction de branche ».

Le gain (ou aucun, certains compilateurs font cette optimisation pour vous) varie en fonction de l'architecture/du compilateur.

Sur ma machine, changer la boucle tout en préservant le nombre d'opérations de

for(int i = 0; i < 500000000; i++){
    residues[i % 100] = largeNumber % modules[i % 100];
}

à

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];
}

avec gcc -O2 le gain est d'environ 15 %.(500000000 au lieu de 100 pour observer un décalage horaire plus important)