优化程序性能

gaunthan Posted on May 6 2016

? Performance Optimization ?

##  概述
### 消除不必要的内容
程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。这些优化不依赖于目标机器的任何具体属性。

为了使程序性能最大化，程序员和编译器都需要一个目标机器的模型，指明如何处理指令，以及各个操作的时序特性。例如，编译器必须知道时序信息，才能够确定是用一条乘法指令，还是用移位和加法的某种组合实现乘法功能。现代计算机用复杂的技术来处理机器级程序，并性地执行许多指令，执行顺序还可能不同于它们在程序中出现的顺序。程序员必须理解这些处理器是如何工作的，从而调整它们的程序以获得最大的速度。

### 指令并行
了解了处理器的运作，就可以进行程序优化的第二步，利用处理器提供的**指令级并行**（instruction-level parallelism）能力，同时执行多条指令。

## 详解
### 优化编译器的能力和局限性
现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及它们是如何被使用的。然后它们会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。大多数编译器，包括GCC，向用户提供了一些对它们所使用的优化的控制。例如，以命令行标志`-On`调用GCC是让GCC使用优化等级n来优化程序。默认情况下，GCC使用优化等级2。

### 消除循环的低效率
对于在循环中会重复计算，但结果不会改变的代码，应该使用一个局部变量来将结果存储起来，并且使用这个变量来替换循环中引用到结果的地方。这类优化被称为**代码移动**（code motion）。

所谓代码移动，就是识别要执行多次但是计算结果不会改变的计算，并且将其移动到代码不会被多次求值的地方。

### 减少过程调用
过程调用会带来相当大的开销，而且妨碍大多数形式的程序优化。如果循环里面有函数调用，那么应该考虑该函数调用是否可以提到循环前面。

### 减少不必要的存储器引用
如果我们代码中的循环内部有持续的修改指针指向对象的语句，例如：

``` c
void sumTo(int a[], int n, int *dest)
{
    int i;
    
    *dest = 0;
    for(i = 0; i < n; ++i)
        *dest += a[i];
}
```
则更好的做法是：

``` c
void sumTo(int a[], int n, int *dest)
{
    int i;
    int sum;
    for(i = 0, sum = 0; i < n; ++i)
        sum += a[i];
    *dest = sum;
}
```
这样编译器就很容易地用一个寄存器来代替sum以达到优化目的。

### 循环展开
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。循环展开减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。其次，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。

#### 让编译器展开循环
编译器可以很容易地执行循环展开。只要优先级别设置得足够高，许多编译器都能理性公事地做到这一点。用命令行选项`-funroll-loops`调用GCC，会执行循环展开。

假设给定下面的代码：

for (i = 1; i <= 60; i++) 
        a[i] = a[i] * b + c;
   
可以如此循环展开：

for (i = 1; i <= 60; i+=3) {
        a[i] = a[i] * b + c;
        a[i+1] = a[i+1] * b + c;
        a[i+2] = a[i+2] * b + c;
    }

这被称为展开了两次。

#### 循环展开的优点
- 分支预测失败减少。
- 如果循环体内语句没有数据相关，增加了并发执行的机会。
- 可以在执行时动态循环展开。

#### 循环展开的缺点
- 代码膨胀。
- 代码可读性降低，除非是编译器透明执行循环展开。
- 循环体内包含递归可能会降低循环展开的得益。

### 提高并行性
#### 多个累计变量
对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。需要注意的是，浮点乘法和加法不是可结合的，因为四舍五入或溢出可能会导致结果不同。

#### 重新结合变换
**重新结合变换**（reassociation transformation）是另一种打破顺序相关从而使性能提高到延迟界限之外的方法。比如下面这条语句：
```c
acc = (acc OP data[i]) OP data[i + 1];
```
将其修改为下面这条会得到令人吃惊的优化效果：
```c
acc = acc OP (data[i] OP data[i + 1]);
```
差别仅在于两个括号是如何放置的。

总的来说，重新结合变换能够减少计算中关键路径上操作的数量，通过更好地利用功能单元的流水线能力得到更好的性能。大多数编译器不会尝试对浮点运算做重新结合，因为这些计算不保证是可结合的。通常，循环展开和并行地累计在多个值中，是提高程序性能的更可靠的方法。

### 限制因素
#### 寄存器溢出
循环并行性的好处受到描述计算的汇编代码的能力限制。如果我们的并行度$p$超过了可用的寄存器数量，那么编译器会报告**溢出**（spilling），将某些临时值存放到栈中。一旦出现这种情况，性能会极度下降。

#### 分支预测和预测错误处罚
现代处理器的工作超前于当前正在执行的指令，从存储器读新指令，并解码指令，以确定在什么操作数上执行什么操作。只要指令遵循的是一种简单的顺序，那么这种**指令流水线化**（instruction pipelining）就能很好地工作。当遇到分支的时候，处理器必须猜测分支该往哪个方向走：

* 对于条件转移的情况，这意味着要预测是否会选择分支。
* 对于像间接跳转（跳转到由一个跳转表条目执行的地址）或过程返回这样的指令，这意味着预测目标地址。

在一个使用**投机执行**（speculative execution）的处理器中，处理器会开始执行预测的分支目标处的指令。它这样做会避免修改任何实际的寄存器或存储器位置，直到确定了实际的结果。如果预测是正确的，那么处理器就会“提交”投机执行的指令的结果，把它们存储到寄存器或存储器中。如果预测是错误的，处理器必须丢弃所有投机执行的结果，在正确的位置，重新开始取指令的过程。这样做会引起**预测错误处罚**，因为在产生有用的结果之前，必须重新填充指令流水线。

## 性能提高技术
### 高级设计
为遇到的问题选择适当的算法和数据结构。要避免使用那些会渐进地产生糟糕性能的算法或编码技术。

### 基本编码原则
避免限制优化的因素，这样编译器就能产生高效的代码:

* 消除连续的函数调用。在可能时，将计算移到循环外，考虑有选择地妥协程序的模块性以获得更大的效率。
* 消除不必要的存储器引用。引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。
 
### 低级优化

* 展开循环，降低开销，并且使得进一步的优化成为可能。 
* 通过使用例如多个累计变量和重新结合等技术，找到方法提高指令级并行。
* 用功能的风格重写条件操作，使得编译采用条件数据传送。

## References

- RandalE.Bryant, DavidR.O’Hallaron, 布赖恩特,等. 深入理解计算机系统[M]. 机械工业出版社, 2011.
- [维基百科——循环展开](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80)