强者恒强：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 的赋值，使得这两个语句之间产生依赖。一般来说，数据依赖存在三种形式：

1. read-after-write：写入的变量后续将被读取
2. write-after-read：读取的变量后续将被写入
3. 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

有如下循环代码：

void
foo(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 中的计算。据此可以将循环拆分成如下形式：

void
foo(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 循环）中存在依赖。同样的，我们也可以采用刚才的方式对循环再做一次变化：

void
foo(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。收益是否一定大于损失，存在很多影响的因素。性能优化很多时候需要掌握平衡，一种优化方式是否真正有效，首先需要抓住主要矛盾，同时也需要实际的实验来最终保证。(测试用的代码已经上传至： https://github.com/PanZhangg/x86perf/blob/master/loop.c ) 请读者采用不同的 gcc 优化参数来实际测试性能的变化。同时也应注意到，如果在原始代码中，将 S1 和 S2 交换一下位置，我们是不能直接做这种拆分的。

虽然 Loop distribution 并不一定可以带来性能的提升，但这也用反例的形式说明了另外一种优化技巧——Loop fusion。如同乘法和除法一样，Loop fusion 和 Loop distribution 也是一对逆运算。Loop fusion 是将拆分的循环结构合并到一起，如果将上面的例子中，loop distribution 拆分出来的代码看作是原始代码，那么最初的原始代码就是 Loop fusion 处理过后的代码。

Loop fusion 的优劣也正好和 Loop distribution 相反。它减少了循环的 overhead，但也可能会引入不必要的依赖。但如果可以以提高数据本地化程度等方式提升整体性能，也不失为一种有效的选择。

对于循环的优化，还有很多种方式，例如 loop unrolling, loop interchange 等等，这些技巧就留待下一期再行介绍。

作者简介

张攀，云杉网络工程师，专注于 x86 网络软件的开发与性能优化，深度参与 ONF/OPNFV/ONOS 等组织及社区，曾任 ONF 测试工作组副主席。

感谢木环对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。