7月 27 2019
0
  1. 编译器的优化能力和局限性
  2. 表示程序性能
  3. 消除循环的低效
  4. 减少过程调用
  5. 消除内存引用

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

编译器的一大安全的优化特点, 就是需要考虑程序所有的情况, 否则运行时可能会出问题. 比如在操作指针的时候, 如果两个参数相同, 其结果可能和希望的不同. 如果编译器无法确定, 则必须假设两个指针有可能指向同一个地方,
那么就限制了优化策略.

例 5.1 内存别名

所谓内存别名, 指的就是两个指针指向同一个位置.

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

这个函数如果两个指针参数相等, 结果无论原来的值是什么, 结果都会把那个值清零.

表示程序性能

有什么指标用来表示程序性能呢, 不同的程序执行的时间不同. 但可以用一个统一的CPE来表示, 就是程序执行中的变量系数.

练习题5.2 比较CPE

    有三个版本的函数执行时钟周期的次数的最小二乘拟合:

  1. 60+35n
  2. 136+4n
  3. 157+1.25n

三个版本执行时间在n值为几的时候是最低的?

实际上, 这是三个一元一次表示的直线, 只要计算出交点, 就可以知道n的取值.

60+35n = 136+4n , 大概计算出 n = 2, 可见n = 1-2的时候, 版本1要比版本2快.

60+35n = 157+1.25n , 大概计算出 n = 2 , 可见n 等于 1 和 2的时候, 版本1最快.

然后比较版本2和版本3 136+4n = 157+1.25n, 计算出 n = 7, 经过比较可以知道 n 在3-7的范围内, 版本2最快.

n大于等于8的时候, 版本三最快.

所谓CPE, 就是这个一元一次方程的系数, 也就是去掉常数执行的时间之外, 真正影响执行效率的系数.

CSAPP使用了一个简单的向量结构的例子和对其的操作, 来教学如何优化程序的运行.

这个向量结构是一个带有向量的长度指示和一个数组来定义的:

typedef long data_t;

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

然后是创建向量和读取向量的函数:

//创建新向量的函数
vec_ptr new_vec(long len){
    //分配内存空间
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    //如果分配不成功, 返回 NULL
    data_t *data = NULL;
    if(!result){
        return NULL;
    }

    result->len = len;

    //如果长度大于0, 就分配相应长度的空间, 如果分配不成功, 释放刚才的result指针
    if (len > 0) {
        data = (data_t *) calloc(len, sizeof(data_t));
        if(!data){
            free((void *) result);
            return NULL;
        }
    }

    result->data = data;
    return result;
}

//从向量结构中读取指定索引的值的函数, 如果成功读取就返回1,  读取失败就返回0
int get_vec_element(vec_ptr v, long index, data_t *dest) {
    //如果索引越界,返回0
    if (index < 0 || index >= v->len) {
        return 0;
    }
    *dest = v->data[index];
    return 1;
}

//获取向量长度的函数
long vec_length(vec_ptr v){
    return v->len;
}

在测试代码性能的时候, 使用如下函数, 这是一个可以将整个向量内的所有元素相乘或者相加的函数:

//通过define IDENT是0或者1, OP是+或者*, 可以方便的计算和和乘
#define IDENT 0
#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;
        //读取第i的索引的值到val中
        get_vec_element(v, i, &val);
        //将val根据OP累计到*dest中
        *dest = *dest OP val;
    }
}

消除循环的低效

仔细观察combine1, 对于过程来说, 这个向量的长度实际上没有变化, 无需在循环中每次都调用过程vec_length(v)来获取长度, 只要在程序开始的时候获取一次, 然后每次都使用这个变量就可以了.

所以将其中的代码移出循环:

void combine2(vec_ptr v,data_t *dest){
    //用局部变量存储向量长度
    long length = vec_length(v);

    long i;
    *dest = IDENT;

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

在移动了之后, 代码的效率大概提升了30%. 这种优化要注意的是, 移出循环的代码不能够对循环依赖的内容产生影响, 否则移出之后, 代码的逻辑会发生变化. 一些为了使用其副作用的函数是不能简单的移出循环的.

所以在编写程序的时候特别要注意, 是不是存在看起来无足轻重, 但实际上具有渐进低效率的小代码. 一个简单的循环可能就会造成n的平方级别的复杂度影响.

练习5.3 判断函数被调用的次数

有四个函数:

  1. long min(long x, long y){ return x < y ? x : y; }, 返回两个数的较小值
  2. long max(long x, long y){ return x < y ? y : x; }, 返回两个数的较大值
  3. void incr(long *xp, long v) { *xp += v; }, 将v加到xp指向的值上
  4. long square(long x){ return x*x;}, 返回x的平方值

判断三个代码片段调用这些函数的次数, 分析如下:

  1.         for(i = min(x, y); i < max(x, y); incr(&i, 1)
            t += square(i);

    首先需要看循环执行了多少次, 无论哪个比较小, 执行循环的次数都是 |x-y|次, 每一次循环都会计算除了min之外的三个函数, 因为他们是在循环体内更新和判断的
    而判断条件会多计算一次, 要比incr的次数多一次

  2.         for(i = max(x,y) - 1, i>= min(x,y); incr(&i, -1)
            t += square(i);

    这个和上一个一样, 也是执行了 |x-y| 次, 除了max函数是初始的条件计算一次. min会计算91次, 剩下的计算90次

  3.             long low = min(x,y)
            long high = max(x,y)
            for(i = low; i < high; incr(&i, 1)
                t += square(i);

    很显然, 一开始调用了一次min和max, 之后不再使用min和max, 只有 incr 和 square 使用了|x-y|次

代码 min max incr square
A. 1 91 90 90
B. 91 1 90 90
C 1 1 90 90

减少过程调用

仔细观察combine2, 里边每次循环都需要使用到 get_vec_element 这个过程. 实际上, 我们在参数中获取了vec_ptr v这个参数, 可以通过v获取数组的指针, 然后通过length来直接操作指针即可, 这样就省去了每次调用过程的固定开销, 为此可以编写combine3函数如下:

void combine3(vec_ptr v, data_t *dest) {
    long length = vec_length(v);
    long i;
    *dest = IDENT;

    //直接获取数组的首元素指针, 不再调用函数
    data_t *ptr = v->data;

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

注意, 这是为了优化程序的性能. 如果有着较高的模块化需求, 实际上是在破坏模块化. 但这里主要是为了性能提升.

理论上, 这会进一步提高效率, 因为省去了call ret 和加载过程的一系列必须的指令. 不过实际上对于这段代码, 没有提高效率, 这是因为分支预测可以有效的预测到执行成功的情况. 只有最后一次预测错误, 所以错误惩罚很小. 总体时间几乎没有变动.

但如果函数执行的结果非常难以预测, 这样就能进一步提高效率.

消除内存引用

继续观察combine3, 可以发现, 每次dest的值发生变化的时候, 必须先从dest中读出值, 然后相加, 再写入到dest中去. 在整个计算的过程中, dest本身一直相当于一个临时变量, 在每次循环中被更改.

然而, 读取内存的开销要比读取寄存器大的多. 完全可以设置一个临时变量, 让编译器通过寄存器来保存这个临时变量, 等到循环结束的时候, 将临时变量的值写入dest. 这样只执行了一次写操作.

根据这样的思路, 可以编写出combine4函数:

void combine4(vec_ptr v, data_t *dest) {
    long length = vec_length(v);
    long i;
    data_t *ptr = v->data;

    //这行不要了, 无需读出dest
    //*dest = IDENT;

    //创建临时变量
    data_t total = IDENT;


    for (i = 0; i < length; i++) {
        total = total OP ptr[i];
    }

    //只写一次dest
    *dest = total;

}

经过这样处理之后, 可以看到程序的性能有了显著的提高, 这说明开销很大的内存访问, 能减少就尽量减少, 争取让计算都在寄存器内完成.

练习 5.4 比较两个级别的优化代码

寄存器在-O2生成的代码的作用相当于一个临时变量, 用于不断累积相乘的0, 最后一次性将%xmm0写回到dest的地址. 在-O1中, %xmm0的作用是每次存放读出的dest, 然后进行运算.

很显然, -O2级别生成的代码是类似于combine4而不是combine3函数的,所以没有忠实的实现combine3.

但是-O2的代码相比combine4, 还有一个问题就是循环中每次都会使用 vmovsd %xmm0, (%rbx) 来更新dest, 而combine4中, 更新dest是在循环结束之后, 这就造成了 -O2 级别优化的代码相比combine4, 性能还是略有不足.

通过上边的几个技巧, 可以在不依赖目标机器的任何特性下, 就可以通过降低执行过程的开销, 来大幅度的提高性能.

如果想要进一步优化, 就必须了解目标机器的特点, 利用指令集和并行计算的能力, 进一步将程序优化.

发表于计算机基础

发表评论

邮箱地址不会被公开。 必填项已用*标注