性能优化的方法和技巧:代码
作者 kernelchina | 2011-04-15 01:53 | 类型 行业动感 | 27条用户评论 »
系列目录 性能优化方法和技巧代码层次的优化是最直接,也是最简单的,但前提是要对代码很熟悉,对系统很熟悉。很多事情做到后来,都是一句话:无他,但手熟尔^-^。 在展开这个话题之前,有必要先简单介绍一下Cache相关的内容,如果对这部分内容不熟悉,建议先补补课,做性能优化对Cache不了解,基本上就是盲人骑瞎马。 Cache一般来说,需要关心以下几个方面 1)Cache hierarchy Cache的层次,一般有L1, L2, L3 (L是level的意思)的cache。通常来说L1,L2是集成 在CPU里面的(可以称之为On-chip cache),而L3是放在CPU外面(可以称之为Off-chip cache)。当然这个不是绝对的,不同CPU的做法可能会不太一样。这里面应该还需要加上 register,虽然register不是cache,但是把数据放到register里面是能够提高性能的。 2)Cache size Cache的容量决定了有多少代码和数据可以放到Cache里面,有了Cache才有了竞争,才有 了替换,才有了优化的空间。如果一个程序的热点(hotspot)已经完全填充了整个Cache,那 么再从Cache角度考虑优化就是白费力气了,巧妇难为无米之炊。我们优化程序的目标是把 程序尽可能放到Cache里面,但是把程序写到能够占满整个Cache还是有一定难度的,这么大 的一个Code path,相应的代码得有多少,代码逻辑肯定是相当的复杂(基本上是不可能,至少 我没有见过)。 3)Cache line size CPU从内存load数据是一次一个cache line;往内存里面写也是一次一个cache line,所以一个 cache line里面的数据最好是读写分开,否则就会相互影响。 4)Cache associative Cache的关联。有全关联(full associative),内存可以映射到任意一个Cache line;也有N-way 关联,这个就是一个哈希表的结构,N就是冲突链的长度,超过了N,就需要替换。 5)Cache type 有I-cache(指令cache),D-cache(数据cache),TLB(MMU的cache),每一种又有L1, L2等等,有区分指令和数据的cache,也有不区分指令和数据的cache。 更多与cache相关的知识,可以参考这个链接: http://en.wikipedia.org/wiki/CPU_cache 或者是附件里面的cache.pdf,里面有一个简单的总结。 代码层次的优化,主要是从以下两个角度考虑问题: 1)I-cache相关的优化 例如精简code path,简化调用关系,减少冗余代码等等。尽量减少不必要的调用。但是有用还是无用,是和应用相关的,所以代码层次的优化很多是针对某个应用或者性能指标的优化。有针对性的优化,更容易得到可观的结果。 2)D-cache相关的优化 减少D-cache miss的数量,增加有效的数据访问的数量。这个要比I-cache优化难一些。 下面是一个代码优化技巧列表,需要不断地补充,优化和筛选。 1) Code adjacency (把相关代码放在一起),推荐指数:5颗星 把相关代码放在一起有两个涵义,一是相关的源文件要放在一起;二是相关的函数在object文件 里面,也应该是相邻的。这样,在可执行文件被加载到内存里面的时候,函数的位置也是相邻的。 相邻的函数,冲突的几率比较小。而且相关的函数放在一起,也符合模块化编程的要求:那就是 高内聚,低耦合。 如果能够把一个code path上的函数编译到一起(需要编译器支持,把相关函数编译到一起), 很显然会提高I-cache的命中率,减少冲突。但是一个系统有很多个code path,所以不可能面 面俱到。不同的性能指标,在优化的时候可能是冲突的。所以尽量做对所以case都有效的优化, 虽然做到这一点比较难。 2) Cache line alignment (cache对齐),推荐指数:4颗星 数据跨越两个cache line,就意味着两次load或者两次store。如果数据结构是cache line对齐的, 就有可能减少一次读写。数据结构的首地址cache line对齐,意味着可能有内存浪费(特别是 数组这样连续分配的数据结构),所以需要在空间和时间两方面权衡。 3) Branch prediction (分支预测),推荐指数:3颗星 代码在内存里面是顺序排列的。对于分支程序来说,如果分支语句之后的代码有更大的执行几率, 那么就可以减少跳转,一般CPU都有指令预取功能,这样可以提高指令预取命中的几率。分支预测 用的就是likely/unlikely这样的宏,一般需要编译器的支持,这样做是静态的分支预测。现在也有 很多CPU支持在CPU内部保存执行过的分支指令的结果(分支指令的cache),所以静态的分支预测 就没有太多的意义。如果分支是有意义的,那么说明任何分支都会执行到,所以在特定情况下,静态 分支预测的结果并没有多好,而且likely/unlikely对代码有很大的侵害(影响可读性),所以一般不 推荐使用这个方法。 4) Data prefetch (数据预取),推荐指数:4颗星 指令预取是CPU自动完成的,但是数据预取就是一个有技术含量的工作。数据预取的依据是预取的数据 马上会用到,这个应该符合空间局部性(spatial locality),但是如何知道预取的数据会被用到,这个 要看上下文的关系。一般来说,数据预取在循环里面用的比较多,因为循环是最符合空间局部性的代码。 但是数据预取的代码本身对程序是有侵害的(影响美观和可读性),而且优化效果不一定很明显(命中 的概率)。数据预取可以填充流水线,避免访问内存的等待,还是有一定的好处的。 5) Memory coloring (内存着色),推荐指数:不推荐 内存着色属于系统层次的优化,在代码优化阶段去考虑内存着色,有点太晚了。所以这个话题可以放到 系统层次优化里面去讨论。 6)Register parameters (寄存器参数),推荐指数:4颗星 寄存器做为速度最快的内存单元,不好好利用实在是浪费。但是,怎么用?一般来说,函数调用的参数 少于某个数,比如3,参数是通过寄存器传递的(这个要看ABI的约定)。所以,写函数的时候,不要 带那么多参数。c语言里还有一个register关键词,不过通常都没什么用处(没试过,不知道效果,不过 可以反汇编看看具体的指令,估计是和编译器相关)。尝试从寄存器里面读取数据,而不是内存。 7) Lazy computation (延迟计算),推荐指数:5颗星 延迟计算的意思是最近用不上的变量,就不要去初始化。通常来说,在函数开始就会初始化很多数据,但是 这些数据在函数执行过程中并没有用到(比如一个分支判断,就退出了函数),那么这些动作就是浪费了。 变量初始化是一个好的编程习惯,但是在性能优化的时候,有可能就是一个多余的动作,需要综合考虑函数 的各个分支,做出决定。 延迟计算也可以是系统层次的优化,比如COW(copy-on-write)就是在fork子进程的时候,并没有复制父 进程所有的页表,而是只复制指令部分。当有写发生的时候,再复制数据部分,这样可以避免不必要的复制, 提供进程创建的速度。 8] Early computation (提前计算),推荐指数:5颗星 有些变量,需要计算一次,多次使用的时候。最好是提前计算一下,保存结果,以后再引用,避免每次都 重新计算一次。函数多了,有时就会忽略这个函数都做了些什么,写程序的人可以不了解,但是优化的时候 不能不了解。能使用常数的地方,尽量使用常数,加减乘除都会消耗CPU的指令,不可不查。 9)Inline or not inline (inline函数),推荐指数:5颗星 Inline or not inline,这是个问题。Inline可以减少函数调用的开销(入栈,出栈的操作),但是inline也 有可能造成大量的重复代码,使得代码的体积变大。Inline对debug也有坏处(汇编和语言对不上)。所以 用这个的时候要谨慎。小的函数(小于10行),可以尝试用inline;调用次数多的或者很长的函数,尽量不 要用inline。 10) Macro or not macro (宏定义或者宏函数),推荐指数:5颗星 Macro和inline带来的好处,坏处是一样的。但我的感觉是,可以用宏定义,不要用宏函数。用宏写函数, 会有很多潜在的危险。宏要简单,精炼,最好是不要用。中看不中用。 11) Allocation on stack (局部变量),推荐指数:5颗星 如果每次都要在栈上分配一个1K大小的变量,这个代价是不是太大了哪?如果这个变量还需要初始化(因 为值是随机的),那是不是更浪费了。全局变量好的一点是不需要反复的重建,销毁;而局部变量就有这个 坏处。所以避免在栈上使用数组等变量。 12) Multiple conditions (多个条件的判断语句),推荐指数:3颗星 多个条件判断时,是一个逐步缩小范围的过程。条件的先后,决定了前面的判断是否多余的。根据code path 的情况和条件分支的几率,调整条件的顺序,可以在一定程度上减少code path的开销。但是这个工作做 起来有点难度,所以通常不推荐使用。 13) Per-cpu data structure (非共享的数据结构),推荐指数:5颗星 Per-cpu data structure 在多核,多CPU或者多线程编程里面一个通用的技巧。使用Per-cpu data structure的目的是避免共享变量的锁,使得每个CPU可以独立访问数据而与其他CPU无关。坏处是会 消耗大量的内存,而且并不是所有的变量都可以per-cpu化。并行是多核编程追求的目标,而串行化 是多核编程里面最大的伤害。有关并行和串行的话题,在系统层次优化里面还会提到。 局部变量肯定是thread local的,所以在多核编程里面,局部变量反而更有好处。 14) 64 bits counter in 32 bits environment (32位环境里的64位counter),推荐指数:5颗星 32位环境里面用64位counter很显然会影响性能,所以除非必要,最好别用。有关counter的优化可以多 说几句。counter是必须的,但是还需要慎重的选择,避免重复的计数。关键路径上的counter可以使用 per-cpu counter,非关键路径(exception path)就可以省一点内存。 15) Reduce call path or call trace (减少函数调用的层次),推荐指数:4颗星 函数越多,有用的事情做的就越少(函数的入栈,出栈等)。所以要减少函数的调用层次。但是不应该 破坏程序的美观和可读性。个人认为好程序的首要标准就是美观和可读性。不好看的程序读起来影响心 情。所以需要权衡利弊,不能一个程序就一个函数。 16) Move exception path out (把exception处理放到另一个函数里面),推荐指数:5颗星 把exception path和critical path放到一起(代码混合在一起),就会影响critical path的cache性能。 而很多时候,exception path都是长篇大论,有点喧宾夺主的感觉。如果能把critical path和 exception path完全分离开,这样对i-cache有很大帮助。 17) Read, write split (读写分离),推荐指数:5颗星 在cache.pdf里面提到了伪共享(false sharing),就是说两个无关的变量,一个读,一个写,而这 两个变量在一个cache line里面。那么写会导致cache line失效(通常是在多核编程里面,两个变量 在不同的core上引用)。读写分离是一个很难运用的技巧,特别是在code很复杂的情况下。需要 不断地调试,是个力气活(如果有工具帮助会好一点,比如cache miss时触发cpu的execption处理 之类的)。 18) Reduce duplicated code(减少冗余代码),推荐指数:5颗星 代码里面的冗余代码和死代码(dead code)很多。减少冗余代码就是减小浪费。但冗余代码有时 又是必不可少(copy-paste太多,尾大不掉,不好改了),但是对critical path,花一些功夫还 是必要的。 19) Use compiler optimization options (使用编译器的优化选项),推荐指数:4颗星 使用编译器选项来优化代码,这个应该从一开始就进行。写编译器的人更懂CPU,所以可以放心 地使用。编译器优化有不同的目标,有优化空间的,有优化时间的,看需求使用。 20) Know your code path (了解所有的执行路径,并优化关键路径),推荐指数:5颗星 代码的执行路径和静态代码不同,它是一个动态的执行过程,不同的输入,走过的路径不同。 我们应该能区分出主要路径和次要路径,关注和优化主要路径。要了解执行路径的执行流程, 有多少个锁,多少个原子操作,有多少同步消息,有多少内存拷贝等等。这是性能优化里面 必不可少,也是唯一正确的途径,优化的过程,也是学习,整理知识的过程,虽然有时很无聊, 但有时也很有趣。 代码优化有时与编程规则是冲突的,比如直接访问成员变量,还是通过接口来访问。编程规则上肯定是说要通过接口来访问,但直接访问效率更高。还有就是许多ASSERT之类的代码,加的多了,也影响性能,但是不加又会给debug带来麻烦。所以需要权衡。代码层次的优化是基本功课,但是指望代码层次的优化来解决所有问题,无疑是缘木求鱼。从系统层次和算法层次考虑问题,可能效果会更好。 代码层次的优化需要相关工具的配合,没有工具,将会事倍功半。所以在优化之前,先把工具准备好。有关工具的话题,会在另一篇文章里面讲。 还有什么,需要好好想想。这些优化技巧都是与c语言相关的。对于其他语言不一定适用。每个语言都有一些与性能相关的编码规范和约定俗成,遵守就可以了。有很多Effective, Exceptional 系列的书籍,可以看看。 代码相关的优化,着力点还是在代码上,多看,多想,就会有收获。 参考资料: 1)http://en.wikipedia.org/wiki/CPU_cache 2) Effective C++: 55 Specific Ways to Improve Your Programs and Designs (3rd Edition) 3) More Effective C++: 35 New Ways to Improve Your Programs and Designs 4) Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library | |
雁过留声
“性能优化的方法和技巧:代码”有27个回复
转载了:)
楼主酿了瓶好酒。
好酒闻起来很香,酒量不好的人一喝就醉,醉了就干坏事
最怕的就是营长先喝醉了,拿着guideline当principal。指挥着下面人,都给老子这么干。美其名曰,流程完备,执行力强
不错的问题,归纳的很全。不过要优化系统性能首要是还是要能准确的measure系统。
有什么好评估系统开销的工具么?给推荐一下
对通讯系统来说,复杂的控制平面通过cache优化很难,提高不容易,但转发平面是一定可以提高很多的,但当转发平面的功能越来越多的时候,所有功能全面提升就非常难并且实际在网络上部署的时候应用也不多,所以在架构设计的时候,就要考虑到根据实际用户使用的特性组合而形成的几个主path进行优化,次要path,也就是使用频率少的被优先舍弃。不同种类的用户使用的特性组合也不同,那么系统就要考虑不同组合可以在线或者离线的可配置方式,提供该用户使用的组合的性能被优化,而不使用的可以降低。从微观上看,很多方法都很好,而从宏观上看,如果组合比较单一,问题不大,而一旦组合很多的时候,如何trade off,如果balance,适应多种主流组合,就需要高超的架构师出手了
to理客:“而一旦组合很多的时候,如何trade off,如果balance,适应多种主流组合,就需要高超的架构师出手了”
可否从架构的角度简单的举些例子来讲下如何trade,如何balance?
作为一线研发人员,惭愧的是这些偏重于细节化的优化技巧感觉派不上用场。看来将来要多投入点精力研究研究,也许会能够事半功倍。
窃以为,架构设计对性能影响才是最重要的,呵呵!
不管怎么样,还是要多谢kernelchina的分享。
to ssxiaohe:不好意思,我只是个跑江湖卖把式的,离开R&D设计一些年了,说大话可以,说具体设计说不好,惭愧。
能 “离开R&D一些年…”
—羡慕理客前辈啊…
Well done.
One more thing to make optimization complete. One has to know cache coherence protocol to do multi-core performance tuning.
In a word, avoiding cache false sharing is the key to improving multi-core performance. If you have any doubt, please read the Linux scalability paper published in OSDI’10, which was recommended by Chen HuiLin in this ite.
使用具有上述功能的编译器,十颗星.实现上述功能的编译器,百花奖.
看到后半部分,感觉这些”注意事项”都是上辈子被C++折磨惨了的人总结出来的, 要性能还是用C和汇编吧, 或者有优化强迫症的话, 使用抽象语言或者函数式语言吧, 会好受很多. 使用C++就是把自己的PY扯破了然后研究怎么缝上之后拉着不疼. 我很心疼不慎上了C++贼船的码农同志.
c++没怎么用过,主要用到是c,c++属于刚入门的水平。
作为一线研发人员,惭愧的是这些偏重于细节化的优化技巧感觉派不上用场。看来将来要多投入点精力研究研究,也许会能够事半功倍。
窃以为,架构设计对性能影响才是最重要的,呵呵!
~~~~~~~~~~~~
在转发面层次上,细节有时候也很重要啊,特别是当前多核比较流行,编码上一个小小的冗余/互锁,性能差上二三成很正常。
作为一线研发人员,惭愧的是这些偏重于细节化的优化技巧感觉派不上用场。看来将来要多投入点精力研究研究,也许会能够事半功倍。
窃以为,架构设计对性能影响才是最重要的,呵呵!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
首席批驳过了。架构就是各种积累的综合,哈哈。细节更重要。
呵呵,我承认细节很重要。但是细节的东西至少好改,架构如果设计得不合适那可就痛苦了~ :)
no no no, 当你不知道的时候如何设计架构。当然要靠历史积累。不能把因果颠倒了。
架构就是服务于个体的另外一层,如果没有足够的细节支撑谈何架构。5张饼吃饱愣是说第5张饼有用玄学。毫无意义。
明白,受教了!:)
世界上没有架构;有的是(从细节中的)提炼。不懂细节的人不可能做架构。
例如,哥哥我现在天天写xcode+php+sql。不可能来一个鸟人从来没玩和写过iphone app,与我谈架构(胶片)。。。
鸟人当道,百姓遭殃啊。。。
同意首席的话。做系统之前,先不要太多考虑架构,先做一个可以WORK的东西出来,然后再逐渐改进、提炼和优化,慢慢会发现架构就出来了。刚开始就想那个架构这个架构的,反而跟容易让系统臃肿而偏离方向。
从一开始就设计完美的架构,除非是做过一次或多次之后,重新构造一个新系统,但是就这个系统,也会慢慢变得不可控,不可看,不可测,所以还是一个进化的过程,没有完美的东西。
深有同感,架构是不断演化成的,不可能从开始就设计成的,不断翻新,完善。每次重写架构都会得到一次升华。
虽然架构是不断演进的,但是学习架构设计的一般经验与技巧,从前人那里吸引更多的架构设计经验。从一开设就力争设计一个比较优秀的架构,对于后期的改良和演进,才真是事半功倍。
我的经验是首先模仿实现一个比较好的框架,先把人家的框架理解透了。单看代码是不可能吃透一个的框架的,必须要亲力亲为,模仿源码实现框架,然后在实现的过程中不断总结框架的不足,吸收好的思想,抛弃不好的思想,渐进完善框架,所谓青出于蓝就是于此。我不相信可以从零开始就能实现一个好的框架,站在前人的肩膀上才是正理。
独孤九贱,您也来了,拜读了太多您的大作了,深感您对于内核的理解给予我等菜鸟太多的帮助,敬仰
所有方法都归结为一句话,减少状态的改变,是性能提升的唯一方法.