CSAPP：优化程序性能

发表于   |   分类于

你能获得的对程序对大的加速比就是当你第一次让它工作起来的时候。
–John K.Ousterhout

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

下面的代码1不能优化为代码2：

代码1：

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

代码2： 

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

看起来两段代码是一样的，但是考虑一下，如果 xp 和 yp 相等的情况，前者xp的值会翻4倍，而后者是3倍。编译器必须假设参数 xp 和 yp 可能相等，所以不能将代码2作为代码1 的优化版本。

两个指针可能指向同一个存储位置的情况称为存储器别名使用。如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，限制了可能的优化策略。如下， p 和 q 可能是指向同一个位置，故不能安全地优化：

x = 1000; y = 3000;
*p = x;
*q = y;
t = *q; // 1000 or 3000

如果可以确定 p 或者 q 是同一个位置或者不是同一个位置，就可以直接优化成赋值。考虑下面的swap程序：

void swap(int *xp, int *yp) {
    *xp += *yp;
    *yp = *xp - *yp;
    *xp = *xp - *yp;
}

这是一种很常见的trick方法，但是考虑存储器别名使用的情况，即 xp 和 yp 相同的情况下， 结果是会被置零。所以为了一般性，不应该适用这样的swap代码。

当函数有副作用时不能对多次调用的函数进行“想当然的”优化，比如 fun()+fun()+fun() 和 3 * fun() 在fun有副作用的时候就不是等价的。一种对函数调用的可能的优化是使用内联函数替换函数调用。即将函数调用转换为函数体。减少了函数调用的开销，也允许对生成的代码进行进一步的优化。这种优化在 -O2 或者更高的等级，或者使用编译选项 -finline 时进行。

消除低效率的循环

类似于把strlen从for循环的条件判断中移出，使用一个临时变量替代，把循环体中的重复计算使用临时变量替换。考虑函数调用的副作用和存储器别名的情况，编译器并不会对这样的重复计算进行优化，需要程序员手动实现。

优化：消除不必要的存储器引用

对存储器的引用，也就是内存读取是一个很低效率的操作，在循环中，如果能消除对存储器的引用可以大大提高程序的效率。看下面的一个例子，这是CSAPP Page.336(chapter 5.5)中的示例。

void combine(vec_ptr v, data_t *dest) {
    long int i;
    long int length = vec_length(v);
    data_t *data = v->data;
    *dest = 1;
    for (i=0; i<length; i++) {
        *dest = *dest * data[i];
    }
}

这段代码简单理解就是vec_ptr结构有一个 *data_t 的域（即data_t的数组），要对所有元素连乘。这里如果查看gcc 的汇编代码可以发现，在循环中多次存储计算结果到dest，因为dest是一个存储器位置（一个指针），我们可以消除这种无用的存储器读取，只把最后计算的记过写入到 *dest 就可以了。
只需要引入一个局部变量即可。

void combine2(...) {
    ...
    data_t *data = v->data;
    data_t acc = 1;
    for (i=0; i<length; i++) {
        acc = acc * data[i];
    }
    *dest = acc;
}

这样临时计算的结果保存在acc中，acc会被保存在一个寄存器中，而不会多次保存到存储器。在循环比较大时能获得不错的性能提升。

循环展开

循环展开是一种程序变换，通过增加每次迭代计算的数量，减少循环的迭代次数。循环展开从两个方面提高性能：首先它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支；其次它提供了一些方法可以进一步变化代码，减少整个计算中关键路径上的操作数量。

进行循环展开要注意循环索引上界（下界）的确定，展开为K次，则上限设置为 n-k+1 。对于可能最后没有遍历到的情况使用一个额外的循环解决。

通过一些实验发现，循环展开只对证书的加法和乘法有性能提升，对于浮点数的加法与乘法并无效果。展开到2-3次就达到了很好的效果。太多层的展开并无更大好处。

有的编译器能自动执行循环展开优化，使用选项 -funroll-loops 会执行循环展开。

提高并行，打破顺序相关

在之前的combine函数中，使用了临时变量和循环展开的优化策略达到了不错的效果，但是由于乘法运算的每一步都是基于之前计算的累积值的，在之前的计算完成之前都不能计算acc的新值。这是合并操作的延迟。我们可以使用一些方法打这种顺序相关。

多个累计变量

一种直观的想法就是使用多个累积值，把待操作数（循环）划分为两路计算。比如下面的示例：

void combine6(vec_ptr v, data_t *dest) {
    long int i;
    long int length = vec_length(v);
    long int limit = length -1;
    data_t *data = v->data;
    data_t acc0 = 1;
    data_t acc1 = 1;

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

得益于处理器的流水线技术，这样的两路划分能获得不错的效果，并且对浮点数运算也有效果。不过由于浮点数的乘法和加法都是不可结合的，由于四舍五入或者溢出，combine6可能产生和之前方法不同的结果。
不过注意到如果数据非常奇葩比如所有个偶数都非常大，所有奇数都非常的小，这样可能使用顺序求值不会溢出，而使用两路划分计算就会溢出。虽然这样的情况在现实程序中很几乎不可能遇到，但是这确实也有可能。

重新结合变换

对于上面的combine函数，考虑下面两种不同的结合方式：

// 结合1
acc = (acc * data[i]) * data[i+1];
// 结合2
acc = acc * (data[i] * data[i+1]);

这两个看起来本质上是一样的，但是对于浮点数的运算，第二种结合方式会得到很大的性能提升（CSAPP Page 355）。而对于整数，由于证书本身是可结合的，其影响可以忽略不计。

之所以浮点数性能提升，是由于使用第二种方式结合，能更好地利用流水线能力。GCC对自动对整数运算进行重新结合，但并不是总有好的效果。
重新结合变换并不是总会带来好的结果，所以实际中它带来的差距并不重要。也就是可用可不用啦。

基本完