//程序优化示例
//待优化程序:
//定义一个抽象类型data_t，这里data_t可以被声明为int float double; typedef int data_t ;
typedef struct
{
int len;
data_t *data;
}vec_rec ,*vec_ptr;
#define IDENT 0
#define OPER +
#define IDENT 1
#define OPER *
//创建向量组
vec_rec new_vec(int len)
{
vec_ptr result=(vec_ptr) malloc(sizeof(vec_rec));
if(!result)
return NULL;
result->len=len;
if(len>0){
data_t * data = (data_t*)calloc(len,sizeof(data_t));
if(!data){
free((void*)result);
return NULL;
}
result->data=data;
}
else
result->data=NULL;
return result;
}
//获取向量元素
int get_vec_element(vec_ptr v,int index, data_t * dest) {
if(index<0 || index>=v-len)
return 0;
*dest = v->data[index];
return 1;
}
int vec_length(vec_ptr v)
{
return v->len;
}
//初始版本
void combine1(vec_ptr v,data_t * dest)
{
int i;
*dest=IDENT;
for(i=0;i<vec_length(v);i++){
data_t val;
get_vec_element(v,i,&val);
*dest=*dest OPER val;
}
}
/*过程combine1调用vec_length(v)作为for循环的测试条件,影响了程序的性能对于整数加法的CPE(每元素周期数)为31.25,乘法的CPE为
33.25。
所以我们对其进行优化。
*/
/*对于我们只是将vec_length过程移出循环，这个过程成为代码移动的优化
而这样的移动能将每个元素消除了10个时钟周期，加法的CPE变为20.66
乘法的 CPE变为21.25。
这种移动在处理大型数据时尤为重要，会严重影响程序的性能。
*/
//改进版本1 消除循环低效率
void combine2(vec_ptr v,data_t * dest)
{
int i;
int length=vec_length(v);
*dest=IDENT;
for(i=0;i<length;i++){
data_t val;
get_vec_element(v,i,&val);
*dest=*dest OPER val;
}
}
/*从combine2 的代码中可以看出,每次循环都会调用get_vec_element
来获得一个元素，这个过程开销特别大，因为它要进行边界检查
所以我们对其进行优化，我们增加一个函数 get_vec_start
这个函数返回数组的起始地址.*/
data_t * get_vec_start(vec_ptr v)
{
return v->data;
}
//改进版 2 减少过程调用
void combine3(vec_ptr v,data_t * dest)
{
int i;
int length=vec_length(v);
data_t * data=get_vec_start(v);
*dest=IDENT;
for(i=0;i<length;i++){
*dest=*dest OPER data[i];
}
}
/*通过改进后的combine3的加法CPE降到6.00 ,乘法降到9.0 达到了将近3.5倍的性能.*/
/*我们继续对combine3进行汇编分析）(假设为乘法):
%ecx指向data,%edx指向i,%edi指向dest
1: .L18：
2 mov1 (%edi),%eax //读取 *dest
3 imull (%ecx,%edx,4),%eax //*dest *data[i]
4 movl %eax,(%edi)
5 incl %edx
6 cmpl %esi,%edx
7 jl .L18
指令2读取存放在dest中的值，指令4写回这个位置。
这正是降低性能的原因，因为下一次迭代时指令2
读取的值会是刚刚写回得那个值。
所以在优化过程中引入一个临时变量x，它用在循环中存放
计算出来的值，只有在完成循环后才存放在*dest中。
*/
//改进版本3 减少存储器引用
void combine4(vec_ptr v,data_t * dest)
{
int i;
int length=vec_length(v);
data_t * data=get_vec_start(v);
data_t x=IDENT;
*dest=IDENT;
for(i=0;i<length;i++){
x=x OPER data[i];
}
*dest=x;
}
/*
改进后我们发现汇编代码为:
1 L.24：
2 imull (%eax,%edx,4),%ecx
3 incl %edx
4 cmpl %esi,%edx
5 jl .L24
我们发现每次迭代的存储器操作从
两次读和一次写减少到只需要一次读
加法CPE 将为2.00 乘法的CPE 4.00
*/
/*在这看似已经很好了，但是当我们理解了现代处理器的工作
工程后，还可以对combine4进行进一步的优化:
因为每条迭代包括四条指令，但是只有两个功能单元能够执行
这些指令，四条指令中一条是对程序数据操作的，其他都是
计算循环的索引和测试循环条件的循环开销部分
因此，我们可以在每次迭代中执行更多的数据操作来减少
循环开销的影响，这就是一种叫做“循环展开”的技术.
*/
//改进版本4 降低循环开销
void combine4(vec_ptr v,data_t * dest)
{
int i;
int length=vec_length(v);
int limit =length-2;
data_t * data=get_vec_start(v);
data_t x=IDENT;
*dest=IDENT;
for(i=0;i<limit;i+=3){
x=x OPER data[i] OPER data[i+1] OPER data[i+2];//循环展开}
for(;i<length;i++){
x=x OPER data[i];
}
*dest=x;
}
//如果循环展开k次，我们就把上限设为n-k+1，则最大循环索引
//i+k-1会比n小。
我们加上第二个循环，以每次处理一个元素的方式
//处理最后几个元素，这个循环体将会执行0~2次。