优化程序性能

本章的目标在于，了解编译器和目标机器的运行规律，通过调整代码的细节提升性能

1. 编译器的能力与局限性

在了解编译器优化能力的局限性时，不要忘记编译器的第一要务是保证其编译结果的正确性

对于

void f1(int *x, int *y) {
    *x += y;
    *x += y;
}
void f2(int *x, int *y) {
    *x += 2* *y;
}

两份代码，表面上有相同的行为，但是当xy指针指向同一个地址时，会产生截然不同的结果。

内存别名使用：两个指针指向同一地址的情况

当编译器优化时，必须确保在任何情况下都是正确的。

2. 表示程序性能

CPE：Cycles Per Element 每元素周期数，概略理解的话可以简单的当作每次执行循环所需要的CPU周期

在本章的学习中，以如下的一个程序及其CPE来测量优化效率，其中 length 函数直接返回vec的len字段，get函数先判断下标是否越界，再返回对应的值。

#define data_t double / long
#define IDENT 0 / 1
#define OP + / *
struct {
    long len;
    data_t *data;
}vec;
void comb1(vec v, data_t *res) {
    *res = IDENT;
    for(long i = 0; i < v.length(); i ++ ) {
        data_t val;
        v.get(i, &val); // put v[i] to val;
        *res = *res OP val;
    }
}

基础的comb1函数在O1优化下，整数加法CPE约为10

4. 消除循环的低效率

消除隐藏的渐进低效率
当使用strlen作为遍历字符串的循环条件时，编译器无法确定循环内是否对字符串长度存在可能的修改，因此会每次都调用该函数，造成复杂度错误

因此，comb2把length外移，实现了第一个优化

    long len = v.length();
    for(long i = 0; i < len; i ++ )

使得整数加法的CPE优化到了7。

5. 减少过程调用

过程调用会带来上下文的切换开销，我们对数组的访问并不会越界，但是get函数会进行越界检测。第二种优化直接使用数组的值，而不是调用函数

    *res = *res OP data[i];

很遗憾，这种优化并没有带来CPE的提升，换句话说，get函数反复的边界检查并没有让这个循环的性能变差。这是由于get函数中的分支预测永远为真，其带来的性能开销没有关键路径的性能开销大，关于关键路径，后面会详细说。

6. 消除不必要内存引用

在我们的代码中，每次结果都会写回给res，下次运算时还要再读取res参与运算，这样的读写很浪费，因为下次读取的正是循环刚刚写回的值。我们做第三个优化，减少内存读写。

现在的函数变成了这样子：

void comb4(vec v; data_t *res) {
    long len = v.length();
    data_t* data = v.data;
    data_t acc = IDENT;
    for(long i = 0; i < len; i ++ ) {
        acc = acc OP data[i];
    }
    *res = acc;
}

我们把结果累计在局部变量acc中，消除反复的读写，使得整数加法的CPE提升到了1.27，相比于上一步的7.17，这是一个很有成效的提升

那么，为什么编译器没能做这么简单有效的优化？根据之前我们说的编译的第一要务是保证结果的正确性，我们可以举一个二义性的例子：

comb3(v, &v.data[2]);
comb4(v, &v.data[2]);

当把数组内某个地址本身作为累加结果的位置时，我们的优化就行不通了。

很显然，对于v:[2, 3, 5]，comb3的结果是5，comb4的结果是10

7 理解现代处理器

指令级并行：处理器内部同时对多条指令求值，但对上层展示的结果和顺序执行一样。现代处理器可能可以有上百条指令同时在处理。

延迟界限：当一系列操作按严格顺序执行程序所能达到的最大性能。数据相关会导致延迟界限对性能的限制

吞吐量界限：硬件的原始计算能力，也是程序性能的最终限制。

7.1 整体操作

分支预测与投机执行：现代处理器会猜测是否选择分支，预测分支的目标地址，提前开始操作。若过后确定分支预测错误，会把状态重设为分支点的状态。
一条包括内存引用的指令，比如 add rax, 8(rdx) 会被拆为多个操作，把内存引用和算术运算分开，对于这条指令，会分为加载、运算、写回。
预测错误会导致很大的性能开销，现代处理器用退役单元记录处理情况，当预测成功时，退役单元内的内容退役，否则清空，丢弃所有已算出来的结果
操作数通过寄存器重命名机制在处理单元中传送数据。使得已经运算出来的结果可以在写回之前被转发到另一个操作。

7.2 功能单元的性能

对于一个典型的i7 Haswell参考机：

完全流水线化：发射时间为1的功能单元。

吞吐量：对于容量为C，发射时间为I的操作，吞吐量为每时钟周期C/I 个操作

对于该处理器，整数加法的延迟界限为1，浮点加法的延迟界限为3，整数加法的吞吐量界限为0.5，浮点加法的吞吐量界限为1

很遗憾，在我的笔记中实在很难很好的描述数据流图和关键路径的概念，我只能尽可能的简洁口述

对于comb4来说，循环内汇编可能是这样的（浮点乘）：

label :
vmulsd (%rdx), %xmm0, %xmm0 ; acc(in xmm0) = acc * data[i]
addq $8, %rdx ; pdata += 8
cmpq %rax, %rdx; pdata cmp data_end
jne label

可以看到，我们可以拆分为：

load→mul→add→cmp→jne

我们考虑两个循环，对于load，下一个循环依赖上一个循环的rdx，对于mul，下一个循环依赖load和上一个循环mul的结果，对于add，下一个循环依赖上一个循环的rdx，对于cmp，也是依赖rdx

因此限制循环的因素就变成了xmm和rdx的更新，也就是mul和add的执行速度，而mul显然时更慢的，所以我们称更新xmm这条mul链为制约程序性能的关键路径。

8 循环展开

每次循环处理优化前k次迭代的内容，减少循环迭代次数，称为k*1循环展开

对于comb的2*1循环展开例子

for(long i = 0; i < len-1; i += 2) 
    acc = (acc OP data[i]) OP data[i+1];
for(; i < len; i ++ )
    acc = acc OP data[i];

循环展开减少了循环开销，使得整数加法的CPE提升到了1.01，非常逼近延迟界限1.00了

对循环展开后的结果画关键路径，还是存在N个mul操作，所以无法打破延迟界限。

9 提高并行性

之前关键路径受xmm0也就是acc变量更新影响，在前面的计算完成前，都不能计算后面的值，即使mul可以每个时钟周期开始一个新的操作，但是只能每L个周期开始一次操作

9.1 多个累积变量

由一个非常浅显的数学知识：数列P的累乘积等于数列P中奇数下标的累乘积乘以偶数下标的累乘积，由此我们引出2x2循环展开comb6

data_t acc0 = IDENT, acc1 = IDENT;
for(long i = 0; i < len-1; i += 2) {
    acc0 = acc0 OP data[i];
    acc1 = acc1 OP data[i+1];
}
for(; i < len; i ++ )
    acc = acc OP data[i];

整数加法CPE被优化到了约0.8，我们打破了延迟界限。

在comb6的流程图中，出现了两条关键路径，每条关键路径上只有n/2个乘法。这也是性能提升的关键因素。

9.2 重新结合变换

对于语句

acc = (acc OP data[i]) OP data[i+1];
acc = acc OP (data[i] OP data[i+1]);

其实是不一样的，后者乘法的关键路径上只有n/2个操作，这是因为在acc被更新前，data[i]和data[i+1]的乘法无需等待前面的结果。我们减少了关键路径上一半的乘法，得到了接近2x2展开的性能提升。

CSAPP 5.优化程序性能