c - 加速循环执行 unsigned long long 模运算的性能

Question

我需要执行许多操作来找到 unsigned long long 数除以 16 位模数的余数:

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

我怎样才能加速这个循环？

迭代次数不多(32-128)，但是这个循环执行的频率很高，所以它的速度很关键。

Answer 1

如果速度很关键，根据这个 answer about branch prediction和 this one ，循环展开可能会有所帮助，避免由 for 指令引起的测试，减少测试次数并改进“分支预测”。

yield (或没有 yield ，一些编译器会为您进行优化)因架构/编译器而异。

在我的机器上，更改循环同时保留来自

的操作数

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

使用 gcc -O2 增益约为 15%。 (500000000 而不是 100 以观察更显着的时间差异)