条件分支优化的一个例子

karma303

* 把项目里的一处代码优化的例子拿出来跟大家分享。
　先说说这处代码的上下文。项目本身是一个模拟vim的文本解析器。
　vim在visual/Visual Block模式(也就是小v和ctrl-v)下按x,d或s，会把删掉的文本保存在寄存器里，不足一行的，送到"-"编号寄存器（称作“小删除”寄存器），否则送到1号寄存器。但如果是visual line模式(大V)，就不加区分直接送到1号寄存器。因为是行选择，总是足行。
　所以在用户在visual选择后（此处visual指代v/V/VB三种，下文请自行区分）按下d,x之类的删除键时，程序要判断光标的选区是否跨行，如果未跨行，再判断是不是v或VB模式，如果是，就要对这次visual　selection做降级处理，得到真实的visual等级。后续的代码依赖这个真实等级。　例如前面提到的，决定使用哪个寄存器。

根据上面的需求，就有了这样一个函数：

1. enum{
   
2.     VMOD_NONE ,   // 0
   
3.     VMOD_v,              // 1
   
4.     VMOD_V,              //2
   
5.     VMOD_VB ,          //3
   
6. };
   
7. 
   
8. /* @head_l　光标选区的起始行
   
9.     @tail_l　光标选区的终止行
   
10. static inline int
    
11. degrade(int vmod, int head_l, int tail_l){
    
12.     if(head_l == tail_l){
    
13.         if(vmod == VMOD_v || vmod == VMOD_VB){
    
14.             vmod = VMOD_NONE;
    
15.         }
    
16.     }
    
17.     return vmod;
    
18. }

复制代码

　我起初觉得这样写，条件判断太多，对流水线有影响。因为实际环境中，处于v/V/VB这三种模式的可能性不能说谁大谁小，cpu的分支预测器等同虚设。
　于是我写了第一个优化版本:

　

1. /* 索引0~4分别对应VMOD_NONE, VMOD_v, VMOD_V, VMOD_VB
   
2. * [0] ~ [4]分别对应不足行时的被"降"到哪一级". 可见VMOD_v和VMOD_VB不足行时，
   
3. * 都被当做VMOD_NONE对待，VMOD_NONE这个命名不太形象，我是想指代”不足行的小的片段选区“。
   
4. */
   
5. int real_level[4] = {0, 0, 2, 0 };
   
6. 
   
7. /* 通过查表来避免条件判断 */
   
8. static inline int
   
9. degrade_with_tbl(int vmod, int head_l, int tail_l){
   
10.             if(head_l == tail_l){
    
11.                         vmod = real_level[vmod];
    
12.             }
    
13.             return vmod;
    
14. }

复制代码

我没有完全消灭所有的if语句，因为我想像if(head_l == tail_l)｛｝里是如此明显和简单的赋值语句，足够暗示gcc把这个if转成一条”条件传送指令“。

然后我做benchmark。

1. /* 先准备好长度为100万的三个数组，分别存储将”下达“给degrade()函数的三个参数，@mod, @head_l,
   
2. 　@tail_l。
   
3. * @mod在1~3之间随机。　
   
4.    @head_l和@tail_l在0,1两个值之间随机，因为要保证一定的”同行“(same-line)的概率。
   
5. *
   
6. * 下面3个数组还是声明为全局的放心一些，因为全局数组，gcc不敢随便优化。即使未初始化，它也不敢断定里面是全０。
   
7. */
   
8. #define MAX (10*100000)
   
9. int random_mods[MAX];
   
10. int random_head_l[MAX];
    
11. int random_tail_l[MAX];
    
12. 
    
13. .....省略degrade()函数代码............
    
14. 
    
15. #pragma GCC push_options
    
16. #pragma GCC optimize ("O０")    //从这儿开始关闭编译优化，防止gcc做一些奇怪的事。（后来证明不用防止）
    
17. 
    
18. int main(void){
    
19.     ...
    
20.     for(int i = 0; i < MAX; i++){
    
21.         random_mods[i] = random() % 3 + 1;
    
22.         random_head_l[i] = random() % 2;
    
23.         random_tail_l[i] = random() % 2;
    
24.     }
    

复制代码

然后四组for循环，两个版本的degrade_with_xx()各调用200万次。

1. TSTAMP_INIT();
   
2.                                                             TSTAMP();
   
3.     for(i = 0;  i < MAX; i++){
   
4.         total1 +=
   
5.         degrade_with_if(random_mods[i], random_head_l[i], random_tail_l[i]);
   
6.     }
   
7.                                                             TSTAMP(&timecost_if);
   
8.    
   
9.     for(i = 0;  i < MAX; i++){
   
10.         total2 +=
    
11.         degrade_with_tbl(random_mods[i], random_head_l[i], random_tail_l[i]);
    
12.     }
    
13.                                                             TSTAMP(&timecost_tbl);
    
14.     for(i = 0;  i < MAX; i++){
    
15.         total3 +=
    
16.         degrade_with_tbl(random_mods[i], random_head_l[i], random_tail_l[i]);
    
17.     }
    
18.                                                             TSTAMP(&timecost2_tbl);
    
19. 
    
20.     for(i = 0;  i < MAX; i++){
    
21.         total4 +=
    
22.         degrade_with_if(random_mods[i], random_head_l[i], random_tail_l[i]);
    
23.     }
    
24.                                                             TSTAMP(&timecost2_if);
    

复制代码

后两组循环和前两组是一模一样的，请不要费眼睛看了～　重复两次是为了放心。
累加total1/2/3/4是我怕gcc把for循环里的degrage_with_xx()函数直接优化掉了，所以让它的返回值对外部造成一些影响。
TSTAMP()顾名思义是”时间戳“，它计算距离前一个TSTAMP（）的时间间隔。然后保存在给它的参数里。
最后打印:

1.         printf("version   timecost   timecost:\n"
   
2.                    "if              %d            %d\n"
   
3.                    "table        %d           %d\n",
   
4.             timecost_if, timecost2_if, timecost_tbl, timecost2_tbl);
   

复制代码

编译: gcc -c -o t t.c ../base/benchmark.c -O3
运行:./t

1. version   timecost   timecost:
   
2. if             9577          9639
   
3. table       9795          9687

复制代码

上面是以微妙为单位的。
结果竟然相差无几。。。table版本比if还要慢一些。。。
看汇编就明白了：

1. 08048520 <degrade_with_tbl>:
   
2. 8048520:       39 ca                                              cmp    %ecx,%edx
   
3. 8048522:       74 0c 　　　　　　　　　　　　　                  je     8048530 <degrade_with_tbl+0x10>
   
4. 8048524:       f3 c3　　　　　　　　　　     　　                   repz ret
   
5. 8048526:       8d 76 00                                                       lea    0x0(%esi),%esi
   
6. 8048529:       8d bc 27 00 00 00 00                      lea    0x0(%edi,%eiz,1),%edi
   
7. 8048530:       8b 04 85 40 a0 04 08                      mov    0x804a040(,%eax,4),%eax
   
8. 8048537:  c3                                                  ret
   

复制代码

@head_l和@tail_l是通过ecx, edx传进来，上来就是一个cmp + je，可见gcc没有把这个if优化掉。
再看if版本的汇编:

1. 080484f0 <degrade_with_if>:
   
2. 80484f0:       39 ca                              cmp    %ecx,%edx
   
3. 80484f2:       74 0c                              je     8048500 <degrade_with_if+0x10>
   
4. 80484f4:       f3 c3                               repz ret
   
5. 80484f6:       8d 76 00                          lea    0x0(%esi),%esi
   
6. 80484f9:       8d bc 27 00 00 00 00    lea    0x0(%edi,%eiz,1),%edi
   
7. 8048500:       89 c2                             mov    %eax,%edx
   
8. 8048502:       83 e2 fd                        and    $0xfffffffd,%edx
   
9. 8048505:       83 fa 01                         cmp    $0x1,%edx
   
10. 8048508:       ba 00 00 00 00             mov    $0x0,%edx
    
11. 804850d:       0f 44 c2                        cmove  %edx,%eax
    
12. 8048510:       c3                                  ret
    
13. 
    

复制代码

同样没有优化第一个if，但        

1. if(vmod == VMOD_v || vmod == VMOD_VB){
   
2.             vmod = VMOD_NONE;
   
3. }

复制代码

被优化成了:
8048502:       83 e2 fd                        and    $0xfffffffd,%edx
8048505:       83 fa 01                         cmp    $0x1,%edx
8048508:       ba 00 00 00 00             mov    $0x0,%edx
804850d:       0f 44 c2                        cmove  %edx,%eax

因为VMOD和VMOD_VB分别是1和3，于是gcc先做一个 vmod & 1111..111101。　（二进制）
11111..111101只有与上1和3时，才能得到1。
然后测试是否得到了1，并使用条件传送指令cmove往@vmod写入0.

注意最后两条指令
mov $0x0, %edx
cmove %edx, %eax
正好在趁着cmp得出结果的空隙被乱序执行。

难怪这么快。我的table版本能跟它打成平手，还多亏了大循环时100%的cache命中率,实际运行时，很可能比它慢不少。
我决定改良table版本，强制gcc帮我消除if语句:

1. int  real_level[4][2] = {{0, 0}, {1, 0}, {2, 2}, {3, 0}};
   
2. static inline int
   
3. degrade_with_tbl(int vmod, int head_l, int tail_l){
   
4.     int equal = head_l == tail_l;
   
5.     vmod = real_level[vmod][equal];   
   
6.     return vmod;
   
7. }

复制代码

编译，看下汇编码:

1. 08048520 <degrade_with_tbl>:
   
2. 8048520:       39 ca                    cmp    %ecx,%edx
   
3. 8048522:       0f 94 c2                sete   %dl
   
4. 8048525:       0f b6 d2                movzbl %dl,%edx
   
5. 8048528:       8d 04 42                lea    (%edx,%eax,2),%eax
   
6. 804852b:       8b 04 85 40 a0 04 08    mov    0x804a040(,%eax,4),%eax
   
7. 8048532:       c3                          ret

复制代码

cmp + sete, 这下放心了。
运行：

1. version   timecost   timecost:
   
2. if             9583          9808
   
3. table      3791           3708

复制代码

如果注释掉前面的#pragma GCC optimize ("O０"),即允许gcc把这两个函数inline,效果会更明显:
(-O3, inline, 100万长数组随机0/1)

1. version   timecost   timecost:
   
2. if             7116         7011
   
3. table      1698          1652

复制代码

因为我们的汇编码很小巧。
由此可见，分支预测失败造成的流水线丢弃对性能的影响有多大。如果把前面的

1.              random_head_l[i] = random() % 2;
   
2.      　　  random_tail_l[i] = random() % 2;

复制代码

这两行注释掉，即，100万长的数组全是默认的0，让if版本100%分支预测成功，看它有多快:
(-O3, inline, 100万长数组全0)

1. version   timecost   timecost:
   
2. if             2053         1935
   
3. table      1353          1239
   
4. 
   

复制代码

快了有3倍之多。
上面的测试结果是在#pragma GCC optimize ("O０")被注释掉后得到的。100万长的全0数组似乎让table版本也快了一点点(我反复测了几次），这应该（我猜的，没看汇编码）是gcc优化了for循环，或者就是操作系统的周期波动，或者是gettimeofday()的问题（哎，我的TSTAMP是用它实现的），因为table版没有分支预测，是不受这个影响的。
为了完整性，再关闭inline,测试:
(-O3, no-inline, 100万长数组全0 )

1. version   timecost   timecost:
   
2. if              4262         3895
   
3. table       4104          4058
   
4. 
   

复制代码

分支预测100%成功时，是不输给table版本的。

测试到这里，我不准备把这个优化引入到项目里了，因为还是初期，而且这种table已经没有可读性了。
项目稳定后，可能会优化，但肯定要一同优化别的if。程序里处处分布的这种小if语句，虽然不是性能瓶颈，但批量优化一下，估计还是有收益。


很多时候，大家都在说不要过度和过早地优化，我想要能够自然的做到这一点的话，是得对编译器的行为有基本的了解。没事读一读gcc的汇编码，不然写性能严苛的程序会很难受。

最后忘了说了，用table来消除if，是有局限性的。像这个程序，因为vmod字段是程序内部维护的，所以我敢断定它是0~4。而且在发布版里不会再assert()它的值，如果真的真的被意外修改了，这个degrade_with_tbl()肯定会造成崩溃，但不要紧，因为反正是要崩溃的，在哪里崩溃无所谓。