CSAPP 5.优化程序性能

yyi
yyi
2023-08-09 / 0 评论 / 110 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2023年08月09日,已超过309天没有更新,若内容或图片失效,请留言反馈。

优化程序性能

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

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参考机:

A6C12D7A-9B60-4D29-8107-6D450E9383D9.jpeg

完全流水线化:发射时间为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展开的性能提升。

0

评论 (0)

取消