- a = 100;
- b = 200;
- a = 100;
- b = a + 100;
以上两组代码虽然最终结果完全相同,但在计算机看来却是完全不同的两行代码。前一组可以以任意顺序执行;而后面一组代码却只能先给 a 赋值,再执行对 b 的赋值,使得这两个语句之间产生依赖。一般来说,数据依赖存在三种形式:
以上三种依赖类型又可以分别叫做 "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(也叫 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 核的时候,也可以增加程序的并行性。下面通过另外一个例子来测试说明。
有如下循环代码:
- 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 等等,这些技巧就留待下一期再行介绍。
来源: http://www.infoq.com/cn/articles/x86-high-performance-programming-annotations-part01