利用分支预测优化代码

2013年6月6日 由 Creater 留言 »

linux中有likely 和unlikely的宏定义

        #define likely(x) __builtin_expect(!!(x),1)
        #define unlikely(x) __builtin_expect(!!(x),0)

__builtin_expect 宏的含义是通知编译器,对相应的分支预测进行优化。

我们知道顺序执行的代码CPU比较喜欢,因为不需要跳转。对于存在大量跳转或者说是分支的代码,CPU比较抓狂,因为CPU一般会提前 取指令 译码,甚至提前计算一些结果。如果分支预测错了,就会丢弃之前的指令,这样会影响效率。

如果我们提前知道代码 不同分支的执行概率,我们应该尽量让高概率的分支作为条件转移指令的下一
条指令,这样prefetch 和decode 就会选择条件 转移指令的下一条指令,从而预测成功,这正是我们期望的

__builtin_expect 就是通知编译器哪个分支出现的概率更高的。

__builtin_expect(!!(x),1)表示,告诉编译器,条件x为真的可能性非常高。

__builtin_expect(!!(x),0)表示,告诉编译器,条件x为假的可能性非常高。

#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include<time.h>

#define TIMES (10000000)
#define BILLION (1000000000)
#define MILLION 1000000
#define likely(x)      __builtin_expect(x,1)
#define unlikely(x)    __builtin_expect(x, 0)



int main(int argc,char *argv[])
{

		int i;
		int j;
		int *array = NULL;
		struct timespec tpstart;
		struct timespec tpend;
		unsigned long long timeif;
		unsigned long long timeif_func;
                struct timeval tv;
		if(argc != 2)
		{
			printf("usage: ./test times\n");
                        return -1;
		}

		int times = atoi(argv[1]);

		if(clock_gettime(CLOCK_MONOTONIC,&tpstart))
		{
			fprintf(stderr,"Fail to get start time for NULL\n");
			return -1;
		}
		for(i = 0;i<times;i++)
		{
			;
		}
		
		if(clock_gettime(CLOCK_MONOTONIC,&tpend))
		{
			fprintf(stderr,"Fail to get start time for NULL\n");
			return -1;
		}
		
		timeif = MILLION*(tpend.tv_sec - tpstart.tv_sec)+
                        (tpend.tv_nsec-tpstart.tv_nsec)/1000;

		printf("%d BLANK OP 's total time is %llu us\n",times,(timeif));

		
		if(clock_gettime(CLOCK_MONOTONIC,&tpstart))
		{
			fprintf(stderr,"Fail to get start time for branch \n");
			return -1;
		}
		for(i = 0;i<times;i++)
		{
			        j = rand();
				if(likely(j >1))
				{
                                   array = malloc(1000*sizeof(int));
				   if(array)
				      free(array);
				}
				else
				{
				    gettimeofday(&tv,NULL);
				}
		}
		
		if(clock_gettime(CLOCK_MONOTONIC,&tpend))
		{
			fprintf(stderr,"Fail to get start time for branch\n");
  		        return -1;
		}
		
		timeif_func =MILLION*(tpend.tv_sec - tpstart.tv_sec)+
                             (tpend.tv_nsec-tpstart.tv_nsec)/1000;

         printf("%d FUNCTION's with right prediction cost time is %llu us\n",
                 times,(timeif_func));	
}

j>1的概率几乎是100%,所以我们预测j>1,所以这是正确的预测。我们期待,malloc分支作为条件转移指令的下一条指令,这样,我们就能顺序取指令,无须跳转。
看下生成的汇编出来的代码。

gcc -o test_ok test.c -lrt -O2
objdump -d test_ok >objdump_ok

--------------------------objdump_ok---------------------------------------

 8048728:	e8 1b fe ff ff       	call   8048548 <rand@plt>
 804872d:	83 f8 01             	cmp    $0x1,%eax
 8048730:	0f 8e ac 00 00 00    	jle    80487e2 <main+0x1c2>
 8048736:	c7 04 24 a0 0f 00 00 	movl   $0xfa0,(%esp)
 804873d:	e8 f6 fd ff ff       	call   8048538 <malloc@plt>
 8048742:	85 c0                	test   %eax,%eax
 8048744:	74 08                	je     804874e <main+0x12e>
 8048746:	89 04 24             	mov    %eax,(%esp)
 8048749:	e8 ca fd ff ff       	call   8048518 <free@plt>

.............................................................

 80487e2:	8d 44 24 38          	lea    0x38(%esp),%eax
 80487e6:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 80487ed:	00 
 80487ee:	89 04 24             	mov    %eax,(%esp)
 80487f1:	e8 02 fd ff ff       	call   80484f8 <gettimeofday@plt>
 80487f6:	e9 53 ff ff ff       	jmp    804874e <main+0x12e>
------------------------------------------------------------------------------------

相反,我们如果预测j<1,即将代码中的likely,改成unlikely,那么我们就做出了错误的预测,那么编译器 生成的汇编代码如下。

       gcc -o test_err test.c -lrt -O2
       objdump -d test_err >objdump_err

——————-objdump_err——————————————-
 8048738:	e8 0b fe ff ff       	call   8048548 <rand@plt>
 804873d:	83 f8 01             	cmp    $0x1,%eax
 8048740:	0f 8f ac 00 00 00    	jg     80487f2 <main+0x1d2>
 8048746:	8d 44 24 38          	lea    0x38(%esp),%eax
 804874a:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 8048751:	00 
 8048752:	89 04 24             	mov    %eax,(%esp)
 8048755:	e8 9e fd ff ff       	call   80484f8 <gettimeofday@plt>
……………………………
 80487f2:	c7 04 24 a0 0f 00 00 	movl   $0xfa0,(%esp)
 80487f9:	e8 3a fd ff ff       	call   8048538 <malloc@plt>
 80487fe:	85 c0                	test   %eax,%eax
 8048800:	0f 84 54 ff ff ff    	je     804875a <main+0x13a>
 8048806:	89 04 24             	mov    %eax,(%esp)
 8048809:	e8 0a fd ff ff       	call   8048518 <free@plt>
——————————————————————————

从上面可以看出,由于我们的预测错误,gettimeofday放到了下一条指令,如果预取指令 译码,甚至执行,会发现,分支预测错了,丢弃之,然后跳转到malloc那条分支。

我们可以预测,由于分支预测出现了错误,test_ok 执行的速度应该比test_err执行的要快。当然,由于CPU还有Branch Target Buffer,这个BTB可以根据上次执行的转移,来预测本次转移。所以下面的两个程序,执行时间差的并不多。

root@libin:~/program/C/function_call# cat do.sh 
 ./test_err 100000000  &
 ./test_ok  100000000  &

root@libin:~/program/C/function_call# ./do.sh 
100000000 BLANK OP 's total time is 1 us
root@libin:~/program/C/function_call# 100000000 BLANK OP 's total time is 1 us
100000000 FUNCTION's with right prediction cost time is 9472328 us
100000000 FUNCTION's with wrong prediction cost time is 9751683 us

参考文献:1 likely()and unlikely()

广告位

发表评论

你必须 登陆 方可发表评论.