最近在恶补计算机基础知识，学到CSAPP第五章的内容，在这里总结并且展开一下C++程序性能优化相关的内容。

衡量程序性能的方式

一般而言，程序的性能可以用CPE（Cycles Per Element）来衡量，其指的是处理每个元素所需的CPU时钟周期数，计算公式为：CPE = 总执行周期数/处理的元素数量。

计算方式为：

#include <iostream>
#include <chrono>

const int N = 1000000;
int arr[N];

void test_function() {
    for (int i = 0; i < N; i++) {
        arr[i] = i * 2;
    }
}

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    test_function();
    auto end = std::chrono::high_resolution_clock::now();

    double elapsed_cycles = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 2.5; // 假设CPU 2.5 GHz
    double cpe = elapsed_cycles / N; // 计算 CPE

    std::cout << "CPE: " << cpe << std::endl;
    return 0;
}

影响编译器优化的因素

用gcc时，gcc -Og可以指定优化方式，但随着优化等级升高，程序规模也可能增加。

gcc优化等级

• -O1：不会进行激进优化（如函数内联、代码重排序），不会影响可读性，编译时间仍然较短。优化包括死代码消除、常量传播、循环优化等。
• -O2：在基本优化的基础上增加更高级优化：消除冗余计算、循环展开、指令调度、函数内联、分支预测优化，仍然不会进行极端优化。
• -O3：实现更激进的循环展开、自动使用SIMD指令，使函数尽可能内联，并消除冗余加载和存储，对复杂的数学运算进行优化。但可能导致代码膨胀，过度优化会导致性能下降，如缓存效率降低。
• -Os：基于-O2，但会避免增加代码大小的优化，适合嵌入式系统。

以下为一些妨碍编译器优化的因素：

内存别名使用

对于以下看似相同的代码段：

//代码段1
void twiddle1(long *xp, long *yp){
	*xp += *yp;
	*xp += *yp;
}

//代码段2
void twiddle2(long *xp, long* yp){
	*xp += 2* *yp;
}

很显然，代码段2的执行所需耗费时间更短，其需要的内存访问次数更少。

然而，编译器无法将代码1优化为代码2，因为当yp=xp时，代码1等效于xp = 4 xp, 而代码2等效于 *xp = 3 * *xp，编译器不知道函数该如何被调用。这种两个指针可能指向同一个内存位置的情况称为内存别名使用，在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中同一位置。

修改全局程序状态的函数

对于以下看似相同的代码段：

long counter = 0;
long f(){
	return counter++;
}
//代码段1
long func1(){
	return f()+f()+f()+f();
}
//代码段2
long func2(){
	return 4*f();
}

当函数f的返回值涉及到全局变量counter时，可以看出，func1的输出为6，而func2的输出为0。

将函数定义为内联函数，可以直接将函数调用替换为函数体，例如，代码段1在o1优化下可以展开为：

long funclin(){
	long t = counter++;
	t += counter++;
	t += counter++;
	t += counter++;
	return t;
}

如果使用-o2及以上优化，可能会展开为：

long funclin() {
    long tmp = counter;
    counter += 4;
    return tmp + (tmp + 1) + (tmp + 2) + (tmp + 3);
}

直接优化方法

为了举例说明优化方法是如何实现的，我们定义向量数据结构如下：

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

data_t代表基本元素的数据类型。

定义初始化该向量、访问向量元素以及获取向量长度的方法如下：

/* Create vector of specified length */
vec_ptr new_vec(long len)
{
    /* Allocate header structure */
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    data_t *data = NULL;
    if (!result)
        return NULL;  /* Couldn't allocate storage */
    result->len = len;
    /* Allocate array */
    if (len > 0) {
        data = (data_t *)calloc(len, sizeof(data_t));
        if (!data) {
            free((void *) result);
            return NULL; /* Couldn't allocate storage */
        }
    }
    /* Data will either be NULL or allocated array */
    result->data = data;
    return result;
}

/*
 * Retrieve vector element and store at dest.
 * Return 0 (out of bounds) or 1 (successful)
 */
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;
}

/* Return length of vector */
long vec_length(vec_ptr v)
{
    return v->len;
}

采用计算向量元素乘积的初始代码如下：

#define IDENT 1
#define OP *
/* Implementation with maximum use of data abstraction */
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;
    }
}

对于这段初始代码，有一些方向可以进行优化改进。

提高循环效率

代码移动

代码移动指的是将在循环里需要执行多次但计算结果不会改变的计算移动到循环外：

#define IDENT 1
#define OP *
/* Implementation with maximum use of data abstraction */
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;
}

/* Direct access to vector 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];
    }
}

这种写法和combine2相比，减少了索引与数组边界的比较，但优化效果并不明显。

消除不必要的内存引用

对于combine3的赋值过程：

*dest = *dest OP data[i];

需要访问*dest指针的值，再根据这个地址从内存中取dest数组的值，并在计算完成后赋值到对应的内存上，在每次迭代过程中都要完成这样一个从内存读写数据的过程，将函数继续简化，减少对内存的读写：

void combine4(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
		data_t cur = IDENT;
    for (i = 0; i < length; i++) {
        cur = cur OP data[i];
    }
    *data = cur;
}

考虑机器特性的优化方法

上述优化方法都没有依赖目标机器的任何特性，如果要进一步提升性能，则需要考虑利用处理器微体系结构进行优化。

现代处理器结构

现代微处理器的简化示意图如下图所示，其可以分为指令控制单元ICU和执行单元EU两部分。

• 取指控制：ICU从指令高速缓存中读取指令，并在译码后将对应的操作发送到EU。一般来说，会在当前执行的指令很早之前就进行取指。然而当程序遇到分支时，处理器采用分支预测技术，会猜测是否选择该分支并预测其目标地址。使用投机执行技术，处理器会在确定分支预测是否正确前就跳到分支对应的指令，甚至开始执行这些对应的操作。如果分支预测错误，则将状态重新设为分支点的状态。
• 指令译码：接收实际的程序指令并将其转换为一组基本操作。
• 加载和存储单元：内置加法器，用于读写内存。
• 分支单元：向ICU返回分支预测是否正确的结果。
• 算术运算单元：执行整数和浮点数操作的不同组合。
• 退役单元：记录正在进行的处理，并确保其遵守机器级程序的语义。退役单元包含了多种寄存器，并控制这些寄存器的更新。指令译码时，其信息被放置在一个队列中，直到分支点预测结果出现，若预测正确，则程序寄存器的更新将被实际执行。任何对程序寄存器的更新都只会在指令退役的时候才会发生。

功能单元的性能

对于功能单元进行运算的性能，有以下几个指标可以用来衡量：

延迟L：表示完成运算所需要的总时间

发射时间I：表示两个连续的同类型运算之间需要的最小周期数

容量C：表示能够执行该运算的功能单元的数量

操作的吞吐量=C/I

对于一个执行n个乘法的函数，若其需要L*n+K个周期，其中K为调用函数和初始化等开销，此时CPE=L，对于单个按照顺序执行的功能单元组成的函数，延迟L表明了CPE的最小值，而对于多个功能单元组成的函数，还需要考虑其吞吐量。

处理器操作的抽象模型

将函数combine4的循环部分转换为汇编代码：

Inner loop of combine44. data_t = double, OP = *
acc in %xmm0, data+i in %rdx, data+length in %rax
1 .L25:
2 vmulsd (%rdx), %xmm0, %xmm0    loop: Multiply acc by data[i]
3 addq $8, %rdx                  Increment data+i
4 cmpq %rax, %rdx                Compare to data+length
5 jne .L25                       If !=, goto loop

将其抽象为数据流图，并去除不影响数据流的指令：

可以看出，乘法和加法运算是制约循环性能的两个因素，而浮点乘法的延迟约为整数加法的5倍，其成为了最关键的制约原因，程序的CPE为5。循环中的其他操作与乘法器并行地执行。

循环展开

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

其优点为，可以提高缓存命中率，增加循环体内语句并发执行的可能性，同时减少分支预测失败的可能性。

用循环展开继续改进上述代码为：

/* 2 x 1 loop unrolling */
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 cur= IDENT;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2) {
        cur= (cur OP data[i]) OP data[i + 1];
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
        cur =  cur OP data[i];
    }

    *dest = cur;
}

编译器可以很轻松地执行循环展开，用GCC的优化等级大于等于3时就会执行循环展开。

提高并行性

我们知道，乘法操作和加法操作是可以并行化的，也就是说，不需要等待对方完成即可进行下一次操作，可以在每个时钟周期就开始一次新的操作。但目前的代码还并不能更高速率地执行乘法和加法，这是因为我们将累积值放在一个单独的变量cur中，在前面计算完成之前都不能计算cur的新值。

为了提高并行性，我们可以用多个累积变量分别计算：

void combine6(vec_ptr v, data_t *dest){
	long i;
	long length = vec_length(v);
	long limit = length - 1;
	data_t cur0 = IDNET;
	data_t cur1 = IDNET;
	for(i = 0; i <limit; i+=2){
		cur0 = cur0 OP data[i];
		cur1 = cur1 OP data[i+1];
	}
	for(; i < length; i++)
		cur0 = cur0 OP data[i];
	*dest = cur0 OP cur1;
}

我们可以将多个累积变量变换归纳为将循环展开k次，以及并行累积k个值，得到k×k的循环展开，当k足够大时，程序在所有情况下几乎都能达到吞吐量界限。通常，只有保持能执行该操作的所有功能单元的流水线都是满的，程序才能达到这个操作的吞吐量界限，对延迟为L，容量为C的操作而言，要求循环展开因子k ≥ L*C即可达到最大吞吐量。

除了以上并行累计的方式以外，还可以通过重新结合变换的方式对combine5进行继续优化：

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 cur = IDENT;
	for(i = 0; i < limit; i+=2){
		cur = cur OP (data[i] OP data{i+1]);
	}
	for(; i < length; i++)
		cur = cur OP data[i];
	*dest = cur;
}

combine7和combine5的区别在于**data[i] OP data[i+1]**计算的先后顺序不同，而(data[i] OP data[i+1])时可以被并行计算的，因为它不依赖于cur的计算结果，可以提前计算。（现代CPU的超标量架构，可以在一个时钟周期内执行多个独立的指令，如果两个指令没有数据依赖，CPU可以同时执行它们。）

书写适用于条件传送的代码

条件传送（Conditional Move, CMOV） 是一种 CPU 指令优化技术，它允许根据条件决定是否执行数据传送，而不使用传统的条件跳转（branching）。
在 x86 架构中，CMOV 指令集（如 CMOVZ, CMOVNZ, CMOVL 等）可以在满足某些条件时，将值从一个寄存器传送到另一个寄存器，而不会触发分支预测失败的问题。

在 C++ 中，我们可以使用 条件运算符（?:）、内联汇编（asm）、标准库函数（std::max） 以及 SIMD 指令 来实现 条件传送。

在现代C++编译器中，使用三元运算符可能被编译器优化为CMOV指令：

#include <iostream>

//传统条件分支的代码
int branching(int x, int y){
	if (x > y)
		return x;
	else
		return y;
	}
//使用条件传送的代码
int conditional_move(int x, int y) {
    return (x > y) ? x : y;  // 编译器可能优化为 CMOV
}

int main() {
    int a = 5, b = 10;
    std::cout << "Max: " << conditional_move(a, b) << std::endl;
    return 0;
}

除此之外，gcc在 -O2 或更高级别优化下，std::max(a, b) 可能会被优化为 CMOV 指令