Chapter 05 Optimization

5.1 优化编译器的能力和局限性

妨碍优化的因素:

内存别名使用:

void fun1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}
void fun2(long *xp, long *yp) {
    *xp += 2* *yp;
}

乍一看, 两个函数似乎有相同的行为, 下面的函数对内存的访问更少, 速度应该更快.

但是考虑 xp=yp 的情况, fun1 相当于 *xp * 4, 而 fun2 相当于 *xp * 3. 因此, 编译器不能随便优化这样的代码.

函数调用:

long f();
long func1() {
    return f() + f() + f() + f();
}
long func2() {
    return 4 * f();
}

两个过程计算的都是相同的结果, 似乎 func2() 更快一些. 但是如果 f 函数有 副作用, 比如执行了某个全局变量 + 1, 那么调用一次 func1() 会 +4, 调用一次 fun2() 只会 +1, 因此编译器不能随便将 fun1() 优化成 fun2().

用内联函数替换优化函数调用

包含函数调用的代码可以用一个称为内联函数替换的过程进行优化, 此时, 将函数调用替换为函数体. 即修改函数调用的位置为函数代码.

例如, 使用 inline 修饰 f, fun1() 的代码会变成这样:

/* Result of inlining f in fun1 */
long func1in() {
   long t = counter++;
   long t = counter++;
   long t = counter++;
   long t = counter++;
   return t;
}

这样的转换减少了函数调用的开销, 同时允许对展开的代码做进一步优化.(可以理解成现在编译器看得到函数具体是怎么实现了, 所以可以更好优化)

然而 GCC 只尝试在单个文件中定义的函数的内联, 因此无法应用于常见的在一个文件中定义函数, 被其他文件调用的情况.

此外, 如果函数调用被内联替换优化过了, 那么任何对这个调用进行追踪或设置断点的尝试都会失败. 因此某些情况下最好阻止编译器执行内联替换.

5.2 表示程序性能

引入度量标准每元素周期数(CPE)作为表示程序性能并指导我们改进代码的方法. 对于一个运行时间是 an+b 个周期的程序来说(n为输入数据量), 我们可以认为 CPE 就是 a.

5.3 程序示例

接下来我们会通过一步步优化一个程序学习如何优化.

我们的程序有一些基本的设置:

typedef struct {
    long len;
    data_t *data;
} vec_rec, *vec_ptr;

data_t 可以是 int, long, float, double.

还有一些生成向量, 访问元素, 确定长度的基本过程

vec_ptr new_vec(long len) {
    ...
}

int get_vec_element(vec_ptr v, long index, data_t *dest) {
    if (index < 0 || index >= v->len)
      return 0;
    *dest = v->data[index];
    return 1;
}

long vec_length(vec_ptr v) {
    return v->len;
}

我们的示例代码如下:

void combine1(vec_ptr v, data_t *dest) {
    long i;

    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

如果是求和, 使用

#define IDENT 0
#define OP +

如果是求积, 使用

#define IDENT 1
#define OP **

5.4 消除循环的低效率

combine1 每次都调用了 vec_length, 向量长度不会变, 所以可以只调用一次. 于是我们可以得到 combine2

void combine2(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);

    *dest = IDENT;
    for (i = 0; i < length; i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

这种优化称为代码移动, 通过识别要执行多次但结果不变的计算, 将计算移到前面不会多次求值的部分. 但是正如前面提到的函数的副作用, 编译器不会轻易地执行这种优化, 所以需要程序员手动进行.

5.5 减少过程调用

我们可以发现对 v 的任意索引的访问其实都是合法的, 所以外面可以不需要执行边界检查. 因此我们用一个 get_vec_start 获取数组的起始地址, 然后直接访问数组.

data_t *get_vec_start(vec_ptr v) {
    return v->data;
}

void combine3(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);
    data_t *data = get_vec_start(v);

    *dest = IDENT;
    for (i = 0; i < length; i++) {
        *dest = *dest OP data[i];
    }
}

令人吃惊的是, 性能没有明显提升, 事实上还略有下降. 显然, 其他操作形成了瓶颈. 我们会在后面再回到这个函数.

5.6 消除不必要的内存引用

我们发现每次循环都要对 dest 寻址, 可以用一个累积变量 acc 替换, 这样每次循环就从两次读一次写变成了一次读.

void combine4(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for (i = 0; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

由于内存别名的存在, 编译器不会轻易执行这样的优化, 因为对 dest 位置数据的更改可能导致 data[i] 发生变化. (比如令 dest=get_vec_start(v)+2)

5.7 理解现代处理器

在代码级上, 看上去是一次执行一个指令, 但是实际的处理器中是同时对多条指令求值的, 这被称为指令级并行. 在某些设计中, 可以有 100 或更多条指令在处理中. 通过一些精细的机制确保这种并行执行的行为可以取得机器级程序顺序执行的结果. 这也被称为乱序执行技术.

有两种下界描述了程序的最大性能, 当一系列操作必须按照严格顺序执行时, 就会遇到延迟界限(latency bound), 因为下一条指令必须等上一条指令执行完. 吞吐量界限刻画了处理器功能单元的原始计算能力, 这是程序性能的终极限制.

5.7.1 整体操作

指令控制单元: 负责从内存读指令, 然后生成一系列基本操作

执行单元: 执行这些操作.

一条指令可能被转化为多个操作, 例如

addq %rax, 8(%rdx)

就会被分解成三个操作: 从内存加载一个值到处理器, 操作加载进来的值加上 %rax 的值, 将结果存放回内存. 硬件单元可以并行地执行多条指令的不同部分.

EU 接受取指单元发送过来的操作, 这些操作会被分派到一组功能单元中, 每个功能单元专门执行不同类型的操作.

Warning

加载/存储单元有一个加法器来完成地址计算, 所以加载内存指令不用再被分割成更小的加法指令和读指令.

一种操作可能有多个功能单元可以执行, 利用这一点可以实现并行执行.

在指令控制单元(ICU)中, 退役单元记录正在进行的处理, 并确保它遵守机器级程序的顺序语义. 简而言之, 它就是控制一条指令对程序员可见状态的更改能否生效. 并且按顺序生效. 因此可以把乱序执行技术看作先运算, 但是不实际更改程序员可见状态, 最后再按顺序使更改生效.

为了运算结果的正确性, 执行单元之间可以彼此相互发送运算结果, 这就是 4.5.5 节中数据转发技术的更精细版本.

简单来说, 要更新寄存器的命令生成一个标记 t. 将 (r,t) 加入表中. 通过计算得到 r 的新值 v, 生成结果 (v,t). 后面所有需要 r 的指令都可以根据 (r,t) 表中的 t 找到 (v,t) 中的 v. 如果表中没有条目说明没有未生效的写寄存器操作, 可以直接读寄存器.

5.7.2 功能单元的性能

整数和浮点数的加法乘法的发射时间都为 1, 说明在每个时钟周期处理器都可以开始一条新的这一的运行. 发射时间为 1 的功能单元称为完全流水线化的.

表达发射时间还能用功能单元的最大吞吐量表示, 它定义为发射时间的倒数. (每时钟周期最多执行几条指令)

对于一个容量为 C, 发射时间为 I 的操作, 处理器可能获得的吞吐量为每时钟周期 C/I 条指令.

根据这些数据, 可以得到某个操作的延迟界限和吞吐量界限, 表里面的是 CPE 值.

注意, 虽然有 4 个加法功能单元而且加法的发射时间为 1, 理论上可以达到 1/4=0.25 CPE(每个周期都有 4 条加法指令执行, 平均一个指令只需要 0.25 周期), 但是由于需要从内存读数据, 就造成了另一个吞吐量界限. 两个加载单元限制了处理器每个周期只能最多读取两个数据值, 使得吞吐量界限为 0.50.

5.7.3 处理器操作的抽象模型

回忆一下 combine4, 可以看到除了整数加法其他操作基本都达到了延迟界限, 这表明这些函数的性能是由执行的求和或乘积运算主导的, 而且这些操作必须顺序执行.

从机器级代码到数据流图

我们可以把机器级代码划分为几个基本操作, 然后观察这之间的数据依赖关系, 以 combine4 为例.

这里 vmulsd 会被分解为 load + mul 操作, 于是我们得到了如下数据流图

我们可以将访问到的寄存器分为 4 类:

• 只读: 只用作源值, 不被修改, 如 %rax
• 只写: 只用作目的, 本例中没有这样的寄存器
• 局部: 在循环内部修改和使用, 但迭代和迭代之间不相关, 例如条件码寄存器. 下一次迭代不需要上一次的条件码寄存器.
• 循环: 这些寄存器既被使用又被修改, 例如 %rdx, %xmm0.

循环寄存器之间的操作链决定了限制性能的数据相关.

通过去除无关的变量, 保留数据依赖, 我们可以得到一张更加简洁的数据流图.

简单的重复它 n 次, 就得到了内循环 n 次迭代的数据流表示. 可以看到由两条数据相关链. 由于浮点乘法延迟为 5 个周期, 整数加法延迟为 1 个周期, 因此左边的链会成为关键路径.

可以看到整数加法并没有达到延迟界限 1.00 而是 1.27 , 可能是一些其他因素限制了性能, 例如功能单元之间传递数据的数量. 数据操作足够快, 使得其他操作供应数据的速度不够块(例如 load 耗时太久)

5.8 循环展开

k*1循环展开

每个循环执行 k 次操作, 只使用一个累积变量.

void combine5(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);
    long limit = length - 1
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for (i = 0; i < limit; i+=2) {
        acc = (acc OP data[i]) OP data[i+1];
    }

    for (; i < length; i++) {
        acc = acc OP data[i];
    }

    *dest = acc;
}

这种循环展开虽然减少了循环的开销(条件判断, 循环变量自增), 但是并没有实质改变数据依赖的关系, 每次循环的两个操作还是需要顺序执行.

5.9 提高并行性

上面的循环展开不能利用发射时间为 1 达到吞吐量界限的根本原因在于只使用了一个累积遍历 acc. 在每次计算, 我们都要等待前面计算出的 acc 的新值.

5.9.1 多个累积变量

对于可结合和可交换的合并运算来说, 比如整数加法或乘法, 我们可以通过将一组合并运算分割成两个或更多部分, 最后合并结果. 也就是使用多个累积变量. 这种循环展开方法称为 k*k循环展开.

void combine6(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);
    long limit = length - 1
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;

    for (i = 0; i < limit; i+=2) {
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }

    for (; i < length; i++) {
        acc0 = acc0 OP data[i];
    }

    *dest = acc0 OP acc1;
}

通过 2*2 循环展开, 我们将一条关键路径分成了两条关键路径, 每条路径上只有 n/2 个操作, 因此 CPE 大约是原来的一般.

当 k 足够大时, 几乎所有情况下都能达到吞吐量界限. 虽然浮点乘更耗时, 但是它的吞吐量界限是浮点加的 1/2. 这是因为浮点乘有更多的功能单元.

为了达到吞吐量界限, 我们需要保证能够执行该操作的所有功能单元的流水线都是满的, 一个延迟为 L, 容量为 C 的完全流水线化的操作, 一个周期至少要同时执行 C*L 条该操作才能把流水线填满. 因此这就要求 k>=C*L.

由于浮点加乘是不可结合的, 所以在使用这种展开的时候要格外小心.

5.9.2 重新结合变换

k*1a循环展开

void combine7(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_legnth(v);
    long limit = length - 1
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for (i = 0; i < limit; i+=2) {
        acc = acc OP (data[i] OP data[i+1]);
    }

    for (; i < length; i++) {
        acc = acc OP data[i];
    }

    *dest = acc;
}

在 combine7 中, 我们将括号放在了后面. 这就是重新结合变换.

因为循环变量 acc 在每次循环只执行了一次乘法, 因此关键路径上只有 n/2 次操作.

CPE 分别是 5, 5/3*2, 5/3, 5/3, 5/3*2.

5.10 一些限制因素

5.10.1 寄存器溢出

一旦循环变量的数量超过了可用寄存器的数量, 程序就必须在栈上分配一些变量, 因此展开次数过高不会有更好的结果.

5.10.2 分支预测和预测错误处罚

1. 不要过分关心可预测的分支

combine3 中的边界检查我们总是预测检测成功, 因此对我们的性能没有什么影响.

2. 书写适合用条件传送实现的代码

5.11 理解内存性能

这里, 我们假设数据都存放在高速缓存中.

5.12.1 加载的性能

对于两个加载单元, 每个时钟周期只能启动一条加载操作, 因此 CPE 不可能小于 0.5.

利用链表我们可以得到加载操作的延迟大约是 4.00 CPE

5.12.2 存储的性能

大多数情况, 存储操作能够在完全流水线的模式下工作, 每个周期开始一条新的存储.

存储操作不影响任何寄存器值, 只有加载操作会受其影响, 因此可能会发生写/读相关

跟我们之前讲的寄存器重命名类似, 存储操作有一个存储缓冲区, 包含已经发射到存储单元而没有完成的存储操作的地址和数据. 一个加载操作发生时, 必须先检查存储缓冲区的条目, 看有没有地址相匹配, 如果有就取出相应的数据条目作为结果.