性能分析

程序性能不仅由算法复杂度决定，常数因子也会造成明显差异。优化通常需要同时考虑算法、数据表示、过程调用和循环结构。

性能分析的基本目标：

  • 理解程序如何被编译和执行。
  • 测量程序性能并定位瓶颈。
  • 在不破坏代码模块化和通用性的前提下改进性能。

常用时间尺度包括绝对时间和时钟周期。机器指令通常以纳秒为尺度；处理器频率越高，单个时钟周期越短。例如 100 MHz 的时钟周期约为 10 ns，2 GHz 的时钟周期约为 0.5 ns。

对向量或链表类程序，常用 CPE Cycles Per Element 表示单位元素的处理代价：

T(n)=CPE⋅n+overheadT(n)=\text{CPE}\cdot n+\text{overhead}

其中 nn 是数据长度，T(n)T(n) 是总运行时间。CPE 越低，单位元素处理效率越高。

性能优化应优先关注内层循环，因为内层循环通常贡献最多执行次数。

prefix sum 示例可用于观察 CPE：

1
2
3
4
5
6
7
8
9
void psum1(float a[], float p[], long n)
{
    long i;
    /* 前缀和第 0 项直接等于输入第 0 项。 */
    p[0] = a[0];
    for (i = 1; i < n; i++)
        /* 每个 p[i] 依赖上一项 p[i-1]，形成串行依赖链。 */
        p[i] = p[i-1] + a[i];
}

一次循环处理两个元素可减少部分循环控制开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void psum2(float a[], float p[], long n)
{
    long i;
    p[0] = a[0];
    for (i = 1; i < n-1; i += 2) {
        /* 先计算 p[i]，复用该中间值继续计算 p[i+1]。 */
        float mid_val = p[i-1] + a[i];
        p[i] = mid_val;
        p[i+1] = mid_val + a[i+1];
    }
    if (i < n)
        /* 处理奇数长度时剩余的最后一个元素。 */
        p[i] = p[i-1] + a[i];
}

psum2 降低了循环开销，但前缀和本身存在数据依赖：p[i] 依赖 p[i-1]，因此无法完全并行。

机器无关优化

向量抽象数据类型

示例程序使用一个向量 ADT。它用结构体保存长度和数据指针，并通过过程接口访问长度、元素和起始地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long data_t;

typedef struct {
    /* 当前向量长度。 */
    long len;
    /* 指向底层数组的指针。 */
    data_t *data;
} vec_rec, *vec_ptr;

vec_ptr new_vec(long len);
long vec_length(vec_ptr v);
data_t *get_vec_start(vec_ptr v);
int get_vec_element(vec_ptr v, long index, data_t *dest);

get_vec_element 会进行边界检查，new_vec 负责分配头部结构和数组空间；若数组分配失败，需要释放已分配的头部结构并返回 NULL。这种接口封装简化了调用方逻辑，但也可能隐藏循环中的访问成本。

combine1 将向量中所有元素合并，IDENT 和 OP 由编译期常量决定，可表示整数或浮点数的加法、乘法。

1
2
3
4
5
6
7
8
9
10
11
12
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 = *dest OP val;
    }
}

循环不变量

combine1 在每次循环迭代中调用 vec_length(v)。该值在循环期间不变，可以移动到循环外：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void combine2(vec_ptr v, data_t *dest)
{
    long i;
    /* vec_length(v) 在整个循环中不变，提前保存避免每轮重复调用。 */
    long length = vec_length(v);

    /* dest 保存最终累积结果，IDENT 是该运算的单位元。 */
    *dest = IDENT;
    for (i = 0; i < length; i++) {
        data_t val;
        /* 仍通过抽象接口读取元素，每轮都会发生一次函数调用。 */
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

代码移动适用于循环不变量：表达式结果在每次迭代中相同，就应避免重复计算。

减少过程调用

combine2 仍在每次迭代中调用 get_vec_element。可以提前取得数组起始地址，在循环中直接访问数组：

1
2
3
4
5
6
7
8
9
10
11
12
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++)
        /* 避免 get_vec_element 的函数调用和边界检查开销。 */
        *dest = *dest OP data[i];
}

该优化减少了内层循环中的函数调用和边界检查。PPT 中指出，这一修改本身不一定带来明显性能提升，因为仍存在不必要的内存读写。

消除不必要内存引用

combine3 在每次循环中读取并写回 *dest。若将累积值保存在局部变量中，编译器通常可以把它放入寄存器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void combine4(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    /* acc 是局部累积变量，编译器通常可将其放入寄存器。 */
    data_t acc = IDENT;

    for (i = 0; i < length; i++)
        /* 循环内只更新 acc，不再反复读写 *dest。 */
        acc = acc OP data[i];

    /* 循环结束后一次性写回目标地址。 */
    *dest = acc;
}

combine3 的循环每轮需要从 dest 读一次、向 dest 写一次。combine4 只在循环结束后写回结果，减少了每轮内存访问。

1
2
3
4
5
6
7
# combine3 的核心行为
read  *dest
apply OP with data[i]
write *dest

# combine4 的核心行为
acc = acc OP data[i]

优化效果

以 CPE 为单位，combine4 相比 combine1 有明显下降：

函数 方法 整数加法 整数乘法 浮点加法 浮点乘法
combine1 抽象接口，-O1 10.12 10.12 10.17 11.14
combine4 局部变量累积 1.27 3.01 3.01 5.01

主要收益来自：

  • 减少内层循环中的函数调用。
  • 减少内层循环中的内存引用。
  • 让编译器更容易使用寄存器保存临时值。

优化编译器的能力与限制

优化编译器通常能完成寄存器分配、指令选择、指令排序和小规模低效代码消除，但通常不会改变算法复杂度。选择合适算法和数据结构仍由程序员负责。

编译器的基本约束是：在任何可能条件下都不能改变程序行为。因此它会保守处理两类常见阻碍。

有些性质对程序员很明显，但编译器不一定能证明。例如某个 int 变量实际只会取少量枚举值，或者数组下标实际不会越界；只要无法在语言语义层面证明，编译器就必须保守。

函数调用与副作用

以下两个函数在数学表达上相似，但不一定等价：

1
2
3
4
5
6
7
8
9
10
11
12
13
int f(int);

int func1(int x)
{
    /* f(x) 被调用四次；若 f 有副作用，每次调用都可能改变程序状态。 */
    return f(x) + f(x) + f(x) + f(x);
}

int func2(int x)
{
    /* f(x) 只调用一次，因此不能在一般情形下等价替换 func1。 */
    return 4 * f(x);
}

若 f 有副作用，则两者行为不同：

1
2
3
4
5
6
7
int counter = 0;

int f(int x)
{
    /* 后缀自增先返回旧值，再把全局 counter 加 1。 */
    return counter++;
}

此时 func1 会调用 f 四次，而 func2 只调用一次。编译器不能把 func1 自动改写为 func2。

内存别名

内存别名指两个不同表达式引用同一内存位置。例如：

1
2
3
4
5
6
7
8
9
10
11
12
void twiddle1(int *xp, int *yp)
{
    /* 两次都从 *yp 读取；若 xp == yp，第一次更新会影响第二次读取。 */
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(int *xp, int *yp)
{
    /* 只读取一次 *yp；在 xp == yp 时与 twiddle1 的结果不同。 */
    *xp += 2 * *yp;
}

若 xp == yp，两段代码结果不同。类似问题也会影响 combine3 和 combine4：

1
2
3
4
v = [2, 3, 5];
// dest 指向 v[2]，因此目标位置与输入数组发生别名。
combine3(v, get_vec_start(v) + 2);
combine4(v, get_vec_start(v) + 2);
函数 初始状态 循环前 i=0 i=1 i=2 最终状态
combine3 [2,3,5] [2,3,1] [2,3,2] [2,3,6] [2,3,36] [2,3,36]
combine4 [2,3,5] [2,3,5] [2,3,5] [2,3,5] [2,3,5] [2,3,30]

combine3 先把目标位置改为 IDENT，随后又从同一数组位置读取值，因此结果受到别名影响。combine4 在局部变量中累积，最后才写回。

在 C 语言中，地址运算和直接内存访问容易产生别名。内层循环中使用局部变量累积，既能减少内存访问，也能向编译器表达更明确的数据依赖。

现代处理器

基本特征

现代处理器通常具有两个关键特征：

  • Superscalar：每个时钟周期可执行多个操作。
  • Out-of-Order Execution：实际执行顺序可以不同于汇编程序中的指令顺序，只要保持程序语义不变。

这些机制利用 指令级并行 Instruction-Level Parallelism, ILP 提高吞吐。

处理器结构

现代处理器可分为两个主要部分。

部件 职责
指令控制单元 ICU 从内存读取指令，将指令解码为较简单的操作，并处理分支预测、寄存器更新和提交。
执行单元 EU 接收操作并在功能单元上执行，包括算术、加载、存储和分支等。

指令解码与寄存器重命名

一条复杂机器指令可能被解码为多个简单操作。例如：

1
addq %rax, 8(%rdx)  # 将 %rax 加到内存地址 8(%rdx) 对应的值上

可理解为：

1
2
3
load 8(%rdx) -> t1       # 从内存读出原值
addq %rax, t1 -> t2      # 在内部临时寄存器中完成加法
store t2, 8(%rdx)        # 把结果写回同一内存位置

寄存器重命名将同一程序寄存器的不同版本分开表示。例如：

1
2
3
addq $8, %rdx                 # 程序视角：更新 %rdx
# 可重命名为
addq $8, %rdx.0 -> %rdx.1     # 硬件内部：旧版本读入，新版本写出

重命名表维护程序寄存器与内部标签之间的对应关系，这样可以消除部分名称相关。以内层循环为例：

1
2
3
4
5
.L25:
    vmulsd (%rdx), %xmm0, %xmm0  # 从 data[i] 取值并与累积值相乘
    addq   $8, %rdx              # 指针前进到下一个 double 元素
    cmpq   %rax, %rdx            # 比较当前指针和循环结束地址
    jne    .L25                  # 未到结束地址则继续循环

可拆分为：

1
2
3
4
5
load (%rdx.0)      -> t.1        # 读取当前元素，生成临时值
mulq t.1, %xmm0.0 -> %xmm0.1    # 使用旧累积值，产生新累积值
addq $8, %rdx.0   -> %rdx.1     # 生成下一轮使用的新指针
cmpq %rax, %rdx.1 -> cc.1       # 生成条件码版本 cc.1
jne-taken cc.1                  # 分支依赖条件码结果

其中：

  • load 从内存生成临时值。
  • mulq 只处理寄存器操作数。
  • %xmm0 和 %rdx 在不同迭代中具有不同版本。
  • 条件码也可像寄存器一样被标记，用于连接比较指令和分支指令。

若分支预测失败，执行单元通知指令控制单元，后者丢弃错误路径上的操作，并从正确位置重新取指。

功能单元与流水线

功能单元从 ICU 接收操作，并在每个周期执行多个操作。Haswell Core i7 中的典型端口功能如下：

端口 可执行操作
0 整数运算、浮点乘法、整数/浮点除法、分支
1 整数运算、浮点加法、整数乘法、浮点乘法
2 加载、地址计算
3 加载、地址计算
4 存储
5 整数运算
6 整数运算、分支
7 存储地址计算

两个重要性能指标：

  • 延迟 Latency：一个操作从发射到完成需要的周期数。
  • 发射间隔 Issue Time：同一功能单元上连续发射同类操作所需间隔。

如果整数乘法延迟为 3 周期、发射间隔为 1 周期，说明该功能单元是流水线化的：单个操作完成较慢，但可以每周期接收新操作。

吞吐下界由可执行该操作的功能单元数量、发射间隔和其他资源限制共同决定。例如浮点乘法可由多个端口执行时，理论吞吐可低于 1 cycle/op；但在完整循环中，加载、存储和循环控制也可能成为限制因素。

乱序调度

操作会在满足以下条件时被派发到功能单元：

  • 所有操作数已经就绪。
  • 对应类型的功能单元可用。

执行结果可以通过数据转发直接传给后续功能单元，不必先写回寄存器文件。

乱序执行提高的是可用并行度；若代码存在严格数据依赖，关键路径仍会限制性能。

关键路径与循环展开

combine4 使用单个累积变量 acc，每次迭代都依赖上一轮结果，因此形成关键路径。对乘法而言，浮点乘法延迟会直接限制吞吐。

循环展开可以减少循环控制开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void combine5(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    /* 每轮处理 2 个元素，limit 确保 data[i+1] 不越界。 */
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for (i = 0; i < limit; i += 2)
        /* 2*1 展开：两个元素合并到同一个累积变量 acc。 */
        acc = acc OPER data[i] OPER data[i+1];

    for (; i < length; i++)
        /* 处理奇数长度数组剩余的最后一个元素。 */
        acc = acc OPER data[i];

    *dest = acc;
}

这是 2 * 1 展开：每轮处理 2 个元素，但只有 1 个累积变量，因此仍有单条依赖链。

多累积变量

多累积变量可把一条依赖链拆成多条独立依赖链：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;

    for (i = 0; i < limit; i += 2) {
        /* 偶数下标元素进入 acc0，奇数下标元素进入 acc1。 */
        acc0 = acc0 OPER data[i];
        acc1 = acc1 OPER data[i+1];
    }

    for (; i < length; i++)
        /* 若元素个数为奇数，剩余元素并入 acc0。 */
        acc0 = acc0 OPER data[i];

    /* 最后再合并两条累积链。 */
    *dest = acc0 OPER acc1;
}

该方法让两个累积链并行执行，更容易利用多个功能单元。

重结合变换

重结合改变表达式结合顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;

    for (i = 0; i < limit; i += 2)
        /* 先组合 data[i] 与 data[i+1]，再与 acc 组合，改变结合顺序。 */
        acc = acc OPER (data[i] OPER data[i+1]);

    for (; i < length; i++)
        /* 处理展开后剩余的尾部元素。 */
        acc = acc OPER data[i];

    *dest = acc;
}

这种写法让部分元素先彼此组合，再与累积值组合，可缩短部分依赖链。需要注意，对于浮点运算，重结合可能改变舍入结果，编译器通常不会在默认条件下自动执行这类变换。

机器相关优化包括：循环展开，多累积变量，重结合变换。

机器无关优化包括：消除循环低效，减少过程调用，消除不必要的内存引用。

分支预测

ICU 需要提前生成足够操作以保持 EU 忙碌，因此会进行分支预测和推测执行。

分支预测的流程：

  1. 预测分支是否跳转。
  2. 按预测路径取指、解码和执行。
  3. 在分支结果确认前，不真正修改体系结构可见的寄存器或内存状态。
  4. 若预测失败，丢弃错误路径结果并从正确位置继续。

退休单元将指令放入 FIFO 队列，并保证顺序语义：

  • Retired：指令操作完成，分支预测正确，寄存器或内存更新正式生效。
  • Flushed：分支预测失败，已计算结果被丢弃，不改变程序状态。

Core i7 上一次分支预测失败大约浪费 19 个时钟周期。可预测分支通常影响较小，例如循环结束分支通常只在最后一次产生预测失败。

避免不可预测分支

以下代码根据条件进行交换：

1
2
3
4
5
6
7
8
9
10
11
12
void minmax1(int a[], int b[], int n)
{
    int i;
    for (i = 0; i < n; i++) {
        /* 若条件结果接近随机，该分支容易预测失败。 */
        if (a[i] > b[i]) {
            int t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

如果 a[i] > b[i] 难以预测，分支失败会造成损失。可改写为条件表达式：

1
2
3
4
5
6
7
8
9
10
11
void minmax2(int a[], int b[], int n)
{
    int i;
    for (i = 0; i < n; i++) {
        /* 条件表达式可被编译为条件传送，避免显式跳转。 */
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

该版本避免显式分支，更适合分支结果随机的情况。若分支高度可预测，则改写收益可能不明显。

加载和存储性能

加载和存储通过数据缓存访问内存。加载或存储单元每周期可发起的操作数有限，因此内存访问可能成为吞吐瓶颈。

链表长度计算示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct ELE {
    /* 指向下一个链表节点。 */
    struct ELE *next;
    /* 当前节点保存的数据。 */
    int data;
} list_ele, *list_ptr;

long list_len(list_ptr ls)
{
    long len = 0;
    while (ls) {
        len++;
        /* 下一次迭代的地址依赖当前节点的 next。 */
        ls = ls->next;
    }
    return len;
}

循环中下一次加载地址依赖当前节点的 next 指针，形成指针追逐，难以通过乱序执行并行化。

存储也可能受限。示例：

1
2
3
4
5
6
7
8
9
void array_clear(int *dest, int n)
{
    int i;
    /* limit 控制循环次数；示例关注连续存储的吞吐行为。 */
    int limit = n - 3;
    for (i = 0; i < limit; i++)
        /* 连续写入 dest[i]，地址按 int 大小递增。 */
        dest[i] = 0;
}

连续写数组时，吞吐受存储单元发射能力和存储缓冲区影响。

存储后立即读取也可能产生相关性：

1
2
3
4
5
6
7
8
9
10
11
void write_read(long *src, long *dest, long n)
{
    long cnt = n;
    long val = 0;
    while (cnt) {
        /* 先写 dest。若 src 与 dest 可能别名，后续读 src 需等待写入关系确认。 */
        *dest = val;
        val = (*src) + 1;
        cnt--;
    }
}

若调用 write_read(&a[0], &a[1], 3)，读写地址不同；若调用 write_read(&a[0], &a[0], 3)，读写地址相同，会出现存储到加载的相关性。处理器需要通过存储缓冲区匹配地址并转发数据，以保证语义正确。

性能调优

调优流程

性能调优应先测量，再修改：

  1. 做计时研究。
  2. 识别热点。
  3. 优先使用更好的算法或数据结构。
  4. 在热点代码上进行局部优化。

不应先从局部代码技巧开始。算法和数据结构的改进通常比单条语句优化更重要。

Amdahl 定律

若程序中比例为 α\alpha 的部分被加速 kk 倍，总体加速比为：

S=ToldTnew=1(1−α)+αkS=\frac{T_{old}}{T_{new}}=\frac{1}{(1-\alpha)+\frac{\alpha}{k}}

当该部分被无限加速时：

S∞=11−αS_{\infty}=\frac{1}{1-\alpha}

PPT 示例中，原始时间 Told=209.0T_{old}=209.0，热点部分时间 Tpart=203.7T_{part}=203.7，因此 α=203.7/209.0=0.974\alpha=203.7/209.0=0.974，理论极限加速比 S∞=39.0S_{\infty}=39.0。若新时间为 5.45.4，实际加速比为 209.0/5.4=38.5209.0/5.4=38.5。

应优先优化耗时最多的热点部分。热点可以使用 gprof 工具来定位。