软件算法优化方法.docVIP

软件算法优化方法（阿华 2011-11-09） 很久没有做过算法了，以后机会可能也不多了，难得一身好本领...噔噔噔...o(╯□╰)o。这里和大家分享一篇我N久前写的总结。方法、工具是会过时的，但是思想却永远不会。希望能给那些仍然奋战在算法优化前线的兄弟们一点小小的启发。 小弟之前是做DSP、ARM算法的，如果有看不懂的术语请自行查阅一下。谢谢。 由于篇幅有限，本文以思想、方法为主，缺少举例，请多多见谅。呵呵。 资质有限，难免有所疏忽，希望大虾们多多指点，欢迎交流。O(∩_∩)O~ —— 阿华 2011-11-09 作者：阿华 QQ：4749920 Email：4749920@ 转载请附带原文链接。 算法优化的思想 尽可能不做、少做不必要的操作； 尽可能使用高效的运算方法取代低效的运算方法； 尽可能将CPU的所有运算器并行起来、寄存器饱和运作； 尽可能将CPU的高效处理单元集中处理性能比重较大的算法部分； 尽可能减少不必要的内存吐出、cache miss；（ARM系统尤为重要） 算法优化的前提 通过Profile工具、打点记时，获知算法中占用性能比重较大、调用次数较多的部分，并对其重点优化； 对算法复杂度进行分析（基于考虑内存吞吐、算术运算），按照CPU性能预估运算时间，并与实际统计运算时间进行比较，分析实际运算时间是否合理，如果不合理，需要再细化分析，并获知性能瓶颈出在哪些环节，可能包括内存吞吐、运算器、寄存器、cache miss等，很多时候需要进行汇编代码级的分析； 算法优化的方法 提高并行度 使用DMA以PingPong方式搬运数据，与CPU处理平行起来，尤其是视频解码显示的情况； 减少相邻代码行数据之间的相关性、依赖性，这样编译器能更容易进行优化； 对于核心循环代码，使用软件流水线优化，将执行逻辑不相关的代码行、指令操作相互并行起来；（DSP可以通过编译器来自动排流水线，ARM基本就只能靠自己写汇编代码了） 使用位宽高的指令（SIMD：Single Instruction Multiple Data）代替位宽低的指令，同时处理多个位宽低的数据运算； 使用高效的运算方法 将核心的运算放在片内内存、cache中进行计算，降低CPU访问片外内存的几率； 尽可能合理的分配寄存器，将经常反复使用的结果保存在寄存器，对于不经常使用的结果保存在栈或则堆中；（注意：栈的访问效率往往高于堆） 使用带复合功能的汇编指令，如乘法累加、相加饱和等； 使用字节对齐的内存访问方式，使用4字节对齐、8字节对齐的内存访问方式，效率会高很多； 使用算术运算（移位、加、减）代替乘法、除法运算； 空间换时间 （内存换性能） 将经常重复运算的结果进行制表，使用查表代替运算；（注意：表不能太大） 将频繁执行、性能比重较大的核心逻辑提取出来，走单独、简单的流程，避免过多执行无效的判断和跳转；（缺点：代码量会增加） 效果换时间 （质量换性能） 当效果、质量允许下降的情况下，适当省略对效果、质量影响不明显的运算部分，如视频技术中的运动估计、去噪滤波、B帧解码、Yuv2Rgb的小数处理； 优化算法架构、流程 避免重复运算、无效运算、意义不大的运算； 重复使用可以利用的中间运算结果、内存读写结果； 调整函数流程，缩短中间变量的生命周期，避免中间变量过多，导致寄存器饱和，引起不必须要的栈操作；（寄存器饱和后，中间变量会缓存在栈中，一写一读引起两次额外的内存操作） 编译方法 使用-o3、-o2；（注意：往往有时使用-o2的性能比-o3还高） 为核心循环提供尽可能多的编译信息，如循环次数、内存对齐等，方便编译器进行优化； 尽可能使用const、restricted指针，方便编译器进行优化； 调整函数代码、表格数据在链接时候的code section、data section位置，将经常互相访问的代码、数据放得相近一些，避免cache miss； 使用feedback编译方法，统计实际运行情况，然后把实际运行情况交给编译器，再对代码进行二次优化编译；（这种牛X的编译器我也只是在Tilera上见到过） 使用性能更佳的编译器； 针对平台定制 使用CPU提供的协处理器接口、硬件加速接口、硬件编解码接口； 总结 算法优化必须要有依、有据、有重点； 要充分了解你的CPU有哪些运算器、寄存器、指令、cache，编译器有哪些选项，平台有哪些接口，那样你才会清楚有多少优化空间； 在优化初期，很容易通过代码行、指令级的优化获得明显的优化效果，但是不要沾沾自喜，因为很快会到了天花板，这个时候你要好好耐心的分析瓶颈，甚至要看看汇编代码，不要怕，没你想象中那么难！ 代码行的优化始终会遇到天花板，天花板是啥？天花板就是你的算法架构！到了必要的时候，要敢于真刀真枪的的给你的架构做手术！ 作者：阿华