60:程序性能优化(1)

对于特定的程序而言，尤其是要长时间多次运行的程序而言，我们需要尽可能的优化他的效率。如计算效率，空间效率…大多数时候编译器会帮助我们完成这个工作，但是特定的场景中，我们需要自己实现程序的优化设计。

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

在现代编译器中，编译器往往会通过各种复杂的算法，根据程序中的值，被计算被使用的过程，来优化程序的实现。其中以GCC为例，编译器为我们提供了一系列指定优化级别，如-Og是使用一些基本的优化。使用-O1 -O2 -O3则会使用更多的优化。但是可能会导致一些未定义的复杂的情况出现。

我们需要保证编译器对程序只进行安全的优化，也就是说对于程序所有可能遇到的情况，在C语言标准之下，优化后得到的程序和优化前得到程序应该有相同的行为。我们可以看下面的一个范例：

void twiddle1(long *xp,long *yp){
    *xp += *yp;		//两次读一次写
    *xp += *yp;		//两次读一次写
}
void twiddle2(long *xp,long *yp){
    *xp += 2* *yp	//两次读一次写
}

看上去，两个程序似乎有这相同的行为，而且看起来twiddle2有着更好的效率。但是实际上，当我们考虑xp=yp的情况时。我们发现twiddle1和 twiddle2的结果并不一样。所以编译器不应该将twddle2做为twiddle1的优化版本。

这种两个指针可能指向同一个内存位置的情况，我们称之为内存别名使用。在编译器优化中，我们必须假设不同的指针可能会指向内存中的同一个位置。这是妨碍优化的第一个因素。

第二妨碍优化的因素是函数调用，我们假设下面的这个范例：

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

我们乍一看可能认为func1和func2效果是相同的，实际上，当我们考虑如下情况时：

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

这个时候就会产生不一样的结果，这是因为这个函数有副作用——它修改了全局程序状态的一部分。改变调用它的次数，会的改变程序的行为。

如果编译器不会试图判断一个函数有没有副作用，那可能会被错误的优化成func2。相反，则会保持函数调用不变。不过还有现代编译器也会使用一种特殊的手段来实现这种优化——内联函数替换。如func1可能会被内联替换成：

long func1in(){
    long t = counter++; 	//+0
    t += counter++;			//+1
    t += counter++;			//+2
    t += counter++;			//+3
    return t;
}

这样的话就减少了函数调用的开销。同时我们可以实现进一步的优化：

long func1opt(){
    long t = 4*counter + 6;
    counter += 4;
    return t;
}

我们可以在gcc中使用-finline和-O1以上等级的优化实现这个优化。但是这个优化也有一定的代价，我们将函数调用的过程优化掉了，意味着我们不能在调试器中，跳转到对应的程序，这意味程序行为一定程度上的失真。

程序示例

为了说明一个抽象的程序是如何被系统地转换成更有效的代码的，我们使用一个基于下面的是向量数据结构的运行示例。

向量有两个内存块组成：头部和数据数组，其中头部的结构声明如下：

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

这个声明由data_t来表示基本元素的数据类型，我们可以指定类型给data_t。同时，我们还会分配一个len个data_t类型对象的数组，来存放实际的向量元素。

我们给出一个生成向量，访问向量元素，以及确定向量长度的基本过程：

//生成指定长度的向量数组
vec_ptr new_vec(long len){
	//分配向量头部的空间
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    data_t *data = NULL;
    if(!result)
        return NULL;	//分配失败
    result->len = len;
    //分配数组的空间
    if(len>0){
        data = (data_t*)calloc(len,sizeof(data_t));
        if(!data){
            free((void *)result);
            return NULL;	//分配失败
        }
    }
    result->data = data;
    return result;
}

//访问向量中的指定元素并存储在指定空间中
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;
}

我们在此基础上实现一个合并运算的实现，通过对基本元素IDENT和合并运算OP的不同声明，我们测量这个函数对不同运算的性能：

#define IDENT 0
#define OP +
//#define IDENT 1
//#define OP *
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
    }
}

下面我们会给出程序的CPE效率（数值越小性能越好），以参考：

消除循环的低效率

我么可以看到过程combine1调用函数vec_length作为for循环的测试条件。这导致每次循环测试的过程中我们都会有一次函数调用开销，我们可以通过以下方式来减少这个开销：

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;
    }
}

效果如下：

这个优化是一个常见的优化，叫做代码移动。这类优化包括识别要执行多次，但是计算结果不会改变的计算。因为可以将计算移动到不会被多次求值的部分。

很遗憾的是，现在的编译器并不能很好的实现这一点。这个看起来无足轻重的代码，实际上在循环次数高的使用环境下，极大的影响了程序的效率。

减少过程的调用

正如我们刚刚所提到的，在循环测试中的过程调用会导致程序的性能下降，同样的在循环体中的过程调用也会导致性能的开销。在我们的代码中，可以看到每次循环迭代都会调用get_vec_element，这个函数会对索引做边界检测，然后再获取指定的数据。

在这里我们可以简化这个过程，我们定义一个新的函数以获取向量的起始位置，然后通过数组索引访问，从而实现对元素的访问。避免在循环体中的过程调用：

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++){
        *dest = *dest OP data[i];
    }
}

效果如下：

令我们吃惊的是，性能并没有明显的提升。事实上，整数求和的性能还略有下降。显然是内存循环中的其他操作形成了瓶颈，限制性能超过调用get_vec_element我们之后还会在此回头看看这个现象。看看为什么combine2中反复的边界检查不会让性能更差。

消除不必要的内存引用

combine3的代码将合并运算的值累积在指针dest指定的位置。通过检查编译出来的内循环代码我们可以看出，每次我们对指定位置的计算都需要先从内存中取出，再重新存入。在此我们给出的数据类型为double,合并运算为乘法的汇编为：

在这里我们可以看出每次迭代都需要从内存中读出再写入内存。这样的内存读写十分浪费，我们应该先用一个临时寄存器来存储每次迭代后的值，等到迭代结束后，再将值写入内存，从而避免不必要的内存引用:

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++){
        acc = acc OP data[i];
    }
    *dest = acc;
}

效果如下：

我们可以看到程序性能显著的提升。但是遗憾的是，编译器无法实现这个简单的变换，因为在大多数情况下，编译器并不能判断函数会在什么情况下被调用，以及程序员的本意是什么。所以在编译的过程中，往往只能进行保守的读写内存。

理解现代处理器

到现在为止，我们所运用的优化都是不依赖于目标机器的任何特性的。这些优化只是简单的降低了过程调用的开销，以及消除了一些妨碍优化的因素。但是随着进一步提高性能，我们必须考虑利用处理器微体系结构的优化，也就是处理器用来执行指令的底层系统设计。

实际上处理器的实际操作与通过观察机器级程序所察觉到的大相径庭。在代码级别上，我们认为程序是一条一条执行的，实际上，在实际的处理器中，使同时对多条指令求值的，我们称这个现象叫做指令并行.

我们对指令并行的认识来理解是什么限制了程序的最大性能：

当一系列操作必须按照严格顺序执行时，就会遇到延迟界限，因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用指令并行的功能时，延迟界限能够限制程序性能
吞吐量界限刻画了处理器功能单元的原始计算能力。这个界限时程序性能的终极限制。

整数操作

这是现代微处理器的一个简单的示意图。这和我们认知的处理器结构并不一样，我们称这种处理器是超标量的，意味着它可以在每个时钟周期执行多个操作，而且是乱序的——意味着指令执行的顺序并不一定要和它们在机器级程序中的顺序是一样的。整个设计由两个主要部分：控制单元和执行单元。前者负责从内存中读出指令序列，并根据指令序列生成一组针对程序数据的基本操作；后者负责执行这些操作。

ICU（控制单元）从指令高速缓存中读取指令，指令高速缓存是一个特殊的存储器，它包含最近访问的指令。ICU会在当前正在执行的指令很早之前取指，这样它才有足够的时间译码，并把操作发送到EU（执行单元）。同时处理器会使用分支预测预测目标地址，并使用投机执行的技术，处理器会开始取出位于它预测分支的地址的指令，在预测之前正确之前就执行这些操作。如果之后发现预测错误，则将状态重新设置到分支点的状态，并开始取出并执行另一个方向上的指令。

指令译码逻辑将接受实际的程序指令，并将它们转换成一系列的微操作。然后EU接受来自取指单元的操作。通常每个时钟周期会接受多个操作。这些操作被分配到功能单元中执行。

读写内存是由加载和存储单元实现的。加载单元处理从内存读数据到处理器的操作。存储单元处理从内存读数据到处理器的操作。这两个单元都有一个加法器来完成地址的计算。图中的数据高速缓存是一个高速存储器，存放着最近访问的数值。

使用投机执行结束对操作求值，但是最终结果不会存放在程序寄存器和数据内存中，直到处理器确定（确定预测是否正确）实际应该执行这些指令，分支操作被送到EU。如果预测错误，EU会丢弃分支点之后计算出来的结果。它还会发送信号告诉分支单元，说预测是错误的，并指出正确的目的和分支。

在ICU中，退役单元记录正在进行的处理，确保它们遵守机器级程序的顺序语义。退役单元控制这些寄存器的更新。指令译码时，关于指令的信息被防止在一个先进先出的队列中。这个信息会一直保持在队列中，直到发生：

一条指令的操作完成了，而且所有引起这条指令的分支点也都被确认为预测正确，那么这条指令就退役了，所有对程序寄存器的更新都可以被实际执行了。
如果引起该指令的某个分支点预测错误，这条指令会被清空，丢弃所有计算出来的结果。这样预测错误就不会改变程序的状态。

由于任何对程序寄存器的更新都是在指令退役的时候进行。为了加速从一条指令到另一条指令的结果的传送，许多信息都是在执行单元之间进行交换的，原理和之前的转发原理相同，只不过更加复杂精细。

实现操作数在执行单元间传送的常用机制是寄存器重命名。当一条更新寄存器r的指令译码时，产生一个标记t（一个执行该操作结果的唯一的标识符）。条目（r，t）被加入一张表中，这个表维护着每个程序寄存器与会更新该寄存器的操作的标识符间的关系。当某个执行单元执行完一个操作时，会产生一个结果（v，t）指明标记为t的操作产生值v。所有等待t为源的操作都能使用v作为源值，这就是一种形式的数据转发。

通过这个机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件中再读出来，使得第二个操作能够再第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目。如果一条被译码的指令需要某寄存器，但是又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。

性能瓶颈

想要理解程序的性能，首先我们要能理解程序中的关键路径延迟。在迭代中，影响性能瓶颈的是迭代寄存器（在迭代中被更新，既作为操作数又作为结果的寄存器）的更新速度。因为其他的操作是可以利用现有的数据进行并行计算的，我们可以以下面的一个问题为例：

多项式求值

a₀ + a₁X + a₂X² + ……. + a_nXⁿ

这个求多项式的过程可以用下面的函数实现：

double poly(double a[],double x,long degree){
    long i;
    double result = a[0];
    double xpwr = x;
    for (i=1;i<=degree;i++){
        result += a[i]*xpwr;
        xpwr = x*xpwr;
    }
    return result;
}

Horner法多项式求值(减少乘法数量)

a₀ + X ( a₁ + X (a₂ + …… + X (a_n-1 + Xa_n) … ))

这个求值过程，我们可以使用下面的函数实现：

double polyh(double a[],double x,long degree){
    long i;
    double result = a[degree];
    for (i=degree-1;i>=0;i--)
        result = a[i] + x*result;
    return result;
}

乍一看我们会认为下面的方法更加高效，因为相较于上面的程序，它只使用了一次乘法。但是事实真的是这样的嘛，我们测得poly的CPE比polyh更低。这是为什么呢？

我们可以判断程序的性能瓶颈主要体现在循环迭代的过程中，而迭代的性能是由迭代寄存器的更新的速度决定的。我们可以看到两个函数对迭代寄存器的更新情况：

poly：他有两个迭代对象，分别是result和xpwr，由于数据的关联性，两个数据的迭代是互不干扰的。而制约迭代性能的关键则是xpwr的更新——一次乘法。
polyh：它只有一个迭代对象result，它的每次更新需要一次乘法和一次加法，由于数据依赖的关联性，加法与乘法并不能并行处理。

所以综上所述，程序的性能实际上是由关键路径延迟所决定的，而不是由整体的运算量决定的。