高效代码原理与实践.ppt

高效代码原理与实践 目录 高效源自设计优化始于剖析编译器优化的两个障碍存储器循环查表并行与SIMD 高效源自设计 高效的误区影响效率的因素算法的选择相关与重复存储器的分配与使用数据类型的选择运算技巧 高效的误区 终于可以跑了 却发现 输在设计 高效的误区 某次 给机顶盒频道切换功能中加入码流搜索 但是切换频道的时候图像经常是花的 后来发现是丢包造成图像花块 但是 码流搜索和收包有什么关系 码流搜索函数效率低 导致CPU占有率瞬时升高 收包线程受到影响 发生丢包 漫不经心地编码 高效的误区 优化某解码器 使用开源代码 解标清图像 初始CPU占有率在1000 以上 3个人优化3个月 天天加班 达到标清实时 自己开发同等难度的另一解码器 开发阶段12个人月 2个人优化2周 不加班 达到标清实时 仅依靠优化来达到高效 高效来自优秀的设计和编码 高效的误区 向某厂商洽购某模块 做评估时发现效率很低 只有每秒5帧 且占有率已经达到80 以上 结果 抛弃 自己开发 历时一个人月 未做任何优化 开发后测试 每秒25帧 占有率40 效率就是金钱 高效的误区 效率无所谓 功能实现就好X漫不经心地设计编码 再优化X精心设计 精心编码 再做适当优化 好慢啊 愁死了 高效三阶段 设计 确定功能和效率目标 设计算法 缓存编码 选择适当的数据类型 数据存放方式 数据表示方式 循环内要选择适当的变量个数 编码标准 规范优化 确定要优化哪些模块 逐块优化 尽量保持代码的可读性和可维护性 影响效率的因素 算法 存储器 并行 算法的选择 在效果和速度之间取得平衡 算法的选择 去除相关 重复是优良算法的共性 相关与重复 循环中与循环变量无关的代码多次重复计算的公共子式把中间结果保存到内存中 然后再从内存中读取能查表计算的 却一次次重复地算 存储器的分配与使用 大量数据的运算尽量放在片内内存中连续访问内存 不要随机访问缓存中的数据尽量用短的类型 能用单字节表示的 不用双字节尽量减少存储器访问 提倡一次读4个字节 中间结果尽量不要再放到内存中注意数据的对齐 数据类型的选择 缓存中的数据用短类型函数中的变量长度和符号对效率不产生重大影响只用整数 运算技巧 移位代替除法使用位运算只使用整数做运算使用乘法 移位 位运算 不使用除法 模运算局部变量使用32位类型尽量少用if switch等跳转语句 优化始于剖析 问题 某系统中各个模块对时间的占用如下图所示如果要达到T优化前 T优化后 1 1 那么需要优化几个模块 每个模块优化多少 如果T优化前 T优化后为1 5 2 3 4 5呢 优化始于剖析 Amdahl定理 某模块占系统的比例为a 如果优化后该模块的速度提高到原来的k倍 那么整个系统在优化前后的时间比例为多少呢 Told Tnew 1 1 a a k 计算 a 0 1 k 100a 0 8 k 2a 0 01 k 10000系统优化某部件所获得的系统性能的改善程度 取决于该部件被使用的频率 或所占总执行时间的比例 优化始于剖析 结论 系统性能的提高 不但取决于被优化的模块所提高的倍数 也取决于该模块的在系统中所占的比例 所以 当需要极大提高性能时 往往需要对系统的各个模块做广泛的优化 优化始于剖析 Profiling的作用 提供系统中各个模块对CPU资源的占用情况的分析 为优化方案提供决策依据 通常先做Profiling 然后结合Amdahl定理 可以估计出对每个模块需要做多少优化 便于估计最终的优化性能 优化始于剖析 Profiling工具 VC下自带一个ProfilerIntel的工具 VTuneCCS下有自带的Profilergccprofiling 编译器优化的两个障碍 存储器别名函数调用 现在的编译器效率已经很高了 打开优化选项后往往能使效率几倍地提高 要充分使用编译器优化就必须知道什么样的代码能得到充分优化 或者说 什么样的代码得不到充分优化 编译器优化的两个障碍 下面两个函数哪个效率高 两个函数是否等价 编译器优化的两个障碍 在上面的函数中 当xp与yp相等时 称为 指针别名 这种情况下会发生什么 编译器优化的两个障碍 下面两个函数哪个效率高 两个函数是否等价 编译器优化的两个障碍 如果f x 中存在一个全局变量count 并且有语句count 会发生什么 编译器优化的两个障碍 结论 在拿不准的情况下 编译器只能假设指针存在别名 并假设函数调用存在副作用 从而采取保守的优化策略 我们的优化 也经常会从这两个方面着手 编译器优化的两个障碍 使用restrict关键字 说明两指针所指向的数据不存在别名使用const说明某缓存是只读的不使用记忆性变量 存储器 存储器的层次结构Cache友好的代码存储器山局部性 存储器的层次结构 存储器的层次结构 结论 越靠近CPU的存储器 容量越小 速度越快 越远离CPU的存储器 容量越大 但是速度也越慢 Cache友好的代码 Cache的特性 当不命中时 会一次性读取该数据及临近的几个数据到cahe中 Cache友好的代码 for i 0 i N i sum v i Cache友好的代码 for j 0 j N j for i 0 i M i sum v i j 这两段代码哪个效率高 for i 0 i M i for j 0 j N j sum v i j Cache友好的代码 存储器山 局部性 时间局部性 Temporallocality 如果被访问过的存储器地址在较短时间内被再次访问 则程序具有良好的时间局部性 在一定的时间内 重复访问同一个地址的次数越多 时间局部性越好 换句话说 对同一个地址的两次访问间隔时间越短 时间局部性越好 空间局部性 Spatiallocality 如果程序访问某个存储器地址后 又在较短时间内访问临近的存储器地址 则程序具有良好的空间局部性 两次访问的地址越接近 空间局部性越好 局部性 局部性原理如何体现在代码中 减少缓存大小 降低访问步长 使用顺序访问而非随机访问循环中尽量使用较少的变量 同一个变量尽可能地多使用 局部性 局部性的一个应用 使用分块来计算矩阵乘法 详见 深入理解计算机系统 P443 循环 循环中只保留与循环变量相关的运算尽量不要使用break continue if等跳转语句核心循环中变量尽量少 对arm 建议不超过12个建议使用i 不用i 查表 表格较小运算复杂 什么时候使用表格 查表 访问越频繁 该表格所对应的cache会越来越 热 cachemiss的次数越来越少 到最后相当于该表格被直接放到了cache中 此时访问速度就很快了 这也是局部性的体现 当表格在一段时间内频繁使用时 效率会比较高 为什么 并行与SIMD 软件流水DMASIMD 软件流水 软件流水 循环体尽量小不使用break if else等跳转操作 DMA DMA DirectMemoryAccess不占用CPU资源 直接把数据搬到想放的地方去 DMA DMA的典型用法 把片外数据搬到片内做运算 运算完之后再搬到片外 在算法设计阶段就要考虑哪些运算放在片内 如何搬运 SIMD SIMD singleinstructionmultipledata 例子 dotpsu4 d c SIMD 两个像素a b 用一个4字节整数表示 其中 RGB 各用一个字节表示 那么 如果要把a b的对应的R G B 做平均 如何做效率最高 a b a b 0 xFEFEFEFE 1 实际的SIMD是硬件实现的 这个例子只是提示大家注意代码中一次性计算多个数据的可能性 能使用4字节数运算一次 就不要使用单字节数计算四次 总结 精