如何优化程序性能

发表于 | 分类于 | | 阅读次数:
字数统计: | 阅读时长 ≈

      代码的简单改变，可能带来程序性能上的飞跃
 我们用高级语言编出的代码都要经过编译器的编译才能形成可以执行的程序，如今的编译器已经比较成熟，但由于编译问题的复杂性而难以做到完美。编译器会对程序自动做出优化，但要在保证正确性的前提下。如果我们在编程中给与编译器更多提示，那编译器就能更好的优化程序。那我们如何跟编译器一起编写出更加高效的程序呢？

消除循环代码中的低效率

通过代码移动优化来消除循环代码中的低效率。

代码移动优化包括识别要执行多次但是计算结果不会改变的计算，因而可以将计算移动到不会被多次求值的部分。

优化编译器会试着进行代码移动，但是会非常小心，当它不能发现这种优化是否会有副作用时，它会假设是有副作用的，因而放弃优化。而编译器又不可能可靠地发现一个函数是否有副作用。所以我们必须帮助编译器显示地完成代码移动优化。下面是一个比较极端的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* Convert string to lowercase: slow */
void lower1(char *s)
{
    long i;
    
    for(i = 0;i < strlen(s); i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
    }
}

/* Convert string to lowercase: faster */
void lower2(char *s)
{
    long i;
    long len = strlen(s);
    
    for(i = 0;i < len; i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
    }
}

/*Sample implementation of library function strlen*/
/*Compute length of string*/
size_t strlen(const char *s)
{
    long length = 0;
    while(*s != '\0')
    {
        s++;
        length++;
    }
    return length;
}

这个例子中当字符床s长度超过十万时，lower2()比lower1()快500000多倍。这是因为后者代码中隐藏着渐近低效率(asymptotic inefficiency)，一个有经验的程序猿会在编程中会尽力避免引入这样的渐近低效率。

减少过程（函数）调用

过程（函数）调用是会带来开销的，而且会阻碍编译器进行程序优化，对于一些简单操作，直接操作比写成函数更高效。当然这样就一定程度上破坏了程序的模块性，需要我们根据实际情况进行权衡。当然内联函数是个不错的折中。

消除不必要的内存访问

我们先来看一段c代码和它对应的汇编代码：

1
2
3
4
5
*result = 1;
for(i = 0;i < length; i++)
{
    *result = *result * data[i];
}
1
2
3
4
5
6
7
8
result in %rbx,data + i in %rdx,data + length in %rax
1 .L17:
2   vmovsd (%rbx), %xmm0
3   vmulsd (%rbx), %xmm0, %xmm0
4   vmovsd %xmm0, (%rbx)
5   addq   $8, %rdx
6   cmpq   %rax, %rdx
7   jne    .L17

 从汇编代码中我们可以看到每次迭代时，累积变量的数值都要从内存读出再写入内存，这样的读写是很浪费的，因为每次迭代开始时从result 读出的值和上次循环最后写入的值是一样的。
 我们可以通过引入一个临时变量（局部变量）来累计计算出的值，只有在计算完成后才存入result。这样就能消除这种不必要的内存读写了。

1
2
3
4
5
6
int acc = 1;
for(i = 0;i < length; i++)
{
    acc = acc * data[i];
}
*result = acc;
1
2
3
4
5
6
acc in %xmm0 ,data + i in %rdx,data + length in %rax
1 .L25:
2   vmulsd (%rdx), %xmm0, %xmm0
3   addq   $8, %rdx
6   cmpq   %rax, %rdx
7   jne    .L25

由于内存别名的使用，这种优化编译器很难自动完成。而一旦我们主动实现这种优化，程序性能可以得到不小的优化。

循环展开

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

例如：

1
2
3
4
5
6
7
8
int sum(int a[],int n)
{
    int i;
    int sum = 0;
    for(i = 0;i< n;i++)
        sum += a[i];
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//2×1循环展开
int sum(int a[],int n)
{
    int i;
    int sum = 0;
    for(i = 0;i < n - 1;i+=2)
        sum += a[i] + a[i+1];
        
    for(;i<n;i++)//处理最后一（几）个元素
        sum += a[i];
        
    return sum;
}

循环展开能够在两个方面改进程序的性能。首先它减少了不直接有助于程序结果的操作的数量。第二，它提供了一些方法进一步改变代码从而减少整个计算中关键路径上的操作数量。

提高并行性

流水线中的数据相关在一定程度上限值了程序的性能，但是我们在编程中又貌似对此无能为力。实际上我们确实可以采用一些方法来提高并行性来缓解数据相关。
比如我们可以将一组合并运算分割为两部分或者更多，并在最后讲结果合并来提高性能。比如对于上一部分的sum()例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//2×2循环展开
int sum(int a[],int n)
{
    int i;
    int sum1 = 0;
    int sum2 = 0
    for(i = 0;i < n - 1;i+=2)
    {
        sum1 += a[i];
        sum2 += a[i+1];
    }
        
    for(;i<n;i++)//处理最后一（几）个元素
        sum1 += a[i];
        
    return sum1 + sum2;
}

这个方法既使用了两次循环展开，以使每次迭代完成更多的计算，也使用两路并行，提高了并行性。我们称这种方法为2×2循环展开。