CSAPP笔记03优化程序性能

我跳过了第四章”处理器体系结构”,因为太偏硬件了，我没有足够的时间和预备知识来学习

0x00 概述

​ 为了编写高效的程序，需要做到以下三点：

​ ①选择一组合适的数据结构与算法。

​ ②编写出编译器能够有效优化的代码，理解编译器的能力和局限性。

​ ③对于预算两特别大的计算，将一个任务分成多个部分，利用处理器的特性并行运算。

​ 在注重性能的情况下，进行大量优化是合适的，并且在优化的同时，还要维护代码的可读性。（这是一个挑战）

​ 现代编译器采用非常复杂的分析和优化形式，但是即使最好的编译器也受到妨碍优化的因素影响（optimization blocker），程序员必须写出容易优化的代码，以帮助编译器。

​ ①程序优化的基础是消除不必要的工作，让代码尽可能有效地执行所期望的任务。包括消除不必要的函数调用，条件测试和内存引用，这些优化在任何目标平台上都是有效的。

​ ②通过了解处理器的运作，我们就可以利用处理器提供的指令级并行（instruction-level parallelism）能力，同时执行多条指令。我们可以降低不同部分之间的数据相关度 ，增加并行度。

​ 本章以循环为例，举例多种降低性能的因素，并给出多种优化方式。通过确认关键路径（critical path）（也就是循环内的数据链）来确定执行一个循环需要的时间（或者说时间下界，因为关键路径是必须要实现的功能）。

​ 作者认为，对于我这种新手程序员，不断改代码，试图优化性能，是有效且不可避免的，但是通过学习本章，能够找到改代码的思路吧。

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

​ 现代编译器采用复杂精细的算法来确定程序中计算的是什么值，以及该值如何被使用。然后找机会来简化表达式，例如将结果多次使用，以及降低一个给定表达式的计算次数等。多数编译器提供给用户优化级别控制选项，比如gcc的-o1 -o2 -o3命令，数字越大，优化成都越好。

​ 但是编译器的优化是有局限的，通过优化我们的c语言代码，有可能即使使用 -o1优化级别的性能也比原始代码执行 -o3 优化好。因为编译器只能对程序使用安全的优化，即不改变代码的任何功能。

​ 对于下面的代码：

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

​ 乍一看，好像都是计算* xp= * xp + 2 * (* yp)，并且我们能够看出 fun2 的计算次数少，性能高。编译器应该把fun1优化成fun2一样的机器代码。

​ 但是考虑xp=yp，也就是是两个相同指针的情况（两个指针指向一个对象称为内存别名），此时fun1 的结果是xp = 4 * (xp)，而 fun2的结果仍然是 xp = 3 * (xp);

​ 因此fun1和fun2的功能不同，编译器不会擅作主张将fun1优化成fun2的机器码，如果我们真的是想实现fun2的功能（即在指针相同的情况下，计算3* (*xp)）,那只能程序员来优化了。

​ 由于内存别名导致的功能不同（并且也伴随着性能不同），是编译器无法优化的。

​ 另一个妨碍优化的因素是内存调用，考虑下面的代码：

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

​ 同样，乍一看，好像func1和func2的功能相同，实际上考虑下面的f()函数：

long global_counter=0;
long f(){
    return global_counter++;
}

​ 这时f()有一个副作用，修改了全局变量，调用它会改变程序的行为，func1()的返回值0+1+2+3=6；而func2的返回值是4 * 0=0；（假设初始值global_counter=0）。

​ 编译器无法判断一个函数有没有副作用，编译器会保持函数调用不变。

​ 另外，用内联函数替换函数调用，可以减少函数调用哦那个的开销，gcc在 -o1级别及以上的优化等级会使用内联函数。

​

0x01 消除循环的低效率

​ 对于下面的代码：

void combine2(vec_ptr v,data *dest){
    long i;
    *dest=IDENT;
    for(i=0;i<vec_length(v);i++){
        data val;
        get_vec_element(v,i,&val);
        *dest=*dest OP val;//OP为宏定义的操作符
    }
}

​ 可以看到，for循环的测试条件，每次都会调用vec_length(v)函数，但实际上，每次的结果都是一样的，且函数没有副作用。但是对于编译器而言，他不会试着将这里优化成只执行一次，而是会忠实于源代码。高效的代码应该是 long length=vec_length(v),然后填入length而不是每次都调用。

​

0x02 减少过程调用的开销

​ 过程调用会带来开销，而且妨碍程序的优化（除了内联外并没有好的优化方式，编译器不会试着移动代码）。

​ 将上面的combine2优化成如下：

void combine3(vec_ptr v,data *dest){
    long i;
    long length=vec_length;
    data *data=get_vec_start(v);
    *dest=IDENT;
    for(i=0;i<length;i++){
        *dest=*dest OP data[i];
    }
}

​ 但是优化后没有明显的性能提升（书中的示例，我并没有测试过）。我们推测是循环中的其他操作形成了瓶颈，对性能的影响远远超过函数调用。

0x03 消除不必要的内存引用

​ 上面combine3的汇编代码对应如下：

​ 可以看到，每次循环中都会读两次内存，然后写一次内存，然而对内存的读写时间开销是很大的。

​ 分析我们程序的功能，先读*dest 计算后再写回 *dest。然后下次再读，结果并没有改变，因此我们可以用寄存器作为来保存中间值。

​ 也就是循环开始前将*dest保存到寄存器，循环中使用寄存器保存中间值，循环结束后，将寄存器的值写回 *dest。 对应的代码如下：

void combine4(vec_ptr v,data* dest){
    long i;
    long length=vec_length(v);
    data * data=get_vec_start(v);
    data acc =IDENT;
    for(i=0;i<length;i++){
        acc = acc OP data[i];
    }
    *dest=acc;
}

​ 消除不必要的内存引用后，性能有了显著提高。编译器不会将combine3自动优化成combine4，妨碍优化的原因还是内存别名使用。考虑传入的 dest 是 get_vec_start(v)，那么在循环开始前，combine3的向量/数组v的初始值就已经改变了。（因为循环前执行了*dest=IDENT），而combine4则没有变化。

0x04 现代处理器

​ 指令级并行

​ 为了进一步提高性能，我们必须要利用处理器微体系架构的优化。在实际的处理中，是同时对多条指令求值的，称为指令级并行，然后通过一些精细的机制，保证和结果和逐条顺序执行相同。

​ 当我们不适用指令级并行是，下一条指令开始之前，上一条语句必须完成，因此受到的限制称为延迟界限（latency bound）；而使用指令级并行可以突破该限制，达到最终的吞吐量界限(throughput bound)。

​ 为了实现并行处理，要求并行处理的指令数据无关。

​ 超标量

​ 处理器将一个指令的处理分成多个过程，并且一次并行处理不同指令的不同过程，称为流水线，这个机制称为超标量，来更好实现指令级并行。因为超标量会预读指令，因此如果发生跳转，那么之前读入流水线的指令都要清空，并重新预读读跳转后的指令到流水线。对于分支跳转，处理器使用分支预测技术，预测会不会跳转，并将预测的分支读入流水线，但该预测并不总是正确的，未命中则需要清空流水想重新读入另一个分支，所预测失败多消耗的时间称为未命中惩罚。

0x05 循环展开

​ 通过增加每次迭代中计算元素的数量，减少迭代次数，可以提高程序的性能：

​ ①减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。

​ ②提供了进一步优化的可能（见后面）。

​ 我们将索引一次增加k，称为按k * 1展开循环，对于k=2，代码如下：

void cmobine5(vec_ptr v,data *dest){
    long i;
    long length = vec_length(v);
    long limit =length -1;
    data *data=get_vec_start(v);
    data acc=IDENT;
    for(i=0;i<limit;i+=2){
        acc=(acc OP data[i]) OP data[i+1];
    }
    for(;i<limit;i++){
        acc=acc OP data[i];//cac remaining elements.
    }
}

​ 到目前位置，仍然没有利用处理器的指令级并行，继续优化（增加k值），性能没有提高，已经到达了延迟界限，因为关键路径中，每个元素都不得不进行一个乘法运算，并对累计寄存器读写一次。

​

0x06 提高并行性

​ 在此之前，程序的性能是受运算单元的延迟限制的。因为流水线的存在，每个时钟周期可以开始一个新的操作（而不必等待一个新的指令周期），硬件具有以更高速率执行乘法和加法的潜力，但是代码不能利用这种能力（要等待前面的结果计算完成），这是因为我们将累计值放在一个单独的变量acc中。在完成计算前，都不能计算acc的新值。

​ 这就导致，虽然每个时钟周期能开始一个新的乘法操作，但是最终变现为，每个指令周期（L个时钟周期）才开始一个新的乘法操作。

​

​ 多个累积变量

​ 对于可结合和可交换的整数的乘法和加法运算来说，将计算分为多个部分，最终将不同部分的累加值合并起来，结果是相同的，并且提高了性能。

​ 对此，我们将计算分为K个部分，每次索引增加K，成为循环的K * K展开，代码如下：(2 * 2如下)

void combine6(vec_ptr v,data* dest){
    long i;
    long length =vec_length(v)l
    long limit=length-1;
    data *data=get_vec_start(v);
    data acc0=IDENT;
    data 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;
}

​ 上面的程序，当K足够大时，程序可以达到吞吐量界限。

​ 另一方面，浮点数不遵循结合律（但是遵循交换律），因为浮点数表示不准确会发生舍入或者溢出，导致并行计算和顺序计算结果有些许不同，但是我们允许这种不同，因为浮点数本身就是不准确的，顺序计算的结果本就不准确。因此，对浮点类型数据也可以应用并行计算提高性能！

​ 重新结合变换

​ 对combine5的代码里循环的主体做如下变换：

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

​ 修改后的函数称为combine7，经过验证（书里的验证，我没测试），combine7在加法运算上，与combine5的k （k极大）* 1展开性能相同，在乘法运算上是combine5的三倍，和循环展开并行的combine6相同。

​ 为什么改变运算顺序会造成巨大的性能提升呢？主要是关键路径减少，按照combine5的运算顺序，下一个循环的开始，必须要先算①旧acc * data[i]，结果保存在acc②再用中间acc * data[i+1],结果保存到acc，变成新的acc。这两步有先后顺序，不能并行计算。

​ 而combine7中data[i] * data[i+1] 的结果不受acc影响，因此可以在流水线里，并行计算。关键路径只有一条，那就是 acc OP x。

0x07 限制并行的因素

​ 寄存器溢出，局部变量一般是用寄存器储存，而循环展开（再并行）时，寄存器可能不够用，那么就得保存到栈里，访问内存的开销远远大于并行计算节省的开销。但是，大多数情况下，x86-64有足够的寄存器，可以在出现寄存器溢出前就达到吞吐量限制。

​ 分支预测和预测错误惩罚：现代处理器都是超标量的，不仅处理当前pc指向的指令，还会对后面的指令进行处理。当时当遇到分支时，处理器必须要猜测该往哪个分支走。如果处理器猜测了一个分支，就会按照该分支的指令进行处理，但是不修改寄存器和内存，直到最终分支确定了，如果预测正确，处理器将预处理结果提交，如果错误，跳到另一个分支，重新填充流水线。

​ 一方面，我们不用过度关心分支对性能带来的影响，因为分支预测在大部分情况下都能猜对，比如循环一般只有最后一次分支预测错误。

​ 另一方面，可以利用条件传送代替分支，编译器倾向于将c中的三元表达式编译成cmov指令。

​ 示例：

void merge(long src1[],long src2[],long dest[],long n){
    long i1=0;
    long i2=0;
    long id=0;
    while(i1<n&&i2<n){//loop 1
        if(src1[i1]<src2[i2]){
            dest[id++]=src1[i1++];
        }else{
            dest[id++]=src2{i2++};
        }
    }
    while(i1<n){
        dest[id++]=src1[i1++];
    }
    while(i2<n){
        dest[id++]=src2[i2++];
    }
}

​ 上面这段代码使用了分支，对于循环1的test-expr的预测通常是准确的（第一次和最后一次的预测可能会错，但中间的不错），而对于src1[i1]和src2[i2]大小的预测就比较困难，因此对于这段代码分支预测的效果很差。

​ 试着用条件传送重写循环1的body-expr：

long v1=src1[i1];
long v2=src2[i2];
long take=v1<v2;
dest[id++]=take?v1:v2;
i1+=take;
i2+=1-take;
//真难想出来，我看的答案。