文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

少写点if-else吧,它的效率有多低你知道吗?

2024-12-03 12:46

关注

 if-else涉及到分支预测的概念,关于分支预测上篇文章《虚函数真的就那么慢吗?它的开销究竟在哪里?来看这4段代码!》程序喵就粗略提到过,这里详细讲解一下。

首先看一段经典的代码,并统计它的执行时间:

  1. // test_predict.cc 
  2. #include  
  3. #include  
  4. #include  
  5.  
  6. int main() { 
  7.     const unsigned ARRAY_SIZE = 50000; 
  8.     int data[ARRAY_SIZE]; 
  9.     const unsigned DATA_STRIDE = 256; 
  10.  
  11.     for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE; 
  12.  
  13.     std::sort(data, data + ARRAY_SIZE); 
  14.  
  15.     {  // 测试部分 
  16.         clock_t start = clock(); 
  17.         long long sum = 0; 
  18.  
  19.         for (unsigned i = 0; i < 100000; ++i) { 
  20.             for (unsigned c = 0; c < ARRAY_SIZE; ++c) { 
  21.                 if (data[c] >= 128) sum += data[c]; 
  22.             } 
  23.         } 
  24.  
  25.         double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; 
  26.  
  27.         std::cout << elapsedTime << "\n"
  28.         std::cout << "sum = " << sum << "\n"
  29.     } 
  30.     return 0; 
  31. ~/test$ g++ test_predict.cc ;./a.out 
  32. 7.95312 
  33. sum = 480124300000 

此程序的执行时间是7.9秒,如果把排序那一行代码注释掉,即

  1. // std::sort(data, data + ARRAY_SIZE); 

结果为:

  1. ~/test$ g++ test_predict.cc ;./a.out 
  2. 24.2188 
  3. sum = 480124300000 

改动后的程序执行时间变为了24秒。

其实只改动了一行代码,程序执行时间却有3倍的差距,而且看上去数组是否排序与程序执行速度貌似没什么关系,这里面其实涉及到CPU分支预测的知识点。

提到分支预测,首先要介绍一个概念:流水线。

拿理发举例,小理发店一般都是一个人工作,一个人洗剪吹一肩挑,而大理发店分工明确,洗剪吹都有特定的员工,第一个人在剪发的时候,第二个人就可以洗头了,第一个人剪发结束吹头发的时候,第二个人可以去剪发,第三个人就可以去洗头了,极大的提高了效率。

这里的洗剪吹就相当于是三级流水线,在CPU架构中也有流水线的概念,如图:

在执行指令的时候一般有以下几个过程:

  1. 取指:Fetch
  2. 译指:Decode
  3. 执行:execute
  4. 回写:Write-back

流水线架构可以更好的压榨流水线上的四个员工,让他们不停的工作,使指令执行的效率更高。

再谈分支预测,举个经典的例子:

火车高速行驶的过程中遇到前方有个岔路口,假设火车内没有任何通讯手段,那火车就需要在岔路口前停下,下车询问别人应该选择哪条路走,弄清楚路线后后再重新启动火车继续行驶。高速行驶的火车慢速停下,再重新启动后加速,可以想象这个过程浪费了多少时间。

有个办法,火车在遇到岔路口前可以猜一条路线,到路口时直接选择这条路行驶,如果经过多个岔路口,每次做出选择时都能选择正确的路口行驶,这样火车一路上都不需要减速,速度自然非常快。但如果火车开过头才发现走错路了,就需要倒车回到岔路口,选择正确的路口继续行驶,速度自然下降很多。所以预测的成功率非常重要,因为预测失败的代价较高,预测成功则一帆风顺。

计算机的分支预测就如同火车行驶中遇到了岔路口,预测成功则程序的执行效率大幅提高,预测失败程序的执行效率则大幅下降。

CPU都是多级流水线架构运行,如果分支预测成功,很多指令都提前进入流水线流程中,则流水线中指令运行的非常顺畅,而如果分支预测失败,则需要清空流水线中的那些预测出来的指令,重新加载正确的指令到流水线中执行,然而现代CPU的流水线级数非常长,分支预测失败会损失10-20个左右的时钟周期,因此对于复杂的流水线,好的分支预测方法非常重要。

预测方法主要分为静态分支预测和动态分支预测:

静态分支预测:听名字就知道,该策略不依赖执行环境,编译器在编译时就已经对各个分支做好了预测。

动态分支预测:即运行时预测,CPU会根据分支被选择的历史纪录进行预测,如果最近多次都走了这个路口,那CPU做出预测时会优先考虑这个路口。

tips:这里只是简单的介绍了分支预测的方法,更多的分支预测方法资料大家可关注公众号回复分支预测关键字领取。

了解了分支预测的概念,我们回到最开始的问题,为什么同一个程序,排序和不排序的执行速度相差那么多。

因为程序中有个if条件判断,对于不排序的程序,数据散乱分布,CPU进行分支预测比较困难,预测失败的频率较高,每次失败都会浪费10-20个时钟周期,影响程序运行的效率。而对于排序后的数据,CPU根据历史记录比较好判断即将走哪个分支,大概前一半的数据都不会进入if分支,后一半的数据都会进入if分支,预测的成功率非常高,所以程序运行速度很快。

如何解决此问题?总体思路肯定是在程序中尽量减少分支的判断,方法肯定是具体问题具体分析了,对于该示例程序,这里提供两个思路削减if分支。

方法一:使用位操作:

  1. int t = (data[c] - 128) >> 31; 
  2. sum += ~t & data[c]; 

方法二:使用表结构:

  1. #include  
  2. #include  
  3. #include  
  4.  
  5. int main() { 
  6.     const unsigned ARRAY_SIZE = 50000; 
  7.     int data[ARRAY_SIZE]; 
  8.     const unsigned DATA_STRIDE = 256; 
  9.  
  10.     for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE; 
  11.  
  12.     int lookup[DATA_STRIDE]; 
  13.     for (unsigned c = 0; c < DATA_STRIDE; ++c) { 
  14.         lookup[c] = (c >= 128) ? c : 0; 
  15.     } 
  16.  
  17.     std::sort(data, data + ARRAY_SIZE); 
  18.  
  19.     {  // 测试部分 
  20.         clock_t start = clock(); 
  21.         long long sum = 0; 
  22.  
  23.         for (unsigned i = 0; i < 100000; ++i) { 
  24.             for (unsigned c = 0; c < ARRAY_SIZE; ++c) { 
  25.                 // if (data[c] >= 128) sum += data[c]; 
  26.                 sum += lookup[data[c]]; 
  27.             } 
  28.         } 
  29.  
  30.         double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; 
  31.         std::cout << elapsedTime << "\n"
  32.         std::cout << "sum = " << sum << "\n"
  33.     } 
  34.     return 0; 

其实Linux中有一些工具可以检测出分支预测成功的次数,有valgrind和perf,使用方式如图:

图片截自下方参考资料中

条件分支的使用会影响程序执行的效率,我们平时开发过程中应该尽可能减少在程序中随意使用过多的分支,能避免则避免。

更多的分支预测方法资料大家可关注公众号回复分支预测关键字领取。

参考资料

http://matt33.com/2020/04/16/cpu-branch-predictor/

https://zhuanlan.zhihu.com/p/22469702

https://en.wikipedia.org/wiki/Branch_predictor

https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array

 

来源:程序喵大人内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯