开始学 CSAPP的第五章

逐步更新吧~

  • 2023-01-08 19:00:00 第一次写
  • 2023-01-11 23:00:00 更新新内容
  • 2023-01-12 12:30:00 写完第五章

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

也懒得去复制书上的东西了，就是告诉了我们编译器在编译代码的时候会对代码做出优化等等之类的，但是我们的优化需要足够安全，我们必须保证在任何情况下，优化和不优化的代码只会带来效率上的差异而不会对任何形式输出的任何结果产生差异。

这一章主要介绍了一个例子

问：

1
2
3
4
int test(int *x,int *y){
	*x+=*y;
	*x+=*y;
}

能否用以下程序作为优化

1
2
3
int test(int *x,int *y){
	*x+=2*(*y);
}

乍一看好像可以，因为就是 x 所指向的 int 内存加了两次 y，完全可以用，并且对比上下的代码，上面需要进行 6 次访存（读 y，读x，写x，读y，读x，写x），而下面的代码只需要 3 次访存（读y，读x，写x）

感觉很完美，但是实际上是不行的，因为如果 x 和 y 指向相同的内存，那么两个示例运行起来就会有差异了。

这里我们让 x=1，运行示例 test(&x,&x) 之后发现，上面的代码运行完之后 x=4，而下面的代码运行之后 x=3，因此在编译的时候，不能用下面的代码作为上面代码的优化版本。

这造成了一个主要的妨碍优化的因素，这也是可能严重限制编译器产生优化代码机会的程序的一个方面。如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，这就限制了可能的优化策略。

这种两个指针可能指向同一个内存位置的情况称为内存别名使用（memory aliasing）

练习5.1 下面的问题说明了内存别名使用可能会导致意想不到的程序行为的方式。考虑下面这个交换两个值的过程：

1
2
3
4
5
6
/* Swap value x at xp with value y at yp */
void swap(long *xp, long *yp){
	*xp = *xp + *уp; /* x+y */
	*уp = *xp - *уp; /* x+y-y = x */
	*xp = *xp - *уp; /* x+у-x = y */
}

如果调用这个过程时xp等于yp，会有什么样的效果？

第二个妨碍优化的因素是函数调用。作为一个示例，考虑下面这两个过程：

1
2
3
4
5
6
long func1() {
    return f() + f() + f() + f();
}
long func2() {
    return 4*f();
}

最初看上去两个过程计算的都是相同的结果，但是func2只调用f一次，而func调用f四次。以func1作为源代码时，会很想产生func2风格的代码。

不过，考虑下面f的代码：

1
2
3
4
long counter = 0; 
long f(){
   	return counter++;
}

这个函数有个副作用——它修改了全局程序状态的一部分。改变调用它的次数会改变程序的行为。特别地，假设开始时全局变量counter都设置为0，对func1的调用会返回0+1+2+3=6，而对func2的调用会返回4*0=0。 大多数编译器不会试图判断一个函数是否没有副作用，如果没有，就可能被优化成像func2中的样子。相反，编译器会假设最糟的情况，并保持所有的函数调用不变。

这两个例子分别介绍了内存别名和函数调用带来的一个优化难题。

表示程序性能

我们引入度量标准每元素的周期数，就是平均每个元素需要多少的时钟周期完成，这里用时钟周期而不用时间主要是因为机器的差异不在我们对程序优化的考虑范围之内。

这里举了一个例子，给定一个数列 \(\{a_i\}\) 要求计算出它的前缀和序列。

下面写了两个函数去计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Compute prefix sum of vector a */
void psum1(float a[], float p[], long n)
{
    long i; 
    p[0] = a[0]; 
    for (i=1; i<n; i++)
        p[i] = p[i-1] + a[i];
}
void psum2(float a[], float p[], long n)
{
    long i; 
    p[0] = a[0]; 
    for (i = 1; i < n-1; i+=2) {
        float mid_val = p[i-1] + a[i]; 
        p[i]= mid_val; 
        p[i+1] =mid_val + a[i+1];
    }
    /* For even n, finish remaining element */
    if (i<n)
        p[i] = p[i-1] + a[i];
}

函数 psum1每次迭代计算结果数列的一个元素。第二个函数使用循环展开的技术，每次迭代计算两个元素。

这里对两个函数把 n 和周期数进行最小二乘拟合：

最小二乘拟合：

对于一个数据点\((x_1,y_1),...,(x_n,y_n)\)的集合，我们常常试图画一条线，它能最接近于这些数据代表的 \(X-Y\) 趋势。使用最小二乘拟合，寻找一条形如 \(y=mx+b\) 的线，使得下面这个误差度量最小： \(E(m,b)=\sum ^{n} _{i=1}(mx_i+b-y_i)^2\) 将\(E(m,b)\)分别对 m 和 b 求导，把两个导数函数设置为0，进行推导就能得出计算 m 和 b 的算法。

结论：

我们发现，psum1和psum2的运行时间（用时钟周期为单位）分别近似于等式368+9.0n和368+6.0n。这两个等式表明对代码计时和初始化过程、准备循环以及完成过程的开销为368个周期加上每个元素6.0或9.0周期的线性因子。对于较大的n的值（比如说大于200），运行时间就会主要由线性因子来决定。这些项中的系数称为每元素的周期数（简称CPE）的有效值。注意，我们更愿意用每个元素的周期数而不是每次循环的周期数来度量，这是因为像循环展开这样的技术使得我们能够用较少的循环完成计算，而我们最终关心的是，对于给定的向量长度，程序运行的速度如何。我们将精力集中在减小计算的 CPE上。根据这种度量标准，psum2 的 CPE 为 6.0，优于 CPE 为 9.0 的 psum1。

下面是我自己的看法：

就是循环展开可以减小访存的一个次数，而访存往往是计算机执行指令时最耗时间的一个指令。我们观察一下 psum1，每次循环有这几次访存：读 p[i-1] 读 a[i]，写 p[i] 三次访存。

而在 psum2 中，我们每次循环有这几次访存：读 p[i-1] ，读 a[i]，读 a[i+1]，写 p[i] ，写 p[i+1]，虽然说有五次访存，但是 psum2 一次循环的操作数是 psum1 的两次。并且在算上 psum1 需要更多的条件跳转语句，这样它被 n 影响的就更多了，相比于此， psum2 就优秀了许多。

所以循环展开是编译器优化一个很好的手段。

程序示例

这里我们声明一类数据结构：

我们在四个数据类型下面做测试：int，long，float，double。分别对他们进行求和和求积的操作来测试程序的 CPE。

最后我们得到了这样的结果：

首先就可以看到，使用命令行选项“-O1”，就会进行一些基本的优化。正如可以看到的，程序员不需要做什么，就会显著地提高程序性能-超过两个数量级。通常，养成至少使用这个级别优化的习惯是很好的。（使用-Og优化级别能得到相似的性能结果。）在剩下的测试中，我们使用 -O1和-O2级别的优化来生成和测量程序。

消除循环的低效率

第一点是我们在打 ACM 中会遇到的一个问题，for(int i=0;i<length(x);i++) 这样的代码过程，一般来说 length(x) 作为一个固定值不会发生改变，但是我们每次循环都要判断一次条件，这样会导致重复执行 n 次 length(x)，所以我们可以定义一个变量，让测试条件都是用这个值。

依稀记得某次自己算法 submit 的脑残写法：for(int i=0;i<strlen(s);i++) ...

优化的版本：

优化的结果我们也列一张表：

没有特别明显的CPE下降，但是也是有效率上的提升，这样的优化称为 代码移动。

但是这种优化不能靠编译器去做，编译器通常会非常小心。它们不能可靠地发现一个函数是否会有副作用，因而假设函数会有副作用，就像前面说过的那样。例如，如果vec_length有某种副作用，么combine1和combine2可能就会有不同的行为。为了改进代码，程序员必须经常帮助编译器显式地完成代码的移动。

蚌埠住了啊，下面就讲到了我们上面提到的这个例子。

这个示例说明了编程时一个常见的问题，一个看上去无足轻重的代码片断有隐藏的渐近低效率（asymptotic inefficiency）。人们可不希望一个小写字母转换函数成为程序性能的限制因素。通常，会在小数据集上测试和分析程序，对此，lower1的性能是足够的。不过，当程序最终部署好以后，过程完全可能被应用到一个有100万个字符的串上。突然，这段无危险的代码变成了一个主要的性能瓶颈。相比较而言，lower2的性能对于任意长度的字符串来说都是足够的。大型编程项目中出现这样问题的故事比比皆是，一个有经验的程序员工作的一部分就是避免引入这样的渐近低效率。

减少过程调用

像我们看到过的那样，过程调用会带来开销，而且妨碍大多数形式的程序优化。从combine2 的代码（见图 5-6）中我们可以看出，每次循环迭代都会调用 get_vec_element来获取下一个向量元素。对每个向量引用，这个函数要把向量索引i与循环边界做比较，很明显会造成低效率。在处理任意的数组访问时，边界检查可能是个很有用的特性，但是对combine2代码的简单分析表明所有的引用都是合法的。

但是当我们去掉重复的判断边界，直接去访问元素的话：

发现效率并没有明显的提升

而现在，我们可以将这个转换视为一系列步骤中的一步，这些步骤将最终产生显著的性能提升。

消除不必要的内存引用

就比如说 *dest=*dest OP data[i]，每一次使用我都要访存，然后写一次，不如我就新建一个临时变量。等到结束的时候再写到这个 *dest 里面去，这个优化依然只能我们完成，编译器不能帮我们完成。

而这个做法让我们的程序效率有了质的飞跃

这里有一个很有意思的练习题：

对比两个代码，我们可以发现 O2 级别的优化少了一步 vmovsd (%rbx),%xmm0 从内存中读取的一个行为，这里相当于把 xmm0 作为了一个临时变量 acc 了，只是说为了防止和源程序有差异，这里还是会每次循环更新 *dest 的值的，所以说这里的优化接近 combine4，但是还达不到 combine4 的原因。

理解现代处理器

现代处理器可以做到指令级并行，多条指令可以并行执行，同时又呈现出一种简单的顺序执行的表象。

两种下界描述了程序的最大性能：

  • latency bound延迟界限，当一系列操作必须按照严格顺序执行时，某一条指令开始前，上一条指令必须结束。代码中的数据相关性会限制指令级并行，程序受限于延时界限。
  • throughput bound吞吐量界限，处理器功能单元的原始计算能力，是程序性能的终极限制

整体操作

超标量(superscalar)处理器可以在每个时钟周期执行多个操作，并且是乱序的(out-of-order)。

处理器的设计有两个部分，都是用非常复杂的数字电路实现的：

  • 指令控制单元(ICU, instruction controll unit)，负责从icache中读取指令序列，生成一组基本操作，发送给EU。
  • 执行单元(EU, execution unit)，每个时钟周期接收多个操作，执行操作。

分支预测(branch prediction)：处理器猜测是否会选择分支，同时预测分支的目标地址。包括在取指控制块中。

投机执行(speculative execution)：处理器取出预测的分支会跳到的指令，进行指令译码，在确定分支之前就开始执行。如果之后确定分支预测错误，会将状态重置到分支点，取出并执行另一个方向上的指令，这个步骤会造成性能损耗。

指令译码：接收程序指令，将他们转换成一组基本操作（微操作），例如两个数相加，从内存读数据，向内存写数据。通常一条只对寄存器操作的指令转换成一个操作，而一个包括内存引用的指令转换成多个操作。执行单元可以并行执行多条基本操作。

例子：

只对寄存器操作的指令：

1
addq %rax,%rax

转换成1个加法操作。

又比如：

1
addq %rax,8(%rdx)

转换成3个操作，加载，加法，存储。

  • 功能单元：EU每个时钟周期可以接收多个来自取指单元的操作。例如Intel Core i7 Haswell8个功能单元，每个功能单元可以执行多种不同的操作。
  • 退役单元retirement unit：在队列中记录正在执行的指令的信息，确保乱序执行的结果遵守机器级程序的顺序语义。退役单元控制寄存器的更新，一旦一条指令执行完成，并且分支预测的结果被确认为预测正确，那么这条指令可以退役(retire)，对寄存器的更新可以被执行，否则这条指令被清空(flushed)，并且丢弃计算的结果。

退役就是指预测正确且已经执行的指令可以不再执行的一个行为，任何预测执行的指令对寄存器和内存的更新只有当指令退役时才会执行。

寄存器重命名(register renaming)：对寄存器的更新只有在指令退役时才会执行，在执行单元间传送指令（退役之前）需要用到寄存器重命名机制。当一条更新寄存器r的指令译码时，产生标记t，条目(r,t)被加入到一张表中，随后以r为操作数的指令在指令译码时，发送到EU时会包含以t为操作数源的值。当执行单元完成第一个操作时，会生成结果(v,t)，之后需要t的指令都可以用v的值。值可以从一个操作直接转发到另一个操作，无需读写寄存器。

功能单元的性能

  • 延迟latency：完成运算所需要的总时间，一般整数加法1、乘法3、除法3~30，浮点数加法3、乘法5、除法3~15。
  • 发射时间issue time：两个连续同类运算之间需要的最小时钟周期，通常fully pipelined运算发射时间都是1，例如加法和乘法。除法一般没有流水线，issue time = latency。
  • 容量capacity：功能单元的数量。
  • 最大吞吐量：容量为C，发射时间为I，则最大吞吐量为每时钟周期C/I

参考机性能

界限 整数+ 整数* 浮点数+ 浮点数*
延迟 1.00 3.00 3.00 5.00
吞吐量 0.50 1.00 1.00 0.50

注意：吞吐量不完全是由capacity决定的，虽然整数加法有4个功能单元，但是加载功能单元只有2个，所以吞吐量是1/2而不是1/4。

处理器操作的抽象模型

将程序用数据流(data flow)表示，展现不同操作之间的数据相关性是如何限制他们的执行顺序的，这些限制形成了图中的关键路径(critical path)，是执行一组指令所需的时钟周期的下界，优化程序时要优化关键路径。

性能优化实例

原始代码

1
2
3
4
5
6
7
8
9
10
11
// OP为+时IDENT为0
// OP为*时IDENT为1
void combine1(vec_ptr v, data_t *dest){
    long i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++){  // 这里vec_length(v)重复求值了
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

消除循环的低效率

优化方法称为代码移动(code motion)

1
2
3
4
5
6
7
8
9
10
void combine2(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);  // 将不变的长度放到循环外
    *dest = IDENT;
    for (i = 0; i < length; i++){
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }   
}

减少过程调用

1
2
3
4
5
6
7
8
9
10
11
12
data_t* get_vec_start(vec_ptr v){return v->data;}

void combine3(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);  // 获取数组起始地址
    *dest = IDENT;
    for (i = 0; i < length; i++){
        data_t val;
        *dest = *dest OP data[i];  // 将函数调用get_vec_element(v, i, &val)改为内存偏移量
    }
}

消除不必要的内存引用

1
2
3
4
5
6
7
8
9
10
11
void combine4(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;  // 计算结果保存在局部变量，减少内存寻址次数
    for (i = 0; i < length; i++){
        data_t val;
        acc = acc OP data[i];
    }
    *dest = acc;
}

循环展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void combine5(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    // 2x1 循环展开
    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;
}

提高并行性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void combine6(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;  // 多个累积变量
    data_t acc1 = IDENT;

    // 2x2 循环展开
    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;
}

到这里程序已经突破了延迟界限。

重新结合变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void combine7(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    // 2x1a 循环展开
    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;
}

一些限制因素

寄存器溢出

循环展开的并行度如果超出了寄存器个数，会造成寄存器溢出，编译器将局部变量分配到栈上，造成性能下降。解决办法是控制循环展开的数量。

分支预测错误处罚

在参考机上，预测错误处罚时19个时钟周期，损耗很大。解决办法是通过 “功能性的” 代码代替 “命令式的” 代码。 例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 优化前命令式
void minmax1(long a[], long b[], long n){
    long i;
    for (i = 0; i <n; i++){
        if (a[i] > b[i]){  // 分支预测错误时损耗很大
            long t = a[i];  // 交换a[i]和b[i]
            a[i] = b[i];
            b[i] = t;
        }
    }
}

// 优化后功能性的
void minmax1(long a[], long b[], long n){
    long i;
    for (i = 0; i <n; i++){
        long min = a[i] < b[i] ? a[i] : b[i];  // 编译为条件传送汇编代码，避免分支预测
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

理解内存性能

咕咕咕，这一节完全看不懂

性能提高的技术

这里做个总结，感觉对我们平时写高效率代码挺有帮助的。

高级设计

  • 选择适当的算法和数据结构

基本编码原则

  • 消除连续函数调用，将计算移到循环外
  • 消除不必要的内存引用

低级优化

  • 循环展开
  • 使用多个累积变量、重新结合技术提高指令级并行
  • 用功能性风格重写条件操作，使编译采用条件传送