优化程序性能

编写高效程序需要两个活动:第一,我们必须选择一组最好的算法和数据结构;第二,我们必须编写出编译器能够有效优化以转换成高效可执行代码的源 代码。这里,我们主要讲述后者。

首先,我们討論一下为什么要编写高效程序。不难想象,如果本来要用10天运行完的程序,经过优化只需要1天就可运行完,这是一件多么令人振奋的 事啊。时间就是金钱呐。那么,什么时候才有必要优化。什么?优化不是无论什么时候都有必要的吗?太不可思议了!当然,作为一个程序员,我们必做在实现与维 护程序的简单性与它的运行速度之间做出权衡折衷。对于一个只会运行一次以产生一组数据点的程序,以一种尽量减少编程工作量并保证正确性来编写程序就更为重 要了。考虑一下,比如一个只用一次的算法,编写时间加上运行时间不超过一天,然而我们花上三天来优化这个算法让它只要一个小时就能出結果。乍一看多好的优 化啊,三天变成一小时!等等,让我们来算一算。不优化编写加运行时候只要一天,而优化后呢?三天加一小时!当然,如果这个算法反复执行的话,我们对它的优 化就值得肯定了。

好了,说了这么多,切入正题,怎样才能在优码级别上进行优化呢?做那些编译器不能帮你做的优化。这里,我们先讲个例子。考虑一个简单向量数据结构。向量由两个存储器块表示。头部是一个声明如下的结构:

1
2
3
4
typedef struct{
int len;
data_t* data;
}vec_rec, *vec_ptr;

这个声明用数据类型data_t作为基本元素的数据类型。可以用int,float,double类型来评价我们代码的性能,这里我们使用float。代码如下:

typedef float data_t;

除了头以外,我们还分配一个len长度的data_t类型对象的数组,以存放实际的向量元素。代码如下:

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

当然,还有另外的操作,如取data_t类型对象数组中的元素,得数组的长度等。

int get_vec_elment(vec_ptr v, int index, data_t* dest)
{
    if(index < 0 || index > 0)
        return 0;
    *dest = v->data[index];
    return 1;
}

int vec_length(vec_ptr v)
{
    return v->len;
}

作为一个优化示例,必须有操作。这里我们将操作定义为把data_t类型对象数组中的元素根据某种运算合并成一个值。通过使用编译时常数IDENT和OPER定义:

#define INENT 1
#define OPER *

最后,我们进行操作,函数如下:

void combine1(vec_ptr v, data_t* dest)
{
    int i;

    *dest = INENT;
    for(i = 0; i < vec_length(v); i++){
        data_t val;
        get_vec_elment(v, i, &val);
        *dest = *dest OPER val;
    }
}

这里就是将所有的元素通过乘法合并成一个元素。假设元素数组有10亿个。默认地,编译器产生的代码没有经过任何的优化,所以,我们这个程序的运 行时间是相当的长。还是先说明下我的实验环境吧。我是在eclipse+Mingw下运行的,CPU为T5670 1.8GHz。那么这样的代码花了我多长时间呢?答案是12.680秒!天呐,那不是很慢嘛!这个嘛,要得益于我们高速发展的硬件设备了。但是,现在只是10亿个,要是更多呢?操作只是简单的相乘,要是更复杂呢?不敢想象。。。

至此,我们先来讨论第一个优化:消除循环的低效率 。观察combine1函数,我们发现,在for(i = 0; i < vec_length(v); i++)中,我们调用函数vec_length()作为测试条件。想象一下上C语言课程时候对循环的讨论,每次循环迭代时都必须对测试条件进行求值。哇, 那我们运行10亿次乘法不是要调用10亿次vec_length()函数,但是,vec_length()的返回值在这10亿次中根本不会变化!没错,我 们对一个不会变的结果运行计算了10亿次!事实上10亿减1次是根本不需要的!你想到了什么?没错,我们可以优化。正如在前面所说,我们要消除循环的低效率。

我们编写combie2版本,它在开始时调用vec_length()函数,并将结果赋值给局部变量length,然后在for循环中使用这个变量。果不其然,我们提高了程序的性能,运行完只花了10.012秒。这里列出combine2的代码:

void combine2(vec_ptr v, data_t* dest)
{
    int i;
    int len = vec_length(v);

    *dest = INENT;
    for(i = 0; i < len; i++){
        data_t val;
        get_vec_elment(v, i, &val);
        *dest = *dest OPER val;
    }
}

这个优化是一类常见的、称为代码移动的优化实例。这类优化包括识别出在循环里执行多次,但结果不会变化的计算,因而我们可以将计算移动到循环体外,这样这个计算就不会被执行多次。

下面,我们对第二个优化进行讨论:减少过程调用 。过程调用可能会带来相当大的开销。如combine2中的get_vec_elment()函数。每次迭代循环,我们都要调用 get_vec_elment()函数以获得下一个元素。仔细观察代码,我们发现完全可以避免这个过程调用,因而也不需要进行边界检查,对程序来说是一个 良好的优化。我们可以进行如下 的改变:

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

void combine3(vec_ptr v, data_t* dest)
{
    int i;
    int len = vec_length(v);
    data_t* data = get_vec_start(v);

    *dest = INENT;
    for(i = 0; i < len; i++){
        *dest = *dest OPER data[i];
    }
}

相比之前,我们在进行循环体之前先取得元素数组的起始位置,然后我们每次循环时用数组得到元素,而省去了对get+vec_elment的过程调用,减少了一些运行时间。改善后的时间是6.36秒。

下面,我们再次进入下一个优化阶段:消除不必要的存储器引用 。我们知道,操作系统中对数据的读取与存储,寄存器快于存储器。然而,我们发现combine3中,每次循环中, dest = dest OPER data[i]语句先是对dest进行读取,然后进行计算,再存到dest中,这些是在存储器上进行的。但是,我们这一次存的数据就是我们下一次循环 读的数据,这样在存储器上操作不是很费时间?没错,所以,我们要消除不必要的存储器引用,将这个数据存到寄存器中。我们引入一个临时变量:

void combine4(vec_ptr v, data_t* dest)
{
    int i;
    int len = vec_length(v);
    data_t* data = get_vec_start(v);
    data_t tmp = INENT;

    for(i = 0; i < len; i++){
        tmp = tmp OPER data[i];
    }
    *dest = tmp;
}

经过如此改变之后,我们程序的性能又有所提高,只需要6.227秒。

最后,我们再一次来回顾一下我们如何提高程序的性能。一、消除循环的低效率。二、减少过程调用。三、消除不必要的存储器引用。这里,有人会问,编译器不是 自己有优化的嘛。没错,现代的各种编译器都有能力不等的优化。但是,作为一个合格的程序员,把程序优化的工作交给编译器固然有益处,可编译器也不是万能的 啊。一部分的优化能是做不到的,而且,作为优化,最重要的是不能改变程序原来的执行结果。编译器当碰到能决定是否会改变你的程序结果的时候,他往往选择不 优化以保证结果的正确性,这个时候就需要我们手动来进行程序的优化了。所以,掌握这个技能还是很有必要的。

另外,这是我第一次写Blog,当然文笔很生疏啦,请读者见谅!不管怎么样,这是我学习过程的一个总结,请批评指正。