CSAPP 学习笔记「优化程序性能」

第四章的处理器体系结构是被我直接跳过了的。

程序员必须再实现和维护程序的简单性与它的运行速度之间做出权衡。

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

编译器必须很小心地对程序只使用安全的优化。程序中有两个妨碍优化的因素。

存储器别名使用
```
  void twiddle1 (int *xp, int *yp){
      *xp += *yp;
      *xp += *yp;
  }
```
```
  void twiddle2 (int *xp, int *yp){
      *xp += 2 * *yp;
  }
```
编译器并不会把第一个函数优化成第二个函数，因为如果考虑到 xp 等于 yp 的情况。twiddle1 中的 xp 会增加 4 倍，而 twiddle2 中的 xp 仅会增加 2 倍。
函数调用

作为一个示例，考虑下面这两个过程：
```
  int f();
	
  int func1() {
      return f() + f() + f() + f();
  }
	
  int func2() {
      return 4 * f();
  }
```
编译器也不会吧第一个函数优化为第二个，考虑下面 f 的代码：
```
  int counter = 0;
	
  int f() {
      return counter++;
  }
```
这个函数有个副作用：它修改了全局程序状态的一部分。改变调用它的次数会改变程序的行为。

###程序示例

考虑下面所示的简单向量数据结构：

typedef int data_t;

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

一段合并运算的代码：

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;
	}
}

其中 vec_length 获取 v 的长度，get_vec_elemnet 获取内容。

特别的，使用声明：

#define IDENT 0
#define OP +

它对向量的元素求和。

#define IDENT 1
#define OP *

它计算的是向量元素的乘积。

###消除循环的低效率

void combine2(vec_ptr v, data_t *dest)
{
	long int i;
	long int length = vec_length(v);
	*dest = IDENT;
	for(i = 0; i < length; i++){
		data_t val;
		get_vec_element(v, i, &val);
		*dest = *dest OP val;
	}
}

这种优化我们称之为代码移动。

###减少过程调用

在 combine2 中，每次循环都要调用 get_vec_element ，为了减少过程调用，代码如下:

data_t * get_vec_start(vec_ptr v)
{
	return v->data;
}


void combine3(vec_ptr v, data_t *dest)
{
	long int i;
	long int length = vec_length(v);
	data_t *data = get_vec_start(v);
	
	*dest = IDENT;
	for(i = 0; i < length; i++){
		*dest = *dest OP data[i];
	}
}

但是这段代码得到的性能提高出乎意料的普通，只提高了整数求和的性能。

###消除不必要的存储器引用

在我们将 combine3 生成汇编代码后，可以看出，在每次迭代中，程序都要读取出指针 dest 处的值，乘以 data[i]，再将结果存回到 dest。这样的读写显得很是浪费。

考虑如下代码：

void combine4(vec_ptr v, data_t *dest)
{
	long int i;
	long int length = 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;
}

我们引入一个临时变量 acc，它在循环中用来累计计算来的值。只有再循环完成之后结果才存放到 dest 中。在汇编代码中可以看到，编译器会使用一个寄存器来保存累积值。与 combine3 中的循环相比，我们将每次迭代的存储器操作从两次读和一次写减少到只需要一次读。

###循环展开

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

void combine5(vec_ptr v, data_t *dest)
{
	long int i;
	long int length = vec_lenght(v);
	long int limit = length - 1;
	data_t *data = get_vec_start(v);
	data_t acc = IDENT;
	
	for (i = 0; i < limit; i += 2) {
		acc = (acc OP data[i]) OP data[i + 1];
	}
	
	for (; i < length; i++) {
		acc = acc OP data[i];
	}
	
	*dest = acc;
}