📚 课程目录第3章算法瓶颈分析

3、算法瓶颈分析：计算热点识别、内存访问模式、数据依赖与并行度、I/O与计算重叠

性能优化，说白了就是“找瓶颈”。

你花一周时间把某个函数加速了 10 倍，结果发现它只占总运行时间的 1%，那这周基本白干。我见过太多团队一上来就对着代码猛优化，最后发现瓶颈根本不在那儿。

所以，动手之前，先做瓶颈分析。这一章，我带你走一遍我自己的分析流程。

3.1 计算热点识别（Profiling）

热点识别，就是找出程序里最耗时的那些代码段。我个人习惯用 自上而下 的方式：先看系统级，再看进程级，最后看函数级。

3.1.1 系统级 Profiling

先看 CPU 利用率、内存带宽、磁盘 I/O 这些宏观指标。用 perf stat 或者 top 就能快速判断。

关键指标速查：

CPU 利用率高（>90%）：计算密集，看函数级热点。
CPU 利用率低（<50%）：大概率在等 I/O 或锁。
上下文切换频繁：锁竞争或者线程数过多。
Cache Miss 率高：内存访问模式有问题。

3.1.2 函数级 Profiling

到了函数级，我常用两种工具：采样（Sampling） 和 插桩（Instrumentation）。

方法	原理	开销	适用场景
采样（perf, VTune）	定期中断，记录调用栈	极低	生产环境、长任务
插桩（gprof, Callgrind）	修改代码，记录每次调用	较高	开发环境、短任务

我一般先用 perf top 看个大概，再用 perf record -g 采样，最后用 perf report 看火焰图。火焰图这东西，一眼就能看出哪个函数是“平顶山”。

我的习惯： 采样频率设 99Hz（避免与系统时钟同步），采样时长至少 30 秒。太短了数据不准。

3.1.3 代码行级热点

有时候函数级还不够，得精确到行。这时候我会用 perf annotate 或者 Intel VTune 的源码视图。

# 生成带源码的汇编注释
perf annotate -s hot_function --stdio

我曾经在优化一个图像处理算法时，发现 80% 的时间花在了一行 memcpy 上。那行代码拷贝的是整张图，但其实只需要拷贝一个 ROI。改完之后，速度直接翻倍。

3.2 内存访问模式分析

找到热点之后，下一步就是看它怎么访问内存的。很多时候，算法本身不慢，慢的是内存。

3.2.1 空间局部性

CPU 缓存是按 Cache Line（通常 64 字节）加载的。如果你访问 a[0]，那 a[1] 到 a[15]（假设是 int）大概率已经在缓存里了。

所以，遍历二维数组时，按行访问 比按列访问快得多。

// 快：按行遍历
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// 慢：按列遍历
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

按列访问那个版本，在我项目里曾经跑出过 10 倍的性能差距。你想想看，只是换了个循环顺序而已。

3.2.2 伪共享（False Sharing）

多线程场景下，两个线程各自修改不同的变量，但这两个变量恰好在同一个 Cache Line 里。结果就是，缓存一直在失效，性能还不如单线程。

避坑指南： 我曾经在写一个多线程累加器时，每个线程更新自己的 counter[thread_id]。结果因为数组连续存放，多个线程的 counter 挤在同一个 Cache Line 里，性能惨不忍睹。后来用 alignas(64) 做了缓存行对齐，问题解决。

3.2.3 内存带宽瓶颈

有些算法，比如矩阵乘法、图像滤波，本质上是 带宽受限 的。你用 perf stat -e instructions,cycles,LLC-load-misses 一看，会发现指令数很高，但 CPI（每指令周期数）也高得离谱。

这时候，优化方向不是减少计算量，而是 减少数据搬运。比如用分块（Tiling）技术，让数据尽量在 L1/L2 缓存里完成计算。

3.3 数据依赖与并行度评估

找到热点、搞定内存，接下来看能不能并行。并行度的核心障碍就是 数据依赖。

3.3.1 三种数据依赖

依赖类型	含义	能否并行
RAW（真依赖）	写后读：B 依赖 A 的结果	不能，必须等
WAR（反依赖）	读后写：A 先读，B 后写同一位置	可重命名消除
WAW（输出依赖）	写后写：两个线程写同一位置	可重命名消除

说白了，只有 RAW 依赖是硬骨头。WAR 和 WAW 可以通过变量重命名或者 privatization（私有化）来解决。

3.3.2 并行度评估方法

我评估并行度时，会先画 依赖图（DAG）。每个节点是一个计算任务，边表示依赖关系。然后看 关键路径长度。

关键路径短：并行潜力大。
关键路径长：串行瓶颈严重，得改算法。

举个例子，一个简单的累加求和，关键路径是 O(N)，几乎没法并行。但用 树形归约，关键路径变成 O(log N)，并行度就上来了。

经验之谈： 别盲目开线程。线程数超过硬件并发度后，性能反而下降。我一般用 std::thread::hardware_concurrency() 获取核心数，再根据任务粒度调整。

3.4 I/O 与计算重叠分析

最后一块，也是容易被忽略的一块：I/O 和计算能不能重叠。

3.4.1 同步 I/O 的痛

传统的 read() / write() 是阻塞的。线程发出 I/O 请求后，就挂起等数据。这段时间 CPU 是空闲的。

我优化过一个视频编码管线，发现 CPU 利用率只有 40%。一查，原来大部分时间都在等磁盘读入原始帧。

3.4.2 异步 I/O 与双缓冲

解决方案是 异步 I/O 或者 双缓冲（Double Buffering）。

// 伪代码：双缓冲模式
buffer_t buf[2];
int current = 0;

// 启动异步读取
async_read(buf[current]);

while (true) {
    // 等待当前缓冲区就绪
    wait_for_io(buf[current]);
    
    // 处理当前缓冲区
    process(buf[current]);
    
    // 切换缓冲区，并预读下一块
    int next = 1 - current;
    async_read(buf[next]);
    current = next;
}

这样，处理数据和读取数据就重叠起来了。CPU 利用率能轻松拉到 90% 以上。

3.4.3 计算与通信重叠

在分布式场景下，这个思路同样适用。比如用 NCCL 做 AllReduce 时，可以把梯度切分成小块，一边计算梯度，一边传输上一块的梯度。这就是所谓的 梯度流水线（Gradient Pipeline）。

小技巧： 用 perf stat -e context-switches 可以快速判断 I/O 是否阻塞了计算。如果上下文切换次数很高，大概率是 I/O 在拖后腿。

知识体系总览

下面这张图，概括了瓶颈分析的完整流程和各个模块的关系。

嗯，这一套流程走下来，你基本就能摸清算法的瓶颈在哪了。下一步，就是针对性地优化。不过那是后面章节的事，先把分析做扎实。