oohcode

$\bigodot\bigodot^H \rightarrow CODE$

csapp chapter5:优化程序性能

编写高效程序需要几类活动：第一，我们必须选择一组合适的算法和数据结构。第二，我们必须编写出编译器能够优化以转化成高效可执行代码的源代码。本章重点讲的是第二个活动，利用我们对编译器的了解来写出让编译器编译出更高效的机器码的方法。

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

程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作。主要包括消除不必要的函数调用，条件测试和存储器引用。
编译器本身通过复杂精细算法对程序编译时进行了优化。编译器的优化有不同的级别，也是高程度的优化程序的执行效率就越高，但同时也可能增加程序的规模，也可能使标准的调试工具更难对程序进行调试。
编译器必须很小心的对程序只是用安全的优化，也就是说对于程序可能遇到的所有可能情况，在C语言标准提供的保证之下，优化后得到的程序和未优化的版本有一样的行为。
通过一个例子来理解决定一种程序转换是否安全的难度：

1
2
3
4
5
6
7
8
9
10
void twiddle1(int *xp, int *yp)
{
    *xp += *yp;
    *xp += *yp;
}

void twiddle1(int *xp, int *yp)
{
    *xp += 2* *yp;
}

这两个过程似乎有相同的行为。而且twiddle2的效率更高一些，因为twiddle1需要6次存储器引用，而twiddle2只需要三次存储器引用。但是当xp与yp的值相同时，twiddle1中*xp的值时原来的4倍，twiddle2却是3倍。编译器并不知道它们会不会指向同一地址，所以不能进行从twiddle1到twiddle2的优化。
这种两个指针可能指向同一存储器位置的情况称为存储器别名使用(memory aliasing)。编译器对这种情况的优化能力是有限的，所以需要写程序的过程中进行优化。

表示程序性能

引入度量标准每元素的周期数(Cycles Per Element, CPE),作为一种表示程序性能并指导我们改进代码的方法。
处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹(GHz)。就是我们常说的CPU的运行频率。时钟周期就是时钟频率的倒数。

程序示例

举例说明程序优化的效果,这里写出最后的运行函数：

1
2
3
4
5
6
7
8
9
void combine1(vec_ptr v, data_t *dest)
{
    long int 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从平均29左右降到了12左右，效果的确很明显啊。

消除循环的低效率

上面过程在执行for循环的时候调用vec_length函数左右循环测试的条件，也就是说每次执行条件测试的时候都要执行这个函数调用过程，这明显地影响了程序的性能。注意到向量的长度并不会随程序运行发生改变，所以可以考虑只计算一次向量的长度，然后条件测试都用这个值，如下函数：

1
2
3
4
5
6
7
8
9
10
11
void combine2(vec_ptr v, data_t *dest)
{
    long int i;
    long int lenght = vec_length(v);
    *dest = IDENT;

    for (i=0; i < length; i++){
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }

再看修改后的程序，CPE降到了8左右。
这个优化是一种常见的优化例子，称为代码移动(code motion)。这类优化包括识别要执行多次但是计算结果不会改变的计算。编译器会试着进行代码移动，但是对于会改变在哪里调用函数或调用多少次的变换，编译器通常都会非常小心。如果vec_length有某种副作用，那么combine1和combine2可能有不同的行为。为了改进代码，程序员必须经常帮助编译器显式地完成代码的移动。

减少过程调用

过程调用会带来相当大的开销，而且妨碍大多数形式的程序优化。
上面的combine2中，每次循环迭代都会调用get_vec_element来获取下一个向量元素，很明显会照成低效率。对其进行优化的思路就是减少过程的调用，具体如下：

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

void combine3(vec_ptr v, data_t *dest)
{
    long int i;
    long int lenght = vec_length(v);
    data_t *data = get_vec_start(v);

    *dest = IDENT;

    for (i=0; i < length; i++){
        *dest = *dest OP data[i];
    }
}

得到的代码运行速度开得多，这是以损害一些程序的模块性为代价的。
实际情况是，得到的性能提高出乎意料的普通，这是因为5.11讲到的分支预测策略会预计函数的返回值，预测对的情况下直接执行，预测错误的话会有更多的处罚，如果分支预测策略比较好的话，预测正确的概率就高，所以带来的性能问题就越小。

消除不必要的存储器引用

combine3过程中for循环对应的汇编代码如下：

1
2
3
4
5
6
7
.L498:
    movss   (%rbp), %xmm0           #从dest读取数据
    mulss   (%rax, %rdx, 4), %xmm0  #数据相乘
    movss   %xmm0, (%rbp)           #存储结果到dest
    addq    $1, %rdx                #加1
    cmpq    %rdx, %r12              #判断边界条件
    jg      .L498                   # if >, 循环

上面的代码不断从(%rbp)处读取和操作数据，其实可以去掉这个中间寄存器以消除不必要的读写。可以直接利用%xmm0来保存积值。向下面这样：
1
2
3
4
5
.L488:
    mulss   (%rax, %rdx, 4), %xmm0  #数据相乘
    addq    $1, %rdx                #加1
    cmpq    %rdx, %rbp              #判断边界条件
    jg      .L488                   # if >, 循环

对应C代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
void combine4(vec_ptr v, data_t *dest)
{
    long int i;
    long int lenght = 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;
}

编译器不会做出这样的优化还是因为前面提到的存储器别名使用带来的问题。例如： 

1
2
combine3(v, get_vec_start(v)+2);
combine4(v, get_vec_start(v)+2);

执行这两个函数的时候结果就会出现不一致性。

理解现代处理器

上面所说的都是从程序的调用角度考虑的，主要是减少不必要的指令执行，但是并没有运用目标机器的任何特性。随着试图进一步提高性能，我们必须考虑利用处理器微体系结构的变化，也就是处理器用来执行指令的底层系统设计。在实际的处理器中，是可以同时对多条指令求值的，这个现象称为指令级并行。现代处理器取得了不起的功绩之一就是：它们采用复杂而奇异的微处理器结构，其中，多条指令可以并行地执行，同时又呈现一种简单地顺序执行的表象。
程序的最大性能在处理器中主要受到下面两个重要因素的影响：

  • 当一系列操作必须严格顺序执行时，就会遇到延迟界限(latency bound)。因为在下一条指令开始之前，这条指令必须结束。
  • 吞吐量界限(throughput bound)刻画了处理器功能但愿的原始计算能力。这个界限是程序性能的终极限制。

下面通过一些例子说明如何利用现代处理器的流水线，指令级并行等特性提高程序性能：

  • 例子1， 下面代码是对一个数据组求和，根据下面的代码可以

    1
    2
    3
    4
    5
    //combine 1
    for(i = 0; i< limit; i++) 
    {
        acc = acc * data[i];
    }

    下面是这段代码对应的在系统中运行的过程：

    下面是过程的简化：

    其中寄存器xmm0是变量acc对应。可见这段代码中，制约性能的瓶颈就是每次都要进行mul运算，更新acc的值，然后进入下一个循环周期。如何提高这样的程序性能呢？这个运算已经是最简洁的了，但是可不可以考虑减少循环的次数来优化呢？请看下面的这段代码.

  • 例子2， 减少循环周期也可以这么做：
    //combine 2

    1
    2
    3
    for(i = 0; i < limit; i+=2) {
        acc = (acc * data[i]) * data[i+1];
    }

    上面这段代码看似把循环周期减少了一般，但其实性能并没有得到提高，通过他的计算过程可以看到：

    虽然周期减少了一半，但是每个周期却进行了两次运算，而且每次运算都依赖上次计算的结果，也就是acc的值，所以性能并未得到改善。再看例子3。

  • 例子3， 多变量提高并行

    1
    2
    3
    4
    5
    for(i = 0; i < limit; i+=2) 
    {
        acc0 = acc0 * data[i];
        acc1 = acc1 * data[i+1];
    }

    这段代码跟上一段代码的区别是增加了一个变量，也就是增加了对寄存器的使用，其过程如下：

    可以看到同样是减少了周期，但是每个周期的运算使用了不同的计算器，每个计算都不依赖同一周期内的其他值，利用了计算器的并行性，从而提高了程序的性能。还有其它的方式。

  • 例子4, 重新结合变换

    1
    2
    3
    for(i = 0; i < limit; i+=2) {
        acc = acc * (data[i] * data[i+1]);
    }

    这段代码跟例子2很像，只不过改变了运算结合的顺序，程序的性能却得到了很大的提高，这是为什么呢？可以看到这个程序在计算机中计算的过程如下：

    可以看到每个周期也是两个mul操作，为什么会快呢？这是因为第一个mul操作并不依赖寄存器的值，也就是说其实对于data数组之间的运算可以通过流水线并行计算，制约性能的只是acc所在的寄存器的计算，所以性能主要因素还是一个mul的操作。
    从上面可以看到利用多个寄存器可以提高性能，那是不是利用的越多越好呢？答案是：NO.因为计算机的寄存器个数是有限的，如果需要的寄存器的个超过了寄存器的个数，那就只能把这些值放入到栈中，这样就会急剧降低程序的性能。

一些限制因素

影响程序性能的限制因素有下面几个：

  • 寄存器溢出：就是上面最后一段介绍的寄存器不够用时的情况。
  • 分支预测和预测错误处罚：这回提高程序的代价。
  • 其它：如加载的性能，存储的性能等。

提高性能的技术

  1. 高级设计: 为遇到的问题选择适当的算法和数据结构。
  2. 基本编码原则:
    • 消除连续的函数调用
    • 消除不必要的存储器引用：引入临时变量来保持中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。
  3. 低级优化
    • 展开循环，降低开销，并且使得进一步优化成为可能。
    • 通过使用例如多个累积变量和重新结合技术，找到方法提高指令级并行。
    • 用功能得风格重写条件操作，使得编译采用条件数据传送。

(本章完 2014-05-17 22:57:27)

CSAPP