摘要:性能优化不管是从方法论还是从实践上都有很多东西,本系列的文章会从C++语言本身入手,介绍一些性能优化的方法,希望能做到简洁实用。
作者:ali4846j3o
原文:http://click.aliyun.com/m/41845/
性能优化不管是从方法论还是从实践上都有很多东西,本系列的文章会从C++语言本身入手,介绍一些性能优化的方法,希望能做到简洁实用。
在开始本文的内容之前,让我们看段小程序:
如果要对这段代码进行优化,你认为瓶颈会是什么呢?代码-g -O2后看一眼汇编:
指令已经很少了,有多少优化空间呢?先不着急,看看下面这段代码
写了一个小程序,digits10_v2 比 digits10_v1快了45%, digits10_v3 比digits10_v1快了60%+。
不难看出测试结论跟数据的取值范围相关,就本例来说数值越大,提升越明显。是什么原因呢?附测试程序:
优化原因不是因为做了循环展开,而是由于不同指令本身的速度就是不一样的,比较、整型的加减、位操作速度都是最快的,而除法/取余却很慢。
下面有一个更详细的列表,为了更直观一些,用了clock cycle来衡量,不过这里的clock cycle是个平均值,不同的CPU还是稍有差异:
虽然大多数场景下,数学运算都不会有太多性能问题,但相对来说,整型的除法运算还是比较昂贵的。编译器就会利用这一特点进行优化,一般称作Strength reduction.
对于前面的例子,核心原因是digits10_v2用比较和加法来减少除法(/=)操作,digits10_v3通过搜索的方式进一步减少了除法操作。
由于cpu并行处理技术,我们不能简单的用后面的clock cycle来衡量性能,但不难看出处理器对类型的还是非常敏感的,以整型和浮点的处理为例:
类型转换
运算
代码示例
这里介绍的大多是编译器的擅长但又不能直接优化的场景,也是平常优化中比较容易忽视的点,其实往往我们往前多走一步,编译器就可以工作得更好。
先看一个数字转字符串的例子,stringstream和sprintf 自然不会是我们考虑的对象,虽然protobuf库中的FastInt32ToBuffer很不错,其实还能优化,下面的版本就比例子中stringstream快6倍,代码如下:
不用细读stringstream/sprintf的源码,反汇编看下就能知道个大概,对于转字符串这个场景,stringstream/sprintf就太重了,通常来说越少的指令性能也越好(如果你读过本系列的上一篇c++性能优化(一) ---- 从简单类型开始,不难发现,这句话也不正确,呵呵)。但本文讨论的重点是内存访问,就上面这段代码,有什么内存使用上的问题?如何进一步优化?
优化前还是得找一下性能热点,下面是vtune结果的截图(虽然cpu time和汇编指令的消耗对应得不是特别好):
数组reverse的开销跟上面生成数组元素相近,reverse有这么耗时么?
从图中的汇编可以看出,一次swap对应着两次内存读(movzxb)、两次内存写(movb),因为一次写就意味着一个读和一个写,描述的是内存-->cache-->内存的过程。
一个很自然的优化想法,应该尽量避免内存写操作,于是代码可以进一步优化,结合 Strength reduction,代码如下:
实测发现新版本比之前版本性能提升了10%,还有优化空间么?答案是,有。方案是:通过查表,一次处理2个数字,减少数据依赖,如:
结论:
下面是完整的测试代码和结果:
看到优化写内存操作的威力了吧,让我们再看一个减少写操作的例子:
假定A、B、C都很小,且不会溢出,可以写成
如果需要考虑溢出,也可以改为
对于内存的写,最好的办法就是减少写的次数,那么内存的读取呢?
教科书的答案是:尽可能顺序访问内存。理解这句话还是得从cache line开始,因为实际的cpu比较复杂,下面的表述尝试做些简化,如有问题,欢迎指正:
cache line
address) / ( line size) % (number of sets )来计算,如地址是10000,则(set)=10000/64%32=28, 即编号为28的集合内的4个cache line之一。
cache miss
可以看出,顺序的访问内存是能够比较高效而且不会因为cache冲突,导致药频繁读取内存。那什么的情况会导致cache miss呢?
对于内存的访问,可以考虑以下一些建议:
让我们再回到最前面的优化,u64ToAscii_v3引入了局部静态变量(digits),是否合适?通常来说,要具体问题具体分析,没有标准答案。
静态变量和栈地址是分开的,可能会带来cache miss的问题,通过去掉static修饰符,直接在栈上声明变的方式可以避免,但这种做法可行有几个前提条件:
其实内存访问和CPU运算是没有一定的赢家,真正做优化时,需要结合具体的场景,仔细测量才能得到答案。
前面两个实例分别从编译器和内存使用的角度介绍了一些性能优化的方法,后面内容则会回到cpu,从指令并行的角度看看我们常见的逻辑控制有哪些可以优化的点。
通常一个CPU可以并行执行多条指令,如:4条浮点乘法,等待4个内存访问、一个还为到来的分支比较,不同的运算单元也是可以并行计算,如for(int i=0; i < N; ++i) a[i]=i0.2; 这里的i < N和++i 在i0.2可以同时执行。提升指令并行能力,往往就能达到提升性能的目的。
从流水线的角度看,指令pipeline的几个阶段:fetch、decode、execute、memory-access、write-back,除了存储器的访问效率会影响并行度外,下一条指令的fetch/decode也很关键,而跳转和分支则是又一个拦路虎,这也是本文接下去要主要分析的地方:
常见的分支预测场景有if/else,for/while,switch,预测正确0~2 clock cycles,错误恢复12~25 clock cycles。
一般应用分支预测的正确率在90%以上,但个位数的误判率对有较多分支的程序来说影响还是非常大的。分支预测的技术(或者说策略)非常多,这里不会展开介绍,对写程序来说,我们知道越简单的场景越容易预测正确:如分支都在在一个循环内或者几乎没有其他分支。
如果对分支预测的概念和作用还不清楚的话,可以看看后面的参考文档。几个影响分支预测因素:
branch target buffer (BTB)
Return Address Stack (RAS)
消除条件分支
bool类型变换
a && b 何时不能转换成a & b,当a不可能为false的情况下
a | | b 何时不能转换成a | b,当a不可能为true的情况下
循环展开
边界检查
使用数组
整形的bit array语义,适用于enum、const、define
<<深入理解计算机系统>>
http://en.wikipedia.org/wiki/Instruction_pipelining
http://web.cecs.pdx.edu/~alaa/ece587/notes/bpred-6up.pdf
http://cseweb.ucsd.edu/~j2lau/cs141/week8.html
http://en.wikipedia.org/wiki/Branch_predictor
http://en.wikipedia.org/wiki/Branch_target_predictor
http://www-ee.eng.hawaii.edu/~tep/EE461/Notes/ILP/buffer.html
http://book.51cto.com/art/200804/70903.htm
http://en.wikipedia.org/wiki/Strength_reduction
https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
http://people.cs.clemson.edu/~dhouse/courses/405/papers/optimize.pdf
http://www.agner.org/optimize/optimizing_cpp.pdf
更多技术干货敬请关注云栖社区知乎机构号:阿里云云栖社区 - 知乎
公司名称: 8A-8A娱乐-注册登录商务站
手 机: 13800000000
电 话: 400-123-4567
邮 箱: admin@youweb.com
地 址: 广东省广州市天河区88号