优化程序性能

编写高效程序需要注意的:

编译器优化的能力和局限性

gcc中指定优化级别的参数有:-O0、-O1、-O2、-O3、-Og、-Os、-Ofast

在执行优化的过程,编译期所考虑的是必须执行安全的优化,所以必须考虑所有的情况,这样优化的选择就比较少了

如内存别名,看似优化能减少几次内存读写成本,但如果两个指针都指向同一块内存,那么看似可以优化的操作就会导致程序结果执行出错

// 如果x与y都指向同一块内存
void func(int *x, int *y) {
    *x += *y;
    *x += *y;
}
// 那么如果编译期将代码优化成这样, 程序的执行结果就错了
void func(int *x, int *y) {
    *x += 2 * *y;
}

对于函数内联优化,也就是将原本的函数调用提取出来,将代码展开到调用处,不仅可以减少函数调用成本,同时展开之后也方便做其他优化, 这种优化方式在JVM的后端编译优化中也得到了较好的执行

内存的读写成本大概是在百纳秒这个级别,而函数的调用成本不仅需要将内存中的帧指针移位到堆栈上,并在其上添加新帧.函数参数被移入本地寄存器以供使用,并且堆栈指针被前进到堆栈的新顶部以执行该函数,需要多条指令来完成,这还只是针对C的函数调用,像OOP语言多态的虚方法之类的东西,调用之前需要进行查表,或者Java语言这种动态方法调用,需要做的事更多,过程调用不仅带来了开销,同时也会妨碍大多数的优化

表示程序性能

也就是执行的CPU周期数

循环展开

通过诸如循环展开等的优化方法,可以使得用更少的循环完成计算

// 未展开前
for (i = 1; i <= 60; i++) 
   a[i] = a[i] * b + c;
// 展开后
for (i = 1; i <= 58; i+=3)
{
  a[i] = a[i] * b + c;
  a[i+1] = a[i+1] * b + c;
  a[i+2] = a[i+2] * b + c;
}

大部分编译器在将优化级别设的足够高都能支持循环展开

消除循环的低效率

void f1(int a[]){
    // 将长度的计算提取到变量, 避免每次循环都进行计算
    int i = length(a);
    int j;
    for(j=0;j<i;j++){
        // DO SOMETHING
    }
}

void f2(int a[]){

    int j;
    for(j=0;j< length(a);j++){
        // DO SOMETHING
    }
}

这种优化操作编译器无法帮助程序员完成,因为编译器必须假设length这个函数是可能具有副作用

消除不必要的内存引用

void sum1(int a[],int n,int *ret){
    int i=0;
    for(;i<n;i++){
        // 每次操作需要读两次内存(ret跟a[i]) 一次写内存(ret)
        *ret += a[i];
    }
}

void sum2(int a[],int n,int *ret){
    int i=0;
    int tmp=0;
    for(;i<n;i++){
        // 使用一个临时变量, 每次操作需要读一次内存(a[i]) 一次写寄存器(tmp)
        tmp += a[i];
    }
    *ret = tmp;
}

理解现代处理器

指令级并行:多条指令在物理上是乱序并行的,但在程序视角是顺序一条条,但肯定会出现一系列指令都必须在物理上顺序执行,这是延迟界限,处理器计算能力也是有上限的,称为吞吐量界限

整体操作

乱序处理器框图

CPU在执行指令之前就已经对后续的指令进行取值与译码,当遇到分支时,会执行分支预测,其会执行CPU选定分支的相关指令,如果预测错误,就会恢复相关状态,执行另一条分支的指令

寄存器重命名

功能单元的性能

处理器操作的抽象模型

一段代码在CPU的数据流

从这个图可以看出CPU是如何并行乱序执行的

提高并行性

多个累积变量

void sum1(int a[],int n,int *ret){
    int i=0;
    int limit = n/2;
    int tmp1=0;
    int tmp2=0;

    for(;i<limit;i++){
        tmp1 += a[i];
    }

    for(i=limit;i<n;i++){
        tmp2+=a[i];
    }

    *ret= tmp1 + tmp2;
}

重新结合变换

tmp = (tmp + a[i]) +a[i+1] // 1
tmp = tmp + (a[i] +a[i+1]) // 2

限制因素

寄存器溢出

如果寄存器不够用,将会使用内存在栈上存放临时变量,造成性能下降

如果循环展开过多,导致每次需要的变量数超过寄存器数,就会不够用

分支预测和预测错误处罚

for(int i = 0; i < n; i++) {
    if (a[i] > b[i]) {
        int t = a[i];
        a[i] = b[i];
        b[i] = a[i];
    }
}
// 条件传送码
for(int i = 0; i < n; i++) {
    int min = a[i] < b[i]? a[i]: b[i];
    int max = a[i] < b[i]? a[i]: b[i];
    a[i] = min;
    b[i] = max;
}

理解内存性能

应用:性能提高技术

高级设计:算法与数据结构

基本编码原则

低级优化

确认和消除性能瓶颈