Beschleunigungsleistung der Schleife, die den nicht signierten langen langen Modulo-Betrieb durchführt

Question

Ich muss viele Vorgänge durchführen, um Reste der Division generationspapieretagcode mit dem 16-Bit-Modul zu finden:

generasacodicetagpre.

Wie kann ich diese Schleife beschleunigen?

Die Iterationszahl ist nicht groß (32-128), aber diese Schleife wurde sehr oft durchgeführt, so dass seine Geschwindigkeit kritisch ist.

Answer 1

Division durch eine Konstante (und es gibt nur 65536), können durch Multiplikation des Wechselkombinationen durchgeführt werden, gefolgt von einer Feinabstimmung.Da dieses Verfahren für einen begrenzten Bereich genau ist, kann man einige Techniken verwenden, um den 64-Bit-Operand auf einen viel kleineren Wert zu reduzieren (das noch mit dem ursprünglichen Wert kongruent ist):

generasacodicetagpre.

Der Zwischenwert kann nur mit (kleinen) Multiplikationen berechnet werden, und der Endrest (% n) hat Potenzial, mit der wechselseitigen Multiplikation berechnet zu werden.

Answer 2

If speed is critical, according to this answer about branch prediction and this one, loop unrolling may be of help, avoiding the test induced by the for instruction, reducing the number of tests and improving "branch prediction".

The gain (or none, some compilers do that optimization for you) varies based on architecture / compiler.

On my machine, changing the loop while preserving the number of operations from

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

to

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

with gcc -O2 the gain is ~15%. (500000000 instead of 100 to observe a more significant time difference)