值得使用mod替换if语句来圈索引 [英] Is worth to use mod to replace if statement for circle index

问题描述

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

I need a variable to point the array index, and like circle to return 0 when it arrive the end of array. I know that I can use if statement to judge, but I'm not sure it's will more quickly or not to use mod to achieve same function, can anyone give me some advise?

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

推荐答案

我编写了一个小测试，并使用gcc -O4优化对其进行了编译.

I wrote a little test and compile it with gcc -O4 optimization.

这是此测试中的add_index_mod和add_index_if实现:

Here is add_index_mod and add_index_if implementations from this test:

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序列. 此处.

Here we can see that the compiler replaced div with sequence of mul, shifts and subs. This trick is well described here.

这就是我为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.

Nothing special here just cmp and conditional mov.

所以现在您可以尝试计算这两个程序的汇编代码的效率 使用此表的功能.但这不是最好的方法，因为执行顺序混乱，分支预测等.

So now you can try to calculate the efficiency of assembly code of both this functions using this table. But this is not the best way to go because of out of order execution, branch prediction and etc.

因此，如上所述，我只是编写了一个小测试:

So as I mentioned above I just wrote a little test:

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

这是我的Intel Core i5-6500的输出:

And here is its output for my Intel core i5-6500:

add_index_mod: 9.643092
add_index_if: 2.063125

因此，对于大量呼叫add_index_if来说，其速度是我CPU上add_index_mod的5倍.

So for huge number of calls add_index_if 5 times faster than add_index_mod on my CPU.

这篇关于值得使用mod替换if语句来圈索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！