编译器的优化能力和局限性
编译器的一大安全的优化特点, 就是需要考虑程序所有的情况, 否则运行时可能会出问题. 比如在操作指针的时候, 如果两个参数相同, 其结果可能和希望的不同. 如果编译器无法确定, 则必须假设两个指针有可能指向同一个地方,
那么就限制了优化策略.
例 5.1 内存别名
所谓内存别名, 指的就是两个指针指向同一个位置.
void swap(long *xp, long *yp){ *xp = *xp + *yp; *yp = *xp - *yp; *xp = *xp - *yp; }
这个函数如果两个指针参数相等, 结果无论原来的值是什么, 结果都会把那个值清零.
表示程序性能
有什么指标用来表示程序性能呢, 不同的程序执行的时间不同. 但可以用一个统一的CPE来表示, 就是程序执行中的变量系数.
练习题5.2 比较CPE
-
有三个版本的函数执行时钟周期的次数的最小二乘拟合:
- 60+35n
- 136+4n
- 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 判断函数被调用的次数
有四个函数:
long min(long x, long y){ return x < y ? x : y; }
, 返回两个数的较小值long max(long x, long y){ return x < y ? y : x; }
, 返回两个数的较大值void incr(long *xp, long v) { *xp += v; }
, 将v加到xp指向的值上long square(long x){ return x*x;}
, 返回x的平方值
判断三个代码片段调用这些函数的次数, 分析如下:
-
for(i = min(x, y); i < max(x, y); incr(&i, 1) t += square(i);
首先需要看循环执行了多少次, 无论哪个比较小, 执行循环的次数都是 |x-y|次, 每一次循环都会计算除了min之外的三个函数, 因为他们是在循环体内更新和判断的
而判断条件会多计算一次, 要比incr的次数多一次 -
for(i = max(x,y) - 1, i>= min(x,y); incr(&i, -1) t += square(i);
这个和上一个一样, 也是执行了 |x-y| 次, 除了max函数是初始的条件计算一次. min会计算91次, 剩下的计算90次
-
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, 性能还是略有不足.
通过上边的几个技巧, 可以在不依赖目标机器的任何特性下, 就可以通过降低执行过程的开销, 来大幅度的提高性能.
如果想要进一步优化, 就必须了解目标机器的特点, 利用指令集和并行计算的能力, 进一步将程序优化.