近两年从同事那里学了不少代码优化方法,在此总结一下。
面向处理器结构的优化可以从以下几个方向入手:缓存命中,指令预测,数据预取,数据对齐,内存拷贝优化,ddr访问延迟,硬件内存管理优化,指令优化,编译器优化等级以及性能描述工具。
缓存未命中是处理器的主要性能瓶颈之一。在FSL的powerpc上,访问一级缓存是3个时钟周期,二级是12个,3级30多个,内存100个以上。一级缓存和内存访问速度差30多倍。我们可以算一下,如果只有一级缓存和内存,100条存取指令,100%命中和95%命中,前者300周期,后者95*3+5*100=785周期,差了1.6倍。这个结果的前提是powerpc上每个核心只有1个存取单元,使得多发射也无法让存取指令更快完成。当然,如果未命中的指令分布的好,当中穿插了很多别的非存取指令那就可以利用乱序多做些事情,提高效率。
怎么用代码提高缓存命中率?我们可以用指令预测和数据预取。
指令预测很常见,处理器预测将要执行的一个分支,把后续指令取出来先执行。等真正确定判断条件的时候,如果预测对了,提交结果,如果不对,丢掉预先执行的结果,重新抓取指令。此时,结果还是正确的,但是性能会损失。
有一个常用的指令预测机制叫btb(branch target buffer),大致方法是,对于跳转指令,把它最近几次的跳转结果记录下来,作为下一次此处程序分支预测的依据。举个例子,for循环1000次,从第二次开始到999次,每次都预取前一次的跳转地址,那么预测准确率接近99.9%。这是好的情况。不好的情况,在for循环里面,有个if(a[i])。假设这个a[i]是个0,1,0,1序列,这样每次if的预测都会错误,预取效率就很低了。改进方法是,把if拆开成两个,一个专门判断奇数次a[i],一个判断偶数次,整体循环次数减少一半,每次循环的判断增加一倍,这样每次都是正确的。如果这个序列的数字预先不可见,只能知道0多或者1多,那么可以用c语言里面的LIKELY/UNLIKELY修饰判断条件,也能提高准确率。需要注意的是,btb表项是会用完的,也就是说,如果程序太久没有走到上次的记录点,那么记录就会被清掉,下次再跑到这就得重新记录了。分支预测有个有趣的效应,如果一段代码处于某个永远不被触发的判断分支中,它仍然可能影响处理器的分支预测,从而影响总体性能。如果你删掉它,说不定会发现程序奇迹般的更快了
数据预取,和指令预测类似,也是处理器把可能会用到的数据先拿到缓存,之后就不必去读内存了。它又分为软件预取和硬件预取两种,硬件的是处理器自己有个算法去预测抓哪里的数据,比如在访问同一类型数据结构的某个元素,处理器会自动预取下一个偏移的数据。当然,具体算法不会这么简单。软件预取就是用编译器的预编译宏修饰某个将要用到的变量,生成相应指令,手工去内存抓某个程序员认为快要用到的数据。为什么要提前?假设抓了之后,在真正用到数据前,有100条指令,就可以先执行那些指令,同时数据取到了缓存,省了不少时间。
需要注意的是,如果不是计算密集型的代码,不会跑了100个周期才有下一条存取指令。更有可能10条指令就有一次访存。如果全都未命中,那么这个预取效果就会打不少折扣。并且,同时不宜预取过多数据,因为取进来的是一个缓存行,如果取得过多,会把本来有用的局部数据替换出去。按照经验同时一般不要超过4条预取。此外,预取指令本身也要占用指令周期,过多的话,会增加每次循环执行时间。要知道有时候1%的时间都是要省的。
在访问指令或者数据的时候,有一个非常重要的事项,就是对齐。四字节对齐还不够,最好是缓存行对齐,一般是在做内存拷贝,DMA或者数据结构赋值的时候用到。处理器在读取数据结构时,是以行为单位的,长度可以是32字节或更大。如果数据结构能够调整为缓存行对齐,那么就可以用最少的次数读取。在DMA的时候一般都以缓存行为单位。如果不对齐,就会多出一些传输,甚至出错。还有,在SoC系统上,对有些设备模块进行DMA时,如果不是缓存行对齐,那么可能每32字节都会被拆成2段分别做DMA,这个效率就要差了1倍了。
还有一种需要对齐情况是数据结构赋值。假设有个32字节的数据结构,里面全是4字节元素。正常初始化清零需要32/4=8次赋值。而有一些指令,可以直接把缓存行置全0或1。这样时间就变成1/8了。更重要的是,写缓存未命中实际上是需要先从内存读取数据到缓存,然后再写入。这就是说写的未命中和读未命中需要一样的时间。而用了这个指令,可以让存指令不再去读内存,直接把全0/1写入缓存。这在逻辑上是没问题的,因为要写入的数据(全0/1)已经明确,不需要去读内存。以后如果这行被替换出去,那么数据就写回到内存。当然,这个指令的限制也很大,必须全缓存行替换,没法单个字节修改。这个过程其实就是优化后的memset()函数。如果调整下你的大数据结构,把同一时期需要清掉的元素都放一起,再用优化的memset(),效率会高很多。同理,在memcpy()函数里面,由于存在读取源地址和写入目的地址,按上文所述,可能有两个未命中,需要访存两次。现在我们可以先写入一个缓存行(没有写未命中),然后再读源地址,写入目的地址,就变成了总共1个访存操作。至于写回数据那是处理器以后自己去做的事情,不用管。
标准的libc库里面的内存操作函数都可以用类似方法优化,而不仅仅是四字节对齐。不过需要注意的是,如果给出的源和目的地址不是缓存行对齐的,那么开头和结尾的数据需要额外处理,不然整个行被替换了了,会影响到别的数据。此外,可以把预取也结合起来,把要用的头尾东西先拿出来,再作一堆判断逻辑,这样又可以提高效率。不过如果先处理尾巴,那么当内存重叠时,会发生源地址内容被改写,也需要注意。如果一个项目的程序员约定下,都用缓存行对齐,那么还能提高C库的效率。
如果确定某些缓存行将来不会被用,可以用指令标记为无效,下次它们就会被优先替换,给别人留地。不过必须是整行替换。
再说说ddr访问优化。通常软件工程师认为内存是一个所有地址访问时间相等的设备,是这样的么?这要看情况。我们买内存的时候,有3个性能参数,比如10-10-10。这个表示访问一个地址所需要的三个操作时间,行选通,数据延迟还有预充电。前两个好理解,第三个的意思是,我这个页或者单元下一次访问不用了,必须关闭,保持电容电压,否则再次使用这页数据就丢失了。ddr地址有三个部分组成,列,行,页。根据这个原理,如果连续的访问都是在同行同页,每一个只需要10单位时间;不同行同页,20单位;同行不同页,30单位。所以我们得到什么结论?相邻数据结构要放在一个页,并且绝对避免出现同行不同页。这个怎么算?每个处理器都有手册,去查查物理内存地址到内存管脚的映射,推导一下就行。此外,ddr还有突发模式,ddr3为例,64位带宽的话,可以一个命令跟着8次读,可以一下填满一行64字节的缓存行。而极端情况(同页访问)平均字节访问时间只有10/64,跟最差情况,30/64字节差了3倍。当然,内存里面的技巧还很多,比如故意哈希化地址来防止最差情况访问,两个内存控制器同时开工,并且地址交织来形成流水访问,等等,都是优化的方法。不过通常我们跑的程序由于调度程序的存在,地址比较随机不需要这么优化,优化有时候反而有负面效应。另外提一句,如果所有数据只用一次,那么瓶颈就变成了访存带宽,而不是缓存。所以显卡不强调缓存大小。当然他也有寄存器文件,类似缓存,只不过没那么大。
每个现代处理器都有硬件内存管理单元,说穿了就两个作用,提供虚地址到时地址映射和实地址到外围模块的映射。不用管它每个字段的定义有多么复杂,只要关心给出的虚地址最终变成什么实地址就行。在此我想说,powerpc的内存管理模块设计的真的是很简洁明了,相比之下x86的实在是太罗嗦了,那么多模式需要兼容。当然那也是没办法,通讯领域的处理器就不需要太多兼容性。通常我们能用到的内存管理优化是定义一个大的硬件页表,把所有需要频繁使用的地址都包含进去,这样就不会有页缺失,省了页缺失异常调用和查页表的时间。在特定场合可以提高不少效率。
这里描述下最慢的内存访问:L1/2/3缓存未命中->硬件页表未命中->缺页异常代码不在缓存->读取代码->软件页表不在缓存->读取软件页表->最终读取。同时,如果每一步里面访问的数据是多核一致的,每次前端总线还要花十几个周期通知每个核的缓存,看看是不是有脏数据。这样一圈下来,几千个时钟周期是需要的。如果频繁出现最慢的内存访问,前面的优化是非常有用的,省了几十倍的时间。具体的映射方法需要看处理器手册,就不多说了。
指令优化,这个就多了,每个处理器都有一大堆。常见的有单指令多数据流,特定的运算指令化,分支指令间化,等等,需要看每家处理器的手册,很详细。我这有个数据,快速傅立叶变化,在powerpc上如果使用软浮点,性能是1,那么用了自带的矢量运算协处理器(运算能力不强,是浮点器件的低成本替换模块)后,gcc自动编译,性能提高5倍。然后再手工写汇编优化函数库,大量使用矢量指令,又提高了14倍。70倍的提升足以显示纯指令优化的重要性。
GCC的优化等级有三四个,一般使用O2是一个较好的平衡。O3的话可能会打乱程序原有的顺序,调试的时候很麻烦。可以看下GCC的帮助,里面会对每一项优化作出解释,这里就不多说了。编译的时候,可以都试试看,可能会有百分之几的差别。
最后是性能描述工具。Linux下,用的最多的应该是KProfile/OProfile。它的原理是在固定时间打个点,看下程序跑到哪了,足够长时间后告诉你统计结果。由此可以知道程序里那些函数是热点,占用了多少比例的执行时间,还能知道具体代码的IPC是多少。IPC的意思是每周期多少条指令。在双发射的powerpc上,理论上最多是2,实际上整体能达到1.1就很好了。太低的话需要找具体原因。而这点,靠Profile就不行了,它没法精确统计缓存命中,指令周期数,分支预测命中率等等,并且精度不高,有时会产生误导。这时候就需要使用处理器自带的性能统计寄存器了。处理器手册会详细描述用法。有了这些数据,再不断改进,比较结果,最终达到想要的效果。
很重要的一点,我们不能依靠工具来作为唯一的判别手段。很多时候,需要在更高一个或者几个层次上优化。举个例子,辛辛苦苦优化某个算法,使得处理器的到最大利用,提高了20%性能,结果发现算法本身复杂度太高了,改进下算法,可能是几倍的提升。还有,在优化之前,自己首先要对数据流要有清楚的认识,然后再用工具来印证这个认识。就像设计前端数字模块,首先要在心里有大致模型,再去用描述语言实现,而不是写完代码综合下看看结果。
原文:http://blog.csdn.net/jdygrdzh/article/details/32407707