程序性能优化

这篇为《深入理解计算机系统》中程序性能优化的笔记。
要想程序跑的快，最重要的是两个方面，一是数选择优秀的数据结构和算法，另外就是写的代码要便于编译器优化成高效的可执行代码。对于大型程序来说，我们更要关注的系统的整体性能，提升对系统性能影响最重要的部分。程序是写给计算机执行的，但是却是写给人看的，所以在性能和可读性方面需要均衡考虑。
以前写代码考虑的更多的数据结构和算法，很少考虑编译器，确实我们不是在写机器指令，需要考虑下编译器的感受：）。

一编译器局限性

虽然现在编译器已经很厉害了，但是为了保证程序的逻辑的正确性，编译器在程序优化方面是很谨慎的。
比如下面一段代码：

代码实例

• 第一个函数需要读取两次yp指针指向的值，二次xp指针指向的值，两次写xp指针指向的值。
• 第二个函数读取一次yp指针指向的值，一次xp指针指向的值，再有一次写xp指针的值。
  从上面代码来看，两次的结果是相同的，但是实际执行过程中，并不会把函数1优化为函数2，原因是如果yp指针和xp指针是同一个指针的话，假如值为3，那么twiddle1的值为：12，twiddle2的值为：6。编译器不能假定两个指针不同，所以不能做这个优化。
  这就是编译器的局限性，所以我们要为编译器考虑，或者我们用更明确的方式来写代码。

二 程序优化实例

2.1 示例数据结构定义

下面是程序的使用到的结构体的定义如下：

#define int data_t;
#define IDENT 0
#define OPER +

// 简单的向量数据结构体定义
typedef struct {
   // 数据的长度   
   int len;
  // 实际数据 
   data_t *data;
} vec_rec, *vec_ptr;

上述代码是一段C代码，比较简单，后面的代码优化不光适合于c，其实也适应于其他的编程语言。
图形化展示如下：

向量数据结构

对这个结构体的支持操作也比较简单，敲下代码：

//创建
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(result);
            return NULL;
        }
        result->data = data;
    }
    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;
    }
}

2.2 优化一 消除循环的低效率

我们观察上述的原始代码，一个比较明显的问题是，循环中除了执行真正的逻辑，而且每次还调用vec_length(v)求向量的长度，但是向量的长度在每次循环中是不变的，所以没有必要每次都计算，优化版本1：

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

只所以我们要明确这样做，是因为编译器不能帮我们优化，原因是，编译器无法准确知道vec_length函数的调用是否有什么副作用，比如除了求长度之外，是否还改变了什么全局变量的值，所以我们必须显示的完成代码的移动。
具书中介绍，这小小的移动，为每个元素减少了10个时钟周期。也许你看不起这么点的优化，但是，这个优化是随着n增大，线性增加的。这在n很大的时候，性能比较是惊人的，看下面类似的代码：

void lower1(char* s)
{
    int i;
    for (i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
}

void lower2(char* s)
{
    int i;
    int len = strlen(s);
    for (i = 0; i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
}

size_t strlen(const char* s)
{
    int len = 0;
    while (*s != '\0') {
        s++;
        len++;
    }
    return len;
}

对于字符串长度为262144的字符串来说，lower1需要执行3.1分钟，lower2 执行需要0.006秒，性能提升了3000倍。

2.3 优化二 减少函数调用

刚才第一个优化也算是循环中的函数调用的优化，仔细看下函数内部，调用的是：
get_vec_element 来获取元素，由于每次调用都要做边界检查，这部分也可以做优化，不通过函数调用，直接访问数组，当然这样违背了封装性的原则，我们先来看看做过二次优化后的代码：

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

void combine3(vec_ptr v, data_t* dest)
{
    int i;
    *dest = IDENT;
    int length = v->len;
    data_t* data = get_vec_start(v);
    for (i = 0; i < length; i++) {
        *dest = *dest OPER data[i];
    }
}

通过这次改进，减少了函数调用，去掉了边界检查，性能有了2-3倍的提升。

2.4 优化三 消除不必要的存储器引用

仔细观察程序，可以发现循环内，每次都对dest赋值，而这个属于指针的引用，每次都赋值给它也没有必要，我们可以定义一个临时变量，每次循环都放入到临时变量中，最后再将结果赋值给dest，就有了优化三的代码：

void combine4(vec_ptr v, data_t* dest)
{
    int i;
    data_t x = IDENT;
    int length = v->len;
    data_t* data = get_vec_start(v);
    for (i = 0; i < length; i++) {
        x = x OPER data[i];
    }
    *dest = x;
}

也许你有这样的意味都是赋值操作，还多引入了一个临时变量，真的有效果吗，可以看看汇编代码就知道了：

2.5 优化四 降低循环开销

我们注意到，前几种优化是对于循环内部的执行体的优化，那么是否可以对循环本身进行优化，即是否可以减少循环次数那？答案是可以的，这种在循环中执行更多操作来减少循环次数的办法，叫循环展开，通过循环展开减少了循环次数，提升了程序性能，优化后的代码如下：

void combine5(vec_ptr v, data_t* dest)
{
    int i;
    data_t x = IDENT;
    int length = v->len;
    data_t* data = get_vec_start(v);
   //  通过这个限制防止越界
    int limit = length - 2;
    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;
}

这个优化的挺奇妙的，每次循环进行了三次操作，limit赋值为length-2 ,假设有个数组长度为n，i<n-2 的最大索引位置为： i+2 <n-2+2 即i<2 ，所以不会越界。

2.6 性能优化5 提高并行性

我们知道处理器的几个功能单元是流水化工作的，比如取指令，解码指令，计算指令是可以并行执行的，只要逻辑上没问题，但是我们这代码限制了这种能力，代码中的结果是累加到x中的，那么在上一个循环没有结束之前x的值是无法确定知道的，就不能开启新的循环，必须等待。

我们可以采用一种叫循环分割的技术，在上面计算的时候，把数组分成索引值为奇数的元素和索引值为偶数的元素，将偶数的元素累计在一个变量x0中，奇数的元素累计在一个变量x1中，这样x0和x1的计算不依赖对方的结果，指令并行执行更好。
优化代码如下：

void combine6(vec_ptr v, data_t* dest)
{
    int i;
    data_t x0 = IDENT;
    data_t x1 = IDENT;
    int length = v->len;
    data_t* data = get_vec_start(v);

    int limit = length - 1;
    for (i = 0; i < limit; i += 2) {
        x0 = x0 OPER data[i];
        x1 = x1 OPER data[i + 1];
    }

    for (; i < length; i++) {
        x0 = x0 OPER data[i];
    }
    *dest = x0 OPER x1;
}

这里面的展开度为2 ，并行度为2，这个展开度和并行度是不是越大越好，显示不是，因为计算机中的寄存器的数量有限的，x0和x1这种变量保存在寄存器中性能会更好，如果临时变量过多，就会造成寄存器放不下，就会把临时变量放在栈中，这叫寄存器溢出，这样性能就会下降；还有一个因素是cpu会对指令的执行进行分支预测，如果预测错了，会进行回退，通过gcc等编译器的一些选择，可以让cpu对指令的预测上更倾向于特定的分支，从而提升性能。

三 总结

优化程序的基本策略:

1. 选择合适的算法和数据结构，警惕渐进式的算法或编程技术，即随着数组n的变化，算法复杂度也会线性或乘积，或阶乘等增加的情况。
2. 基本编码原则：

• 消除连续的函数调用。
• 消除不必要的储存器的引用。

3. 低级优化

• 尝试各种与数组相似的指针形式。
• 通过展开循环，降低循环次数。
• 通过分割技术等，这种可以使用流水线功能单元的办法。

4. 确认和消除性能瓶颈
   我们在大型程序中，找到性能瓶颈才是优化性能的关键，这里面有个性能优化的通用原则叫Amdahl 定律，主要思想是我们加快了系统的一部分性能，对整体系统的性能提升多少依赖于这部分有多重要和性能提升的多少。
   假设一个系统运行的时间为T_old, 假设系统中某个部分占用总时间比为α，而我们将它的性能提升了k倍，也就是原来这部分执行时间为αT_old变成了：αT_old/k，整体执行时间为：
   T_new = (1-α)T_old+(αT_old/k)
   加速比：S = T_new /T_old = 1/(1-α)+α/k
   举个例子，假如你优化的部分占系统的80%执行时间，这部分性能倍优化提升了4倍，那么整体加速：
   S = 1/(1-0.8)+ 0.8/4 = 2.5