程序优化方法总结

代码优化指南：从算法到裸机架构

核心法则： 在进行任何优化之前，清先进行Profiling(性能分析)

凭直觉的优化往往是徒劳的。只有找出真正的性能瓶颈(Hotspots),优化才有意义

优化层级概述

优化层级 核心关注点 预期收益 适用场景
一、 算法级 复杂度降低、数学模型替换 极高（指数级提升） 系统设计初期、核心计算模块
二、 内存级 缓存命中率、数据局部性 高（打破内存墙） 数据密集型任务、大规模数组处理
三、 编译器级 指令重排、消除别名、循环展开 中至高 现代 C/C++ 项目、LLVM/GCC 工具链
四、 架构级 SIMD 向量化、流水线利用 中至高 深度学习算子、矩阵运算
五、 裸机与安全级 确定性、内存占用、零开销抽象 架构强相关 嵌入式系统

算法与数据结构级优化

这是位于金字塔顶端的优化。如果基础数学模型存在缺陷，底层的任何指令级优化都无法弥补 O(N^2) 与 O(Nlog N) 之间的巨大鸿沟。

核心思想

  • 寻找更优的数学等价替换
  • 空间换时间（如查表）

例1： 数学信号处理中的频域转换

  • 未优化(DFT): 嵌入式循环遍历，时间复杂度O(N^2)

  • 优化后 (FFT)： 采用快速傅里叶变换（FFT）的蝶形分治算法，时间复杂度骤降至 $O(N \log N)$。当采样点变大时，性能差异是天壤之别。

    TODO: 代码实现

例2： 内存与数据布局（结构体对齐）

  • 非优化： 按直觉定义
1
2
3
4
5
6
7
8
9
// 假设在 64 位系统上
struct Node_Bad {
    char a;     // 1 byte
                // 7 bytes padding (为了让下一个 double 对齐)
    double b;   // 8 bytes
    int c;      // 4 bytes
                // 4 bytes padding (为了让整个结构体大小是 8 的倍数)
}; 
// sizeof(Node_Bad) = 24 bytes
  • 优化后：按类型大小降序
1
2
3
4
5
6
7
struct Node_Good {
    double b;   // 8 bytes
    int c;      // 4 bytes
    char a;     // 1 byte
                // 3 bytes padding 
};
// sizeof(Node_Good) = 16 bytes

收益： 仅仅是调整了声明顺序，结构体体积就缩小了 33%。如果在深度学习模型或嵌入式节点中分配一百万个这样的结构体，直接节省了 8MB 的宝贵内存，同时大幅提升了缓存行（Cache Line）的数据密度。

内存与缓存友好型优化

现代处理器的运算速度远超内存的读写速度。优化代码的内存访问模式，让数据尽可能留在 CPU Cache 中，是打破“内存墙”的关键。

核心思想

  • 空间局部性： 数据结构在内存中尽量紧凑排列。

  • 时间局部性： 集中处理同一块数据，避免频繁换入换出。

例1：二维数组(矩阵)的遍历

c/c++中的二维数组是按行连续存储的(Row-major)

  • 反面教材(引发Cache Miss)

    1
    2
    3
    4
    5
    6
    // 按列遍历： 每次读取都会跳跃一整行的内存地址
    for(int j = 0; j < COLS; j++) {
        for(int i = 0; j < ROWS; +i+) {
            matrix[i][j] *= 2.0f;
        }
    }

  • 优化后

    1
    2
    3
    4
    5
    6
    // 按行遍历：完美契合Caline Line 预取
    for(int i = 0; j < ROWS; +i+) {
       for(int j = 0; j < COLS; j++) {
            matrix[i][j] *= 2.0f;
        }
    }

编译器友好型代码

现代编译器（如 LLVM 或 GCC）内部包含数百个优化 Pass。编写清晰、无歧义的代码，能够最大程度释放编译器的优化潜力。

核心思想

  • 明确指针关系，消除内存别名（Aliasing）。
  • 结构化循环，方便编译器进行中间表示（IR）分析和自动展开。

例1：指针别名阻碍优化

当函数接收多个指针时，编译器默认它们可能指向同一块内存，从而放弃积极的指令重排或向量化。

  • 反面教材（保守生成标量指令）
1
2
3
4
5
void add_arrays(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; i++) {
        a[i] = b[i] + c[i];
    }
}
  • 优化后（使用restrict关键字）
1
2
3
4
5
6
// 明确告知编译器：a, b, c 指向的内存绝对互不重叠
void add_arrays_opt(float* restrict a, const float* restrict b, const float* restrict c, int n) {
    for (int i = 0; i < n; i++) {
        a[i] = b[i] + c[i];
    }
}

架构与硬件级优化

当编译器自动优化达到瓶颈，需要针对特定的硬件架构（如 x86, ARM, 或 RISC-V）榨干最后一滴算力。

核心思想

  • 利用单指令多数据（SIMD）机制处理并行数据
  • 消除分支预测失败造成的流水线冲刷

示例：利用向量指令集加速

对于密集的计算（如深度学习算子或图像处理），可以使用架构专属的向量扩展（例如 RISC-V Vector Extension, RVV）。

  • 优化思路： 通过引入 Intrinsics 内置函数或内联汇编，将原本需要循环 $N$ 次的标量加法，打包交由硬件的向量寄存器处理。假设向量寄存器宽度支持同时处理 8 个浮点数，循环次数将直接缩减为 N/8，大幅提升吞吐量。