CPU程序性能优化

作者：MegEngine

链接：https://my.oschina.net/u/5265910/blog/10143748

简单认识编译器

编译器的优化选项

• -O<number>，其中 number 为 0/1/2/3，数字越大，优化级别越高。默认为 -O0。

• -Ofast，除了开启 -O3 的所有优化选项外，会额外打开 -ffast-math 和 -fallow-store-data-races。注意这两个选项可能会引起程序运行错误。

• -Og，调试代码时推荐使用的优化级别。

编译器的限制

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

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

2、side effect

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

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

程序性能优化

typedef struct {
    long len;
    data_t *data;
} vec_rec, *vec_ptr;

/* 创建vector */
vec_ptr new_vec(long len) {
    vec_ptr result = (vec_ptr)malloc(sizeof(vec_rec));
    if (!result)
        return NULL;
    data_t *data = NULL;
    result->len = len;
    if (len > 0) {
        data = (data_t*)calloc(len, sizeof(data_t));
        if (!data) {
            free(result);
            return NULL;
        }
    }
    result->data = data;
    return result;
}

/* 根据index获取vector元素 */
int get_vec_element(vec_ptr v, long index, data_t *dest) {
    if (index < 0 || index >= v->len)
        return 0;
    *dest = v->data[index];
    return 1;
}

/* 获取vector元素个数 */
long vec_length(vec_ptr v) {
    return v->len;
}

void combine1(vec_ptr v, data_t *dest) {
    long i;

    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

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++) {
        *dest = *dest OP data[i];
    }
}

// combine3 -O1
.L1:
    vmovsd (%rbx), %xmm0
    vmulsd (%rdx), %xmm0, %xmm0
    vmovsd %xmm0, (%rbx)
    addq $8, %rdx
    cmpq %rax, %rdx
    jne .L1

// combine3 -O2
.L1
    vmulsd (%rdx), %xmm0, %xmm0
    addq $8, %rdx
    cmpq %rax, %rdx
    vmovsd %xmm0, (%rbx)
    jne .L1

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++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

// combine4 -O1
.L1
    vmulsd (%rdx), %xmm0, %xmm0
    addq $8, %rdx
    cmpq %rax, %rdx
    jne .L1

• combine1 版本不同编译优化级别，-O1 的性能是 -O0 的两倍，表明开启适当地编译优化级别是很有必要的。

• combine2 将 vec_length 移出循环后，在同样的优化级别编译，相较 combine1 的性能有微小的提升。

• 但是 combine3 相比 combine2 并没有性能提升，原因是由于循环中的其它操作的耗时可以掩盖调用 get_vec_element 的耗时，之所以可以掩盖，得益于 CPU 支持分支预测和乱序执行，本文的后面会简单介绍这两个概念。

• 同样地，combine3 的 -O2 版本比 -O1 版本性能好很多，从汇编码可以看到，-O2 时比 -O1 每次循环减少了一次对 (% rbx) 的读，更重要的是消除了对 (% rbx) 写后读的访存依赖。

• 经过 combine4 将中间结果暂存到临时变量的优化，可以看到即使使用 -O1 的编译优化，也比 combine3 -O2 的编译优化性能更好，表明即使编译器有强大的优化能力，但是注意细节来编写高性能代码也是非常有必要的。

以下测试数据引用自《深入理解计算机系统》第五章。

指令级并行

完整的 Intel Core i7 Haswell 的硬件结构见：https://en.wikichip.org/w/images/c/c7/haswell_block_diagram.svg

硬件性能

• 指令级并行：即通过指令流水线技术，支持同时对多条指令求值。

• 乱序执行：指令的执行顺序未必和其书写的顺序一致，可以使硬件达到更好的指令级并行度。主要是通过乱序执行、顺序提交的机制，使得能够获得和顺序执行一致的结果。

• 分支预测：当遇到分支时，硬件会预测分支的走向，如果预测成功则能够加快程序的运行，但是预测失败的话则需要把提前执行的结果丢弃，重新 load 正确指令执行，会带来比较大的预测错误惩罚。

• 延迟：执行完一条指令需要的时钟周期数。

• 发射时间：两个连续的同类型的运算之间需要的最小时钟周期数。

• 容量：某种执行单元的数量。从上图可以看出，在 EUs 中，有 4 个整数加法单元 (INT ALU)、1 个整数乘法单元 (INT MUL)、1 个浮点数加法单元 (FP ADD) 和 2 个浮点数乘法单元 (FP MUL)。

• 延迟界限：任何必须按照严格顺序完成 combine 运算的函数所需要的最小 CPE，等于功能单元的延迟。

• 吞吐界限：功能单元产生结果的最大速率，由容量/发射时间决定。若使用 CPE 度量，则等于容量/发射时间的倒数。

处理器操作的抽象模型

1. 只读：这些寄存器只用作源值，在循环中不被修改，本例中的 %rax。

2. 只写：作为数据传送的目的。本例没有这样的寄存器。

3. 局部：在循环内部被修改和使用，迭代与迭代之间不相关，比例中的条件码寄存器。

4. 循环：这些寄存器既作为源值，又作为目的，一次迭代中产生的值会被下一次迭代用到，本例中的 %rdx 和 %xmm0。由于两次迭代之间有数据依赖，所以对此类寄存器的操作通常是程序性能的限制因素。 

将上图重排，并只留下循环寄存器相关的路径，可得到简化的数据流图。 

将简化完的数据流图进行简单地重复，可以得到关键路径，如下图。如果 combine4 中计算的是浮点数乘法，由于支持指令级并行，浮点数乘法的的延迟能够掩盖整数加法 (指针移动，图中右半边的路径) 的延迟，所以 combine4CPE 的理论下界就是浮点乘法的延迟 5.0，与上面给出的测试数据 5.01 基本一致。 

循环展开

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 acc0 = IDENT;
    data_t acc1 = IDENT;

    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;
}

combine5 的关键路径的数据流图如下，图中有两条关键路径，但两条关键路径是可以指令级并行的，每条关键路径只包含 n/2 个操作，因此性能可以突破延迟界限，理论上浮点乘法的 CPE 约为 5.0/2=2.5。 

SIMD(single instruction multi data)

参考资料

1. Randal E. Bryant, David R. O’Hallaron. Computer Systems: A Programmer’s Perspective, Chapter 5.

2. Antonio González, Fernando Latorre, Grigorios Magklis. Processor Microarchitecture: An Implementation Perspective, Chapter 1.

3. https://github.com/MegEngine/MegCC