强者恒强：x86高性能编程笺注之循环(上)

强者恒强 x86 高性能编程笺注之循环 上 读者须知 强者恒强 x86 高性能编程笺注 该系列文章将分享 x86 高性能 开发方面的实践和思考 主要内容目录如下 欢迎各位业界同仁与我们讨论交 流相关话题 1 什么是性能 2 流水线 3 分支 4 循环 5 缓存 6 预取 7 大页 8 锁 9 RCU 10 无锁 11 SIMD 指令 循环一般是程序中计算最密集的代码段 也最容易成为性能的热点 在熟悉了 CPU 的流水线之后 有很多很多技巧可以提升执行循环的效率 但程序性能的 优化如果仅仅是 堆砌 技巧 那么想必也不会吸引如你这般聪慧的读者 就 如同 BUG 总是会出现在自己认为一定没问题的地方一样 一些被奉为 万金 油 式的优化手段也可能正是性能下降的本因 对于自己写出来的代码 无论 是优化性能还是单纯的 DEBUG 都像是在看一场情节跌宕的犯罪电影 在 这里面 你既是侦探 同时也是凶手 很少有人会愿意将自己 绳之以法 因此也只有很少的人能够看到片尾的彩蛋 循环之所以容易成为热点 完全出于它的天然属性 调用的次数足够多 与 其外围的代码相比 可能是几个数量级的差距 再加上数据依赖 内部分支等 等因素 使得循环往往成为 Profiling 时重点关怀的对象 但循环也因为 重复 再重复 这一天然属性 提供了一些可资利用的优势 循环内部的代码 因其 重复调用 使得 CPU 的指令缓存可以保持一个很高的命中率 批量的重复操作 可以引入一些并行操作机制等等 但 CPU 的流水线是否可以满效率的运行 还 是取决于我们之前介绍的很多其他因素 另外关于循环的性能优化 最有意思的一点可能就是 完全按照理论的指导 优化 了代码 实际的性能反而有所下降 无论是 gcc 还是 clang 在其数 十载的发展过程中 都积累了深厚的循环优化处理方法 如果仅仅将编译器认 为是缺乏头脑的 执行者 那么在性能优化的路上 将会失去一个重要的伙 伴 为了说明如何去 配合 而非 驾驭 编译器 本文也将在介绍理论的基 础上 更加侧重实践的经验 以测试例的方式摸清编译器的脾气 数据依赖 a 100 b 200 单纯对两个变量写入数据 并不产生数据依赖 无论是这两条语句执行的先后 顺序如何 或并行执行 都不影响程序的最终结果 数据依赖往往产生于对同 一个变量的读写之间 a 100 b a 100 以上两组代码虽然最终结果完全相同 但在计算机看来却是完全不同的两行代 码 前一组可以以任意顺序执行 而后面一组代码却只能先给 a 赋值 再执行 对 b 的赋值 使得这两个语句之间产生依赖 一般来说 数据依赖存在三种形 式 12 read after write 写入的变量后续将被读取 13 write after read 读取的变量后续将被写入 14 write after write 写入的变量后续被重新写入 以上三种依赖类型又可以分别叫做 flow dependence antidependence 和 output dependence 举一个简单的例子 for i 0 i 4 i a i b i c i c i 1 a i 假设 a b c 三个数组长度都为 4 在每一次的循环中 a 数组中的某些元素 将首先被写入赋值 之后将读取新值计算 c 数组中的单独元素虽然在一次循 环之中没有被同时读写 但在不同的循环迭代之间存在对同一个元素的读写操 作 那么对于 a 数组的 0 3 号元素 都存在 read after write 依赖 对于 c 数组的 1 3 号元素 都存在 write after read 依赖 而对 a 和 c 的重新赋值 又与它们的初始化指令之间 存在 write after write 依赖 如上说述 在循环的每次迭代之间 也会存在依赖关系 如对数组 a 的操作 其 read after write flow dependence 依赖关系都只存在于同一次迭代内 则称这种依赖为 loop independent 而对于数组 c 其依赖关系存在于循 环的不同次迭代之间 则称这种依赖为 loop carried 数据依赖对循环最大的影响 是它限定了执行的顺序 从之前关于 CPU 流水线 的介绍中可以知道 在微指令的执行层面 CPU 会尽力让乱序执行核心并行执 行指令 这也是影响 IPC 的一个重要因素 而数据间的相互依赖会破坏这种并 行关系 进而拉低程序的性能 数据依赖以及它们与循环迭代之间的关系可以 帮助我们分析循环的优化方式 尽最大可能地减少数据依赖 增加程序的并行 化程度是我们追求的整体目标之一 Loop Distribution and Fusion 从这一节开始会陆续介绍几种常见的循环优化技巧 但如前所述 理论与实践 相结合才能真正发挥人的主观能动性 并激活人与客观世界的奖励反馈机制 所以针对每一种技巧 除了讲解原理和举个栗子之外 还会给出真实的编译结 果以及性能测试结果以便读者揣摩玩味 Theory Loop distribution 也叫 fission 是指将原本的循环体拆分 分别放入循环控 制逻辑之中 如上面所举的例子可以写为 for i 0 i 4 i a i b i for i 0 i 4 i c i c i 1 a i 拆分成多个循环体 确实会增加循环的 overhead 多出额外的循环计数操作 和分支判断 但也会有多种 收益 比如可以隔离数据依赖并为并行操作和 循环向量化做准备 减少每次循环中的数据引用以提高缓存命中 或者针对 x86 处理器 Loop distribution 可以隔离循环体中的数据流 并为硬件预取 hardware prefetching 服务 当有多个 CPU 核的时候 也可以增加程序的并 行性 下面通过另外一个例子来测试说明 Test Case 有如下循环代码 voidfoo void int i j for i 1 i N i for j 1 j N j S1 a i j b i j c i j S2 d i j a i 1 j 1 2 分析可知 S1 和 S2 之间存在 loop carried 依赖 但因为与程序执行顺序相同 的依赖关系 使得程序完全可以在执行内层循环 j 循环 S2 之前执行 S1 中的 计算 据此可以将循环拆分成如下形式 voidfoo void int i j for i 1 i N i for j 1 j N j S1 a i j b i j c i j for j 1 j N j S2 d i j a i 1 j 1 2 这里就完成了一次对原始循环的拆分 在新的形式中 两个内层循环 j 循环 可以分别作向量化处理 以提升循环效率 在此之后我们又可以注意到 S1 和 S2 之间仍在外层循环 i 循环 中存在依赖 同样的 我们也可以采用刚才的 方式对循环再做一次变化 voidfoo void int i j for i 1 i N i for j 1 j N j a i j b i j c i j for i 1 i N i for j 1 j N j d i j a i 1 j 1 2 如此处理之后 两个循环体就成为了完全独立的可以并行操作的循环 但是否 这样就一定会带来性能的提升 答案是不一定 可以明显地看出 虽然循环体 不再因为数据依赖而必须顺序执行 但也引入了大量的 overhead 收益是否 一定大于损失 存在很多影响的因素 性能优化很多时候需要掌握平衡 一种 优化方式是否真正有效 首先需要抓住主要矛盾 同时也需要实际的实验来最 终保证 请读者采用不同的 gcc 优化参数来实际测试性能的变化 同时也应注意到 如 果在原始代码中 将 S1 和 S2 交换一下位置 我们是不能直接做这种拆分的 虽然 Loop distribution 并不一定可以带来性能的提升 但这也用反例的形式 说明了另外一种优化技巧 Loop fusion 如同乘法和除法一样 Loop fusion 和 Loop distribution 也是一对逆运算 Loop fusion 是将拆分的循环 结构合并到一起 如果将上面的例子中 loop distribution 拆分出来的代码看 作是原始代码 那么最初的原始代码就是 Loop fusion 处理过后的代码 Loop fusion 的优劣也正好和 Loop distribution 相反 它减少了循环的 overhead 但也可能会引入不必要的依赖 但