忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 386 | 回复: 0

[其他] 条件分支优化的一个例子 [复制链接]

论坛徽章:
13
程序设计版块每日发帖之星
日期:2016-06-29 06:20:00每日论坛发贴之星
日期:2016-08-14 06:20:00操作系统版块每日发帖之星
日期:2016-08-14 06:20:00每日论坛发贴之星
日期:2016-08-13 06:20:00数据库技术版块每日发帖之星
日期:2016-08-13 06:20:00程序设计版块每日发帖之星
日期:2016-08-13 06:20:00IT运维版块每日发帖之星
日期:2016-08-13 06:20:00每日论坛发贴之星
日期:2016-08-12 06:20:00数据库技术版块每日发帖之星
日期:2016-08-12 06:20:00程序设计版块每日发帖之星
日期:2016-08-12 06:20:00操作系统版块每日发帖之星
日期:2016-08-12 06:20:00综合交流区版块每日发帖之星
日期:2016-08-09 06:20:00
发表于 2017-06-23 20:26 |显示全部楼层
本帖最后由 karma303 于 2017-06-24 14:29 编辑

* 把项目里的一处代码优化的例子拿出来跟大家分享。
 先说说这处代码的上下文。项目本身是一个模拟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. /* @head_l 光标选区的起始行
  8.     @tail_l 光标选区的终止行
  9. static inline int
  10. degrade(int vmod, int head_l, int tail_l){
  11.     if(head_l == tail_l){
  12.         if(vmod == VMOD_v || vmod == VMOD_VB){
  13.             vmod = VMOD_NONE;
  14.         }
  15.     }
  16.     return vmod;
  17. }
复制代码
 我起初觉得这样写,条件判断太多,对流水线有影响。因为实际环境中,处于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. static inline int
  8. degrade_with_tbl(int vmod, int head_l, int tail_l){
  9.             if(head_l == tail_l){
  10.                         vmod = real_level[vmod];
  11.             }
  12.             return vmod;
  13. }
复制代码
我没有完全消灭所有的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不敢随便优化。即使未初始化,它也不敢断定里面是全0。
  7. */
  8. #define MAX (10*100000)
  9. int random_mods[MAX];
  10. int random_head_l[MAX];
  11. int random_tail_l[MAX];

  12. .....省略degrade()函数代码............

  13. #pragma GCC push_options
  14. #pragma GCC optimize ("O0")    //从这儿开始关闭编译优化,防止gcc做一些奇怪的事。(后来证明不用防止)

  15. int main(void){
  16.     ...
  17.     for(int i = 0; i < MAX; i++){
  18.         random_mods[i] = random() % 3 + 1;
  19.         random_head_l[i] = random() % 2;
  20.         random_tail_l[i] = random() % 2;
  21.     }
复制代码
然后四组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.     for(i = 0;  i < MAX; i++){
  20.         total4 +=
  21.         degrade_with_if(random_mods[i], random_head_l[i], random_tail_l[i]);
  22.     }
  23.                                                             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

复制代码
同样没有优化第一个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 ("O0"),即允许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

复制代码
快了有3倍之多。
上面的测试结果是在#pragma GCC optimize ("O0")被注释掉后得到的。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

复制代码
分支预测100%成功时,是不输给table版本的。

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


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

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






您需要登录后才可以回帖 登录 | 注册

本版积分规则

10张SACC2017门票等你来拿~

在数字化转型时代,云已成为万物智能的数字化大脑。而随着大数据应用、人工智能、移动互联网等技术的飞速发展,“智慧 +” 的概念正在深入到各行各业,提升企业效率,释放商业潜能,创造全新机遇。作为国内顶级技术盛会之一,2017 中国系统架构师大会(SACC2017)将于 10 月 19-21 日在北京新云南皇冠假日酒店震撼来袭。今年,大会以 “云智未来” 为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置 2 大主会场,18 个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100 余位技术专家及行业领袖来分享他们的经验;并将吸引 4000 + 人次的系统运维、架构师及 IT 决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年10月19日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP