第 5 章 优化程序性能
# 第 5 章 优化程序性能
编写高效程序的要点
- 必须选择一组适当的算法和数据结构
- 必须编写出编译器能够有效优化以转换成高效可执行代码的源代码
- 针对运算量特别大的计数, 将一个任务分成多个部分
- 以让这些部分可以在多核和多处理器的某种组合上并行的计算
程序优化的步骤
- 消除不必要的工作
- 消除不必要的函数调用、条件测试和内存引用
- 利用处理器提供的指令级并行(instruction-level parallelism) 能力, 同时执行多条指令
- 前提是理解处理器的运作特性
# 5.1 优化编译器的能力和局限性
编译器必须很小心地对程序只使用安全的优化
内存别名使用 (memory aliasing)
- 指的是两个指针可能指向同一个内存的情况
- 这种情况会限制编译器可能的优化策略
函数的调用可能存在副作用
- 为了安全, 编译器会保持所有的函数调用不变
- 内联函数替换(inline substitution)
- 其会将函数的调用替换为函数体
- 如此即减少了函数调用的开销, 也允许对展开的代码做进一步的优化
gcc
的最近版本在使用命令行选项-finline
或者使用高于-O1
的优化等级时- 会尝试在单个文件中定义的函数的内联
- 其会将函数的调用替换为函数体
# 5.2 表示程序性能
每元素周期数(CPE)
- Cycles Per Element
- 教材中引入的表示程序性能的方法
- 元素是指数组元素
# 5.3 程序示例
示例程序: 计算数组中所有元素的累加或累积
- 边界检查降低了程序出错的机会, 但是它也会减缓程序的执行
- 确定变换组合的最好方法是实验加上分析
- 反复尝试不同的方法, 进行测量
- 并检查汇编代码表示以确定底层的性能瓶颈
# 5.4 消除循环的低效率
代码移动(code motion)
- 识别要执行多次但是计算结果不会改变的计算
- 并将这些计算移到到代码前面不会被多次求值的部分
- 优化编译器会尝试进行代码移动
- 但是它们不能可靠的发现一个函数是否有副作用, 因而假设函数有副作用
- 为了改进代码, 程序员必须经常帮助编译器显式的完成代码移动
# 5.5 减少过程调用
牺牲程序的模块性来获得高性能
- 不使用函数调用来获取每个向量元素, 而是直接访问数组
# 5.6 消除不必要的内存引用
用一个临时变量储存累加和, 最后再赋值给 `*dest`
- 编译器不能判断函数会在什么情况下被调用, 以及程序员的本意
- 所以需要人为的创建临时变量来避免不断地读和写内存
# 5.7 理解现代处理器
考虑利用处理器微体系结构的优化
- 处理器的微体系结构即是处理器用来执行指令的底层系统设计
- 多条指令可以并行地执行, 同时又呈现出一种简单的顺序执行指令的表象
- 这种现象即为指令级并行
延迟界限与吞吐量界限
- 当一系列操作必须按照严格顺序执行时, 就会遇到延迟界限(latency bound)
- 当代码中的数据相关限制了处理器利用指令级并行的能力时, 延迟界限能限制程序性能
- 吞吐量界限(throughput bound)
- 刻画了处理器功能单元的原始计算能力
- 这个界限是程序性能的终级限制
# 5.7.1 整体操作
超标量乱序处理器
- 超标量(superscalar)
- 可以在每个时钟周期执行多个操作
- 乱序(out-of-order)
- 指令执行的顺序不一定要与它们在机器级程序中的顺序一致
乱序处理器的框图
# 5.7.2 功能单元的性能
算术运算的性能
- 延迟(latency)
- 表示完成运算所需要的总时间
- 发射时间(issue time)
- 表示两个连续的同类型运算之间需要的最小时钟周期数
- 发射时间为 1 的单元被称为完全流水线化(fully pipelined)的
- 容量(capacity)
- 表示能够执行该运算的功能单元的数量
- 吞吐量
- 针对特定的操作定义
- 对于容量为
, 发射时间为 的操作来说 - 处理器可能获得的吞吐量为每时钟周期
个操作
- 处理器可能获得的吞吐量为每时钟周期
需要注意的是加载单元的数量也会限制吞吐量
- 设
为加载单元的数量, 则吞吐量为
- 设
参考机算术运算的性能
延迟界限给出了任何必须按照严格顺序完成运算的函数所需要的最小 CPE 值
吞吐量界限给出了 CPU 的最小界限
# 5.7.3 处理器操作的抽象模型
程序的数据流(data-flow)表示
- 一种图形化的表示方法, 展示了不同操作之间的数据相关是如何限制它们的执行顺序的
- 这些限制会形成图中的关键路径(critical path)
- 这是执行一种机器指令所需时钟周期数的一个下界
循环寄存器
- 对于循环来说, 即作为源值, 又作为目的的寄存器称为循环寄存器
- 循环寄存器之间的操作链决定了限制性能的数据相关
可以重新调整操作链的结构来增加指令的并行性
确定关键路径时, 主要以涉及到循环寄存器的运算为主
- 其它运算可以并发执行
# 5.8 循环展开
循环展开是一种程序变换, 其通过增加每次迭代计算的元素的数量, 减少循环的迭代次数
- 其能从两个方面改善程序的性能
- 减少了不直接有助于程序结果的操作的数量
- 如循环索引计算和条件分支
- 它提供了一些方法, 可以进一步的变化代码, 减少整个计算中关键路径上的操作数量
- 减少了不直接有助于程序结果的操作的数量
对一个循环按任意因子
k
进行展开的处理方法- 将循环上限设为
n-k+1
- 在循环内对元素
i
到i+k-1
进行循环操作- 每次迭代, 循环索引
i
加k
- 每次迭代, 循环索引
- 采用第二个循环, 以每次处理一个元素的方式, 处理向量的最后几个元素
- 将循环上限设为
用
-o3
或更高的等级调用gcc
时, 它就会执行循环展开
# 5.9 提高并行性
硬件具有以更高速率执行乘法和加法的潜力, 但是代码不能利用这种能力
# 5.9.1 多个累积变量
分割运算
- 对于一个可结合和可变换的合并运算来说
- 比如整数加法或乘法
- 可以通过将一组合并运算分割成两个或更多的部分,并在最后合并结果来提高性能
- 与循环展开结合在一起,可以消除部分数据相关,充分利用处理器的并行能力
- 只有保持能够执行该操作的所有功能的流水线都是满的,程序才能达到这个操作的吞吐量界限
- 对于延迟为
, 容量为 的操作而言, 要求循环展开因子
- 对于延迟为
- 只有保持能够执行该操作的所有功能的流水线都是满的,程序才能达到这个操作的吞吐量界限
浮点加法和乘法
- 浮点加法和乘法是不可结合的
- 大多数物理现象是连续的, 所以数值数据也趋向于相当平滑, 分割运算不会出什么问题
- 对于大多数应用程序来说, 使性能翻倍, 要比冒对奇怪的数据模式产生不同的结果的风险更重要
# 5.9.2 重新结合变换
变换运算顺序
- 核心是通过重新组合变换, 减少关键路径上的运算数量, 以提升并行性
- 示例
acc = (acc OP data[i]) OP data[i+1]
变换为acc = acc OP (data[i] OP data[i+1]
- 如此第二个
OP
运算便不在关键路径上, 可以并发的执行
提示
- 大多数编译器不会尝试对浮点运算做重新组合
- 当前的 GCC 版本会对整数运算执行重新结合, 但不是总有好的结果
#
SIMD 用向量指令达到更高的并行度
- SIMD(Single-Instruction, Multiple-Data) 单指令多数据
- 一条指令能够产生对多个数据值的计算
- AVX 向量寄存器长为 32 字节, 可以存放 8 个 32 位数和 4 个 64 位数
- AVX 指令可以对这些寄存器进行向量操作
- 比如并行执行 8 组数值或 4 组数值的加法或乘法
- AVX 指令可以对这些寄存器进行向量操作
# 5.10 优化合并代码的结果小结
书上的例子说明现代处理器具有相当的计算能力, 但是可能需要按非常程式化的方式编写程序才能将这些能力诱发出来
# 5.11 一些限制因素
# 5.11.1 寄存器溢出
笔记
- 如果循环展开的
k
值过大, 则并行度p
会超过可用的寄存器数量, 如此编译器就会诉诸溢出(spilling) - 溢出后一些临时变量(一般为累加值)会存放到内存中
- 通常是在运行时堆栈上分配空间
- 如此会导致较多的内存读写操作, 其性能可能反而会下降
# 5.11.2 分支预测和预测错误惩罚
书写适合用条件传送实现的代码
- 分支预测只对有规律的模式可行
- 对于本质上无法预测的情况
- 如果编译器能产生使用条件数据传送而不是使用条件控制转移的代码, 则可以极大的提升程序的性能
- GCC 能够为以一种更"功能性的"风格书写的代码产生条件传送
如在程序中使用条件操作符
long min = a[i] < b[i] ? a[i] : b[i]; long max = a[i] < b[i] ? b[i] : a[i];
1
2
# 5.12 理解内存性能
# 5.12.1 加载的性能
笔记
- 对于参考机的两个加载单元而言, 其每个时钟周期只能启动一条加载操作
- 所以各个操作的 CPE 不可能小于 0.5
- SIMD 操作可以突破这个限制
- 所以各个操作的 CPE 不可能小于 0.5
# 5.12.2 存储的性能
存储操作
- 存储操作并不影响任何寄存器
- 因此一系列的储存操作不会产生数据相关
- 只有加载操作会受存储操作结果的影响
存储缓冲区
存储缓冲区示意图
- 注意图中数据和地址箭头的方向
- 存储缓冲区中包含已经被发射到存储单元而又还没有完成存储操作的地址和数据
- 这里的完成包括更新数据高速缓存
- 当一个加载操作发生时, 其必须检查存储缓冲区的条目, 看有没有地址相匹配
- 如果有地址相匹配, 其就取出相应的数据条目作为加载操作的结果
对于内存操作, 只有加载地址和存储地址被计算出来以后, 处理器才能确定哪些指令会影响其他的指令
# 5.13 应用: 性能提高技术
基本策略
- 高级设计
- 为遇到的问题选择适当的算法和数据结构
- 基本编码原则
- 消除连续的函数调用
- 在可能时, 将计算移至循环外
- 考虑有选择地妥协程序的模块性以获得更大的效率
- 消除不必要的内存引用
- 引入临时变量来保存中间结果
- 只有在最后的值计算出来时, 才将结果存放到数组或全局变量中
- 低级优化
- 循环展开, 降低开销, 并且使进一步的优化成为可能
- 使用诸如多个累积变量和重新结合等技术, 找到方法提高指令级并行
- 用功能性的风格重写条件操作, 使得编译器采用条件数据传送, 而不是条件跳转指令
# 5.14 确认的消除性能瓶颈
# 5.14.1 程序剖析
笔记
- UNIX 系统中有 GPROF 可以用于性能剖析
# 5.14.2 使用剖析程序来指导优化
编辑 (opens new window)