💻 CSC3060 Week 12-13 Optimizing Program Performance

Project5 Code Optimization


Week 12-13 Optimization I&II

很多成本——性能改进，不只是算法或模型结构带来的，更大量来自系统层面的性能工程优化。 程序性能 = 算法 + 编译器 + 数据访问模式 + 硬件执行特性 + 测量方法。


编译器自动优化

编译器优化是保守的，虽然很强大，但是宁慢不错。

Compiler Flags

最基本的做法是在终端编译时打开优化选项 -On flags (在老版编译器中 n 为 0, 1, 2, 3, 4)，让编译器执行低级但稳定的优化：

  • -O0：不优化地快速编译，通常用于调试 debugging

  • -O1：基础优化，-O == -O1

  • -O2：Default 推荐的默认优化级别，通常是“效果好且稳”，代码量级不会显著变大

  • -O3：更激进，会做循环展开 (loop unrolling)、向量化 (SIMDilization) 等优化。

    ⚠️ 比如将以下循环 “按 4 展开 + 向量化”，同时利用加法 DLP 和寄存器并行；代价是代码变大，且可能影响 I-cache，可能反而导致性能下降。

    for (int i = 0; i < size; i++) a[i] = b[i] + c[i];
// 按 4 展开：
for (int i = 0; i < size-4; i += 4) {
    a[i]   = b[i]   + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];   // 四条相似代码可以向量化
}
for (i = 0; i + 3 < size; i += 4) {  
    A[i]   = B[i]   * k + C[i];
    A[i+1] = B[i+1] * k + C[i+1];
    A[i+2] = B[i+2] * k + C[i+2];
    A[i+3] = B[i+3] * k + C[i+3];
}
for (; i < nelts; i++) A[i] = B[i] * k + C[i];  // 加上 cleanup

    ⚠️ 当循环次数 size 不是展开宽度的倍数时，展开后的循环会漏掉最后剩下的元素；如果没有额外的收尾循环 (cleanup loop)，这个变换就是错误的。当 **size**小于展开宽度、递归循环、Aliasing 时也会错。

  • -O4：以前代表 Link-Time Optimization (程序全局分析)；较新的语境下常理解为在 -O3 基础上结合 LTO (等价于 -O3 -flto)

  • -Os：在 -O2 基础上，Optimize for size，以减小程序体积为目标进行优化 (关闭会明显增大代码体积的优化)。-Os 不一定比 -O2 慢，但是在计算密集型程序里，-O2 或 -O3 通常更快。

  • -Oz：更极端的优化体积。

其他非等级类 flag：(属于 -O3，比如 -O3 -march=native)

  • -flto：链接时优化 (Link-Time Optimization) ——让编译器在 Linker 阶段跨文件站在 “整个程序” 角度优化，比如 gcc -O3 -flto main.c helper.c -o app。可能导致编译/链接更慢和内存压力
  • -march=native：专门针对当前 CPU architecture 生成更合适的指令
  • -mtune=native：针对当前 CPU 调整调度策略，但确保兼容性
  • -fprofile-generate / -fprofile-use：PGO (Profile-Guided Optimization)，产生/利用运行画像 profile 做优化
  • -Ofast：等价于 –O3 -ffast-math，比 -O3 激进，但可能放宽浮点 FP 的严格语义进行重排序

性能优化的第一步往往不是改代码，而是先正确使用编译器。


Compiler Limitations

  • 当前，编译器并不能直接改变代码或提升 Complexity，只能做 Code Scheduling ——

    比如：如果你写了一个本质上是 O(n2) 的算法，编译器一般不可能把它变成 O(n log n) 或 O(n)。

  • 编译器必须严格保持程序语义，即使你觉得某些边界行为 (edge cases) “不重要”，编译器也不能擅自改。限制来源包括：memory aliasing、FP associativity (浮点不满足严格结合律)、函数副作用、volatile var.、内存一致性要求、异常语义……

    (Volatile: 声明 prone-to-change variables，比如 volatile int x，编译器禁止随意删改此类变量)

  • 编译器通常缺少/难以预测 Runtime & Domain 知识，不知道什么是好的数据分布。它不知道你的输入分布，不知道常见路径，也不知道业务语义。这就是为什么：Profile-Guided Optimization 有用 / 手工改 data layout 有用 / 某些领域特定优化必须由程序员提供 / 需要 dynamic translators。

    ⚠️ PGO 可以改善普通情况，但是最差情况 (比如网络服务器被攻击) 几乎无法预测。

  • 很多优化本身就是 NP 级别的困难问题

    比如：最优寄存器分配、最优指令调度、最优内存布局、优化编译器阶段顺序（phase ordering）

  • 一次基本只能分析一个 function、Boundary crossing 问题 (需要分离独立编译)：用 LTO 解决非常昂贵，但是逐渐被采用 (GCC, LLVM…)


AI-assisted Compiler

AI 已经可以帮助做：

  • heuristics tuning 启发式微调、phase ordering、inlining / register allocation 的启发式改进、cost model、autotuning kernels (CPU, GPU, TPU)、ML guided 调度优化

但 今天仍没有真正端到端、全能替代人的 AI 编译器。

编译器优化很强，AI 在加强编译器，但它们仍不能代替 “好算法 + 好数据布局 + 测量驱动的工程判断”。


Compiler Optimization Goals

1. 减少指令数量

  • Constant Folding：常量折叠——在编译期直接算出常量表达式。例如：0xFF << 8 直接折叠成常量结果 0xFF00，、strlen("Harry Bovik") 这种计算也可能被折叠。⚠️ 但是输入值若是变量就无法折叠。

  • CSE：公共子表达式消除 Common Subexpression Elimination，⚠️ 不多做重复计算——编译器非常擅长做 CSE，程序员一般不手工做。

    ⚠️ 整数加法可以安全重排，所以对于 a+b+c、c+a+b 是否可以 CSE —— long long、char 等可以；浮点加法因舍入误差等问题不能默认重排，所以 float、double 不安全。

    norm[i] = v[i].x*v[i].x + v[i].y*v[i].y;
// CSE:
elt = &v[i];
x = elt->x;
y = elt->y;
norm[i] = x*x + y*y

  • DCE：死代码消除 Dead Code Elimination，不 emit 无效计算——不只是删明显无效代码 (比如 if(0){…} 或被覆盖的赋值)，很多死代码其实是其他优化之后新产生的。

    ⚠️ cascading DCE 是唯一一种可以导致 1000x 显著提速的优化

  • SR：强度削弱 Strength Reduction，用便宜运算替代昂贵运算，比如避免 mul和 div

  • LICM：循环不变量外提 Loop Invariant Code Motion，把循环中每次都相同的计算移到循环外。 条件是每次迭代结果确实相同，外提后不改变语义

    long j;
for (j = 0; j < n; j++) a[n*i+j] = b[j];
// LICM: 
long j;
int ni = n*i;
for (j = 0; j < n; j++) a[ni+j] = b[j];

2. 减少执行周期

  • 尽量把数据全存在寄存器中 (RA: Register Allocation)
  • 利用 ILP 隐藏延迟，比如 Code Scheduling：比如把所有 lw 全部提前到 unrolled loop 最上方，并赋值给局部变量，以提前访存。现代 GCC、Clang、MSVC 在 unrolling/scheduling 上通常比人强，对 superscalar 和 OoO 机器，人手工调度往往不如编译器。
  • ⚠️ 因此，调度时为了把多条加载、多个中间值都先准备在 CPU 附近，必须有足够多的寄存器
  • 提前加载数据，消除冗余加载 (Preload, Redundant Load Elimination)
  • 改善局部性（cache-friendly access）

3. 减少分支或降低分支代价

  • 减少分支 (x86: conditional move / ARM: conditional execution)

通过以下方式展开代码减少分支造成的影响：

  • loop unrolling (-O3)：循环扩展，上文已介绍。

  • procedure inlining (-O1~-O3 逐渐加强)：过程内联扩展，把被调用函数的函数体，直接复制到调用处，属于 C++ OOP 的一种形式 (CSC3200 知识)。优点：不再传参/调用返回，方便后续的常量折叠/CSE/DCE；缺点：代码变大变慢、内联太多拖慢 I-cache、⚠️ 对递归函数不友好。

    内联本质是编译器衡量 “代码变大” 和 “解除调用” trade-off 的平衡点 (GPU kernels 通常内联所有调用)

    可以考虑：较小的函数、执行/调用频率低、嵌套深度浅(最好不递归)、传参有(很多)是常量 (可以引发 CF 等后续优化)…

  • unswitching (-O3)：循环条件扩展，**如果循环里的某个条件在整个循环过程中都不变，就把这个 if 从循环里搬出去。**优点：避免每轮循环都判断一次 if，方便后续的 unrolling, SIMDilization 等；缺点：复制循环段导致代码变大变慢、只有当条件在循环期间不变适用。

    for (int i = 0; i < n; i++) {
    if (flag) a[i] = b[i] + 1;
		else a[i] = b[i] - 1;
}
// Unswitching:
if (flag) {
    for (int i = 0; i < n; i++) a[i] = b[i] + 1;
} else for (int i = 0; i < n; i++) a[i] = b[i] - 1;
}

​ 本质和 LICM 一样，都是在循环中避免重复执行同样的工作。


Basic Compiler Optimizations

Local Optimizations：在 basic block 内部工作——常量折叠/SR/CSE (local)/DCE

Global Optimizations：处理函数体的整个控制流——code motion/loop unrolling/inlining/unswitching


Data Dependency Graph & Control Flow Graph

1. CFG：Control Flow Graph

控制流图描述程序可能沿哪些路径执行，解释程序接下来可能走到哪里

也就是分支、循环、基本块之间如何跳转。

2. DFG：Data Flow Graph

数据流图描述值如何在程序中传播。

它帮助分析：变量值从哪来/到哪要用、哪些表达式可复用 (CSE)、哪些代码无用 (DCE)、RA。

CFG & DFG 提供给编译器执行 -O1~-O3 的基础信息

3. DDG：Data Dependence Graph

DDG 是我们在 Project3-code scheduling 利用的图，强调指令间执行顺序约束 (常用于代码调度)

DFG 更偏向变量/值的流动分析。


Major Limit: Memory Aliasing

如果两个指针可能指向同一块内存 (内存重名)，那么编译器就必须保守。因为一边读写可能会影响另一边看到的值。

比如 对于一维数组 a 储存的 nxn 矩阵，用数组 b 表示其每行之和：

void sum_rows1(double *a, double *b, long n) {
    long i, j;     // i 表示行，j 表示列
    for (i = 0; i < n; i++) {
        b[i] = 0;
        for (j = 0; j < n; j++) b[i] += a[i*n + j];
    }
}

明显的是，b[i] 在同一个内层循环中始终是同一个位置 (一直表示矩阵的第 i 行)。 可不可以这样想？——

  1. 先把 b[i] 读一次到寄存器
  2. 在寄存器里不断加
  3. 最后循环结束时再一次性写回内存

答案是编译器不允许。编译器不能确定 a 和 b 会不会指向同一块内存或部分重叠 (Aliasing!)。也就是说，编译器不能只凭变量名不同就断定写 b[i] 一定不会影响 a[i*n+j]。不敢把 b 存在寄存器，最终结果只能非常保守——

  1. 从内存读 b[i]
  2. 加上一个 a[...]
  3. 立刻把结果写回 b[i]

优化是否合法，取决于程序语义是否允许。

用局部变量代替重复访存

如果采用局部变量，把代码改成：

void sum_rows2(double *a, double *b, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        double val = 0;
        for (j = 0; j < n; j++) val += a[i*n + j];
        b[i] = val;
    }
}

⚠️ b[i] 不再在内层循环中反复更新，只更新局部变量 val。

  • 局部标量天然更适合放寄存器
  • 不再每叠加一次 sw 一次，内层循环只读不写内存，计算在寄存器完成

restrict 承诺

void sum_rows1(double *restrict a, double *restrict b, long n) //···

这里的 restrict 是 C 语言给编译器的承诺：在这个指针的生命周期里，通过这个 restrict 指针访问的对象，不会再通过别的指针别名访问。

通俗说：

  • restrict a：告诉编译器，这块数据主要就通过 a 来访问
  • restrict b：告诉编译器，这块数据主要就通过 b 来访问
  • 同时暗示：a 和 b 指向的有效访问区域不会互相重叠

这样编译器才允许：把 b[i] 暂存寄存器、重排部分 l/s、向量化、更激进的 loop optimization。

val：把代码写得更容易优化；restrict：让编译器知道它确实可以优化。两者可以配合使用。

诊断 Aliasing

  • GCC：-fopt-info-missed——gcc -O3 -fopt-info-missed=missed_opts.txt my_program.c
  • Clang (LLVM)：-Rpass-missed、-Rpass-analysis——clang -O3 -Rpass-missed=.* -Rpass-analysis=.* my_program.c

如果编译器提示：

  • data dependence
  • dependent memory operations
  • cannot vectorize due to memory dependencies

通常就是它在说不敢断定这些指针不别名，所以我只能保守执行。



衡量优化效果: CPE

CPE (Cycles Per Element)：

对于处理长度为 n 的向量型程序，Cycles = CPE · n + Overhead

  • CPE 是 elements-cycles 斜率，表示“平均每个元素需要多少周期”

  • Overhead 是固定开销，和 n 无关。反映了函数调用、初始化、收尾等固定代价；对小输入影响明显，对大输入影响相对小

  • 一般来说，elements 看做指令数


Reduction

reduction (向量归约) 代表把一组元素通过某种结合操作归并成一个值。

常见包括：sum、product、parity、AND / OR / XOR、max / min。

  • Scalar reduction：单个累积器一路加下去，问题是依赖链长，限制并行度。

  • Vector reduction：把数据分成多路并行累积 (sum0~sumx)，最后再做一次总合并，可以做进一步向量化。

vector reduction 更好，因为它减少单条依赖链长度，利用 SIMD 宽度，提高吞吐率

⚠️ 向量归约是 -O2/-O3 常见优化的一部分。



Memory Locality Optimizations

程序如何通过改善 memory locality（内存局部性）来减少 cache miss，从而大幅提升性能。

Memory Wall 不断扩大，因而减小 L/S (访存) Latency 愈发重要。我们已经讨论过，为解决这个问题，硬件引入多级缓存，那软件可以做到什么？—— 利用局部性让访问 cache 越快越好。

Loop Interchange 循环交换

通过交换多级嵌套循环的顺序，尽量贴合内存的顺序依次遍历 (⚠️ Spacial Locality)

  • 比如 C/C++ 的二维数组是 row-major order，按行存储。(M[0][0], M[0][1], M[0][2] ... 在内存中是连续的) 所以先行再列遍历在现代处理器上会快 5～10 倍：

    int M[10000][10000]; 
for (int i = 0; i < 10000; i++)    // 比外 j 内 i 快
    for (int j = 0; j < 10000; j++) 
        M[i][j] = M[i][j] + 1;

Loop Fusion 循环融合

融合两个条件一致的循环，不仅内部重复的变量只需要 fetch 一次 (减小 mem. traffic)，也能得到⚠️ Temporal Locality 的改善。

⚠️ Loop Fusion 不一定是安全的，要注意维护数据依赖关系 (Only valid when preserves data dependencies)。例如第二个循环依赖第一个循环已经完整处理整个数组，那就不能随便融合：

for (int i = 0; i < N; i++) A[i] = B[i] + 1;
for (int i = 1; i < N-1; i++) C[i] = A[i+1] + A[i];  // 使用了超过一项

这种类型的合并需要 1. 考虑临界值；2. 提前计算所有被用到的依赖项 ——

A[0] = B[0] + 1; A[1] = B[1] + 1;
for (int i = 1; i < N - 1; i++) {
    A[i + 1] = B[i + 1] + 1;
    C[i] = A[i + 1] + A[i];
}

Array Padding to Avoid Conflict Miss

数组填充避免冲突缺失，连续声明两个数组，且数组宽为 2 的幂，那么 A[i][j] 与 B[i][j] 、 A[i][j] 与 A[i+4][j] 都容易发生 conflict miss。因为很多缓存的 set count 也是 2 的幂，即使缓存容量够，也会导致不同数组或不同行频繁映射到同一个 set，互相踢出 set (cache thrashing)。

  • DMC 发生的频率最高，因为 set 宽为 1
#define N 1024 
int A[N][N]; int B[N][N]; 
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) A[i][j] += B[i][j];
}
  • 通过给每一行增加额外不用的元素，比如 #define PAD 16; int A[N][N+PAD]; int B[N][N+PAD]; 改变数组元素在 cache 中的映射位置，避免 2 的幂步长导致的 conflict miss。

Matrix Transpose

矩阵转置对缓存很不利，读写总有一者必然按列进行 (Bad Spatial Locality)。比如若按行写矩阵 A，就被迫按列读 B；对于大矩阵，按列读取会导致 cache evictions，被一同加载进缓存的其他元素还没用就被丢掉。

for (int i = 0; i < N; i++) { 
    for (int j = 0; j < N; j++) A[i][j] = B[j][i]; 
}

⚠️ 导致 capacity miss + conflict miss，前者为主。

方案: Blocking / Tiling

把大型矩阵切成很多小块，让顺带加载进缓存的周边元素更快被用，避免放不下被挤出去。虽然第一列无避免大量 compulsory miss，后续的列可以 hit。

如下，切成边长 BS 的小矩阵，按行完成这些矩阵 (每个矩阵内依旧读写有一者按列访问)

for (int i = 0; i < N; i += BS) {
    for (int j = 0; j < N; j += BS) {
        for (int ii = i; ii < i + BS; ii++) {
            for (int jj = j; jj < j + BS; jj++) A[ii][jj] = B[jj][ii];
        }
    }
}

把大范围的不连续访问，变成小范围内的局部访问，让数据更容易留在 cache 里


Matrix Multiplication

计算 N x N 矩阵的乘法 C = A × B，需要至少 3xN2 次访存，以及 2xN3 数量级的计算指令 (实际是 2N3 - N2)。平均每访问一个矩阵元素，对应的计算量是 N 数量级的，所以每个矩阵元素会被使用 N 次 —— 复用率不错，看起来应该 cache hit 可观；但当 N 很大时，会出现 capacity miss ……索性就放不下了。

  • 虽然数据理论上会复用，但它可能在下次复用前已经被赶出 cache。

方案依旧是 Blocking / Tiling

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) C[i][j] += A[i][k] * B[k][j];
    }  // B 通常按列访问，很差；C 反复读写，但可能被替换
}
// 改写成...
for (int ii = 0; ii < N; ii += BS) {
    for (int jj = 0; jj < N; jj += BS) {
        for (int kk = 0; kk < N; kk += BS) {
            for (int i = ii; i < ii + BS; i++) {
                for (int j = jj; j < jj + BS; j++) {
                    for (int k = kk; k < kk + BS; k++) C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
}  // 让当前在计算的 A、B、C 的小块尽量同时塞进缓存

BS (tile / block size) 选择规则：A block + B block + C block ≤ cache capacity，即 3 × BS2 × n bytes ≤ capacity (其中 n 取决于数据类型，int 4、double 8 ……)

Tile size should be chosen so that the working set fits in cache


Software Prefetching 软件预取

⚠️ Hardware Prefetcher 负责观察使用情况，提前取最可能即将访问的内存位置

对于 sum += b[a[i]]; 中的 a[]，属于顺序访问，很容易预测；但 b[a[]] 是随机访问，硬件很难猜下一次访问哪里。

软件预取：在真正使用前，提前若干轮把未来要访问的数据放进 cache。

for (int i = 0; i < N; i++) {
    if (i + PREFETCH_DISTANCE < N) { 
        int future_index = indices[i + PREFETCH_DISTANCE];
        __builtin_prefetch(&values[future_index], 0, 1);  
    }  // 第二个参数区分读(0)写(1)；第三个参数通常是 0 到 3，记录时间局部性的高低
    sum += values[indices[i]];
}
  • 不使用 load 指令，因为会直接读数据且程序必须等它完成。prefetch 指令要求提前把这个地址附近的数据拿进 cache，但现在不需要。通常不会或轻度阻塞程序。
  • 区分读写，是因为读和写预取对 cache coherence、写分配策略、权限状态可能不同。
  • 记录时间局部性，为了让 CPU 判断要不要把数据留在 cache。

AoS vs. SoA

AoS：Array of Structures

⚠️ 适合经常一次使用一个对象的大部分字段/参数，比如渲染一个粒子：

struct Particle {
    float a, b, c, d, e;
    float va, vb, vc, vd, ve;
    int color;
    float lifetime;
};
struct Particle* particles = malloc(N * sizeof(struct Particle));

内存布局为：

Particle 0: a b c d e va vb vc vd ve color lifetime
Particle 1: a b c d e va vb vc vd ve color lifetime ......

如果修改每个结构体的某个参数，这种方寸缺乏 spatial locality，浪费大量 cache bandwidth 在取目标周围的参数。

SoA：Structure of Arrays

适合批量处理很多对象的同一个字段 (可以利用 SIMD/vectorization)，更常见于高性能计算、游戏物理、图形、机器学习内核等。

struct Particle {
    float *a, *b, *c, *d, *e;
    float *va, *vb, *vc, *vd, *ve;
    int *color;
    float *lifetime;
};

内存布局变成：

a[0], a[1], a[2], a[3], ...
b[0], b[1], b[2], b[3], ...
vx[0], vx[1], vx[2], vx[3], ......

这种布局对更新某个具体参数友好，可以更好的利用 spatial locality。

comments powered by Disqus