《CSAPP》笔记5 - 优化程序性能

编写高效程序需要做到的几点⌗

选择适当的算法和数据结构
写出编译器能够有效优化成高效可执行程序的代码
对于运算量特别大的计算，将一个任务分成多个部分，并行计算

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

GCC提供不同等级的优化-Og,-O1,-O2,-O3，其中-O2是被接受的标准。另外，-O0表示不做任何优化。

妨碍编译器优化的两个因素⌗

一是内存别名，二是函数调用。

内存别名memory aliasing⌗

void twiddle1(long *xp, long *yp){
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(long *xp, long *yp){
    *xp += 2* *yp;
}

函数twiddle1需要求6次内存引用，而twiddle2只需要2次。twiddle1看上去和twiddle2做了相同的事，当xp和yp指向同一个地址时两个函数是等价的，可是xp和yp可能指向同一个地址，这时两个函数是不等价的。举个例子，假设a = 1，执行下面这行语句后，a的值变为4。

twiddle1(&a, &a);

而执行下面这行语句后，a的值变为3，所以twiddle1和twiddle2是不等价的。

twiddle2(&a, &a);

在编程时要避免这种情况，因为编译器无法做出优化。

函数调用⌗

看个例子

long f();

long func1(){
    return f() + f() + f() + f();
}

long func2(){
    return 4 * f();
}

上面的func1不能优化为func2，因为函数f可能是有副作用的，例如下面这种情况：

long counter = 0;
long f(){
    return counter++;
}

所以编译器不会优化函数调用。

表示程序性能⌗

用每元素周期数CPE(Cycles Per Element)表示程序性能。通常用不同大小的数据集进行测试，记录运行周期数，再用最小二乘拟合，拟合出一条直线，斜率就是CPE。

理解现代处理器⌗

现代处理器可以做到指令级并行，多条指令可以并行执行，同时又呈现出一种简单的顺序执行的表象。

两种下界描述了程序的最大性能：

latency bound延迟界限，当一系列操作必须按照严格顺序执行时，某一条指令开始前，上一条指令必须结束。代码中的数据相关性会限制指令级并行，程序受限于延时界限。
throughput bound吞吐量界限，处理器功能单元的原始计算能力，是程序性能的终极限制

整体操作⌗

超标量(superscalar)处理器可以在每个时钟周期执行多个操作，并且是乱序的(out-of-order)。

处理器的设计有两个部分，都是用非常复杂的数字电路实现的：

指令控制单元(ICU, instruction controll unit)，负责从icache中读取指令序列，生成一组基本操作，发送给EU。
执行单元(EU, execution unit)，每个时钟周期接收多个操作，执行操作。

分支预测(branch prediction)：处理器猜测是否会选择分支，同时预测分支的目标地址。包括在取指控制块中。

投机执行(speculative execution)：处理器取出预测的分支会跳到的指令，进行指令译码，在确定分支之前就开始执行。如果之后确定分支预测错误，会将状态重置到分支点，取出并执行另一个方向上的指令，这个步骤会造成性能损耗。

指令译码：接收程序指令，将他们转换成一组基本操作（微操作），例如两个数相加，从内存读数据，向内存写数据。通常一条只对寄存器操作的指令转换成一个操作，而一个包括内存引用的指令转换成多个操作。执行单元可以并行执行多条基本操作。

例子：

addq %rax,%rdx

转换成1个加法操作。

addq %rax,8(%rdx)

转换成3个操作，加载，加法，存储。

功能单元：EU每个时钟周期可以接收多个来自取指单元的操作。例如Intel Core i7 Haswell8个功能单元，每个功能单元可以执行多种不同的操作。

退役单元retirement unit：在队列中记录正在执行的指令的信息，确保乱序执行的结果遵守机器级程序的顺序语义。退役单元控制寄存器的更新，一旦一条指令执行完成，并且分支预测的结果被确认为预测正确，那么这条指令可以退役(retire)，对寄存器的更新可以被执行，否则这条指令被清空(flushed)，并且丢弃计算的结果。

寄存器重命名(register renaming)：对寄存器的更新只有在指令退役时才会执行，在执行单元间传送指令（退役之前）需要用到寄存器重命名机制。当一条更新寄存器r的指令译码时，产生标记t，条目(r,t)被加入到一张表中，随后以r为操作数的指令在指令译码时，发送到EU时会包含以t为操作数源的值。当执行单元完成第一个操作时，会生成结果(v,t)，之后需要t的指令都可以用v的值。值可以从一个操作直接转发到另一个操作，无需读写寄存器。具体实现可以看Wiki。

功能单元的性能⌗

延迟latency：完成运算所需要的总时间，一般整数加法1、乘法3、除法3~30，浮点数加法3、乘法5、除法3~15。

发射时间issue time：两个连续同类运算之间需要的最小时钟周期，通常fully pipelined运算发射时间都是1，例如加法和乘法。除法一般没有流水线，issue time = latency。

容量capacity：功能单元的数量。

最大吞吐量：容量为C，发射时间为I，则最大吞吐量为每时钟周期C/I

参考机性能

界限	整数+	整数*	浮点数+	浮点数*
延迟	1.00	3.00	3.00	5.00
吞吐量	0.50	1.00	1.00	0.50

注意：吞吐量不完全是由capacity决定的，虽然整数加法有4个功能单元，但是加载功能单元只有2个，所以吞吐量是1/2而不是1/4。

处理器操作的抽象模型⌗

将程序用数据流(data flow)表示，展现不同操作之间的数据相关性是如何限制他们的执行顺序的，这些限制形成了图中的关键路径(critical path)，是执行一组指令所需的时钟周期的下界，优化程序时要优化关键路径。

性能优化实例⌗

优化前的原始代码⌗

// OP为+时IDENT为0
// OP为*时IDENT为1
void combine1(vec_ptr v, data_t *dest){
    long i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++){  // 这里vec_length(v)重复求值了
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

消除循环的低效率⌗

优化方法称为代码移动(code motion)

void combine2(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);  // 将不变的长度放到循环外
    *dest = IDENT;
    for (i = 0; i < length; i++){
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }   
}

减少过程调用⌗

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

void combine3(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);  // 获取数组起始地址
    *dest = IDENT;
    for (i = 0; i < length; i++){
        data_t val;
        *dest = *dest OP data[i];  // 将函数调用get_vec_element(v, i, &val)改为内存偏移量
    }
}

消除不必要的内存引用⌗

void combine4(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;  // 计算结果保存在局部变量，减少内存寻址次数
    for (i = 0; i < length; i++){
        data_t val;
        acc = acc OP data[i];
    }
    *dest = acc;
}

循环展开⌗

void combine5(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    // 2x1 循环展开
    for (i = 0; i < limit; i+=2){
        acc = (acc OP data[i]) OP data[i+1];
    }
    for (; i < length; i++){
        acc = acc OP data[i];
    }
    *dest = acc;
}

提高并行性⌗

void combine6(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;  // 多个累积变量
    data_t acc1 = IDENT;

    // 2x2 循环展开
    for (i = 0; i < limit; i+=2){
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }
    for (; i < length; i++){
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;
}

到这里程序已经突破了延迟界限。

重新结合变换⌗

void combine7(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    // 2x1a 循环展开
    for (i = 0; i < limit; i+=2){
        acc = acc OP (data[i] OP data[i+1]);  // 重新结合
    }
    for (; i < length; i++){
        acc = acc OP data[i];
    }
    *dest = acc;
}

这个优化是combine5的变体，虽然整数+运算没有突破延迟界限，其他运算都突破了延迟界限。

SIMD向量指令⌗

使用AVX可以获得4到8倍的加速，需要immintrin.h头文件。

一些限制因素⌗

寄存器溢出

循环展开的并行度如果超出了寄存器个数，会造成寄存器溢出，编译器将局部变量分配到栈上，造成性能下降。解决办法是控制循环展开的数量。

分支预测错误处罚在参考机上，预测错误处罚时19个时钟周期，损耗很大。解决办法是通过 “功能性的” 代码代替 “命令式的” 代码。例如：

// 优化前命令式
void minmax1(long a[], long b[], long n){
    long i;
    for (i = 0; i <n; i++){
        if (a[i] > b[i]){  // 分支预测错误时损耗很大
            long t = a[i];  // 交换a[i]和b[i]
            a[i] = b[i];
            b[i] = t;
        }
    }
}

// 优化后功能性的
void minmax1(long a[], long b[], long n){
    long i;
    for (i = 0; i <n; i++){
        long min = a[i] < b[i] ? a[i] : b[i];  // 编译为条件传送汇编代码，避免分支预测
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

理解内存性能⌗

略

性能提高技术⌗

1 高级设计⌗

选择适当的算法和数据结构

2 基本编码原则⌗

消除连续函数调用，将计算移到循环外
消除不必要的内存引用

3 低级优化⌗

循环展开
使用多个累积变量、重新结合技术提高指令级并行
用功能性风格重写条件操作，使编译采用条件传送

性能剖析⌗

gprof