0

我需要一个变量来指向数组索引，并且像圆一样在到达数组末尾时返回 0。我知道我可以使用if语句来判断，但是我不确定使用mod来实现相同的功能是否会更快，谁能给我一些建议？

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

3 回答 3

2

我写了一个小测试并通过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

在这里我们可以看到编译器将 div 替换为 mul、shifts 和 subs 的序列。这个技巧在这里有很好的描述。

这就是我得到的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 <stdio.h>
#include <stdint.h>

#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

因此，对于大量调用，比我的 CPUadd_index_if快 5 倍。add_index_mod

于 2016-06-07T15:18:20.233 回答
2

曾几何时，绝对是的。这些天，可能没有！

我将以 Intel Skylake 为例。DIV 指令（同时产生商和余数，用于此类事情）在 32 位被除数和除数上运行，具有 23 个周期的延迟和 6 个周期的倒数吞吐量。也就是说，根据它与其他操作的流水线方式，“成本”是 6-23 个周期。（好吧，由于执行端口的原因，它比那个复杂一点，但在这里和我一起工作。）正确预测的跳转是 0.5-2 个周期，具体取决于它是否被采取，错误预测的跳转有 16 个惩罚-17 个周期。（所有人都为 Agner Fog 欢呼计时。）

英特尔分支预测硬件真的非常好。期望它正确预测每第九个分支都会被采用可能太过分了，但在一个内部循环中，我至少希望它能够正确预测其他 8 次。这意味着 if 语句平均大约需要 3.5 个周期（不包括各种整数操作，可能会增加1-2 个周期）。哦，那是假设编译器特别笨拙，而不仅仅是像它应该使用的那样使用 CMOV。

要记住的是，整数除法是现代 CPU 可以做的最慢的“正常”事情之一。但是，对于已知除数的模数，您可以改为使用特殊的加法/乘法/移位序列。因此，在上述代码的情况下，除数是编译时常量而不是取自变量，您实际上可能会击败 DIV。这些序列可能很难流水线化，所以很难说它是否真的是一场胜利。无论如何，现代编译器绝对知道这样的技巧。

底线：很难说。如果您在内部循环中多次执行该操作，那么实际上可能值得尝试两种方式和时间。但是，您可能不会看到有意义的差异，也不会证明在其上花费优化时间是合理的。但是我经常写代码，需要极高的性能，我以前默认为 PPC 的模数，现在我默认为 x64 的 if/else。（嗯，三元。）

于 2016-06-07T13:24:32.410 回答
1

我宁愿使用 mod，而不深入研究情况的组装，这里有几件事需要考虑。

1）当您分支时（if 语句/函数调用/等），您的处理器可能需要刷新它的管道。这意味着，您有一堆指令在知道它们是否需要执行之前已经执行，并且“处理能力”只是丢失了。我不是说这会一直发生，但它可以

2）假设您想找到在当前条目之前发生 5 个条目的条目，并对其进行一些数学运算。假设您需要两者之间的平均值。您可以有一个更优雅的解决方案，而不是进行数学计算和存储结果、拥有一个额外的变量以及所有这些笨拙。

(array[index%10] + array[(index-5)%10])/2;

这现在可以环绕您的循环缓冲区。

如果你这样做，我觉得你会更习惯以这种方式编写代码，而不是用 if/else 语句来确定你的索引。

不过，有一点需要注意。如果取负数的模，c 在数学上是错误的。你最终会得到否定的答案。因此，如果您要执行此类操作（例如在当前条目之前查找条目），请从顶部索引开始索引

希望这可以帮助。

于 2016-06-07T13:00:39.833 回答