关于程序的性能优化-part2

实例为了说明一个抽象程序是如何被系统转换为更有效地代码的，之后的例子我们将使用如下的向量数据结构的运行示例，向量由两个内存块表示：头部和数据数组。
头部是一个声明如下的结构：

/* Create abstract data type for vector */typedef struct { long len; data_t *data;} vec_rec, *vec_ptr;
这个声明用data_t来表示基本元素的数据类型。在测试中，我们度量代码对于整数和浮点数数据的性能。为此，会分别为不同的类型声明编译和运行程序，像下面这个例子对数据类型long一样：
typedef long data_t;我们还会分配一个len个data_t类型对象的数组，来存放实际的向量元素。
如下给出的是一些生成向量，访问向量元素以及确定向量长度的基本过程。值得注意的是向量访问函数get_vec_element,它会对每个向量引用进行辩解检查。类似于很多其它语言所使用的数组表示法。边界检查降低了程序出错的机会，但会减缓程序的执行。
向量抽象数据类型的实现，在实际的程序中，数据类型data_t会被声明为明确的数据类型如int或float：

/* Create vector of specified length /vec_ptr new_vec(long len){ / Allocate header structure */ vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec)); data_t data = NULL; if (!result) return NULL; / Couldn’t allocate storage / result->len = len;/ $end vec / / We don’t show this in the book / result->allocated_len = len;/ $begin vec / / Allocate array */ if (len > 0) { data = (data_t *)calloc(len, sizeof(data_t));if (!data) { free((void ) result); return NULL; / Couldn’t allocate storage /} } / data will either be NULL or allocated array / result->data = data; return result;}/ Free storage used by vector /void free_vec(vec_ptr v) { if (v->data)free(v->data); free(v);}/ * Retrieve vector element and store at dest. * Return 0 (out of bounds) or 1 (successful) */int get_vec_element(vec_ptr v, long index, data_t *dest){ if (index < 0 || index >= v->len)return 0; dest = v->data[index]; return 1;}/ Return length of vector /long vec_length(vec_ptr v){ return v->len;}
作为一个优化的示例，如下的代码会使用某种运算，将一个向量中所有的元素合并为一个值，通过使用编译时常数IDENT和OP的不同定义，这段代码可以重编译为对数据进行不同的运算。
这是一个合并运算的初始实现，通过定义IDENT和OP，可以用来测试该函数对不同运算的性能：
/ Implementation with maximum use of data abstraction */void combine1(vec_ptr v, data_t *dest){ long i; *dest = IDENT; for(i = 0; i < vec_length(v); i++) { data_t val; get_vec_element(v, i, &val); *dest = *dest OP val; }}在之后我们会对这段代码进行一系列的优化，为评估性能优化，会在一个参考机上测量函数的CPE性能。
以下是combine1的CPE度量值

函数	方法	整数 (+)	整数 (*)	浮点数 (+)	浮点数 (*)
combine1	抽象的未优化的	22.68	20.02	10.12	10.12
combine1	抽象的-O1	19.98	20.18	10.17	11.14

未经优化的代码是从C语言代码到机器代码的直接翻译，通常效率较低，简单的使用命令行选项”-O1”，就会进行一些基本的优化，这样就可以显著提升性能。
消除循环的低效率可以观察到，过程combine1调用函数vec_length作为for循环的测试条件。在循环中，每次循环迭代时都必须对测试条件求值。另一方面，向量的长度并不会随着循环的进行而改变。因此，我们只需要计算一次向量的长度，然后在我们的测试条件中都会使用这个值。
以下是一个修改了的版本，称为combine2，它在开始时就调用了vec_length,并且将结果赋值给局部变量length。对于某些数据类型和操作，这个变换明显地影响了某些数据类型和操作的整体性能，对于其他的则很小甚至没有影响。无论哪种情况，都需要这种变化来消除这个低效率，这有可能称为尝试进一步优化时的瓶颈。
改进循环测试的效率，通过把vec_length的调用移出循环，不需要每次迭代都执行该函数。

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

函数	方法	整数 (+)	整数 (*)	浮点数 (+)	浮点数 (*)
combine1	抽象的-O1	10.12	10.12	10.17	11.14
combine2	移出vec_length	7.02	9.03	9.02	11.03

这是一类常见的优化，称为代码移动（code motion）。这类优化需要识别执行多次但是计算结果不会改变的计算。因而可以将计算移动到代码前面不会被多次求值的部分。
优化编译器会试着进行代码移动。不过，对于会改变在哪里调用函数或调用多少次的变换，编译器会非常小心。他们不能够可靠的发现一个函数是否会有副作用，因而会假设函数有副作用。例如，vec_length函数由某周副作用，那combine1和combine2可能就会有不同的行为。为了改进代码，程序员一般要显式的完成代码移动。
减少过程调用如我们所知，过程调用会带来开销，而且妨碍大多数形式的程序优化。从combine2的代码可以看出，每次循环都要调用get_vec_element来获取下一个向量元素。对于每个向量调用，这个函数要把向量索引i与循环边界做比较，很明显会造成低效率。在处理任意的数组访问时，边界检查是很有用的特性，但是对combine2代码的简单分析表明所有的引用都是合法的。
作为替代，假设为我们的抽象数据类型增加一个函数get_vec_start。这个函数返回数组的起始地址。之后我们可以写出图三的函数，其内循环里没有函数调用。它没有用函数调用来获取每个向量元素，而是直接访问数组。虽说这种变换损害了程序的模块性，但是在获取高性能结果的路上，这是必要步骤。

data_t *get_vec_start(vec_ptr v){ return v->data;}void combine3(vec_ptr v, data_t *dest){ long i; long length = vec_length(v); data_t *data = get_vec_start(v); *dest = IDENT; for (i = 0; i < vec_length(v); i++) { dest = dest OP data[i]; }}| 函数 | 方法 | 整数 (+) | 整数 () | 浮点数 (+) | 浮点数 () |
|——|——|———|———|———-|———-|
| Combine2 | 移出vec_length | 7.02 | 9.03 | 9.02 | 11.03 |
| Combine3 | 直接数据访问 | 7.17 | 9.02 | 9.02 | 11.03 |

OK，我们可以看到，性能提升和理论配合的并不是很好，显然内循环中有其他的操作形成了瓶颈，限制性能超过了调用get_vec_element。我们继续做优化。
消除不必要的内存引用combine3的代码将合并运算计算的值累积在dest指定的位置。在dest指针地址存放在寄存器中时，考虑到底层汇编，累计变量的数值都需要从内存读出再写入到内存。这样的读写是很浪费的。为了消除这种不必要的读写，我们按如下生成了combine4的代码。
把结果累积在临时变量中，将累积值存放在局部变量acc中，消除了每次循环迭代中从内存中读出并将更新值写回的需要:

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

函数	方法	整数 (+)	整数 (*)	浮点数 (+)	浮点数 (*)
Combine3	直接数据访问	7.17	9.02	9.02	11.03
Combine4	直接数据访问	1.27	3.01	3.01	5.01

在这操作之后，我们可以看到程序的性能有了显著的提升。