实例
为了说明一个抽象程序是如何被系统转换为更有效地代码的，之后的例子我们将使用如下的向量数据结构的运行示例，向量由两个内存块表示：头部和数据数组。
头部是一个声明如下的结构：
/* 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 combine1 | 抽象的未优化的 抽象的-O1 | 22.68 20.02 10.12 10.12 | 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 combine2 | 抽象的-O1 移出vec_length | 10.12 10.12 7.02 9.03 | 10.17 11.14 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 Combine3 | 移出vec_length 直接数据访问 | 7.02 9.03 7.17 9.02 | 9.02 11.03 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 Combine4 | 直接数据访问 直接数据访问 | 7.17 9.02 1.27 3.01 | 9.02 11.03 3.01 5.01 |
在这操作之后，我们可以看到程序的性能有了显著的提升。
