值得用mod替换if语句为圆形索引
我需要一个变量来指向数组索引，并且像圆圈一样，当它到达数组的末尾时返回0。 我知道我可以使用if语句判断，但我不确定是否会更快或者不使用mod来实现相同的function，有人能给我一些建议吗？
int p=0; int arr[10]; void add_index(){ if(p==9) p=0; else p++; } 要么
int p=0; int arr[10]; void add_index(){ p=(p+1)%10; }
曾几何时，绝对是的。 这些天，可能没有！
我将以英特尔Skylake为例。 DIV指令（产生商和余数，并用于此类事物），在32位被除数和除数上运行，具有23个周期的等待时间和6个周期的倒数吞吐量。 也就是说，取决于它与其他操作的流水线方式，“成本”是6-23个周期。 （好吧，由于执行端口，它比执行端口稍微复杂一点，但是在这里和我一起工作。）正确预测的跳跃是0.5-2个周期，取决于它是否被采用，错误预测的跳跃有16的惩罚-17个周期。 （所有欢呼Agner Fog的时间。）
英特尔分支预测硬件非常非常好 。 期望它能够正确地预测每个第九个分支都会被采用，这可能太过分了，但在内循环中，我至少期望它能够正确地预测其他8个分支。 这意味着if语句的平均值大约为3.5个周期（不包括各种整数运算，可能会增加1-2个周期）。 哦，这是假设编译器特别狡猾，而不仅仅是像它应该使用CMOV。
要记住的是整数除法是现代CPU可以做的最慢的“正常”事情之一。 但是，对于已知除数的模数，您可以使用特殊的加/ muls / shift序列。 因此，对于上面的代码，除数是一个编译时常量而不是从变量中获取，你可能实际上击败了DIV。 这些序列很难管道化，因此很难说它是否真的是一场胜利。 无论如何，现代编译器绝对知道这样的技巧。
一句话：很难说。 如果你在内循环中进行了大量的操作，实际上可能值得尝试它的方式和时间。 但是，可能，你不会看到有意义的差异，也不会有理由在其上花费优化时间。 但我经常编写需要极高性能的代码，而我以前默认为PPC的模数，现在我默认使用if / else for x64。 （好吧，三元。）
我写了一个小测试并用gcc -O4优化编译它。
这是来自此测试的add_index_mod和add_index_if实现：
void add_index_mod(int *p) { *p = (*p + 1) % 10; } void add_index_if(int *p) { if (*p == 9) *p = 0; else (*p)++; }
这就是我为add_index_mod得到的：
mov eax, dword [rdi] mov edx, 0x66666667 lea ecx, dword [rax + 1] mov eax, ecx imul edx mov eax, ecx sar eax, 0x1f sar edx, 2 sub edx, eax lea eax, dword [rdx + rdx*4] add eax, eax sub ecx, eax mov dword [rdi], ecx ret
在这里我们可以看到编译器用mul，shift和subs的序列替换了div。 这个技巧在这里有很好的描述。
这就是我为add_index_if得到的：
mov edx, dword [rdi] lea eax, dword [rdx + 1] cmp edx, 9 mov edx, 0 cmove eax, edx mov dword [rdi], eax ret
这里没什么特别的，只有cmp和条件的mov。
所以现在你可以尝试使用这个表来计算这两个函数的汇编代码的效率。 但这不是最好的方法，因为乱序执行，分支预测等。
因此，正如我上面提到的，我只是写了一个小测试：
#include #include #define REPEATS (1 << 30) static inline uint64_t rdtsc() { unsigned int hi, lo; __asm__ volatile("rdtsc" : "=a" (lo), "=d" (hi)); return ((uint64_t)hi << 32) | lo; } void add_index_mod(int *p) { *p = (*p + 1) % 10; } void add_index_if(int *p) { if (*p == 9) *p = 0; else (*p)++; } int main() { int p = 0; uint32_t i; uint64_t start, stop; double delta, ticks_per_call; // mod ================================ start = rdtsc(); for (i = 0; i < REPEATS; ++i) { add_index_mod(&p); } stop = rdtsc(); // gcc with -O4 can remove above loop // if we don't use its result so print it printf("%d\n", p); delta = (double)(stop - start); ticks_per_call = delta / REPEATS; printf("add_index_mod: %f\n", ticks_per_call); // if ================================ start = rdtsc(); for (i = 0; i < REPEATS; ++i) { add_index_if(&p); } stop = rdtsc(); printf("%d\n", p); delta = (double)(stop - start); ticks_per_call = delta / REPEATS; printf("add_index_if: %f\n", ticks_per_call); return 0; }
这是我的英特尔酷睿i5-6500的输出：
add_index_mod: 9.643092 add_index_if: 2.063125
因此，对于大量的调用， add_index_if比我的CPU上的add_index_if快5倍。
我宁愿使用mod，也没有深入了解情况的集合，这里有几点需要考虑。
1）分支时（如果语句/函数调用/ etc），您的处理器可能需要刷新它的管道。 这意味着，在知道是否需要执行之前，您有一堆执行的指令，并且“处理能力”刚刚丢失。 我不是说这总是会发生，但它可以
2）假设您想要找到当前发生的5个条目的条目，并对其进行一些数学计算。 让我们说你需要两者之间的平均值。 您可以拥有更优雅的解决方案，而不是进行数学运算和存储结果，拥有额外的变量以及所有这些笨拙的内容。
(array[index%10] + array[(index-5)%10])/2;
现在可以环绕您的循环缓冲区。
如果你这样做，我觉得你习惯于以这种方式编写代码，而不是使用if / else语句来确定你的索引。
但是要注意这一点。 如果你取负数的模数，c在数学上是错误的。 你最终会得到一个否定的答案。 因此，如果您要执行此类操作，请在您的顶级索引处开始索引（例如，在当前条目之前查找条目）
希望这可以帮助。